package tree_layout

  1. Overview
  2. Docs
On This Page
  1. Functorized API

Module Tree_layout.LayeredSource

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
Sourceval layout : ?m:(module Hashtbl.HashedType with type t = 'a) -> children:('a -> 'a array) -> distance:('a -> 'a -> float) -> 'a -> 'a -> 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.

Functorized API

Sourcemodule type S = sig ... end

The output signature for the layered layout engine.

Sourcemodule type TREE = sig ... end

The input signature for Make

Sourcemodule Make (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).