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.



96
97
98
99
100
 
# File 'lib/rgl/edmonds_karp.rb', line 96

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.



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

def parents_map
  @parents_map
end

Instance Method Details

#follow_edge?(u, v) ⇒ Boolean

Returns:

  • (Boolean) 


107
108
109
110
 
# File 'lib/rgl/edmonds_karp.rb', line 107

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 



112
113
114
115
 
# File 'lib/rgl/edmonds_karp.rb', line 112

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

#reset ⇒ Object 



102
103
104
105
 
# File 'lib/rgl/edmonds_karp.rb', line 102

def reset
  super
  @parents_map = {}
end