Parallel graph and tree algorithms
This page contains a collection of parallel graph and tree algorithm.
It includes a brief description of each algorithm along with the NESL code. These algorithms have been developed
by the Scandal project.
If you have arrived here via a search engine, we suggest going to the
toplevel algorithms page.
The rootfix operation takes a tree structure and a value for each node
and returns to each node the sum of the values on the path from the
root to the node. This can be used, for example, to find the depth of
each node by using 1 for the value at each node. The algorithm we
show uses the Euler tour technique in which we represent a tree in
parenthetical form.
The example we use is the tree
0
/ \
1 5
/ | \
2 3 4
which has the parenthetical form ((()()())()). This
is then represented by the array
[(0, 11), (1, 8), (2, 3), (4, 5), (6, 7), (9, 10)];
which specifies the position of the left and right parenthesis
for each node.
The leaffix operation is similar to the rootfix operation but it sums
the values below each node rather than above each node. By placing 1
at each node this can be used, for example, to find the size of each
subtree. Like rootfix, the algorithm we show uses the Euler tour technique.
The explanation of the example tree is give above in the text for leaffix.