Week 07
Graph Traversal |
Graph Traversal | 2/49 |
A common class of graph algorithms involves
Two strategies for graph traversal/search: depth-first, breadth-first
... Graph Traversal | 3/49 |
Previous expression of algorithms used
g->nV
g->nE
g->edges[v][w]
To make things more representation-independent, use
nV(g)
nE(g)
hasEdge(g,v,w)
Depth-first Traversal | 4/49 |
Traverse graph (depth-first, recording visiting order):
int order;// visiting order int *visited;// array of visiting orders // indexed by vertex 0..V-1 void dfs(Graph g) { int i; visited = calloc(nV(g),sizeof(int)); order = 1; dfsR(g, 0); } void dfsR(Graph g, Vertex v) { visited[v] = order++; Vertex w; for (w = 0; w < nV(g); w++) {// for each if (!hasEdge(g,v,w)) continue;// neighbour if (!visited[w]) dfsR(g, w); } }
... Depth-first Traversal | 5/49 |
Visiting order for ...
Exercise 1: Depth-first Traversal | 6/49 |
Which vertices will be visited during dfs(g)
How can we ensure that all vertices are visited?
... Depth-first Traversal | 7/49 |
Modified dfs
void dfs(Graph g) { int i; visited = calloc(nV(g),sizeof(int)); order = 1; while (order < nV(g)) { Vertex v; for (v = 0; v < nV(g); v++) if (visited[v] == -1) break; dfsR(g, v); } }
DFS Examples | 8/49 |
Some problems to solve via DFS graph search
Checking for Cycles | 9/49 |
A graph has a cycle if
bool hasCycle(Graph g)
We are not required to give the path, just indicate its presence.
Exercise 2: Buggy Cycle Check | 10/49 |
This DFS cycle check has a bug. Fix it.
int *visited;// array [0..V-1] of booleans int hasCycle(Graph g) { visited = calloc(nV(g),sizeof(int)); int result = dfsCycleCheck(g, 0); free(visited); return result; } int dfsCycleCheck(Graph g, Vertex v) { visited[v] = 1; Vertex w; for (w = 0; w < nV(g); w++) { if (!hasEdge(g,v,w)) continue; if (visited[w]) return 1;// found cycle return dfsCycleCheck(g, w); } return 0;// no cycle at v }
Connected Components | 11/49 |
Each vertex belongs to a connected component
Function components(Graph g)
componentOf[]
componentOf[v]
v
... Connected Components | 12/49 |
Assign vertices to connected components:
int ncounted;// # vertices allocated int *componentOf;// array of component ids // indexed by vertex 0..V-1 void components(Graph g) { int i, componentID = 1; componentOf = calloc(nV(g),sizeof(int)); ncounted = 0; while (ncounted < nV(g)) { Vertex v; for (v = 0; v < nV(g); v++) if (componentOf[v] == -1) break; dfsR(g, v, componentID); componentID++; }// componentOf[0..nV-1] is now set } void dfsR(Graph g, Vertex v, int c) { componentOf[v] = c; ncounted++; Vertex w; for (w = 0; w < nV(g); w++) { if (!hasEdge(g,v,w)) continue; if (componentOf[w] == 0) dfsR(g,w,c); } }
Breadth-first Search | 13/49 |
BFS algorithm (records visiting order):
int *visited;// array [0..V-1] of visiting order void bfs(Graph g, Vertex v) { int i, order = 1; visited = calloc(nV(g),sizeof(int)); Queue q = newQueue(); QueueJoin(q,v); while (!QueueIsEmpty(q)) { Vertex y, x = QueueLeave(q); if (visited[x]) continue; visited[x] = order++; for (y = 0; y < nV(g); y++) { if (!hasEdge(g,x,y)) continue; if (!visited[y]) QueueJoin(q,y); } } }
Exercise 3: Breadth-first Traversal | 14/49 |
Show the BFS order we visit vertices in bfs(g,0)
Exercise 4: BFS Visiting Order | 15/49 |
Change the above algorithm so that visited
0-3-1-4-2
visited = {0=>0, 1=>3, 2=>1, 3=>4, 4=>2}
visited = {0=>0, 1=>2, 2=>4, 3=>1, 4=>3}
Paths: Simple, Hamilton, Euler |
Simple Paths | 17/49 |
A simple path is
Questions on paths:
Path Finding | 18/49 |
BFS algorithm for path checking:
int hasPath(Graph g, Vertex src, Vertex dest) { int *visited = calloc(nV(g),sizeof(int)); Queue q = newQueue(); QueueJoin(q,src); int isFound = 0; while (!QueueIsEmpty(q) && !isFound) { Vertex y, x = QueueLeave(q); for (y = 0; y < nV(g); y++) { if (!hasEdge(g,x,y)) continue; if (y == dest) { isFound = 1; break; } if (!visited[y]) { QueueJoin(q,y); visited[y] = 1; } } } free(visited); return isFound; }
... Path Finding | 19/49 |
BFS algorithm for finding shortest path:
int findPath(Graph g, Vertex src, Vertex dest) { Vertex *path = malloc(nV(g) * sizeof(Vertex)); int *visited = calloc(nV(g),sizeof(int)); Queue q = newQueue(); QueueJoin(q,src); int isFound = 0; while (!emptyQ(q) && !isFound) { Vertex y, x = QueueLeave(q); for (y = 0; y < nV(g); y++) { if (!hasEdge(g,x,y)) continue; if (!visited[y]) { path[y] = x; QueueJoin(q,y); visited[y] = 1; } if (y == dest) { isFound = 1; break; } } } if (isFound) {// display path in dest..src order Vertex v; for (v = dest; v != src; v = path[v]) printf("%d-", v); printf("%d\n", src); } free(visited); free(path); return isFound; }
... Path Finding | 20/49 |
The above algorithm finds a "shortest" path
Hamilton Path and Tour | 21/49 |
Hamilton path problem:
Simple to state, but difficult to solve (NP-hard).
Example graph and two possible Hamilton paths:
... Hamilton Path and Tour | 22/49 |
Approach (generate-and-test):
... Hamilton Path and Tour | 23/49 |
Function to find Hamilton path:
Vertex *visited;// array [0..V-1] of bools int hasHamiltonPath(Graph g, Vertex src, Vertex dest) { visited = calloc(nV(g),sizeof(int)); int res = HamiltonR(g, src, dest, nV(g)-1); free(visited); return res; } int HamiltonR(Graph g, Vertex v, Vertex w, int d) { int t; if (v == w) return (d == 0) ? 1 : 0; visited[v] = 1; for (t = 0; t < nV(g); t++) { if (!hasEdge(g,v,t)) continue; if (visited[t] == 1) continue; if (HamiltonR(g,t,w,d-1)) return 1; } visited[v] = 0; return 0; }
... Hamilton Path and Tour | 24/49 |
Analysis: worst case requires (V-1)! paths to be examined
Consider a graph with isolated vertex and the rest fully-connected
Checking hasHamiltonPath(g,0,
)
Note, however, that the above case could be solved in constant time if
we had a fast check for 0 and x being in the same connected component
Hamilton Path and Tour | 25/49 |
Hamilton path problem:
No efficient algorithm known (use generate-and-test)
Euler Path and Tour | 26/49 |
Euler path problem:
If v = w, the we have a Euler tour.
... Euler Path and Tour | 27/49 |
One possible "brute-force" approach:
... Euler Path and Tour | 28/49 |
Assume the existence of degree(G,v)
Function to check whether a graph has a Euler path:
int hasEulerPath(Graph g, Vertex v, Vertex w) { int t = degree(g,v) + degree(g,w); if ((t % 2) != 0) return 0; Vertex x; for (x = 0; x < nV(g); x++) { if (x != v && x != w) { if ((degree(g,x) % 2) != 0) return 0; } } return 1; }
Analysis:
Exercise 5: Vertex Degrees | 29/49 |
degree(g,v)
int
Use the function interface:
void degrees(Graph g, int ds[]) { ... }
degrees
hasEulerPath()
Connected Components | 30/49 |
Problems:
components(g)
Exercise 6: Connectedness Checks | 31/49 |
Assume that components(g)
componentOf[nV]
sameComponent(g,v,w)
v
w
nComponents(g)
... Connected Components | 32/49 |
Consider an application where connectivity is critical
components()
GraphRep
struct GraphRep { ... int nC;// # connected components int *cc;// which component contains each vertex ...// i.e. array [0..nV-1] of 0..nC-1 }
... Connected Components | 33/49 |
With this structure, the above tasks become trivial:
// How many connected subgraphs are there? int nComponents(Graph g) { return g->nC; }// Are two vertices in the same connected subgraph? int sameComponent(Graph g, Vertex v, Vertex w) { return (g->cc[v] == g->cc[w]); }
... Connected Components | 34/49 |
Consider maintenance of such a graph representation:
(nC == nV)
nC
nC
cc[]
v,w
nComponents()
sameComponent()
Exercise 7: Implementing Component Array | 35/49 |
Add the nC
cc
GraphRep
Modify the following functions to maintain them:
Graph newGraph(int nV) { ... } void insertE(Graph g, Edge e) { ... } void removeE(Graph g, Edge e) { ... }
Consider adding the dotted edges to the following graph
Directed Graphs (Digraphs) |
Directed Graphs (Digraphs) | 37/49 |
In our previous discussion of graphs:
... Directed Graphs (Digraphs) | 38/49 |
Example digraph and adjacency matrix representation:
Non-directional ⇒ symmetric matrix
Directional ⇒ non-symmetric matrix
... Directed Graphs (Digraphs) | 39/49 |
Terminology for digraphs ...
Directed path: list of n ≥ 2 vertices v1, v2, ... vn
Indegree of vertex: d-1(v) = number of edges like (_, v)
Reachability: w is reachable from v if ∃ directed path v,...,w
Strong connectivity: every vertex is reachable from every other vertex
Directed acyclic graph (DAG): graph containing no directed cycles
Digraph Applications | 40/49 |
Potential application areas:
Domain | Vertex | Edge | ||
Web | web page | hyperlink | ||
scheduling | task | precedence | ||
chess | board position | legal move | ||
science | journal article | citation | ||
dynamic data | malloc'd object | pointer | ||
programs | function | function call | ||
make | file | dependency |
... Digraph Applications | 41/49 |
Problems to solve on digraphs:
Digraph Representation | 42/49 |
Similar set of choices as for non-directional graphs:
... Digraph Representation | 43/49 |
Costs of representations: (where degree d(v) = #edges leaving v)
Representation | Space | Add edge | Exists edge (v,w)? | Get edges leaving v |
|||||
Adjacency matrix | V2 | 1 | 1 | V | |||||
Adjacency lists | V+E | d(v) | d(v) | d(v) | |||||
Adjacency sets | V+E | d(v) | log(d(v)) | d(v) |
Overall, adjacency sets representation (using sorted arrays) is best
PageRank | 44/49 |
Goal: determine which Web pages are "important"
Approach: ignore page contents; focus on hyperlinks
Most frequent operation in algorithm "Does edge (v,w) exist?"
Exercise 8: Estimate the size of the Web | 45/49 |
How could you work out ...
What makes it difficult to work out?
One attempt: http://www.worldwidewebsize.com/
... PageRank | 46/49 |
Simple PageRank algorithm:
PageRank(myPage): rank = 0; foreach (page in the Web) if (linkExists(page,myPage)) rank++;
Note: requires inbound link check (not outbound as assumed above)
For analysis:
Exercise 9: Checking inbound links | 47/49 |
Write a function
Vertex *inBound(Graph g, Vertex v, int *nInBound)
that returns a count and array of vertices w s.t. (w,v)
Do this for
... PageRank | 48/49 |
Costs for computing PageRank for each representation:
Representation | linkExists(v,w) | Cost | ||
Adj. matrix | edge[v][w] | V.1 | ||
Adj. lists | search(w,list[v]) | V.(E/V) = E | ||
Adj. sets | isElem(w,set[v]) | V.log(E/V) |
Not feasible ... V ≅ 4×1010 ⇒ matrix has 1021 cells
I.e. we can't store the entire web as a Graph structure
So how to really do it?
... PageRank | 49/49 |
Approach: the random web surfer
curr = random page for (a long time) { if (!isElem(seen, (prev,curr))) if (!inArray(rank,curr)) rank[curr] = 0 rank[curr]++ seen = include(seen, (prev,curr)) if (random(0,100) < 85) prev = curr curr = choose hyperlink from curr else// avoids getting stuck prev = null curr = random page }
Could be accomplished while we crawl web to build search index
Produced: 6 Sep 2017