Module `Tree_layout__.Layered`

Layered trees

A layered tree is a tree that is organized by layers: the horizontal position of a node is fixed depending on its depth in the tree, regardless of its height.

(* Given a nice tree, ... *)
let tree : Tree.t = ...

(* and a distance function. *)
let distance v1 v2 = ...

(* Get positions ! *)
let positions =
  Tree_layout.Layered.layout
    ~children:Tree.children
    ~distance
    tree

val layout : ?⁠m:(module Stdlib.Hashtbl.HashedType with type t = 'a) -> children:('a -> 'a array) -> distance:('a -> 'a -> float) -> 'a -> 'a -> Tree_layout.Common.pos

layout ~children ~distance g v returns the layered layout for the tree g rooted in v. Layered layout are such that vertices with the same depth have the same vertical coordinate. The layout is returned as a lookup functions from trees to positions.

This algorithm is in linear time if children is constant time. Use Make for a more flexible implementation.

distance v1 v2 should return the horizontal distance between v1 and v2 placed at the same depth.

parameter m: An hashing specification for the tree type. If not provided, polymorphic comparison and hashing are used.

parameter children: Return all the subtrees of a tree.

see http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.16.8757: Improving Walker's Algorithm to Run in Linear Time

Functorized API

module type S = sig ... end: The output signature for the layered layout engine.

module type TREE = sig ... end: The input signature for Make

module Make : functor (G : TREE) -> S with type t := G.t and type vertex := G.V.t: Full implementation. If the operations in TREE are O(1), the layout functions is O(n).