13: graphs #2

Cycle Detection | Minimum Spanning Trees | Connectivity | Topological Sort

Cycle Detection

To use the WFIAlgorithm to detect cycles, it takes O(|V|^3) time.

Undirected Graphs

A simple modification to depth-first search can be done for undirected graphs that takes O(|V| + |E|) time.
1:  
bool
 
cycleDetect(
IVertex 
v)

2:  
 
 
vector<
IVertex 
*>
 
path;

3:  
 
 
set<
IVertex 
*>
 
visited;

4:  
 
 
add 
to 
path;

5:  
 
 
add 
to 
visited;

6:  
 
 
return
 
doCycleDetect(
v, 
path, 
visited)
;

7:  

8:  
bool
 
doCycleDetect(
IVertex 
v, 
vector<
IVertex 
*>
&
 
path, 
set<
IVertex 
*>
&
 
visited)

9:  
 
 
foreach(
edge 
'e' 
in 
v->getEdges)

10: 
 
 
 
 
IVertex 
target 
e->getTarget(
)
;

11: 
 
 
 
 
if
(
 
last 
element 
in 
path 
== 
target)

12: 
 
 
 
 
 
 
continue;

13: 
 
 
 
 
if
(
 
visited 
contains 
target 
)

14: 
 
 
 
 
 
 
return
 
true;

15: 
 
 
 
 
add 
to 
path;

16: 
 
 
 
 
add 
target 
to 
visited;

17: 
 
 
 
 
if
(
doCycleDetect(
target, 
path, 
visited)
)

18: 
 
 
 
 
 
 
return
 
true;

19: 
 
 
 
 
else

20: 
 
 
 
 
 
 
path.pop_back(
)
;

21: 
 
 
return
 
false;

CycleDetectionGraph
Cycles: [acfa], [acfda], [dbed]

Directed graph cycle detection

In directed graphs, there may be edges between different spanning sub-trees, called side-edges. A back-edge only indicates a cycle if it joins two vertices already included in the same spanning tree.
  • To handle this case we check to see if num(u) is infinity and set num(v) to infinity after leaving the recursion of the current spanning tree.
1: 
algorithm
 
digraphCycleDetectionDFS(
vertex 
v)

2: 
 
 
num(
v)
 
i++;

3: 
 
 
for
 
all 
vertices 
adjacent 
to 
v

4: 
 
 
 
 
if
 
num(
u)
 
is 
0

5: 
 
 
 
 
 
 
digraphCycleDetectionDFS(
u)
;

6: 
 
 
 
 
else
 
if
 
num(
u)
 
is 
not 
infinity

7: 
 
 
 
 
 
 
cycle 
detected;

8: 
 
 
num(
v)
 
infinity;

CycleDetectionGraph
Cycles: [abca], [abcda]

Spanning Trees

A spanning tree (or forest, set of trees) is a tree that includes all the vertices of an original graph, but not necessarily all the edges.
  1. Original Graph
    SpanningTree
  2. Spanning Tree Built From Breadth-First Search
    SpanningTree

The edges in a spanning tree are forward edges in the original graph.

Minimum Spanning Trees

  • Consider a graph representing airline connections between cities
  • If the airline needs to save money and shut down as many connections as possible, can it be done in a way that it is still possible to reach any city from any other city?
A minimum spanning tree is a spanning tree in which the sum of the weights is minimized.
1: 
algorithm
 
kruskalAlgorithm(
weight 
connected 
undirected 
graph)

2: 
 
 
tree 
null;

3: 
 
 
edges 
sequence 
of 
all 
edges 
of 
graph 
sorted 
by 
weight;

4: 
 
 
for
(
1;
 
<= 
|E| 
and 
|tree| 
|V| 
1;
 
++i)

5: 
 
 
 
 
if
(
e_i 
from 
edges 
does 
not 
form 
cycle 
with 
edges 
in 
tree

6: 
 
 
 
 
 
 
add 
e_i 
to 
tree;

  1. Start Graph:
    MinimumSpanningTree
  2. Add the smallest weighted edge to the tree:
    MinimumSpanningTree
  3. Add the next smallest weighted edge to the tree:
    MinimumSpanningTree
  4. Add the 3rd smallest weighted edge to the tree:
    MinimumSpanningTree
  5. Add the 4th smallest weighted edge to the tree:
    MinimumSpanningTree
  6. Add the 5th smallest weighted edge to the tree.
    MinimumSpanningTree
  7. Add the 7th smallest weighted edge to the tree. (The 6th formed a cycle). All other edges form a cycle so we are done.
    MinimumSpanningTree
The time complexity of Kruskal's Algorithm is dependent on
  • The sorting method used: O(|E|lg|E|)
  • The for loop: O((|V|-1)|V|) = O(|V|^2)
  • The max number of edges in a graph is |V|^2, so the time complexity is O(|E|lg|E|)

Dijkstra's Method for Spanning Trees

Kruskal's Algorithm requires all edges are ordered. Dijkstra's Method for Spanning Trees does not.
1: 
algorithm
 
dijkstraSpanningTree(
weight 
connected 
undirected 
graph)

2: 
 
 
tree 
null;

3: 
 
 
edges 
an 
unsorted 
sequence 
of 
all 
edges 
of 
graph;

4: 
 
 
for
(
to 
|E|)

5: 
 
 
 
 
add 
e_j 
to 
tree;

6: 
 
 
 
 
if
(
there 
is 
cycle 
in 
tree)

7: 
 
 
 
 
 
 
remove 
an 
edge 
with 
maximum 
weight 
from 
this 
only 
cycle;

  1. Start Graph:
    MinimumSpanningTree
  2. Add a random edge:
    MinimumSpanningTree
  3. Add a random edge:
    MinimumSpanningTree
  4. Add a random edge:
    MinimumSpanningTree
  5. Add a random edge:
    MinimumSpanningTree
  6. Add a random edge:
    MinimumSpanningTree
  7. Add a random edge:
    MinimumSpanningTree
  8. There is a cycle, remove the largest weighted edge
    MinimumSpanningTree
  9. Add a random edge:
    MinimumSpanningTree
  10. There is a cycle, remove the largest weighted edge (the one we just added)
    MinimumSpanningTree
  11. Add a random edge:
    MinimumSpanningTree
  12. Add a random edge:
    MinimumSpanningTree
  13. There is a cycle, remove the largest weighted edge. Done
    MinimumSpanningTree
Time complexity: O(|E||V|).
  • The for loop executes |E| times
  • Each time checking for a cycle takes |V| time

Connectivity in Undirected Graphs

  • An undirected graph is called connected if there is a path between any two vertices
  • A graph is n-connected if there are at least n different paths between its vertices
  • A 2-connected or biconnected graph has at least two paths between each vertex
  • A graph is not biconnected if you can find an edge that is required between the path of two vertices
  • If that edge edge is removed, the graph is split into two.
  • The vertices joined by this edge are called articulation points or cut-vertices
  • The edge is called a bridge or cut-edge
Connected subgraphs with no articulation points or bridges are called blocks (or biconnected components when there are at least two vertices).
1:  
algorithm
 
blockSearch(
)

2:  
 
 
for
 
all 
vertices 
v

3:  
 
 
 
 
num(
v)
 
0;

4:  
 
 
1;

5:  
 
 
while
 
there 
is 
vertex 
such 
that 
num(
v)
 
== 
0

6:  
 
 
 
 
blockDFS(
v, 
NULL)
;

7:  

8:  
algorithm
 
blockDFS(
vertex 
v, 
vertex 
parent_v)

9:  
 
 
pred(
v)
 
num(
v)
 
i++;

10: 
 
 
for
 
all 
vertices 
adjacent 
to 
v

11: 
 
 
 
 
if
 
edge(
uv)
 
has 
not 
been 
processed

12: 
 
 
 
 
 
 
push(
edge(
uv)
)
;

13: 
 
 
 
 
if
 
num(
u)
 
is 
0

14: 
 
 
 
 
 
 
blockDFS(
u, 
v)

15: 
 
 
 
 
 
 
if
 
pred(
u)
 
>
num(
v)

16: 
 
 
 
 
 
 
 
 
pop(
)
;

17: 
 
 
 
 
 
 
 
 
while
 
!= 
edge(
vu)

18: 
 
 
 
 
 
 
 
 
 
 
output 
e;

19: 
 
 
 
 
 
 
 
 
 
 
pop(
)
;

20: 
 
 
 
 
 
 
 
 
output 
e;

21: 
 
 
 
 
 
 
else

22: 
 
 
 
 
 
 
 
 
pred(
v)
 
min(
pred(
v)
pred(
u)
)
 

23: 
 
 
 
 
else
 
if
 
is 
not 
parent_v

24: 
 
 
 
 
 
 
pred(
v)
 
min(
pred(
v)
num(
u)
)
 

Time complexity of blockSearch: O(|V| + |E|)

BlockDFS

  1. Start:
    BlockDFS
  2. Lines 9 - 14. Visiting edge (a, c)
    BlockDFS
  3. Recurse, Lines 9 - 14. Visiting edge (c, a)->visited, Visiting edge (c, f).
    BlockDFS
  4. Recurse, Lines 9 - 13. Visiting edge (f, a). Num(a) != 0.
    BlockDFS
  5. Lines 23 - 24. u != parent. pred(f) = num(a)
    BlockDFS
  6. Line 9 - 14. Visiting edge (f, c)->visited, Visiting edge (f, d). Recurse
    BlockDFS
  7. Line 9 - 24. Visiting edge (d, a). Add edge to stack. u != parent, pred(d)=num(a)
    BlockDFS
  8. Line 9 - 14. Visiting edge (d, f)->visited. Visiting edge (d, b). Add edge to stack. Recurse
    BlockDFS
  9. Line 9 - 14. Visiting edge (b, d)->visited. Visiting edge (b, e). Add edge to stack. Recurse
    BlockDFS
  10. Line 9 - 24. Visiting edge (e, d). Add Edge to stack, u != parent, pred(e) = num(d)
    BlockDFS
  11. Last edge: (e, b) is visited. Returning from recursion, twice.
    BlockDFS
  12. Sitting at edge (d, b). Block Found: [d, e, b].
    BlockDFS
  13. Visiting edge (d, e)->visited. pred(d) = pred(d). Returning from recursion three times
    BlockDFS
  14. Block Found: [a, d, f, c]. Done
    BlockDFS

Connectivity in Directed Graphs - Strong Components

1:  
algorithm
 
strongDFS(
vertex 
v)

2:  
 
 
pred(
v)
 
num(
v)
 
i++;

3:  
 
 
push(
v)
;

4:  
 
 
for
 
all 
vertices 
adjacent 
to 
v

5:  
 
 
 
 
if
 
num(
u)
 
is 
0

6:  
 
 
 
 
 
 
strongDFS(
u)
;

7:  
 
 
 
 
 
 
pred(
v)
 
min(
pred(
v)
pred(
u)
)
;

8:  
 
 
 
 
else
 
if
 
num(
u)
 
<
 
num(
v)
 
and 
is 
on 
stack

9:  
 
 
 
 
 
 
pred(
v)
 
min(
pred(
v)
num(
u)
)

10: 
 
 
if
 
pred(
v)
 
== 
num(
v)
;

11: 
 
 
 
 
pop(
)
;

12: 
 
 
 
 
while
 
!= 
v

13: 
 
 
 
 
 
 
output 
w;

14: 
 
 
 
 
 
 
pop(
)
;

15: 
 
 
 
 
output 
w;

16: 

17: 
algorithm
 
strongSearch(
)

18: 
 
 
for
 
all 
vertices 
v

19: 
 
 
 
 
num(
v)
 
0;

20: 
 
 
1;

21: 
 
 
while
 
there 
is 
vertex 
such 
that 
num(
v)
 
== 
0

22: 
 
 
 
 
strongDFS(
v)
;

StrongDFS
1:  
Executing 
strongDFS 
on:
 
v1

2:  
 
 
pred(
v1)
 
== 
num(
v1)
 
1

3:  
Executing 
strongDFS 
on:
 
v4

4:  
 
 
pred(
v4)
 
== 
num(
v4)
 
2

5:  
pred(
v4)
 
== 
num(
v4)

6:  
Strong 
Component:
 

7:  
v4

8:  
Returing 
from 
recursion 
on:
 
v4

9:  
 
 
pred(
v1)
 
min(
pred(
v1)
pred(
v4)
)
 
1

10: 
Executing 
strongDFS 
on:
 
v7

11: 
 
 
pred(
v7)
 
== 
num(
v7)
 
3

12: 
Executing 
strongDFS 
on:
 
v3

13: 
 
 
pred(
v3)
 
== 
num(
v3)
 
4

14: 
num(
v1)
 
<
 
num(
v3)
 
and 
v1 
is 
on 
stack

15: 
 
 
pred(
v3)
 
min(
pred(
v3)
num(
v1)
)
 
1

16: 
Returing 
from 
recursion 
on:
 
v3

17: 
 
 
pred(
v7)
 
min(
pred(
v7)
pred(
v3)
)
 
1

18: 
Returing 
from 
recursion 
on:
 
v7

19: 
 
 
pred(
v1)
 
min(
pred(
v1)
pred(
v7)
)
 
1

20: 
pred(
v1)
 
== 
num(
v1)

21: 
Strong 
Component:
 

22: 
v3

23: 
v7

24: 
v1

25: 
Executing 
strongDFS 
on:
 
v2

26: 
 
 
pred(
v2)
 
== 
num(
v2)
 
5

27: 
Executing 
strongDFS 
on:
 
v5

28: 
 
 
pred(
v5)
 
== 
num(
v5)
 
6

29: 
Executing 
strongDFS 
on:
 
v6

30: 
 
 
pred(
v6)
 
== 
num(
v6)
 
7

31: 
num(
v2)
 
<
 
num(
v6)
 
and 
v2 
is 
on 
stack

32: 
 
 
pred(
v6)
 
min(
pred(
v6)
num(
v2)
)
 
5

33: 
Returing 
from 
recursion 
on:
 
v6

34: 
 
 
pred(
v5)
 
min(
pred(
v5)
pred(
v6)
)
 
5

35: 
Returing 
from 
recursion 
on:
 
v5

36: 
 
 
pred(
v2)
 
min(
pred(
v2)
pred(
v5)
)
 
5

37: 
pred(
v2)
 
== 
num(
v2)

38: 
Strong 
Component:
 

39: 
v6

40: 
v5

41: 
v2

Time complexity of strongSearch: O(|V| + |E|)

Topological Sort

Topological Sort can be used to find the build order in C++ programs. The first file that needs to be built is the file with no dependencies. Toplogical Sort must be done on a graph where strong components are compressed into single nodes.

Summary algorithm:
1: 
algorithm
 
topologicalSort(
digraph 
g)

2: 
 
 
for
 
to 
|V|

3: 
 
 
 
 
find 
minimal 
vertex 
v;

4: 
 
 
 
 
num(
v)
 
i;

5: 
 
 
 
 
remove 
from 
vertex 
and 
all 
edges 
incident 
with 
v;


Algorithm Based on DFS:
1:  
algorithm
 
TS(
v)

2:  
 
 
num(
v)
 
i++;

3:  
 
 
for
 
all 
vertices 
adjacent 
to 
v

4:  
 
 
 
 
if
 
num(
u)
 
== 
0

5:  
 
 
 
 
 
 
TS(
u)
;

6:  
 
 
 
 
else
 
if
 
TSNum(
u)
 
== 
0;

7:  
 
 
 
 
 
 
error 
cycle 
was 
detected;

8:  
 
 
TSNum(
v)
 
j++;

9:  

10: 
algorithm
 
topologicalSorting(
digraph 
g)

11: 
 
 
for
 
all 
vertices 
v

12: 
 
 
 
 
num(
v)
 
TSNum(
v)
 
0;

13: 
 
 
1;

14: 
 
 
while
 
there 
is 
vertex 
such 
that 
num(
v)
 
== 
0

15: 
 
 
 
 
TS(
v)
;

16: 
 
 
output 
vertices 
according 
to 
their 
TSNum;

TopoSortGraph
1:  
in 
topo:
 
num(
a)
 
is 
0

2:  
num(
a)
 
1

3:  
in 
ts:
 
num(
b)
 
is 
0

4:  
num(
b)
 
2

5:  
in 
ts:
 
num(
c)
 
is 
0

6:  
num(
c)
 
3

7:  
TSNum(
c)
 
1

8:  
in 
ts:
 
num(
d)
 
is 
0

9:  
num(
d)
 
4

10: 
TSNum(
d)
 
2

11: 
in 
ts:
 
num(
e)
 
is 
0

12: 
num(
e)
 
5

13: 
in 
ts:
 
num(
f)
 
is 
0

14: 
num(
f)
 
6

15: 
TSNum(
f)
 
3

16: 
TSNum(
e)
 
4

17: 
TSNum(
b)
 
5

18: 
TSNum(
a)
 
6

19: 
has 
ts_num:
 
1

20: 
has 
ts_num:
 
2

21: 
has 
ts_num:
 
3

22: 
has 
ts_num:
 
4

23: 
has 
ts_num:
 
5

24: 
has 
ts_num:
 
6