Graph Algorithms

John Mellor-Crummey
Department of Computer Science Rice University johnmc@cs.rice.edu

COMP 422

Lecture 23 19 April 2011

Topics for Today

Terminology and graph representations Minimum spanning tree
Prim's algorithm

Single-source shortest paths

Dijkstra's Algorithm

All-Pairs shortest paths Transitive closure Connected components

Terminology

Graph G = (V,E)
V is a finite set of points called vertices E is a finite set of edges

Undirected graph
edge e E
unordered pair (u,v), where u,v V

Directed graph
edge (u,v) E
incident from vertex u incident to vertex v

Path from a vertex u to v

a sequence <v0,v1,v2,,vk> of vertices v0 = u, vk = v, and (vi, vi+1) E for i = 0, 1,, k-1

path length = # of edges in a path

Directed and Undirected Graph Examples

undirected graph

directed graph

More Terminology

Connected undirected graph
every pair of vertices is connected by a path.

Forest: an acyclic graph Tree: a connected acyclic graph Weighted graph: graph with edge weights Common graph representations
adjacency matrix adjacency list

Adjacency Matrix for Graph G = (V,E)

|V| x |V| matrix
matrix element ai,j = 1 if nodes i and j share an edge; 0 otherwise for a weighted graph, ai,j = wi,j, the edge weight

Requires (|V|2) space

Adjacency matrix representation

adjacency matrix is symmetric about the diagonal for undirected graphs

Undirected graph
6

Adjacency List for Graph G = (V,E)

An array Adj[1..|V|] of lists
each list Adj[v] is a list of all vertices adjacent to v

Requires (|E|) space

Adjacency list representation

Undirected graph
7

Minimum Spanning Tree

Spanning tree of a connected undirected graph G
subgraph of G that is a tree containing all the vertices of G if graph is not connected: spanning forest

Weight of a subgraph in a weighted graph

sum of the weights of the edges in the subgraph

Minimum spanning tree (MST) for weighted undirected graph

spanning tree with minimum weight

Minimum Spanning Tree

Undirected graph

Minimum spanning tree

Computing a Minimum Spanning Tree

Prim's sequential algorithm

// initialize spanning tree vertices VT with vertex r, the designated root // compute d[:], the // weight between // r and each // vertex outside VT // while there are vertices outside T // add u to T // recompute d[:] now // that u is in T // use d[:] to find u, // vertex closest to T 10

Minimum Spanning Tree: Prim's Algorithm

start with arbitrary root

3 iterations of Prims algorithm

11

Parallel Formulation of Prim's Algorithm

Parallelization prospects
outer loop (|V| iterations): hard to parallelize
adding 2 vertices to tree concurrently is problematic

inner loop: relatively easy to parallelize

consider which vertex is closest to MST in parallel

12

Parallel Formulation of Prim's Algorithm

Data partitioning
partition adjacency matrix in a 1-D block fashion (blocks of columns) partition distance vector d accordingly

distance array

adjacency matrix

partition d and A among p processes

13

Parallel Formulation of Prim's Algorithm

In each step,
each process first identifies the locally closest node perform a global reduction to select globally closest node
minloc reduction: node id and distance

leader inserts node into MST broadcasts choice to all processes each process updates its part of d vector locally based on choice

14

Parallel Formulation of Prim's Algorithm

Cost to select the minimum entry
O(n/p): scan n/p local part of d vector on each processor O(log p) all-to-one reduction across processors

Broadcast next node selected for membership

O(log p)

Cost of locally updating d vector

O(n/p): replace d vector with min of d vector and matrix row

Parallel time per iteration

O(n/p + log p)

Total parallel time

O(n2/p + n log p)

15

Single-Source Shortest Paths

Given weighted graph G = (V,E,w) Problem: single-source shortest paths
find the shortest paths from vertex v V to all other vertices in V

Dijkstra's algorithm: similar to Prim's algorithm

maintains a set of nodes for which the shortest paths are known grows set by adding node closest to source using one of the nodes in the current shortest path set

16

Computing Single-Source Shortest Paths

Dijkstras sequential algorithm

// initialize tree vertices VT with vertex s, the designated src // compute L[:], the // distance between Dijkstra's sequential single-source shortest paths algorithm. vertex VT // s and each // while some vertices are not in VT // add u to T // recompute L[:] // now that u is in T // use L[:] to find u, // next vertex closest // to s 17

Parallel Formulation of Dijkstra's Algorithm

Similar to parallel formulation of Prim's algorithm for MST

Approach
data partitioning
partition weighted adjacency matrix in a 1-D block fashion partition distance vector L accordingly

in each step,
each process identifies its node closest to source perform a global reduction to select globally closest node broadcast choice to all processes each process updates its part of L vector locally

Parallel performance of Dijkstra's algorithm

identical to that of Prim's algorithm
parallel time per iteration: O(n/p + log p) total parallel time: O(n2/p + n log p) 18

All-Pairs Shortest Paths

Given weighted graph G(V,E,w) Problem: all-pairs shortest paths
find the shortest paths between all pairs of vertices vi, vj V

Several algorithms known for solving this problem

19

All-Pairs Shortest Path

Serial formulation using Dijkstras algorithm

Execute n instances of the single-source shortest path

one for each of the n source vertices

Sequential time per source: O(n2) Total sequential time complexity: O(n3)

20

All-Pairs Shortest Path

Parallel formulation using Dijkstras algorithm Two possible parallelization strategies

Source partitioned: execute each of the n shortest path problems on a different processor Source parallel: use a parallel formulation of the shortest path problem to increase concurrency

21

All-Pairs Shortest Path Dijkstra's Algorithm

Source partitioned parallel formulation

Use n processors
each processor Pi finds the shortest paths from vertex vi to all other vertices
use Dijkstra's sequential single-source shortest paths algorithm

Analysis
requires no interprocess communication
provided adjacency matrix is replicated at all processes

parallel run time: (n2)

Algorithm is cost optimal

asymptotically same # of ops in parallel as in sequential version

However: can only use n processors (one per source)

22

All-Pairs Shortest Path Dijkstra's Algorithm

Source parallel parallel formulation

Each of the shortest path problems is executed in parallel

can therefore use up to n2 processors.

Given p processors (p > n)

each single source shortest path problem is executed by p/n processors.

Recall time for solving one instance of all-pair shortest path

O(n2/p + n log p)

Considering the time to do one instance on p/n processors

Represents total time since each instance is solved in parallel

23

Transitive Closure

Given graph G = (V,E) Transitive closure of G
graph G* = (V,E*)
E* = {(vi,vj) | there is a path from vi to vj in G}

Connectivity matrix of G
matrix A* = (ai*,j)
ai*,j = 1 if there is a path from vi to vj or i = j, ai*,j = otherwise.

Computing A*
use all-pairs shortest paths algorithm on the connectivity matrix resulting matrix A*: ai,j = 1 if di,j < or i = j

24

Connected Components
Definition: equivalence classes of vertices under the is reachable from relation for undirected graphs

Example: graph with three connected components {1,2,3,4}, {5,6,7}, and {8,9}
25

Connected Components
Serial depth-first search based algorithm

Perform DFS on a graph to get a forest

each tree in the forest = separate connected component.

Depth-first forest above obtained from depth-first traversal of the graph at top. result = 2 connected components
26

Connected Components Parallel Formulation

Partition the graph across processors Step 1
run independent connected component algorithms on each processor result: p spanning forests.

Step 2
merge spanning forests pairwise until only one remains

27

Connected Components Parallel Formulation

Graph G 1. Partition adjacency matrix of the graph G into two parts

2. Each process gets a subgraph of graph G

3. Each process computes the spanning forest of its subgraph of G

4. Merge the two spanning trees to form the final solution

28

Connected Components Parallel Formulation

Merge pairs of spanning forests using disjoint sets of vertices Consider the following operations on the disjoint sets
find(x)
returns pointer to representative element of the set containing x each set has its own unique representative

union(x, y)
merges the sets containing the elements x and y the sets are assumed disjoint prior to the operation

29

Connected Components Parallel Formulation

To merge forest A into forest B

for each edge (u,v) of A,
perform find operations on u and v determine if u and v are in same tree of B if not, then union the two trees (sets) of B containing u and v result: u and v are in same set, which means they are connected else , no union operation is necessary.

Merging forest A and forest B requires at most

2(n-1) find operations (n-1) union operations at most n-1 edges must be considered because A and B are forests

Using disjoint set union find algorithm with path compression

each operation takes O((n))
(n) is inverse Ackermanns function 30

Connected Components
Analysis of parallel 1-D block mapping

Partition an n x n adjacency matrix into p blocks Each processor computes local spanning forest: (n2/p) Merging approach
embed a logical tree into the topology
log p merging stages each merge stage takes time (n(n))

total cost due to merging is (n(n) log p)

During each merging stage

spanning forests are sent between nearest neighbors (n) edges of the spanning forest are transmitted

Parallel execution time

(n(n) log p)

31

Algorithms for Sparse Graphs

Dense algorithms can be improved significantly if we make use of the sparseness Sparse algorithms: use adjacency list instead of matrix Example: Prims algorithm complexity
can be reduced to O(|E| log n)
use heap to maintain costs outperforms original as long as |E| = O(n2/ log n)

Partitioning adjacency lists is more difficult for sparse graphs

do we balance number of vertices or edges?

Parallel algorithms typically make use of graph structure or degree information for performance

32

References

Ananth Grama, George Karypis, Vipin Kumar, Anshul Gupta. Chapter 10. Introduction to Parallel Computing, Second Edition. Addison Wesley, 2003. Ananth Grama, Anshul Gupta, George Karypis, Vipin Kumar. Graph Algorithms. Slides.

33