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?



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];
  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";


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);

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


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

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


note: i have use the graph describe at

have a nice day


Aug 28, 2009 at 8:14 PM

or simpler:

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

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