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.



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

def bipartite_sets_map
  @bipartite_sets_map
end

#found_odd_cycle ⇒ Object (readonly)

Returns the value of attribute found_odd_cycle.



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

def found_odd_cycle
  @found_odd_cycle
end

Instance Method Details

#handle_back_edge(u, v) ⇒ Object 



73
74
75
 
# File 'lib/rgl/bipartite.rb', line 73

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

#handle_forward_edge(u, v) ⇒ Object 



77
78
79
 
# File 'lib/rgl/bipartite.rb', line 77

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

#handle_tree_edge(u, v) ⇒ Object 



69
70
71
 
# File 'lib/rgl/bipartite.rb', line 69

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 



51
52
53
54
55
56
 
# File 'lib/rgl/bipartite.rb', line 51

def reset
  super

  @bipartite_sets_map = {}
  @found_odd_cycle = false
end

#reset_start(new_start) ⇒ Object 



64
65
66
67
 
# File 'lib/rgl/bipartite.rb', line 64

def reset_start(new_start)
  @start_vertex = new_start
  set_to_begin
end

#set_to_begin ⇒ Object 



58
59
60
61
62
 
# File 'lib/rgl/bipartite.rb', line 58

def set_to_begin
  super

  @bipartite_sets_map[@start_vertex] = 0
end