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, line 10 def initialize(graph, edge_capacities_map) raise NotDirectedError.new('Edmonds-Karp algorithm can only be applied to a directed graph') unless graph.directed? @graph = graph validate_edge_capacities(edge_capacities_map) @edge_capacities_map = NonNegativeEdgePropertiesMap.new(edge_capacities_map, true) 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, line 23 def maximum_flow(source, sink) raise ArgumentError.new("source and sink can't be equal") if source == sink @flow_map = Hash.new(0) @residual_capacity_map = lambda { |u, v| @edge_capacities_map.edge_property(u, v) - @flow_map[[u, v]] } loop do bfs = EdmondsKarpBFSIterator.new(@graph, source, sink, @residual_capacity_map) bfs.move_forward_until { bfs.color_map[sink] == :GRAY } if bfs.color_map[sink] == :WHITE break # no more augmenting paths else min_residual_capacity = INFINITY augmenting_path = [sink] while augmenting_path.first != source v = augmenting_path.first u = bfs.parents_map[v] augmenting_path.unshift(u) min_residual_capacity = [min_residual_capacity, @residual_capacity_map[u, v]].min end augmenting_path.each_cons(2) do |(u, v)| @flow_map[[u, v]] += min_residual_capacity @flow_map[[v, u]] -= min_residual_capacity end end end @flow_map end
Private Instance Methods
get_capacity(u, v, edge_capacities_map)
click to toggle source
# File lib/rgl/edmonds_karp.rb, line 78 def get_capacity(u, v, edge_capacities_map) edge_capacities_map.fetch([u, v]) { raise ArgumentError.new("capacity for edge (#{u}, #{v}) is missing") } end
validate_capacity(u, v, edge_capacities_map)
click to toggle source
# File lib/rgl/edmonds_karp.rb, line 68 def validate_capacity(u, v, edge_capacities_map) capacity = get_capacity(u, v, edge_capacities_map) reverse_capacity = get_capacity(v, u, edge_capacities_map) validate_negative_capacity(u, v, capacity) validate_negative_capacity(v, u, reverse_capacity) raise ArgumentError.new("either (#{u}, #{v}) or (#{v}, #{u}) should have 0 capacity") unless [capacity, reverse_capacity].include?(0) end
validate_edge_capacities(edge_capacities_map)
click to toggle source
# File lib/rgl/edmonds_karp.rb, line 61 def validate_edge_capacities(edge_capacities_map) @graph.each_edge do |u, v| raise ArgumentError.new("reverse edge for (#{u}, #{v}) is missing") unless @graph.has_edge?(v, u) validate_capacity(u, v, edge_capacities_map) end end
validate_negative_capacity(u, v, capacity)
click to toggle source
# File lib/rgl/edmonds_karp.rb, line 82 def validate_negative_capacity(u, v, capacity) raise ArgumentError.new("capacity of edge (#{u}, #{v}) is negative") unless capacity >= 0 end