Unformatted text preview:

15-499: Parallel Algorithms Lecturer: Guy BlellochTopic: Graphs I Date: February 24, 2009Scribe: Jose H Sandoval13.1 Graphs13.1.1 RepresentationA common way to represent the adjacency of nodes in a graph would be with an adjacency list. In thisapproach, we create a list for every node in the graph and keep adding its neighbors to the end of the list.Figure 13.1.1: A graph and its correspondent adjacency listNevertheless, since using a list, this approach does not provide an easy way to run calculations in parallel.Different representations, such as adjacency matrices, binary trees or edge arrays, can give us better results.Figure 13.1.2: A graph can also be represented by an adjacency matrix, a binary tree or an edge array13.1.2 Graph connectivityProblem: Find all connected components in a graph [label every vertex with a representation of its com-ponent], [spanning tree].Sequential solution: Depth first search.1. Solve for a smaller subset.2. Join adjacent nodes.3. Label nodes with ones.14. Repeat contraction until single vertices.Figure 13.1.3: Contraction of a graph after one iterationWe can use random mate to decide what vertices to contract at every step. We then flip a coin on every vertexand contract only those that obtained heads and are pointing to a vertex that obtained tails. A problematiccase will arise when two vertices that obtained heads attempt to contract the same vertex at the same time,creating a race condition. Nevertheless, as this race condition does not affect the result in a significant way,we can allow this to happen. This will result in the node that obtained tails being contracted to only one ofthe nodes that obtained heads.Using random mate1. Flip coins on every vertex.2. Contract only heads that are pointing to tails.Figure 13.1.4: Different situations of graph contraction. The rightmost graph creates a race condition.repeatFlip a coin on every vertexfor all edge (u, v) doif u is a head and v a tail thenRelabel v with uL[v]=uend ifend forfor all edge (u, v) do(L[u], L[v])end for2Remove self edgesUntil edge array is emptyuntil edge array is emptyFigure 13.1.5: Graph contraction with race conditions.Figure 13.1.5 shows two cases of race condition. Vertex 5 and vertex 3 will attempt to contract vertex 2 atthe same time, while vertex 5 and vertex 8 will try to do the same to vertex 6. After concurrent labeling isapplied by all vertices, the result is the graph shown on the rightmost figure. The corresponding label arrayand edge array look as follows:L = [1, 2, 3, 4, 5, 6, 7, 8] → [1, 3, 3, 4, 5, 5, 5, 8]E = [ ( 2 , 3 ) . . . ] → [(3, 3) ...]This algorithm consists in O(log n) rounds, each one of them O(log n). The probability of contraction in thiscase is greater than14, as one vertex that obtained heads could be connected to more than one vertex. If thegraph starts with n2edges, the algorithm reduces n after its first iteration. This algorithm is not quite workefficient.Depth = O(log2n)W ork = O(mlogn)13.2 Minimum spanning treesPriority write: Writes with a priority and that with the highest priority wins.Examples of priorities: Smaller index wins, bigger index wins, etc.Graph = (V, E)Edges from U to V − UE′= { u, v ∈ E | u ∈ U, v ∈ V − U }3Minimum spanning tree: Sum of its weights is minimum.e = minimum edge from E′, e in


View Full Document

CMU CS 15499 - Lecture

Download Lecture
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?