class RGL::EdmondsKarpAlgorithm

Implements {en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm Edmonds–Karp algorithm}. @see Graph#maximum_flow

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
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

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.

@return [Hash]

   # 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

Private Instance Methods

get_capacity(u, v, edge_capacities_map) click to toggle 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
validate_capacity(u, v, edge_capacities_map) click to toggle 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
validate_edge_capacities(edge_capacities_map) click to toggle 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
validate_negative_capacity(u, v, capacity) click to toggle 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