Week 08

Reachability

Transitive Closure 2/34

Given a digraph g it is potentially useful to know

is vertex t reachable from vertex s?
alternatively, is there a path from s to t?

Could be encapsulated as

bool reachable(Graph g, Vertex s, Vertex t)

Example applications:

can I complete a schedule from the current state?
is a malloc'd object being referenced by any pointer?

How to compute transitive closure?

... Transitive Closure 3/34

How to compute transitive closure?

One possibility:

implement it via hasPath(s,t) (itself implemented by DFS or BFS algorithm)
feasible if reachable(g, s,t) is infrequent operation

What if we have an algorithm that frequently needs to check rechability?

Would be very convenient/efficient to have a look-up table:

int reachable(Graph g, Vertex s, Vertex t)
{
    return (g->tc[s][t]);
}

Of course, if V is very large, then this is not feasible.

... Transitive Closure 4/34

Goal: produce a matrix of reachability values

if tc[s][t] is 1, then t is reachable from s
if tc[s][t] is 0, then t is not reachable from s

Example: which reachable s..t exist in the following graph?

... Transitive Closure 5/34

Transitive Closure matrix for more complex graph:

Reachability matrix = transitive closure (tc) under connection

... Transitive Closure 6/34

A possible implementation to compute Transitive Closure Matrix:

for each edge in G
   copy edge[v][w] to tc[v][w]

for (i = 0; i < V; i++) {
   for (s = 0; s < V; s++) {

      for (t = 0; t < V; t++) {
         if (tc[s][i] && tc[i][t]) 
             tc[s][t] = 1;
      }

   }
}

then we get an algorithm to convert e into a tc

This is know as Warshall's algorithm

Exercise 1: Transitive Closure Matrix 7/34

Trace Warshall's algorithm on the following graph:

[Diagram:Pics/graphs/tc-graph2-small.png]

... Transitive Closure 8/34

1^st iteration i=0:

`tc`	[0]	[1]	[2]	[3]
[0]	0	1	1	1
[1]	1	1	1	1
[2]	0	1	0	0
[3]	0	0	0	0

2^nd iteration i=1:

`tc`	[0]	[1]	[2]	[3]
[0]	1	1	1	1
[1]	1	1	1	1
[2]	1	1	1	1
[3]	0	0	0	0

3^rd iteration i=2: unchaged

4^th iteration i=3: unchanged

Exercise 2: Transitive Closure 9/34

Trace Warshall's algorithm on the following graph:

[Diagram:Pics/graphs/tc-example-small.png]

... Transitive Closure 10/34

Cost analysis (tc[][]):

storage: additional V² items (each item may be 1 bit)
computation of makeClosure(): V³ on first call to reachable()
computation of reachable(): O(1) after first call to reachable()

Amortization: many calls to reachable() would justify other costs

Alternative: use DFS in each call to reachable()

Cost analysis (DFS):

storage: cost of queue and set during reachable
computation of reachable(): O(V²) (for adj matrix)

Bitmap Transitive Closure (TC) Matrix 11/34

The space cost of a Transitive Closure (TC) matrix implemented as

int **tc;
// or even 
unsigned char **tc

would be significant.

We could improve the actual cost by implementing as

BitMap tc;

which uses just one bit for each entry in the TC.

Note: does not improve asymptotic behaviour

Bitmap Transitive Closure (TC) Matrix (cont) 12/34

Implement the BitMap ADT (square boolean matrix):

typedef struct {
   unsigned int dimension;
   unsigned int *bits;
} *BitMap;
BitMap newBitMap(int dimension);
void   setBit(BitMap b, int i, int j);
int    unsetBit(BitMap b, int i, int j);
int    isSet(BitMap b, int i, int j);

What a BitMap looks like

Weighted Graphs

Weighted Graphs 14/34

Graphs so far have considered

edge = an association bewteen two vertices/nodes
may be a precedence in the association (directed)

Some applications require us to consider

a cost or weight of an association
modelled by assigning values to edges (0..1?, -ve?)

Weights can be used in both directed and non-directed graphs.

... Weighted Graphs 15/34

Example: major airline flight routes in Australia

[Diagram:Pics/wgraphs/flights-small.png]

Representation: edge = direct flight; weight = approx flying time (hours)

... Weighted Graphs 16/34

Weights lead to minimisation-type questions, e.g.

1. Cheapest way to connect all vertices?

a.k.a. minimum spanning tree problem
assumes: edges are weighted and non-directed

2. Cheapest way to get from A to B?

a.k.a shortest path problem
assumes: edges are weighted and directed

Exercise 3: Implementing a Route Finder 17/34

If we represent a street map as a graph

what are the vertices?
what are the edges?
are edges directional?
what are the weights?
are the weights fixed?

What kind of algorithm would ...

help us find the "quickest" way to get from A to B?

Exercise 4: Implementing Facebook 18/34

Facebook could be considered as a giant "social graph"

what are the vertices?
what are the edges?
are edges directional?
what are the weights?
are the weights fixed?

What kind of algorithm would ...

help us find people that you might like to "friend"?

Weighted Graph Representations 19/34

Adjacency matrix representation with weights:

[Diagram:Pics/wgraphs/adjmatrixw-small.png]

Note: need distinguished value to indicate "no edge".

... Weighted Graph Representations 20/34

Adjacency lists representation with weights:

[Diagram:Pics/wgraphs/adjlistsw-small.png]

Note: if non-directed, each edge appears twice with same weight

... Weighted Graph Representations 21/34

Edge list representation with weights:

[Diagram:Pics/wgraphs/edgelistw-small.png]

Note: not very efficient for use in processing algorithms, unless weight-sorted

Minimum Spanning Trees

Minimum Spanning Trees 23/34

Reminder: Spanning tree ST of graph G(V,E)

spanning = all vertices, tree = no cycles
ST is a subgraph of G (G'(V,E') where E' ⊆ E)
ST is connected and acyclic

Minimum spanning tree MST of graph G

MST is a spanning tree of G
sum of edge weights is no larger than any other ST

Problem: how to (efficiently) find MST for graph G?

... Minimum Spanning Trees 24/34

Brute force optimisation solution:

typedef Graph MSTree; // an MST is a subgraph

MSTree findMST(Graph g)
{
   MSTree t, best;  float bestCost = MAXFLOAT;
   foreach (t in AllSpanningTrees(g)) {
      if (cost(t) < bestCost) {
         best = copy(t);  bestCost = cost(t);
      }
   }
   return best;
}

Not useful because #spanning trees is potentially large.

Exercise 5: Cost of MST 25/34

The cost(t) function gives sum of edge weights in t.

Write a C function to compute this value, assuming

adjacency matrix representation
non-directed edges ⇒ symmetric matrix

How about a function generate all spanning trees?

... Minimum Spanning Trees 26/34

Simplifying assumptions:

edges in G are not directed (MST for digraphs is harder)
no edge weights are negative
all edge weights are distinct

If edges may have same weight:

MST may not be unique (not necessarily a problem)
if we have to choose between edges with same weight ...
- greedy algorithms might make wrong choice
- might not end up with minimum cost solution

Kruskal's Algorithm 27/34

One approach to computing MST for graph G(V,E):

start with empty MST
consider edges in increasing weight order
add edge if it does not form a cycle in MST
repeat until V-1 edges are addedw

Critical operations:

iterating over edges in weight order
checking for cycles in a graph

... Kruskal's Algorithm 28/34

Execution trace of Kruskal's algorithm:

[Diagram:Pics/wgraphs/kruskal-small.png]

Exercise 6: Kruskal's MST Algorithm 29/34

Show how Kruskal's algorithm produces an MST on:

[Diagram:Pics/wgraphs/example-graph-small.png]

Implementation of Kruskal's Algorithm 30/34

C-like description of algorithm:

MSTree kruskalFindMST(Graph g)
{
   Graph mst = newGraph(); //MST initially empty
   Edge eList[g->nV]; //sorted array of edges
   edges(eList, g->nE, g);
   sortEdgeList(eList, g->nE);
   int i;  Edge e;
   for (i = 0; mst->nE < g->nV-1; i++) {
      e = eList[i];
      insertE(mst, e);
      if (hasCycle(mst)) removeE(mst, e);
   }
   return mst;
}

... Implementation of Kruskal's Algorithm 31/34

Rough cost analysis:

sorting edge list is O(E log E)
at least V iterations over sorted edges
on each iteration ...
- getting next lowest cost edge is O(1)
- checking whether adding it forms a cycle: cost = ??

Possibilities for cycle checking:

use DFS ... too expensive?
use Union-Find data structure (see Sedgewick ch.1)

Prim's Algorithm 32/34

Another approach to computing MST for graph G(V,E):

start from any vertex s and empty MST
choose edge not already in MST to add to MST
- must not involve a self-loop
- must connect to a vertex already on MST
- must have minimal weight of all such edges
repeat until MST covers all vertices

Critical operations:

checking for vertex being connected in a graph
finding min weight edge in a set of edges

... Prim's Algorithm 33/34

Execution trace of Prim's algorithm:

Exercise 7: Prim's MST Algorithm 34/34

Exercise: show how Prim's algorithm produces an MST on:

Produced: 8 Sep 2017