flow augmentation in a directed network with the constraint edges with a common source must have the same flow

Question

I am currently trying to create a program that finds the maximum flow through a network under the constraint that edges with a common source node must have the same flow. It is that constraint that I am having trouble with.

Currently, I have the code to get all flow augmenting routes, but I am hesitant to code the augmentation because I can't figure out how to add in the constraint. I am thinking about maybe a backtracking algorithm that tries to assign flow using the Ford-Fulkerson method and then tries to adjust to fit the constraint.

So my code:
There is a graph class that has as attributes all the vertices and edges as well as methods to get the incident edges to a vertex and the preceding edges to a vertex:

class WeightedEdge:
    def __init__(self, from_vertex, to_vertex, capacity):
        self.tail = from_vertex
        self.head = to_vertex
        self.capacity = capacity

class Graph:
    def __init__(self, vertices, edges, capacities):
        self.vertices = vertices
        self.edges = [WeightedEdge(edges[i][0], edges[i][1], capacities[i]) for i in range(len(edges))]

        self.__forward_list = {v : [] for v in vertices}
        self.__reverse_list = {v: [] for v in vertices}

        for i in range(len(edges)):
            self.__forward_list[edges[i][0]].append((edges[i][1], capacities[i]))
            self.__reverse_list[edges[i][1]].append((edges[i][0], capacities[i]))

    def out_edges(self, vertex):
        return [WeightedEdge(vertex, next_vertex, capacity) for (next_vertex, capacity) in self.__forward_list[vertex]]
    
    def in_edges(self, vertex):
        return [WeightedEdge(prev_vertex, vertex, capacity) for (prev_vertex, capacity) in self.__reverse_list[vertex]]

Each edge is an object that has a tail vertex attribute, a capacity attribute and a head vertex attribute. So far this is my function that gets the flow augmenting routes:

def max_equal_split_flow(graph, source, sink):
    def find_augmenting_routes(vertex):
        route_buffer.append(vertex)
        if vertex == sink:
            flow_augmenting_routes.append([v for v in route_buffer])
            return
        else:
            out_edges = graph.out_edges(vertex)
            for edge in out_edges:
                find_augmenting_routes(edge.head)
                route_buffer.pop()
    flow_augmenting_routes = []
    route_buffer = []
    find_augmenting_routes(source)
    print(flow_augmenting_routes)

TLDR: How can I find the maximum flow through a network when all edges that share a source node must have the same flow?

Answer 1

So I figured it out!!! I was massively overcomplicating the problem. This algorithm here finds the desired output:

It works by finding out how much you would divide an initial flow by once you had got to the current edge and storing that in a dictionary, and then works out using the stored capacities of all the edges, what the maximum initial flow would be. For example:

Answer 2

I would guess that you have an input that specifies the maximum flow through each edge.

The algorithm is then:

1. Because edges with a common source must have same actual, final flow the first step must be a little pre-processing to reduce the max flow at each edge to the minimum flow from the common source.

2. apply the standard maximum flow algorithm.

3. do a depth first search from the flow origin ( I assume there is just one ) until you find a node with unequal outflows. Reduce the max flows on all edges from this node to the minimum flow assigned by the algorithm. Re-apply the algorithm.

Repeat step 3 until no uneven flows remain.

=====================

Second algorithm:

1. Adjust capacity of every out edge to be equal to the minimum capacity of all out edges from the common vertex

2. Perform breadth first search through graph. When an edge is added, set the flow through the edge the minimum of

• the flow into the source node divided by the number of exiting edges
• the edge capacity

3. When search is complete sum flows into destination node.

For reference, here is the C++ code I use for depth first searching using recursion

void cPathFinder::depthRecurse(int v)
{
    // record new node on the search
    myPred.push_back(v);

    // remember this node has been visted
    myPath[v] = 1;

    // look for new adjacent nodes
    for (int w : myGraph.adjacent(v))
        if (!myPath[w])
        {
            // search from new node
            depthRecurse(w);
        }
}

Here is the simplest sample graph that shows that adjusting the capacity of out edges is not sufficient to balance the actual outflows

format flows
g
l src a 210
l a b 200
l a c 200
l b d 500
l c d 500
s src
e d

( if this specification format is not immediately obvious it is documented here )

Node 'a' has two out edges, whose capacities have been adjusted to balance. However the 'src' node does not supply sufficient flow to fill the edges so the output is

total flow 210
a   -- b capacity 200 used 10
a   -- c capacity 200 used 200
src -- a capacity 210 used 210
b   -- d capacity 500 used 10
c   -- d capacity 500 used 200

This suggests another algorithm #3:

1. Adjust capacity of every out edge to be equal to the minimum capacity of all out edges from the common vertex

2. Apply the standard maximum flow algorithm.

3. do a depth first search from the flow origin until you find a node with unequal outflows. Re-allocate the flows so they balance. Remove in-edges to node and make it a new flow source with flow equal to sum of removed in-edges

4. Apply maximum flow algorithm modified to handle multiple sources

5. Repeat steps 3 and 4 until all flows balance.

Applying step 3 and 4 to the previous example gives

format multiflows
g
l a1 b 105
l a2 c 105
l b d 500
l c d 500
s a1
s a2
e d

b -- d capacity 500 used 105
a1 -- b capacity 105 used 105
c -- d capacity 500 used 105
a2 -- c capacity 105 used 105
total flow 210.000000

which meets the requirements.

=================================

Here is the PathFinder implementation of Nestor's algorithm

 void cPathFinder::equiflows()
        {
            // source outflows
            int outlinkpercent = 100 / node(myStart).outdegree();
            for (auto &outlink : node(myStart).myLink)
                outlink.second.myValue = outlinkpercent;

            // function to call each time a node is visited in BFS
            myVisitor.set(
                [this](int v)
                {
                    static int X = INT_MAX;

                    if( v == myEnd ) {
                        // destination reached, report maximum flow
                        std::cout << "maximum flow is " << X << "\n";
                        return;
                    }
                    
                    // sum the inputs
                    int sumInput = 0;
                    for (auto &inlink : inlinks(v)) {
                        sumInput += inlink.second.myValue;
                    }

                    // node outflows
                    int outValue = sumInput / node(v).outdegree();
                    for (auto &outlink : node(v).myLink) {
                        outlink.second.myValue = outValue;

                        // check if this outflow reduces maximum flow through network
                        int x = outlink.second.myCost * 100 / outValue;
                        if( x < X )
                            X = x;
                    }

                });

            // do a breadth first search, updating flows as we go along
            breadth();
        }
    }