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.

Tree Rootfix

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

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

Tree Leaffix

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.