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 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 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 , 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 , 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 are stored in the principal elements of the tree, which is where the output values are to be placed. The leaffix value at a node i whose children have values is . Each nonprincipal element is assigned the identity for its value. A binary treefix computation performed on the binary tree representation underlying the tree computes the desired values. Performance: .

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 as integer addition and for all nodes. The height of a node can also be computed by a leaffix computation where , the identity is , and for all nodes. The depth of a node can be computed by a rootfix computation with as addition and for all nodes except the root which has value 0. Performance: .

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

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 and if , and use Boolean OR for . Each principal element whose leaffix value is 1 lies on the path from to the root. Reverse the direction of the graph pointers of these elements. (Note: rerooting a tree changes the principal elements.) Performance: .

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 , the number of nodes visited before the left subtree of k. Use a leaffix computation to compute the number 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 . If node k is a right child, set to the size of its sibling subtree plus 1. A rootfix computation with + yields , which is the preorder numbering of node k. The inorder numbering can be computed similarly. If node k is a left child, set . If k is a right child, set to the size of its sibling subtree plus 1. Compute for each node using a rootfix computation with +. The inorder numbering of node k is plus the size of its left subtree plus 1. The postfix numbering can be computed by setting if node k is a left child, and by setting to the size of its sibling subtree if k is a right child. After computing using a rootfix computation with +, the postfix numbering of node k is plus the sizes of its two subtrees plus 1. Performance: .

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

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

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

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 , , and , 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 in C, and put the remainder in A. Performance: .

Subexpression evaluation. Given a directed tree in which each leaf has a value and each internal node has an operator from , 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: .

Minimum-cost spanning forest. Given an undirected input graph and a cost function , determine a set 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 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 of rooted trees, where the index i of the tree is the address of the root. The algorithm proceeds as follows. For each tree , use a rootfix computation to broadcast i to all of the elements in . Use a leaffix computation on to determine an edge connecting an edge element with an edge element , where , with smallest weight. If no such edge exists, the algorithm terminates. If picks the same edge as , the tree with smaller index does nothing. Otherwise, mark e as a member of F, directing it into , and reroot with u as the new root. Repeat this procedure until the algorithm terminates. Performance: .

Connected components. Given an undirected input graph , determine a labeling such that if and only if v and 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 . The label of a vertex is the index of its tree. Performance: .

Biconnected components. Two edges of an undirected graph are in the same biconnected component if they lie on a common simple cycle. Determine a labeling such that if and only if e and 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 of G. Number the vertices in the minimum spanning tree in preorder. Use leaffix computations to compute for each vertex v three values: , , and . The value is the number of descendants of v, and ( ) 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 where the edges of F are the vertices of . Let e be an edge from u to , where is the parent of u in F. The adjacency ring for u in G acts as the adjacency ring for e in . Add two kinds of edges to . For each edge in E-F such that , add an edge to . For each edge of F such that and , and or , add an edge to . It can be verified that the representation of is conservative with respect to the representation of G. Find the connected components of . Two edges of F are in the same block if as vertices in they are in the same connected component. Finally, for each edge in E-F, let . Performance: .

Eulerian cycle. An Eulerian cycle of an undirected graph 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: .