# Software Programming

Kunuk Nykjaer

## Graph flow Ford Fulkerson algorithm example with C#

Graph flow with Ford Fulkerson algorithm, source code in C#

FordFulkerson.cs

```using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace GraphFlowExample
{
/// <summary>
/// Author: Kunuk Nykjaer
/// </summary>
public class FordFulkerson
{
static Dictionary<int, Node> Nodes { get; set; }
static Dictionary<string, Edge> Edges { get; set; }
private const float MaxValue = float.MaxValue;

public FordFulkerson()
{
Nodes = new Dictionary<int, Node>();
Edges = new Dictionary<string, Edge>();
}

public static void Main(string[] args)
{
new FordFulkerson().Run();
PrintLn("Press key to exit ...");
}

void ParseData()
{
Reset();

/**
* Example graph reference
* http://www.cs.princeton.edu/%7Ewayne/kleinberg-tardos/07demo-maxflow.ppt
*
* Put your graph info here
*/
var names = new[] { "dummy", "s", "2", "3", "4", "5", "t" };
foreach (Node node in names.Select(name => new Node() { Name = name }))

var edges = new[]
{ "1 2 10", "1 3 10", "2 5 8", "2 3 2", "2 4 4", "3 5 9", "4 6 10", "5 4 6", "5 6 10" };

foreach (var edge in edges)
{
string[] s = edge.Split(' ');

Node node1 = Nodes[int.Parse(s[0])];
Node node2 = Nodes[int.Parse(s[1])];
float capacity = float.Parse(s[2]);

AddEdge(node2, node1, 0f); // residual, if undirected graph, set value as capacity
}
}

public void Run()
{
ParseData();
Algo();
}

void Algo()
{
var nodeSource = Nodes[1];
var nodeTerminal = Nodes[Nodes.Count - 1];

PrintNodes();

FordFulkersonAlgo(nodeSource, nodeTerminal);
}

void FordFulkersonAlgo(Node nodeSource, Node nodeTerminal)
{
PrintLn("\n** FordFulkerson");
var flow = 0f;

var path = Bfs(nodeSource, nodeTerminal);

while (path != null && path.Count > 0)
{
var minCapacity = MaxValue;
foreach (var edge in path)
{
if (edge.Capacity < minCapacity)
minCapacity = edge.Capacity; // update
}

if (minCapacity == MaxValue || minCapacity < 0)
throw new Exception("minCapacity " + minCapacity);

AugmentPath(path, minCapacity);
flow += minCapacity;

path = Bfs(nodeSource, nodeTerminal);
}

// max flow
PrintLn("\n** Max flow = " + flow);

// min cut
PrintLn("\n** Min cut");
FindMinCut(nodeSource);
}

static void AugmentPath(IEnumerable<Edge> path, float minCapacity)
{
foreach (var edge in path)
{
var keyResidual = GetKey(edge.NodeTo.Id, edge.NodeFrom.Id);
var edgeResidual = Edges[keyResidual];

edge.Capacity -= minCapacity;
edgeResidual.Capacity += minCapacity;
}
}

// similar to bfs
void FindMinCut(Node root)
{
var queue = new Queue<Node>();
var discovered = new HashSet<Node>();
var minCutNodes = new List<Node>();
var minCutEdges = new List<Edge>();
queue.Enqueue(root);

while (queue.Count > 0)
{
var current = queue.Dequeue();
if (discovered.Contains(current))
continue;

var edges = current.NodeEdges;
foreach (var edge in edges)
{
var next = edge.NodeTo;
if (edge.Capacity <= 0 || discovered.Contains(next))
continue;
queue.Enqueue(next);
}
}

// bottleneck as a list of arcs
var minCutResult = new List<Edge>();
List<int> nodeIds = minCutNodes.Select(node => node.Id).ToList();

var nodeKeys = new HashSet<int>();
foreach (var node in minCutNodes)

var edgeKeys = new HashSet<string>();
foreach (var edge in minCutEdges)

ParseData(); // reset the graph

// finding by comparing residual and original graph

foreach (var id in nodeIds)
{
var node = Nodes[id];
var edges = node.NodeEdges;
foreach (var edge in edges)
{
if (nodeKeys.Contains(edge.NodeTo.Id))
continue;

if (edge.Capacity > 0 && !edgeKeys.Contains(edge.Name))
}
}

float maxflow = 0;
foreach (var edge in minCutResult)
{
maxflow += edge.Capacity;
PrintLn(edge.Info());
}
PrintLn("min-cut total maxflow = " + maxflow);
}

/*
Customized for network flow, capacity

Wikipedia
1. Enqueue the root node.
2. Dequeue a node and examine it.
* If the element sought is found in this node, quit the search and return a result.
* Otherwise enqueue any successors (the direct child nodes) that haven't been seen.
3. If the queue is empty, every node on the graph has been examined
4. Repeat from Step 2.
*/
List<Edge> Bfs(Node root, Node target)
{
root.TraverseParent = null;
target.TraverseParent = null; //reset

var queue = new Queue<Node>();
var discovered = new HashSet<Node>();
queue.Enqueue(root);

while (queue.Count > 0)
{
Node current = queue.Dequeue();

if (current.Id == target.Id)
return GetPath(current);

var nodeEdges = current.NodeEdges;
foreach (var edge in nodeEdges)
{
var next = edge.NodeTo;
var c = GetCapacity(current, next);
if (c > 0 && !discovered.Contains(next))
{
next.TraverseParent = current;
queue.Enqueue(next);
}
}
}
return null;
}

static List<Edge> GetPath(Node node)
{
var path = new List<Edge>();
var current = node;
while (current.TraverseParent != null)
{
var key = GetKey(current.TraverseParent.Id, current.Id);
var edge = Edges[key];
current = current.TraverseParent;
}
return path;
}

public static string GetKey(int id1, int id2)
{
return id1 + "|" + id2;
}

public float GetCapacity(Node node1, Node node2)
{
var edge = Edges[GetKey(node1.Id, node2.Id)];
return edge.Capacity;
}

public void AddEdge(Node nodeFrom, Node nodeTo, float capacity)
{
var key = GetKey(nodeFrom.Id, nodeTo.Id);
var edge = new Edge() { NodeFrom = nodeFrom, NodeTo = nodeTo, Capacity = capacity, Name = key };
}

static void PrintNodes()
{
for (int i = 0; i < Nodes.Count; i++)
{
var node = Nodes[i];
PrintLn(node.ToString() + " outnodes=" + node.GetInfo());
}
}

static void Reset()
{
Nodes.Clear();
Edges.Clear();
Node.ResetCounter();
}

public class Node
{
private static int _counter;
public string Name { get; set; }
public List<Edge> NodeEdges { get; set; }
public Node TraverseParent { get; set; }

public Node()
{
Id = _counter++;
NodeEdges = new List<Edge>();
}

public static void ResetCounter()
{
_counter = 0;
}

public string GetInfo()
{
var sb = new StringBuilder();
foreach (var edge in NodeEdges)
{
var node = edge.NodeTo;
if (edge.Capacity > 0)
sb.Append(node.Name + "C" + edge.Capacity + " ");
}
return sb.ToString();
}

public override string ToString()
{
return string.Format("Id={0}, Name={1}", Id, Name);
}
}
public class Edge
{
public Node NodeFrom { get; set; }
public Node NodeTo { get; set; }
public float Capacity { get; set; }
public string Name { get; set; }

public override string ToString()
{
return
string.Format("NodeFrom={0}, NodeTo={1}, C={2}",NodeFrom.Name,NodeTo.Name,Capacity);
}

public string Info()
{
return string.Format("NodeFrom=({0}), NodeTo=({1}), C={2}", NodeFrom, NodeTo, Capacity);
}
}

public static void PrintLn(object o) { Console.WriteLine(o); } //alias
public static void PrintLn() { Console.WriteLine(); } //alias
public static void Print(object o) { Console.Write(o); } //alias
}
}
```

Result:

Id=0, Name=dummy outnodes=
Id=1, Name=s outnodes=2C10 3C10
Id=2, Name=2 outnodes=5C8 3C2 4C4
Id=3, Name=3 outnodes=5C9
Id=4, Name=4 outnodes=tC10
Id=5, Name=5 outnodes=4C6 tC10
Id=6, Name=t outnodes=

** FordFulkerson

** Max flow = 19

** Min cut
NodeFrom=(Id=1, Name=s), NodeTo=(Id=2, Name=2), C=10
NodeFrom=(Id=3, Name=3), NodeTo=(Id=5, Name=5), C=9
min-cut total maxflow = 19

Written by kunuk Nykjaer

November 9, 2010 at 10:34 pm