0
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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:

enter image description here

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][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]]
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.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.