Introduction
In this tip,I want to demonstrate a way to find one allowed flow in any flow network with minimum and maximum capacities on each edge by reducing the problem to a maximum flow problem which can be solved by any maxflow algorithm (in this case Ford-Fulkerson).
Background
This project was created as a university project in a course covering basic and advanced algorithms and data structures. I hope the code will be useful to someone who is working on a similar problem.
Using the Code
1. Reading Flow Network from File
To understand the program flow, let's take a look at the Main function: At first, we create a new FlowNetwork by using the static CreateNetworkFromFile-method which projects the given flow network into the code. The input file contains one edge on every line and has the following format:
Node1Id Node2Id Min-Capacity Max-Capacity
These values are taken over into a List of Vertices, where a Vertex represents a single node and a list of edges which contain the Ids of the two connected nodes and their capacities. For further details on this process, take a look at the CreateNetworkFromFile-method.
2. Creating a Helper Network
To find a valid flow in our network, we have to first create a helper network without minimum capacities (min-cap. = 0 for all edges) so we can then use the Ford-Fulkerson algorithm to find its maximum flow. Once we found the maximum flow, we can easily read out a valid flow for the original network. (see point 4) To create this helper network, I created the function GetExpandedNetwork():
public FlowNetwork GetExpandedNetwork()
{
FlowNetwork g = new FlowNetwork(Edges.Select(item =>
(Edge)item.Clone()).ToList(), this.Vertices.Select(item =>
(Vertex)item.Clone()).ToList());
Dictionary<int, int> indiceTable = new Dictionary<int, int>();
foreach (Vertex v in Vertices)
{
int value = 0;
foreach (Edge e in g.Edges.Where(x => x.Vertex2 == v.Id))
{
value += e.MinCap;
}
foreach (Edge e in g.Edges.Where(x => x.Vertex1 == v.Id))
{
value -= e.MinCap;
}
indiceTable.Add(v.Id, value);
}
foreach (Edge e in g.Edges.Where(x => x.MinCap > 0))
{
e.MaxCap = e.MaxCap - e.MinCap;
e.MinCap = 0;
}
g.Source = 0;
g.Sink = g.Vertices.Count() + 1;
g.Vertices.Add(new Vertex(g.Source));
g.Vertices.Add(new Vertex(g.Sink));
foreach (var p in indiceTable.Where(x => x.Value != 0))
{
if (p.Value > 0)
{
g.Edges.Add(new Edge(g.Source, p.Key, 0, p.Value));
}
else if (p.Value < 0)
{
g.Edges.Add(new Edge(p.Key, g.Sink, 0, Math.Abs(p.Value)));
}
}
g.Edges.Add(new Edge(Sink, Source, 0, INFINITY));
return g;
}
For every node in our network, we calculate the difference between the minimum capacities of the edges pointing away from it and the edges pointing towards it. These values are saved in our indiceTable. For each edge in our helper network, we set its maximum capacity to the difference of its maximum-cap and its minimum-cap. The minimum capacity is set to 0 for all edges.
Additionally, I added a new source and sink as starting and end point of our maxflow algorithm.
Finally, we add edges from our new source and to our new sink (or no edge at all), depending on whether the corresponding value in our indiceTable is smaller than, greater than or equal to zero. I also added a edge from the original sink to the original source.
3. Finding the Maximum Flow of the Helper Network
To find the maximum flow in our helper network, I used an implementation of the Ford-Fulkerson-method. As this method (and others) are covered widely on the internet, I won't go into any details for this step. If you are interested in the used method, search for the Edmond-Karp algorithm or take a look at the code of the MaxFlow-class.
4. Finding our Valid Flow
To find our valid flow, we first set the minimum capacity of each edge as its default flow. In doing so, we make sure no edge can transport less units as restricted by its min-cap. property. Now all we have to do is add the flow values of the helper network (found in step 3) to the original network. All the helper edges we added in step 2 have to be ignored here as they don´t even exist in the original network.
For an illustration, take a look at the FindAllowedFlow(..) function:
public void FindAllowedFlow(List<edge> flowEdges)
{
foreach (Edge e in Edges)
{
e.Flow += e.MinCap;
foreach (Edge fe in flowEdges.Where(x => x.Vertex1 == e.Vertex1 && x.Vertex2 == e.Vertex2))
{
e.Flow += fe.Flow;
}
}
}
5. Complexity
The complexity of the program is given by the complexity of the maxflow algorithm as this step is usually the most complex one. As we are using the Edmond-Karp algorithm, we get a total complexity of O(|V| * |E|^2) where V is the amount of vertices and E is the amount of edges in our network.
Practically, this is a pretty good runtime behaviour. However, depending on the layout of the network, it might be useful to use another method to find the maxflow. For example, the push-relabel algorithm provides O(|V|^3) runtime, which is better if the amount of edges highly overweights the amount of vertices.
Alternatively, Dinics algorithm provides a runtime of O(|V|^2 * |E|) which is probably the best solution for most practical applications.
So feel free to replace the maxflow algorithm of step 3 with one of the above algorithms or any other one you prefer.
6. Getting the Code
To compile and run the project, simply extract the appended folder and open the .sln file in Visual Studio. Make sure to put the file "Data.txt" containing your network in the same directory as the executable (usually bin\Debug) or change the path to your own flow network.
Points of Interest
As a university project, I had a lot of fun writing this code (even so I am no expert in theoretical Computer Science:)). I hope you find this project useful! Feel free to leave any hints, critique or questions!
Thanks for reading. :)
