14: graphs #3

Maximum Flows | Maximum Matching | Graph Clustering

Maximum Flows

A network is a type of graph that can be used to represent water flow through pipes (or maybe packets through cat5e cables).
MaximumFlows

A network has one vertex (source) with no incoming edges and one vertex (sink) with no outgoing edges. Each edge has a capacity associated with it.

A flow is a real function that assigns a number to each edge of the network that meets these two conditions:
  1. The flow through an edge cannot be greater than it's capacity
  2. The total flow coming to a vertex is the same as the total flow coming out of it
The problem we are trying to solve is to find a flow function so that the summation of the flow at each edge is maximized.

A cut separating s and t is as follows:
  • X = {s, a}
  • X_bar = {b, c, d, t}
  • The cut = {(a,b), (s,c), (s,d)}
In any network, the maximal flow from s to t is equal to the minimal capacity of any cut.

1:  
algorithm
 
findPath(
node 
source, 
node 
sink, 
path)

2:  
 
 
if
(
source 
== 
sink)

3:  
 
 
 
 
return
 
path;

4:  
 
 
foreach 
edge 
in 
source.edges

5:  
 
 
 
 
residual 
edge.capacity 
edge.flow;

6:  
 
 
 
 
if
 
residual 
and 
edge 
is 
not 
in 
path

7:  
 
 
 
 
 
 
new_path 
findPath(
edge.target, 
sink, 
path 
edge)
;

8:  
 
 
 
 
 
 
if
 
new_path 
is 
not 
EMPTY_PATH

9:  
 
 
 
 
 
 
 
 
return
 
new_path;

10: 
 
 
foreach 
edge 
in 
edges 
pointing 
to 
source 
(
reverse 
edge)

11: 
 
 
 
 
flow 
forward 
edge 
flow

12: 
 
 
 
 
if
 
flow 
and 
edge 
is 
not 
in 
path

13: 
 
 
 
 
 
 
new_path 
findPath(
edge.target, 
sink, 
path 
edge)
;

14: 
 
 
 
 
 
 
if
 
new_path 
is 
not 
EMPTY_PATH

15: 
 
 
 
 
 
 
 
 
return
 
new_path;

16: 
 
 
print 
"backtracking at: "
 
source;

17: 
 
 
return
 
EMPTY_PATH;

18: 

19: 
algorithm
 
fordFulkerson(
digraph 
g, 
node 
source, 
node 
sink)

20: 
 
 
path 
findPath(
g, 
source, 
sink, 
NULL)
;

21: 
 
 
printPath(
path)
;

22: 
 
 
while
 
path 
!= 
EMPTY_PATH

23: 
 
 
 
 
foward_flow 
min 
of 
all 
residuals 
for
 
each 
forward 
edge 
in 
path

24: 
 
 
 
 
reverse_flow 
min 
of 
all 
forwards 
flows 
for
 
each 
reverse 
edge 
in 
path

25: 
 
 
 
 
min_flow 
min(
forward_flow, 
reverse_flow)
;

26: 
 
 
 
 

27: 
 
 
 
 
//augment path

28: 
 
 
 
 
foreach 
edge 
in 
path

29: 
 
 
 
 
 
 
if
 
edge 
is 
forward

30: 
 
 
 
 
 
 
 
 
edge.flow 
+= 
min_flow;

31: 
 
 
 
 
 
 
if
 
edge 
is 
reverse

32: 
 
 
 
 
 
 
 
 
fedge 
find 
foward 
edge 
for
 
edge

33: 
 
 
 
 
 
 
 
 
fedge.flow 
-= 
min_flow;
 

34: 
 
 
 
 
path 
findPath(
g, 
source, 
sink, 
NULL)
;

35: 
 
 
 
 
printPath(
path)
;

36: 
 
 
return
 
the 
sum 
of 
edge.flow 
forall 
the 
edges 
in 
source.edges

  1. Start:
    MaxFlow
  2. End:
    MaxFlow

Time Complexity

  • The algorithm is never guarenteed to terminate, but if it does:
  • O(Ef) - E is the number of edges, f is the max flow value
  • Each edge gets incremented a flow value by at least 1 each time until the max is reached
The algorithm may not be able to complete if there are irrational flow values.

Backward Edges

  1. Start:
    MaxFlowsFixed
  2. Follow forward edges:
    MaxFlowsFixed
  3. Follow backward edge:
    MaxFlowsFixed

Maximum Matching

1:  
algorithm
 
findMaximumMatching(
bipartite 
graph)
{

2:  
 
 
for
(
all 
unmatched 
vertices 
v)
{

3:  
 
 
 
 
set 
level 
of 
all 
vertices 
to 
0;

4:  
 
 
 
 
set 
parent 
of 
all 
vertices 
to 
null;

5:  
 
 
 
 
level(
v)
 
1;

6:  
 
 
 
 
last 
null;

7:  
 
 
 
 
clear 
queue;

8:  
 
 
 
 
enqueue(
v)
;

9:  
 
 
 
 
while
(
queue 
is 
not 
empty 
and 
last 
is 
null)
{

10: 
 
 
 
 
 
 
dequeue(
)
;

11: 
 
 
 
 
 
 
if
(
level(
v)
 
is 
an 
odd 
number)
{

12: 
 
 
 
 
 
 
 
 
for
(
all 
vertices 
adjacent 
to 
such 
that 
level(
u)
 
is 
0)
{

13: 
 
 
 
 
 
 
 
 
 
 
if
(
is 
unmatched)
{

14: 
 
 
 
 
 
 
 
 
 
 
 
 
parent(
u)
 
v;

15: 
 
 
 
 
 
 
 
 
 
 
 
 
last 
u;

16: 
 
 
 
 
 
 
 
 
 
 
 
 
break
;

17: 
 
 
 
 
 
 
 
 
 
 
}
 
else
 
if
(
is 
matched 
but 
not 
with 
v)
{

18: 
 
 
 
 
 
 
 
 
 
 
 
 
parent(
u)
 
v;

19: 
 
 
 
 
 
 
 
 
 
 
 
 
level(
u)
 
level(
v)
 
1;

20: 
 
 
 
 
 
 
 
 
 
 
 
 
enqueue(
u)
;

21: 
 
 
 
 
 
 
 
 
 
 
}
 

22: 
 
 
 
 
 
 
 
 
}

23: 
 
 
 
 
 
 
}
 
else
 
{
 
//if level(v) is an even number

24: 
 
 
 
 
 
 
 
 
enqueue(
vertex 
matched 
with 
v)
;

25: 
 
 
 
 
 
 
 
 
parent(
u)
 
v;

26: 
 
 
 
 
 
 
 
 
level(
u)
 
level(
v)
 
1;

27: 
 
 
 
 
 
 
}

28: 
 
 
 
 
}

29: 
 
 
 
 
if
(
last 
is 
not 
null)
{
 
//augment matching by updating the augmenting path;

30: 
 
 
 
 
 
 
for
(
last;
 
is 
not 
null;
 
parent(
parent(
u)
)
)
{

31: 
 
 
 
 
 
 
 
 
matchedWith(
u)
 
parent(
u)
;

32: 
 
 
 
 
 
 
 
 
matchedWith(
parent(
u)
)
 
u;

33: 
 
 
 
 
 
 
}

34: 
 
 
 
 
}

35: 
 
 
}

36: 
}

MaximumMatching

MaximumMatching

Steps of the algorithm:
v level u matching queue path
a 1 d d is unmatched. d a empty [d a]
b 1 c c is unmatched. c b empty [c b]
e 1 j j is unmatched. j e empty [j e]
f 1 b b is matched but not with f [b] [b f]
f 1 c c is matched but not with f [b c] [b f] [c f]
b 2   match = c. parent[c] = b [c c] [c b f]
c 3 a a is matched but not with c [c a] [a c b f]
c 3 b level[b] != 0 [c a] [a c b f]
c 3 f level[f] != 0 [c a] [a c b f]
c 3 g g is unmatched. g c. b f. [c a] [a c b f] [g c b f]
h 1 g g is matched but not with v [g] [g h]
h 1 j j is matched but not with h [g j] [j h] [g h]
h 1 i i is unmatched. i h [g j] [j h] [i h] [g h]

K-Core Graph Clustering

1:  
algorithm
 
kcoreCreation(
Graph 
g)

2:  
 
 
compute 
the 
degrees 
of 
vertices

3:  
 
 
sort 
vertices 
in 
increasing 
order 
by 
degrees

4:  
 
 
foreach(
vertex 
in 
in 
order)

5:  
 
 
 
 
core[
v]
 
:
degree[
v]
;

6:  
 
 
 
 
foreach(
in 
neighbors(
v)
)

7:  
 
 
 
 
 
 
if
(
degree[
u]
 
degree[
v]
)

8:  
 
 
 
 
 
 
 
 
degree[
u]
 
:
degree[
u]
 
1;

9:  
 
 
 
 
 
 
 
 
reorder 
accordingly

KCoreAssign

Node Degree K Number Node Degree K Number
A 1 1 I 4 3
B 1 1 J 3 3
C 4 2 K 3 3
D 3 3 L 5 3
E 5 3 M 4 2
F 3 3 N 2 2
G 3 3 O 1 1
H 6 3
1:  
algorithm
 
kcoreCluster(
Graph 
g)

2:  
 
 
:
V;

3:  
 
 
foreach(
vertex 
in 
V)
{

4:  
 
 
 
 
p[
v]
 
:
degree(
v)
;

5:  
 
 
}

6:  
 
 
build_min_heap(
v, 
p)
;

7:  
 
 
while
(
heap.size(
)
 
>
 
0)
{

8:  
 
 
 
 
:
C\{
top}
 
 
//remove top from C

9:  
 
 
 
 
core[
top]
 
:
p[
top]
;

10: 
 
 
 
 
foreach(
vertex 
in 
neighbors(
top, 
C)
{

11: 
 
 
 
 
 
 
p[
v]
 
:
max(
p[
top]
p(
v, 
N(
v, 
C)
)
)
;

12: 
 
 
 
 
 
 
update_heap(
v, 
p)

13: 
 
 
 
 
}
 
 

14: 
 
 
}

k_core
(image from [7])

Time complexity:
  1. O(m): cores decomposition
  2. O(m * max(deg, lgn)): finding cores
m: number of edges.
deg: maximum degree.
n: number of vertices.

References

  1. http://en.wikipedia.org/wiki/Ford-Fulkerson
  2. http://en.wikipedia.org/wiki/Traveling_salesman_problem
  3. http://en.wikipedia.org/wiki/NP_%28complexity%29
  4. http://en.wikipedia.org/wiki/Polynomial_time#Polynomial_time
  5. http://en.wikipedia.org/wiki/NP-hard
  6. http://en.wikipedia.org/wiki/P_%3D_NP_problem
  7. Fast algorithms for determining (generalized) core groups in social networks, Vladimir Batagelj, Matjaž Zaveršnik. Discussions with Mubarek Kedir Mohammed
  8. Cormen, Leiserson, Rivest, Stein, "Introduction to Algorithms", Second Edition. pages 966 -1021