15,114,611 members
Articles / Web Development / HTML
Tip/Trick
Posted 7 Jan 2014

15.9K views
6 bookmarked

# Finding a Valid Flow in a Flow Network with Minimum and Maximum Capacities

Rate me:
Finding a valid flow in a flow network with minimum and maximum capacities

## 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()`:

C#
```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;
}

}

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;

foreach (var p in indiceTable.Where(x => x.Value != 0))
{
if (p.Value > 0)
{
}
else if (p.Value < 0)
{
}
}
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:

C#
```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!

## Share

 Software Developer (Senior) Germany
Hi there 🙂
My name is Philipp Engelmann, I work as a web developer at FIO SYSTEMS AG in Leipzig. I am interested in C#, Python, (REST-)API-Design, software architecture, algorithms and AI. Check out my blog at https://cheesyprogrammer.com/

 First Prev Next
 Data.txt Member 1204912018-Apr-16 23:28 Member 12049120 18-Apr-16 23:28
 dear! teasr102415-Nov-15 22:28 teasr1024 15-Nov-15 22:28
 Data sample DungTQ11-Oct-15 15:36 DungTQ 11-Oct-15 15:36
 Re: Data sample Philipp_Engelmann11-Oct-15 21:53 Philipp_Engelmann 11-Oct-15 21:53
 Re: Data sample DungTQ12-Oct-15 15:03 DungTQ 12-Oct-15 15:03
 Data.txt Member 955126821-Sep-15 20:05 Member 9551268 21-Sep-15 20:05
 Re: Data.txt Philipp_Engelmann21-Sep-15 23:29 Philipp_Engelmann 21-Sep-15 23:29
 Data File Andy Bantly9-May-14 11:47 Andy Bantly 9-May-14 11:47
 Re: Data File Philipp_Engelmann11-May-14 5:21 Philipp_Engelmann 11-May-14 5:21
 Last Visit: 31-Dec-99 19:00     Last Update: 29-Nov-21 2:56 Refresh 1