Class: RGL::BipartiteBFSIterator

Inherits:
BFSIterator show all
Defined in:
lib/rgl/bipartite.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, #initialize

Methods included from GraphVisitor

#attach_distance_map, #finished_vertex?, #follow_edge?, included, #initialize

Methods included from GraphVisitor::ClassMethods

#def_event_handlers

Methods included from GraphWrapper

#initialize

Methods included from GraphIterator

#length

Constructor Details

This class inherits a constructor from RGL::BFSIterator

Instance Attribute Details

#bipartite_sets_map ⇒ Object (readonly)

Returns the value of attribute bipartite_sets_map.



47
48
49
 
# File 'lib/rgl/bipartite.rb', line 47

def bipartite_sets_map
  @bipartite_sets_map
end

#found_odd_cycle ⇒ Object (readonly)

Returns the value of attribute found_odd_cycle.



47
48
49
 
# File 'lib/rgl/bipartite.rb', line 47

def found_odd_cycle
  @found_odd_cycle
end

Instance Method Details

#handle_back_edge(u, v) ⇒ Object 



71
72
73
 
# File 'lib/rgl/bipartite.rb', line 71

def handle_back_edge(u, v)
  verify_odd_cycle(u, v)
end

#handle_forward_edge(u, v) ⇒ Object 



75
76
77
 
# File 'lib/rgl/bipartite.rb', line 75

def handle_forward_edge(u, v)
  verify_odd_cycle(u, v)
end

#handle_tree_edge(u, v) ⇒ Object 



67
68
69
 
# File 'lib/rgl/bipartite.rb', line 67

def handle_tree_edge(u, v)
  @bipartite_sets_map[v] = (@bipartite_sets_map[u] + 1) % 2 unless u.nil?  # put v into the other set
end

#reset ⇒ Object 



49
50
51
52
53
54
 
# File 'lib/rgl/bipartite.rb', line 49

def reset
  super

  @bipartite_sets_map = {}
  @found_odd_cycle = false
end

#reset_start(new_start) ⇒ Object 



62
63
64
65
 
# File 'lib/rgl/bipartite.rb', line 62

def reset_start(new_start)
  @start_vertex = new_start
  set_to_begin
end

#set_to_begin ⇒ Object 



56
57
58
59
60
 
# File 'lib/rgl/bipartite.rb', line 56

def set_to_begin
  super

  @bipartite_sets_map[@start_vertex] = 0
end