Class: GraphMatching::Graph::Bigraph

Inherits:
Graph
  • Object
show all
Defined in:
lib/graph_matching/graph/bigraph.rb

Overview

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.

Direct Known Subclasses

WeightedBigraph

Instance Method Summary collapse

Methods inherited from Graph

[], #adjacent_vertex_set, #connected?, #initialize, #max_v, #print, #vertexes, #vertexes_must_be_integers

Constructor Details

This class inherits a constructor from GraphMatching::Graph::Graph

Instance Method Details

#maximum_cardinality_matching ⇒ Object 



13
14
15
 
# File 'lib/graph_matching/graph/bigraph.rb', line 13

def maximum_cardinality_matching
  Algorithm::MCMBipartite.new(self).match
end

#partition ⇒ Object

‘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!



26
27
28
29
30
31
32
33
34
 
# 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