Tree Graphs

GraphIdx.Tree — Module.

Bundle functions regarding (rooted) tree graphs.

For computing a spanning tree from within a general graph, see here. For debugging, outputting the tree as a hierarchy was usefule:

GraphIdx.Tree.hierarchy — Function.

hierarchy([io,] cidx, [indent])

Print a tree given by a ChildrenIndex hierarchically onto io (default stdout).

Example

julia> import GraphIdx.Tree: ChildrenIndex, hierarchy

julia> hierarchy(ChildrenIndex([1, 1, 1, 3]))
1
├─2
└─3
  └─4

source

GraphIdx.Tree.hierarchy_string — Function.

hierarchy_string(cidx)

Same as hierarchy but output as String. More precisely, print to a buffer and return as String.

source

GraphIdx.Tree.parenthesis — Function.

parenthesis([io,] cidx [, stack])

Print the tree in parenthesis notation: recursively print <node id>(subtree). Per default output on stdout.

Example

julia> import GraphIdx.Tree: ChildrenIndex, parenthesis

julia> parenthesis(ChildrenIndex([1, 1, 1, 3]))
1(2()3(4()))

source

GraphIdx.Tree.parenthesis_string — Function.

parenthesis_string(cidx [, stack])

Like parenthesis but return output as String.

source

Data Structures

We provide some framework specialized for (rooted) tree graphs:

GraphIdx.Tree.RootedTree — Type.

A rooted tree represanted by its parent vector, i.e. if u is the parent node of v then parent[v] == u. We always require that root is its own parent (parent[root] == root) and length(parent) == n.

Often you might want to have a ChildrenIndex. For debugging, the hierarchy function might be useful.

source

GraphIdx.Tree.find_root — Function.

find_root(pi)

Find the first index i with pi[i] == i. Report an error if non such exist.

Example

julia> GraphIdx.Tree.find_root([2, 1, 3, 2])
3

source

GraphIdx.Tree.node_degrees — Function.

node_degrees(parent, [root = 1])

Return a vector telling the degree of each node.

source

Often, we will need to access the children of arbitrary nodes; for this the GraphIdx.Tree.ChildrenIndex was developed.

Traversal

Classical depth first search

GraphIdx.Tree.dfs_walk — Function.

dfs_walk(f, tree [,stack])

Call f on each node of tree in depth-first search (DFS) order. Hereby the node v is negative v < 0 if the node is discovered the first time and non-negative (v >= 0) if the node has been finished.

The tree can be given as ChildrenIndex or parent Vector{Int}; in the latter case ChildrenIndex will be constructed. To avoid allocation, you can pass a stack Vector.

Example

julia> import GraphIdx.Tree: ChildrenIndex, hierarchy, dfs_walk

julia> tree = ChildrenIndex([1, 1, 1, 3, 1]); hierarchy(tree)
1
├─2
├─3
│ └─4
└─5

julia> dfs_walk(tree) do v
          println(v >= 0 ? "finished   " : "discovered ", abs(v))
       end
discovered 1
discovered 2
finished   2
discovered 3
discovered 4
finished   4
finished   3
discovered 5
finished   5
finished   1

source

GraphIdx.Tree.dfs_walk_rev — Function.

dfs_walk_rev(f, tree::ChildrenIndex [, stack])

Like dfs_walk but process the children in reversed order!

Example

julia> import GraphIdx.Tree: ChildrenIndex, hierarchy, dfs_walk_rev

julia> tree = ChildrenIndex([1, 1, 1, 3, 1]); hierarchy(tree)
1
├─2
├─3
│ └─4
└─5

julia> dfs_walk_rev(tree) do v
          println(v >= 0 ? "finished   " : "discovered ", abs(v))
       end
discovered 1
discovered 5
finished   5
discovered 3
discovered 4
finished   4
finished   3
discovered 2
finished   2
finished   1

source

GraphIdx.Tree.dfs_finish — Function.

dfs_finish(parent)

For each node, compute the DFS finish time (without computing a ChildrenIndex).

julia> import GraphIdx.Tree: ChildrenIndex, hierarchy, dfs_finish

julia> pi = [1, 1, 2, 1, 2, 3]; hierarchy(ChildrenIndex(pi))
1
├─2
│ ├─3
│ │ └─6
│ └─5
└─4

julia> dfs_finish(pi)
6-element Array{Int64,1}:
 6
 3
 5
 2
 4
 1

source

For binary trees, there is also the inorder:

GraphIdx.Tree.binary_inorder — Function.

Return the Inorder traversal of a complete binary tree with given height. (Root node will be 0 and placed in the middle of the array

source

Lowest Common Ancestors

GraphIdx.Tree.lowest_common_ancestors — Function.

lowest_common_ancestors(tree, parent, pairs)

For a list of pairs [(u1, v1), ..., (uk, vk)] compute the lowest common ancestors [a1, ..., ak], i.e. ai is the lowest node in the tree that is ancestor (parent, grand-parent, grand-grand-parent, etc.) of both, ui and vi.

Runtime is O(length(tree) + length(pairs)). More precisely, due to the use of the UnionFind data structure, the inverse Ackermann function is also included; however the impact is at most 4 for all practical instances ($n < 10^{100}$).

See CLRS (3rd edition) page 584 or networkx.

source