Class: RGL::EdmondsKarpAlgorithm

Inherits:
Object
  • Object
show all
Defined in:
lib/rgl/edmonds_karp.rb

Overview

Implements Edmonds–Karp algorithm.

See Also:

Defined Under Namespace

Classes: EdmondsKarpBFSIterator

Instance Method Summary collapse

Constructor Details

#initialize(graph, edge_capacities_map) ⇒ EdmondsKarpAlgorithm

Initializes Edmonds-Karp algorithm for a graph with provided edges capacities map.

Raises:



13
14
15
16
17
18
19
 
# File 'lib/rgl/edmonds_karp.rb', line 13

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

Instance Method Details

#maximum_flow(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.

Returns:

  • (Hash)

Raises:

  • (ArgumentError) 


27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
 
# File 'lib/rgl/edmonds_karp.rb', line 27

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 |(uu, vv)|
        @flow_map[[uu, vv]] += min_residual_capacity
        @flow_map[[vv, uu]] -= min_residual_capacity
      end
    end
  end

  @flow_map
end