Class: RGL::EdmondsKarpAlgorithm::EdmondsKarpBFSIterator

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

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(graph, start, stop, residual_capacities) ⇒ EdmondsKarpBFSIterator

Returns a new instance of EdmondsKarpBFSIterator.



94
95
96
97
98
 
# File 'lib/rgl/edmonds_karp.rb', line 94

def initialize(graph, start, stop, residual_capacities)
  super(graph, start)
  @residual_capacities = residual_capacities
  @stop_vertex = stop
end

Instance Attribute Details

#color_map ⇒ Hash (readonly) Originally defined in module GraphVisitor

Returns a map which store the colors for each vertex.

Returns:

  • (Hash) —

    a map which store the colors for each vertex

#graph ⇒ Graph Originally defined in module GraphWrapper

Returns the wrapped graph.

Returns:

  • (Graph) —

    the wrapped graph

#parents_map ⇒ Object

Returns the value of attribute parents_map.



92
93
94
 
# File 'lib/rgl/edmonds_karp.rb', line 92

def parents_map
  @parents_map
end

Instance Method Details

#follow_edge?(u, v) ⇒ Boolean

Returns:

  • (Boolean) 


105
106
107
108
 
# File 'lib/rgl/edmonds_karp.rb', line 105

def follow_edge?(u, v)
  # follow only edges with positive residual capacity
  super && @residual_capacities[u, v] > 0
end

#handle_tree_edge(u, v) ⇒ Object 



110
111
112
113
 
# File 'lib/rgl/edmonds_karp.rb', line 110

def handle_tree_edge(u, v)
  super
  @parents_map[v] = u
end

#reset ⇒ Object 



100
101
102
103
 
# File 'lib/rgl/edmonds_karp.rb', line 100

def reset
  super
  @parents_map = {}
end