Method: RGL::Graph#maximum_flow

Defined in:
lib/rgl/edmonds_karp.rb

#maximum_flow(edge_capacities_map, source, sink) ⇒ Hash

Finds the maximum flow from the source to the sink in the graph.

Returns flows map as a hash that maps each edge of the graph to a flow through that edge that is required to reach the maximum total flow.

For the method to work, the graph should be first altered so that for each directed edge (u, v) it contains reverse edge (u, v). Capacities of the primary edges should be non-negative, while reverse edges should have zero capacity.

Raises ArgumentError if the graph is not directed.

Raises ArgumentError if a reverse edge is missing, edge capacity is missing, an edge has negative capacity, or a reverse edge has positive capacity.

Returns:

  • (Hash) 


136
137
138
 
# File 'lib/rgl/edmonds_karp.rb', line 136

def maximum_flow(edge_capacities_map, source, sink)
  EdmondsKarpAlgorithm.new(self, edge_capacities_map).maximum_flow(source, sink)
end