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