Click here to Skip to main content
Click here to Skip to main content

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

, 7 Jan 2014
Rate this:
Please Sign up or sign in to vote.
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():

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 ScienceSmile | :) ). I hope you find this project useful! Feel free to leave any hints, critique or questions!

Thanks for reading. Smile | :)

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Philipp_Engelmann
Software Developer (Junior)
Germany Germany
No Biography provided

Comments and Discussions

 
QuestionData File PinpremiumAndy Bantly9-May-14 10:47 
AnswerRe: Data File PinmemberPhilipp100011-May-14 4:21 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web01 | 2.8.140827.1 | Last Updated 7 Jan 2014
Article Copyright 2014 by Philipp_Engelmann
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid