Class: RGL::EdmondsKarpAlgorithm::EdmondsKarpBFSIterator

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

Instance Attribute Summary collapse

Attributes inherited from BFSIterator

#start_vertex

Attributes included from GraphVisitor

#color_map

Attributes included from GraphWrapper

#graph

Instance Method Summary collapse

Methods inherited from BFSIterator

#at_beginning?, #at_end?, #basic_forward, #set_to_begin

Methods included from GraphVisitor

#attach_distance_map, #finished_vertex?, included

Methods included from GraphVisitor::ClassMethods

#def_event_handlers

Methods included from GraphIterator

#length

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

#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