Peli's Farm - Pex, Stubs, Moles, QuickGraph, MbUnit, Reflector Addins - Maximum Flow in Network computation using QuickGraph

Tuesday, August 24, 2004

Maximum Flow in Network computation using QuickGraph

In this entry, I'll give a tutorial on using QuickGraph to compute the maximum flow of a capacitated network. I will start by giving some defnitions in order to make things clear, then I will apply the QuickGraph algorithms to a practical example.

Maximum Flows

Computing the maximum flow in a network is one of the classic graph theory problem (see [1]). Here's a prototype of flow network:

Imagine a pipeline network for transporting oil from a single source to a single sink. Each edge represents a section of pipeline, and the endpoints of the edge corresponds to the junctures at the ends of that section. The edge capacity is the maximum amount of oil that can flow through the corresponding section per unit time.

What is the maximum amount of oil per unit time that can flow through the network ? That question is a maximum flow problem.

A single-source single-sink network is a connected directed graph that has a distinguised vertex called the source with nonzero outdegree, and a distinguished vertex called sink with nonzero indegree. A single source-single sink network with source s and sink t (also called target) is called a s-t network. A capacitated network is a connected directed graph such that each edge e is assigned a nonnegative weight cap(e), called the capacity of edge e.

In the following, we shall consider a capacitated s-t network.

Sample network

I will illustrate the example on a 5-vertex capacitated network with source s and sink t as depicted below. This network is extracted from Chapter 12 of [1].

By convention, each edge is tagged with it's capacity (on the left) and, if computed, the flow. s is the source, t is the sink.

Building the sample network with QuickGraph

The first step of the tutorial is to create the sample network above using QuickGraph. To do so, we create a AdjacencyGraph and populate it "manually" with the vertices and edges:

using QuickGraph; // NamedVertex
using QuickGraph.Providers; // providers
using QuickGraph.Representations; // AdjacencyGraphg
using QuickGraph.Concepts; // IEdge

// the graph
AdjacencyGraph graph = new AdjacencyGraph(
    new NamedVertexProvider(),
    new EdgeProvider(),
    true);
// the capacity dictionary
EdgeDoubleDictionary capacities = new EdgeDoubleDictionary();

// adding vertices
NamedVertex s = (NamedVertex)graph.AddVertex(); s.Name = "s";
NamedVertex x = (NamedVertex)graph.AddVertex(); x.Name = "x";
NamedVertex v = (NamedVertex)graph.AddVertex(); v.Name = "v";
NamedVertex w = (NamedVertex)graph.AddVertex(); w.Name = "w";
NamedVertex t = (NamedVertex)graph.AddVertex(); t.Name = "t";

// adding edges
IEdge sx = graph.AddEdge(s, x); capacities[sx] = 5;
IEdge sv = graph.AddEdge(s, v); capacities[sv] = 7;
IEdge xv = graph.AddEdge(x, v); capacities[xv] = 3;
IEdge xw = graph.AddEdge(x, w); capacities[xw] = 7;
IEdge wv = graph.AddEdge(w, v); capacities[wv] = 5;
IEdge wt = graph.AddEdge(w, t); capacities[wt] = 4;
IEdge vt = graph.AddEdge(v, t); capacities[vt] = 6;

Once the graph is built, you can easily draw it using GraphvizAlgorithm. This topic has already been discribed in previous posts so I won't enter into the details .

Preparing the network for the Maximum Flow

In order to work properly, the maximum flow algorithms require that for each edge (u,v) in the network, there exists a reversed edge (v,u). Moreover, a dictionary associating each edge to its reversed must be provided. The sample network obviously does not fullfill this requirement. Therefore, we must add "articifial" reversed edge that have capacity equal to zero. In order to help you with this (tedious) task, QuickGraph provides the ReversedEdgeAugmentorAlgorithm algorithm that will do the job for you:

using QuickGraph.Algorithms.MaximumFlow;

// creating the augmentor
ReversedEdgeAugmentorAlgorithm reversedEdgeAugmentor = new ReversedEdgeAugmentorAlgorithm(this.graph);
// attaching handler to the ReversedEdgeAdded event
// this event is triggered on each "artifical" edge added to the graph
ReversedEdgeAugmentorAlgorithm reversedEdgeAugmentor.ReversedEdgeAdded += new EdgeEventHandler(reversedEdgeAugmentor_ReversedEdgeAdded);

// add the articifial edges
reversedEdgeAugmentor.AddReversedEdges();
...
// cleans up
reversedEdgeAugmentor.RemoveReversedEdges();

// this handler sets the capacity of the new edge to zero
void reversedEdgeAugmentor_ReversedEdgeAdded(Object sender, EdgeEventArgs e)
{
    capacities[e.Edge] = 0;
}

The method AddReversedEdges augments the graph with the reversed edges, while the RemoveReversedEdges "cleans up the mess". If we draw the flow graph after the AddReversedEdges call, it gives the following results (where the reversed edges are dashed):

Computing the MaximumFlow

QuickGraph implements 2 maximum flow algorithms: Edmund Karp and Push Relabel. We will use PushRelabel as it is more efficient, however, both inherit from the abstract base class MaximumFlowAlgorithm. The method Compute computes the maximum flow and returns it's value:

MaximumFlowAlgorithm algo = new PushRelabelMaximumFlowAlgorithm(
    graph,
    capacities,
    reversedEdgeAugmentor.ReversedEdges
    );

double value = algo.Compute(s, t);

After cleaning up the reversed edges, we can draw the graph with the maximum flow in each edge. Note that for this sample, the maxium flow value is 10.