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