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
# File lib/graph_matching/graph/graph.rb, line 48 def print base_filename = SecureRandom.hex(16) Visualize.new(self).png(base_filename) end
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