Week 08
Reachability |
Transitive Closure | 2/34 |
Given a digraph g it is potentially useful to know
bool reachable(Graph g, Vertex s, Vertex t)
Example applications:
... Transitive Closure | 3/34 |
How to compute transitive closure?
One possibility:
hasPath(s,t)
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
... 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
This is know as Warshall's algorithm
Exercise 1: Transitive Closure Matrix | 7/34 |
Trace Warshall's algorithm on the following graph:
... Transitive Closure | 8/34 |
1st iteration i=0
i=1
i=2
4th iteration |
Exercise 2: Transitive Closure | 9/34 |
Trace Warshall's algorithm on the following graph:
... Transitive Closure | 10/34 |
Cost analysis (tc[][]
makeClosure()
reachable()
reachable()
reachable()
reachable()
Alternative: use DFS in each call to reachable()
Cost analysis (DFS):
reachable()
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
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
Weighted Graphs |
Weighted Graphs | 14/34 |
Graphs so far have considered
... Weighted Graphs | 15/34 |
Example: major airline flight routes in Australia
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?
Exercise 3: Implementing a Route Finder | 17/34 |
If we represent a street map as a graph
Exercise 4: Implementing Facebook | 18/34 |
Facebook could be considered as a giant "social graph"
Weighted Graph Representations | 19/34 |
Adjacency matrix representation with weights:
Note: need distinguished value to indicate "no edge".
... Weighted Graph Representations | 20/34 |
Adjacency lists representation with weights:
Note: if non-directed, each edge appears twice with same weight
... Weighted Graph Representations | 21/34 |
Edge list representation with weights:
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)
... 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)
t
Write a C function to compute this value, assuming
... Minimum Spanning Trees | 26/34 |
Simplifying assumptions:
Kruskal's Algorithm | 27/34 |
One approach to computing MST for graph G(V,E):
... Kruskal's Algorithm | 28/34 |
Execution trace of Kruskal's algorithm:
Exercise 6: Kruskal's MST Algorithm | 29/34 |
Show how Kruskal's algorithm produces an MST on:
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:
Prim's Algorithm | 32/34 |
Another approach to computing MST for graph G(V,E):
... 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