The meet in middle method for maximum flow calculation
Given the problem to compute the maximum flow between a source and a
destination in a graph, one could use the Ford Fulkerson method with
Edmonds and Karp breadth-first-scanning in O(VE^2). Imagining that we
are computing the flow between 2 cities in the world, say Bucharest
and Bruxelles, the shortest ways are added first to the flow, then a
storm of long ways arises even overseas through America or Asia, that
contribute to the maximum flow.
It's rather inefficient to compute the flow this way at a global
scale, instead, think of extending ways in the same time from the
source to the destination and from the destination to the source and
when the ways meet in middle we've found an augmenting path (an
ameliorating way), then the process continues in the current step with
all the ways that meet somewhere "in the middle". After the first full
step, when there are no more ways to link paths into gains, another
step is required on the modified graph after augmenting till no gains
are available in a step. At this point we've found the maximum flow.
So instead of going one way at a time, we do one move expanding the
source (towards the destination) and another move expanding the
destination (towards the source), at step k we have in the source/
destination nodes queue all the cities on a path of length k from
source/destination. When the 2 ways meet in middle, we've found an
amelioration and we use it. One step of the algorithm stops when there
are no more gains joining paths. When this happens, another full step
is required and when there's not even the slightest gain in one step,
the algorithm finishes and the maximum flow is found.
Think as all the cars leaving from Bruxelles to Bucharest and vice
versa chaotic in the same time via any direction and when they meet
somewhere "in the middle" (but also could be overseas), they return to
where they came from with some maximal gain equal to the minimum edge
of the path from source to dest.
The number of full steps required to find the maximum flow in a graph,
depends on the graph, an average of 2-3 full steps required it's
observed, but there are also cases when that number increases. It runs
much faster than standard Ford Fulkerson.
Determining by formula what's the average number of big steps or the
overall complexity of the algorithm is a bit strange, but it is
obviously better than standard one way at a time Ford Fulkerson -
Edmonds Karp algorithm.
Here's some C# source code for this:
using System;
using System.Collections.Generic;
using System.Text;
namespace AdvancedTree
{
class clsMaxFlow
{
const int MAX_N = 1000;
const int INF = 1000 * 1000 * 1000;
int[,] C = new int[MAX_N, MAX_N];
int[,] F = new int[MAX_N, MAX_N];
int N, S, T;
public clsMaxFlow()
{
N = MAX_N;
S = 0;
T = MAX_N - 1;
Random R = new Random(10);
for (int I = N; --I >= 0; )
for (int J = N; --J >= 0; )
C[I, J] = R.Next(10000);
}
//-----------------------------------------------------------------------------------------------------------------------------
public int MAX_FLOW_Ford_Fulkerson_Edmonds_Karp()
{
Queue<int> Q = new Queue<int>(N);
int[] flow = new int[N]; //max flow till this
point...
int[] back = new int[N]; //where the flow comes
from (previous
point on path)...
for (int I = N; --I >= 0; )
for (int J = N; --J >= 0; )
F[I, J] = 0;
int res = 0;
do {
for (int I = N; --I >= 0; flow[I] = -1, back[I]
= -1) ;
flow[S] = INF; //Flow from source to source is
infinite
Q.Clear();
Q.Enqueue(S); //Start from source only.
while (Q.Count > 0) {
int I = Q.Dequeue();
for (int J = N; --J >= 0; ) {
int fl = Math.Min(flow[I], C[I,
J] - F[I, J]);
//we can reach point J with a
flow of fl
if (fl > 0) {
if (flow[J] < 0)
//if J is unseen
Q.Enqueue(J);
//we add it to queue.
if (fl > flow[J]) {
//if we got a
bigger flow to J than previously,
//we update the
max flow to point J.
flow[J] = fl;
back[J] = I;
//I was processed before J so no cycle can
occur...
}
}
}
}
int Cf = flow[T];
if (Cf <= 0) //if no flow at all to
destination then quit, we're
done.
break;
res += Cf;
for (int J = T, I; (I = back[J]) >= 0; J = I) {
F[I, J] += Cf;
F[J, I] -= Cf;
} //update the residual network, aquiring
current flow.
} while (true);
for (int I = N; --I >= 0; )
for (int J = N; --J >= 0; )
if (F[I, J] > C[I, J])
throw new Exception("Error: The
flow is bigger than graph
capacity...");
return res;
}
//-----------------------------------------------------------------------------------------------------------------------------
private int flow_pass_thru(int[] back)
{ //run-time: O(V) -> double pass...
int flow = INF;
for (int I = T; I != S; ) {
int K = back[I];
flow = Math.Min(flow, C[K, I] - F[K, I]);
I = K;
} //step 1: get the max flow from source to dest
in the given path
for (int I = T; I != S; ) {
int K = back[I];
F[K, I] += flow;
F[I, K] -= flow;
I = K;
} //Aquire the flow.
return flow;
}
public int MAX_FLOW_Meet_in_Destination()
{
Queue<int> Q = new Queue<int>(N);
int[] seen = new int[N]; // (0 = unseen), (1 =
seen), (-1 =
destination)
int[] back = new int[N]; //previous point on
path...
for (int I = N; --I >= 0; )
for (int J = N; --J >= 0; )
F[I, J] = 0;
int res = 0;
do {
for (int I = N; --I >= 0; seen[I] = 0, back[I]
= -1) ;
Q.Clear();
Q.Enqueue(S); //Start from source only.
seen[S] = 1; //consider source is seen
seen[T] = -1;
int flow = 0;
while (Q.Count > 0) {
int I = Q.Dequeue();
for (int J = N; --J >= 0; )
if (seen[J] <= 0 && C[I, J] >
F[I, J])
if (seen[J] == 0) {
//marked from end
Q.Enqueue(J);
seen[J] = 1;
back[J] = I;
} else {
//We reached
the destination (seen[J] < 0)
back[J] = I;
flow +=
flow_pass_thru(back);
}
}
if (flow <= 0)
break;
res += flow;
} while (true);
for (int I = N; --I >= 0; )
for (int J = N; --J >= 0; )
if (F[I, J] > C[I, J])
throw new Exception("Error: The
flow is bigger than graph
capacity...");
return res;
}
//-----------------------------------------------------------------------------------------------------------------------------
private int flow_pass_thru(int _I, int _J, int[] back)
{ //run-time: O(V) -> double pass...
int
I = _I,
J = _J,
flow = C[I, J] - F[I, J];
while (I != S) {
int K = back[I];
flow = Math.Min(flow, C[K, I] - F[K, I]);
I = K;
} //flow = maximum from I to source
while (J != T) {
int K = back[J];
flow = Math.Min(flow, C[J, K] - F[J, K]);
J = K;
} //flow = maximum also from J to destination
I = _I;
J = _J;
F[I, J] += flow;
F[J, I] -= flow;
while (I != S) {
int K = back[I];
F[K, I] += flow;
F[I, K] -= flow;
I = K;
} //Aquire flow one way (to source).
while (J != T) {
int K = back[J];
F[J, K] += flow;
F[K, J] -= flow;
J = K;
} //Aquire flow the other way (to destination).
return flow;
}
public int MAX_FLOW_Meet_in_Middle()
{
Queue<int> Q = new Queue<int>(N);
int[] seen = new int[N]; //(0 = unseen) (1 =
seen from source) (-1
= seen from destination)
int[] back = new int[N]; //back point...
for (int I = N; --I >= 0; )
for (int J = N; --J >= 0; )
F[I, J] = 0;
int
res = 0,
flow;
do {
for (int I = N; --I >= 0; seen[I] = 0, back[I]
= -1) ;
Q.Clear();
Q.Enqueue(S);
Q.Enqueue(T); //Start from source and
destination in alternating
moves.
seen[S] = 1;
seen[T] = -1;
flow = 0;
while (Q.Count > 0) {
int I = Q.Dequeue();
if (seen[I] > 0) { //if we're from
source
for (int J = N; --J >= 0; )
if (seen[J] <= 0 &&
C[I, J] > F[I, J])
if (seen[J] ==
0) {
//if
this node is unseen,
//we
add it to queue, we saw it from source
Q.Enqueue(J);
seen[J]
= 1;
back[J]
= I;
} else {
//otherwise we've found a path connecting source and
//dest.
flow +=
flow_pass_thru(I, J, back);
//we
aquire it.
}
} else { //else we're from dest
int J = I;
for (I = N; --I >= 0; )
if (seen[I] >= 0 &&
C[I, J] > F[I, J])
if (seen[I] ==
0) {
//if
this node is unseen,
//we
add it to queue, we saw it from dest
Q.Enqueue(I);
seen[I]
= -1;
back[I]
= J;
} else {
//otherwise we've found a path connecting dest and
//source.
flow +=
flow_pass_thru(I, J, back);
//we
aquire it also.
}
}
}
res += flow;
} while (flow > 0);
for (int I = N; --I >= 0; )
for (int J = N; --J >= 0; )
if (F[I, J] > C[I, J])
throw new Exception("Error: The
flow is bigger than graph
capacity...");
return res;
}
//-----------------------------------------------------------------------------------------------------------------------------
}
}
//We can use a sorted list of edged or a hash(I, J) giving the flow
from I to J in O(1) to speed the calculations, but that's data //
structure dependent.
A small timing experiment:
clsMaxFlow F = new clsMaxFlow();
Stopwatch sw = new Stopwatch();
int flow;
string S = "";
sw.Reset(); sw.Start();
flow = F.MAX_FLOW_Ford_Fulkerson_Edmonds_Karp();
sw.Stop();
S += "MAX_FLOW_Ford_Fulkerson_Edmonds_Karp: " +
flow.ToString("N")
+ " " + sw.ElapsedMilliseconds + "ms\n";
sw.Reset(); sw.Start();
flow = F.MAX_FLOW_Meet_in_Destination();
sw.Stop();
S += "MAX_FLOW_Meet_in_Destination: " +
flow.ToString("N") + " "
+ sw.ElapsedMilliseconds + "ms\n";
sw.Reset(); sw.Start();
flow = F.MAX_FLOW_Meet_in_Middle();
sw.Stop();
S += "MAX_FLOW_Meet_in_Middle: " + flow.ToString("N")
+ " " +
sw.ElapsedMilliseconds + "ms\n";
MessageBox.Show(S);
TEST RESULTS:
MAX_FLOW_Ford_Fulkerson_Edmonds_Karp: 5,038,169.00 43042ms
MAX_FLOW_Meet_in_Destination: 5,038,169.00 1527ms
MAX_FLOW_Meet_in_Middle: 5,038,169.00 104ms
Hope you find this post useful.
Badita Robert - Romania
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
