next up previous
Next: 8 Conclusion Up: Communication-Efficient Parallel Algorithms Previous: 6 Treefix computations

7 Graph algorithms


This section presents a collection of conservative DRAM algorithms for solving graph problems. The algorithms use two processors per edge of an input graph tex2html_wrap_inline1829 and require only constant extra space in each processor. Most of the algorithms use treefix computations as subroutines.

We represent each vertex in an undirected graph tex2html_wrap_inline1831 by a doubly linked incidence ring of processors, one for each edge. Each element of the incidence ring contains pointers to the next and previous elements in the ring, and one pointer for a graph edge. For each edge tex2html_wrap_inline1833 , the element in the incidence ring for u contains a pointer to an edge element in the incidence ring for v, and vice versa. A directed graph is represented in the same doubly linked fashion, but the graph edges are labeled with their directions.

We represent trees with arbitrary vertex degrees by an incidence ring structure as well. If the tree is directed, each ring has a unique principal element that points toward the root. Breaking the incidence ring before the principal element yields the standard binary-tree representation of the tree [14, pp. 332-333,].

We now present brief descriptions of the algorithms. The performance is given in terms of the number of steps on a DRAM when the input representation has size n. We assume the implicit tree contractions in the algorithms are performed by the randomized Algorithm TC . Deterministic bounds can be obtained by multiplying the number of steps by tex2html_wrap_inline1841 , where m is the number of processors. An upper bound on the time required in the DRAM model can be obtained by multiplying the number of steps by the load factor of the input.

Generalized treefix. Perform a treefix operation on a directed tree with arbitrary vertex degree. The input values tex2html_wrap_inline1845 are stored in the principal elements of the tree, which is where the output values tex2html_wrap_inline1847 are to be placed. The leaffix value at a node i whose children have values tex2html_wrap_inline1851 is tex2html_wrap_inline1853 . Each nonprincipal element is assigned the identity tex2html_wrap_inline1855 for its value. A binary treefix computation performed on the binary tree representation underlying the tree computes the desired values. Performance: tex2html_wrap_inline1857 .

Tree functions. Given a directed tree, compute for each node the number of descendants, its height, or its depth. The number of dependents for each node can be computed by a leaffix computation with tex2html_wrap_inline1859 as integer addition and tex2html_wrap_inline1861 for all nodes. The height of a node can also be computed by a leaffix computation where tex2html_wrap_inline1863 , the identity is tex2html_wrap_inline1865 , and tex2html_wrap_inline1867 for all nodes.gif The depth of a node can be computed by a rootfix computation with tex2html_wrap_inline1873 as addition and tex2html_wrap_inline1875 for all nodes except the root which has value 0. Performance: tex2html_wrap_inline1879 .

Rooting an undirected tree. Pick a root of a tree with undirected graph pointers, and orient the graph pointers toward the root. Form an ``Eulerian tour'' of the pointers of the representation [27] by directing each element of the tree to link its incoming ring pointer with its graph edge directed outward and its graph edge directed inward with its outgoing ring pointer. Each graph edge is used twice in the tour, once in each direction, but each ring pointer is used only once. Use Algorithm LC to form a contraction tree of the tour. Choose the root of the contraction tree to be the root of the tree, and break the tour so that it begins with the root. Use parallel prefix to number each node according to its first occurrence in the tour. Use contraction trees to distribute the smallest value in each incidence ring to the elements of the ring. Orient each graph edge from the larger value to the smaller. Performance: tex2html_wrap_inline1881 .

Rerooting a directed tree. Given a directed tree and another distinguished vertex k, reorient the graph edges of the tree to point toward k. The algorithm for rooting a tree can be used by picking k as the root instead of the root of the contraction tree, but a single treefix computation suffices. Perform a leaffix computation with tex2html_wrap_inline1889 and tex2html_wrap_inline1891 if tex2html_wrap_inline1893 , and use Boolean OR for tex2html_wrap_inline1895 . Each principal element whose leaffix value is 1 lies on the path from tex2html_wrap_inline1899 to the root. Reverse the direction of the graph pointers of these elements. (Note: rerooting a tree changes the principal elements.) Performance: tex2html_wrap_inline1901 .

Tree-walk numberings of a binary tree. Number the nodes of a binary tree according to the order they would be visited in a preorder/inorder/postorder tree walk. For each of the walks, we will compute tex2html_wrap_inline1903 , the number of nodes visited before the left subtree of k. Use a leaffix computation to compute the number tex2html_wrap_inline1907 of the subtree rooted at k. We first compute the preorder numbering. (For the purposes of these numbering algorithms, we consider the root to be a left child.) If node k is a left child, set tex2html_wrap_inline1913 . If node k is a right child, set tex2html_wrap_inline1917 to the size of its sibling subtree plus 1. A rootfix computation with + yields tex2html_wrap_inline1923 , which is the preorder numbering of node k. The inorder numbering can be computed similarly. If node k is a left child, set tex2html_wrap_inline1929 . If k is a right child, set tex2html_wrap_inline1933 to the size of its sibling subtree plus 1. Compute tex2html_wrap_inline1937 for each node using a rootfix computation with +. The inorder numbering of node k is tex2html_wrap_inline1943 plus the size of its left subtree plus 1. The postfix numbering can be computed by setting tex2html_wrap_inline1947 if node k is a left child, and by setting tex2html_wrap_inline1951 to the size of its sibling subtree if k is a right child. After computing tex2html_wrap_inline1955 using a rootfix computation with +, the postfix numbering of node k is tex2html_wrap_inline1961 plus the sizes of its two subtrees plus 1. Performance: tex2html_wrap_inline1965 .

Prefix and postfix numberings of a directed tree. Number the edges of an arbitrary directed tree according to the order they are visited in a preorder/postorder tree walk. The problem reduces to prefix/postfix numbering on the underlying binary tree representation. Performance: tex2html_wrap_inline1967 .

Diameter and center of a tree. The diameter is the length of the longest path in the tree. A center is a vertex v such that the longest path from v to a leaf is minimal over all vertices in the tree. The diameter can be determined by rooting the tree and using rootfix to find the farthest leaf from the root. Reroot the tree at this leaf. The distance from the new root to the farthest leaf is the diameter. (This algorithm is based on an analog algorithm attributed to J. Wennmacker [6].) A center of the tree can be determined by finding a median element of the path that realizes the diameter. Performance: tex2html_wrap_inline1973 .

Centroid of a tree. A centroid is a vertex v such that the largest subtree with v as a leaf is minimal over all vertices in the tree. A centroid can be determined by rooting the tree and computing the size of each subtree. By broadcasting the size m of the tree from the root, each graph edge in each incidence ring can determine the number of elements on the other side of the edge. For each incidence ring, compute the maximum of these values. A vertex with the minimum of these maximum values is a centroid. Performance: tex2html_wrap_inline1981 .

Separator of a tree. A separator [20] is a partition of the vertices of an n-vertex tree into three sets A, B, and C, with tex2html_wrap_inline1991 , tex2html_wrap_inline1993 , and tex2html_wrap_inline1995 , such that no edge of the tree goes between a vertex in A and a vertex in C. Determine a centroid of the tree. This vertex is the separator vertex in B. It remains to partition the remaining vertices between A and C. For each graph edge in the incidence ring, count the number of vertices in the subtree on the other side of the edge. Put the largest subtree in A. Use parallel prefix on the incidence ring to compute a running sum of the sizes of the other subtrees. Put all subtrees whose prefix value is at most tex2html_wrap_inline2009 in C, and put the remainder in A. Performance: tex2html_wrap_inline2015 .

Subexpression evaluation. Given a directed tree in which each leaf has a value and each internal node has an operator from tex2html_wrap_inline2017 , compute for each internal node the subexpression rooted at that node. A single leaffix-like computation suffices using the ideas of Brent [2] and Miller and Reif [22]. Performance: tex2html_wrap_inline2019 .

Minimum-cost spanning forest. Given an undirected input graph tex2html_wrap_inline2021 and a cost function tex2html_wrap_inline2023 , determine a set tex2html_wrap_inline2025 of edges such that each vertex in V is incident on an edge of F, and the sum of the weights of the edges in F is minimal. We give a conservative DRAM implementation of Boruvka's algorithm, also attributed to Sollin [26, pp. 71-83,]. We assume without loss of generality that the edge weights are distinct--otherwise, we can assign the weight of a graph edge e between two incidence-ring elements with addresses a and b to be tex2html_wrap_inline2039 and then compare weights lexicographically. We determine F by marking edges in G. Initially, no edges are marked. At each step of the algorithm, the currently marked graph edges form a subforest of F. Break each incidence ring by removing a single ring pointer, and direct the resulting linear list. At each step of the algorithm, the marked graph edges and the ring pointers form a set tex2html_wrap_inline2047 of rooted trees, where the index i of the tree is the address of the root. The algorithm proceeds as follows. For each tree tex2html_wrap_inline2051 , use a rootfix computation to broadcast i to all of the elements in tex2html_wrap_inline2055 . Use a leaffix computation on tex2html_wrap_inline2057 to determine an edge tex2html_wrap_inline2059 connecting an edge element tex2html_wrap_inline2061 with an edge element tex2html_wrap_inline2063 , where tex2html_wrap_inline2065 , with smallest weight. If no such edge exists, the algorithm terminates. If tex2html_wrap_inline2067 picks the same edge as tex2html_wrap_inline2069 , the tree with smaller index does nothing. Otherwise, mark e as a member of F, directing it into tex2html_wrap_inline2075 , and reroot tex2html_wrap_inline2077 with u as the new root. Repeat this procedure until the algorithm terminates. Performance: tex2html_wrap_inline2081 .

Connected components. Given an undirected input graph tex2html_wrap_inline2083 , determine a labeling tex2html_wrap_inline2085 such that tex2html_wrap_inline2087 if and only if v and tex2html_wrap_inline2091 are in the same connected component of G. The algorithm is the same as the minimum spanning tree algorithm, choosing the weight of a graph edge e between incidence ring elements with addresses a and b to be tex2html_wrap_inline2101 . The label of a vertex is the index of its tree. Performance: tex2html_wrap_inline2103 .

Biconnected components. Two edges of an undirected graph tex2html_wrap_inline2105 are in the same biconnected component if they lie on a common simple cycle. Determine a labeling tex2html_wrap_inline2107 such that tex2html_wrap_inline2109 if and only if e and tex2html_wrap_inline2113 are in the same biconnected component of G. We give a conservative DRAM implementation of the biconnectivity algorithm of Tarjan and Vishkin [27]. We assume that the reader has some familiarity with that algorithm. Find a (directed) minimum spanning tree tex2html_wrap_inline2117 of G. Number the vertices in the minimum spanning tree in preorder. Use leaffix computations to compute for each vertex v three values: tex2html_wrap_inline2123 , tex2html_wrap_inline2125 , and tex2html_wrap_inline2127 . The value tex2html_wrap_inline2129 is the number of descendants of v, and tex2html_wrap_inline2133 ( tex2html_wrap_inline2135 ) is the lowest (highest) numbered vertex (with respect to the preorder numbering of T) that is either a descendant of v or adjacent to a descendant of v by an edge of E-F. Build a new graph tex2html_wrap_inline2145 where the edges of F are the vertices of tex2html_wrap_inline2149 . Let e be an edge from u to tex2html_wrap_inline2155 , where tex2html_wrap_inline2157 is the parent of u in F. The adjacency ring for u in G acts as the adjacency ring for e in tex2html_wrap_inline2169 . Add two kinds of edges to tex2html_wrap_inline2171 . For each edge tex2html_wrap_inline2173 in E-F such that tex2html_wrap_inline2177 , add an edge tex2html_wrap_inline2179 to tex2html_wrap_inline2181 . For each edge tex2html_wrap_inline2183 of F such that tex2html_wrap_inline2187 and tex2html_wrap_inline2189 , and tex2html_wrap_inline2191 or tex2html_wrap_inline2193 , add an edge tex2html_wrap_inline2195 to tex2html_wrap_inline2197 . It can be verified that the representation of tex2html_wrap_inline2199 is conservative with respect to the representation of G. Find the connected components of tex2html_wrap_inline2203 . Two edges of F are in the same block if as vertices in tex2html_wrap_inline2207 they are in the same connected component. Finally, for each edge tex2html_wrap_inline2209 in E-F, let tex2html_wrap_inline2213 . Performance: tex2html_wrap_inline2215 .

Eulerian cycle. An Eulerian cycle of an undirected graph tex2html_wrap_inline2217 is a cycle containing each edge in E exactly once. If any vertex has odd degree, then no Eulerian cycle exists. Form a set of disjoint cycles of the pointers of the representation of G as in the algorithm for directing a tree. The cycles can be merged using an algorithm similar to the minimum-cost-spanning-forest algorithm. Performance: tex2html_wrap_inline2223 .

next up previous
Next: 8 Conclusion Up: Communication-Efficient Parallel Algorithms Previous: 6 Treefix computations

Bruce Maggs
Thu Jul 25 19:12:36 EDT 1996