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?
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: