package tree_layout

You can search for identifiers within the package.

in-package search v0.2.0

On This Page

Functorized API

tree_layout
- Tree_layout
  - Common
  - Layered
    
    Make
    
    G
    
    V
    
    H
    
    S
    
    H
    
    TREE
    
    V
  - Treemaps

Legend:
Library
Module
Module type
Parameter
Class
Class type

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 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.

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