class RGL::EdmondsKarpAlgorithm
Implements {en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm Edmonds–Karp algorithm}. @see Graph#maximum_flow
Public Class Methods
Source
# File lib/rgl/edmonds_karp.rb 13 def initialize(graph, edge_capacities_map) 14 raise NotDirectedError.new('Edmonds-Karp algorithm can only be applied to a directed graph') unless graph.directed? 15 16 @graph = graph 17 validate_edge_capacities(edge_capacities_map) 18 @edge_capacities_map = NonNegativeEdgePropertiesMap.new(edge_capacities_map, true) 19 end
Initializes Edmonds-Karp algorithm for a graph with provided edges capacities map.
Public Instance Methods
Source
# File lib/rgl/edmonds_karp.rb 27 def maximum_flow(source, sink) 28 raise ArgumentError.new("source and sink can't be equal") if source == sink 29 30 @flow_map = Hash.new(0) 31 @residual_capacity_map = lambda { |u, v| @edge_capacities_map.edge_property(u, v) - @flow_map[[u, v]] } 32 33 loop do 34 bfs = EdmondsKarpBFSIterator.new(@graph, source, sink, @residual_capacity_map) 35 36 bfs.move_forward_until { bfs.color_map[sink] == :GRAY } 37 38 if bfs.color_map[sink] == :WHITE 39 break # no more augmenting paths 40 else 41 min_residual_capacity = INFINITY 42 43 augmenting_path = [sink] 44 45 while augmenting_path.first != source 46 v = augmenting_path.first 47 u = bfs.parents_map[v] 48 49 augmenting_path.unshift(u) 50 min_residual_capacity = [min_residual_capacity, @residual_capacity_map[u, v]].min 51 end 52 53 augmenting_path.each_cons(2) do |(uu, vv)| 54 @flow_map[[uu, vv]] += min_residual_capacity 55 @flow_map[[vv, uu]] -= min_residual_capacity 56 end 57 end 58 end 59 60 @flow_map 61 end
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.
@return [Hash]
Private Instance Methods
Source
# File lib/rgl/edmonds_karp.rb 82 def get_capacity(u, v, edge_capacities_map) 83 edge_capacities_map.fetch([u, v]) { raise ArgumentError.new("capacity for edge (#{u}, #{v}) is missing") } 84 end
Source
# File lib/rgl/edmonds_karp.rb 72 def validate_capacity(u, v, edge_capacities_map) 73 capacity = get_capacity(u, v, edge_capacities_map) 74 reverse_capacity = get_capacity(v, u, edge_capacities_map) 75 76 validate_negative_capacity(u, v, capacity) 77 validate_negative_capacity(v, u, reverse_capacity) 78 79 raise ArgumentError.new("either (#{u}, #{v}) or (#{v}, #{u}) should have 0 capacity") unless [capacity, reverse_capacity].include?(0) 80 end
Source
# File lib/rgl/edmonds_karp.rb 65 def validate_edge_capacities(edge_capacities_map) 66 @graph.each_edge do |u, v| 67 raise ArgumentError.new("reverse edge for (#{u}, #{v}) is missing") unless @graph.has_edge?(v, u) 68 validate_capacity(u, v, edge_capacities_map) 69 end 70 end
Source
# File lib/rgl/edmonds_karp.rb 86 def validate_negative_capacity(u, v, capacity) 87 raise ArgumentError.new("capacity of edge (#{u}, #{v}) is negative") unless capacity >= 0 88 end