pythongraph-theorynetwork-flow

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


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?


Solution

  • 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: Example of my method to find maximum equal split flow