# How can I find the maximum equal-split flow of a network

I am working on a program currently that works out the maximum flow through a network using the Ford-Fulkerson algorithm, and that works fine, however, I need the final flow to meet the constraint that all edges that share a source node must also share the same flow value. (or flow splits evenly between edges from a common vertex). I am not mathematically literate when it comes to describing network flows, I only studied it for a brief period in high school so if people could try and explain simply I would really appreciate it! Am I missing another more simple way of working this out, my assignment says that this constraint simplifies the problem but I am at a loss as to how to do this. TLDR: How can I find the maximum flow in a network if flow has to split evenly between all edges that share a source node

## 1 Answer

So I figured it out. Assign the initial flow into the network a value of x, and then split the flow evenly under the constraints:

• All flow into a vertex must leave that vertex
• All edges that share a source must also share a flow

Then once each edge has been assigned a flow, for each edge set the flow equal to the capacity of that edge, and find the value of x. the smallest value of x will be the maximum initial flow allowed under the constraints.

Here is an example I drew up in ms paint to get the point across: Also if you are interested here is a python function that will do the same:

def max_equal_split_flow(graph, source, sink):
flow_split = dict()
for vertex in graph.vertices:
out_edges = graph.out_edges(vertex)
if vertex == source:
for edge in out_edges:
flow_split[edge.tail, edge.head] = 1/len(out_edges)
elif vertex != sink:
in_edges = graph.in_edges(vertex)
flow_in = sum([flow_split[edge.tail, edge.head] for edge in in_edges])
for edge in out_edges:
flow_split[edge.tail, edge.head] = flow_in/len(out_edges)
max_equal_flow = min([(edge.capacity/flow_split[edge.tail, edge.head]) for edge in graph.edges])
return max_equal_flow


And here is the code for the graph objects and the edge objects used:

class Graph:
def __init__(self, vertices, edges, capacities):
self.vertices = vertices
self.edges = [WeightedEdge(edges[i], edges[i], 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]].append((edges[i], capacities[i]))
self.__reverse_list[edges[i]].append((edges[i], 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]]

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

New contributor
Micheal Nestor is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.