Method: RGL::Graph#bipartite_sets

Defined in:
lib/rgl/bipartite.rb

#bipartite_sets ⇒ Array

Separates graph’s vertices into two disjoint sets so that every edge of the graph connects vertices from different sets. If it’s possible, the graph is bipartite.

Returns an array of two disjoint vertices sets (represented as arrays) if the graph is bipartite. Otherwise, returns nil.

Returns:

  • (Array)

Raises:



14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
 
# File 'lib/rgl/bipartite.rb', line 14

def bipartite_sets
  raise NotUndirectedError.new('bipartite sets can only be found for an undirected graph') if directed?

  bfs = BipartiteBFSIterator.new(self)

  # if necessary, we start BFS from each vertex to make sure
  # that all connected components of the graph are processed
  each_vertex do |u|
    next if bfs.finished_vertex?(u)

    bfs.reset_start(u)
    bfs.move_forward_until { bfs.found_odd_cycle }

    return if bfs.found_odd_cycle
  end

  bfs.bipartite_sets_map.inject([[], []]) do |sets, (vertex, set)|
    sets[set] << vertex
    sets
  end
end