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.



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

#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