question on use of EdmondsKarpMaximumFlowAlgorithm

Topics: algorithm
Jun 15, 2009 at 7:48 PM

I am trying to use the EdmondsKarpMaximumFlowAlgorithm object but am unsure what I am supposed to pass in for the third constructor parameter of type System.Collections.Generic.Dictionary<TEdge,TEdge>.  If I pass an empty dictionary I get a KeyNotFoundException.  What am I supposed to fill the Dictionary with?

 

Is there a usage example?

 

Thanks!

Aug 28, 2009 at 3:01 PM
Edited Aug 28, 2009 at 3:12 PM

Hi,  a simple way to create your third argument is to used the ReversedEdgeAugmentorAlgorithm. here is a simple full example of how to use a maximum flow algorith:

static Edge<string> MyEdgeFactory(string source, string target)
{
 return new Edge<string>(source, target);
}

static double ComputeCapacity(Edge<string> curEdge)
{
 if (edgeCapacitiesDictionary.ContainsKey(curEdge) == true)
  return edgeCapacitiesDictionary[curEdge];
 else
  return 0; //you may want to put unused reversed edge to 0
}

static public Dictionary<Edge<string>, double> edgeCapacitiesDictionary = new Dictionary<Edge<string>, double>();
static void Main(string[] args)
{
////////////////////////////////////////
// test maximum flow algorith
//////////////////////////////////////////
var g = new AdjacencyGraph<string, Edge<string>>(true);
string source = "A";
string sink = "G";

//Vertices
//////////////
g.AddVertex("A");g.AddVertex("B");g.AddVertex("C");g.AddVertex("D");
g.AddVertex("E");g.AddVertex("F");g.AddVertex("G");

//Edge
////////////
var edgesList = new List<Edge<string>>();
var ad = new Edge<string>("A", "D"); g.AddEdge(ad); edgeCapacitiesDictionary.Add(ad, 3);
var ab = new Edge<string>("A", "B"); g.AddEdge(ab); edgeCapacitiesDictionary.Add(ab, 3);
var bc = new Edge<string>("B", "C"); g.AddEdge(bc); edgeCapacitiesDictionary.Add(bc, 4);
var ca = new Edge<string>("C", "A"); g.AddEdge(ca); edgeCapacitiesDictionary.Add(ca, 3);
var cd = new Edge<string>("C", "D"); g.AddEdge(cd); edgeCapacitiesDictionary.Add(cd, 1);
var de = new Edge<string>("D", "E"); g.AddEdge(de); edgeCapacitiesDictionary.Add(de, 2);
var df = new Edge<string>("D", "F"); g.AddEdge(df); edgeCapacitiesDictionary.Add(df, 6);
var eb = new Edge<string>("E", "B"); g.AddEdge(eb); edgeCapacitiesDictionary.Add(eb, 1);
var ce = new Edge<string>("C", "E"); g.AddEdge(ce); edgeCapacitiesDictionary.Add(ce, 2);
var eg = new Edge<string>("E", "G"); g.AddEdge(eg); edgeCapacitiesDictionary.Add(eg, 1);
var fg = new Edge<string>("F", "G"); g.AddEdge(fg); edgeCapacitiesDictionary.Add(fg, 9);

/////////////////////////////////////
// creating the augmentor
////////////////////////////////////
var reversedEdgeAugmentor = new ReversedEdgeAugmentorAlgorithm<string, Edge<string>>(g, MyEdgeFactory);
reversedEdgeAugmentor.AddReversedEdges();

// (other option)                                                                           new PushRelabelMaximumFlowAlgorithm
MaximumFlowAlgorithm<string, Edge<string>> algo = new EdmondsKarpMaximumFlowAlgorithm<string, Edge<string>>(g, /*e => 2*/ComputeCapacity, reversedEdgeAugmentor.ReversedEdges);

algo.Compute(source,sink);

Console.WriteLine("MaxFlow: {0}", algo.MaxFlow);

Console.WriteLine("Press <ENTER> to complete");
Console.ReadLine();

}

note: i have use the graph describe at http://en.wikipedia.org/wiki/Edmonds-Karp_algorithm#Example

have a nice day

 

Coordinator
Aug 28, 2009 at 8:14 PM

or simpler:

TryFunc<string, Edge<string>> flowPredecessors;
double flow = g.MaximumFlowEdmondsKarp(
    ComputeCapacity, 
    source, sink, 
    out flowPredecessors);

Also, in this case, you should use SEdge<string> instead of Edge<string>.