class GraphMatching::Graph::Graph

Base class for all graphs.

Public Class Methods

[](*args) click to toggle source
Calls superclass method
# File lib/graph_matching/graph/graph.rb, line 15
def self.[](*args)
  super.tap(&:vertexes_must_be_integers)
end
new(*args) click to toggle source
Calls superclass method
# File lib/graph_matching/graph/graph.rb, line 19
def initialize(*args)
  super
  vertexes_must_be_integers
end

Public Instance Methods

adjacent_vertex_set(v) click to toggle source

`adjacent_vertex_set` is the same as `adjacent_vertices` except it returns a `Set` instead of an `Array`. This is an optimization, performing in O(n), whereas passing `adjacent_vertices` to `Set.new` would be O(2n).

# File lib/graph_matching/graph/graph.rb, line 28
def adjacent_vertex_set(v)
  s = Set.new
  each_adjacent(v) do |u| s.add(u) end
  s
end
connected?() click to toggle source
# File lib/graph_matching/graph/graph.rb, line 34
def connected?
  count = 0
  each_connected_component { count += 1 }
  count == 1
end
max_v() click to toggle source
# File lib/graph_matching/graph/graph.rb, line 44
def max_v
  vertexes.max
end
maximum_cardinality_matching() click to toggle source
# File lib/graph_matching/graph/graph.rb, line 40
def maximum_cardinality_matching
  Algorithm::MCMGeneral.new(self).match
end
print() click to toggle source
vertexes() click to toggle source
# File lib/graph_matching/graph/graph.rb, line 53
def vertexes
  to_a
end
vertexes_must_be_integers() click to toggle source
# File lib/graph_matching/graph/graph.rb, line 57
def vertexes_must_be_integers
  return if vertices.none? { |v| !v.is_a?(Integer) }
  raise ArgumentError, 'All vertexes must be integers'
end