class GraphMatching::Graph::Bigraph

A bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V.

Public Instance Methods

maximum_cardinality_matching() click to toggle source
# File lib/graph_matching/graph/bigraph.rb, line 13
def maximum_cardinality_matching
  Algorithm::MCMBipartite.new(self).match
end
partition() click to toggle source

`partition` either returns two disjoint (complementary) proper subsets of vertexes or raises a NotBipartite error.

An empty graph is partitioned into two empty sets. This seems natural, but unfortunately is not the behavior of RGL's new `bipartite_sets` function. So, we have to check for the empty case, but at least we don't have to implement the algorithm ourselves anymore!

# File lib/graph_matching/graph/bigraph.rb, line 26
def partition
  if empty?
    [Set.new, Set.new]
  else
    arrays = bipartite_sets
    raise NotBipartite if arrays.nil?
    [Set.new(arrays[0]), Set.new(arrays[1])]
  end
end