Class: GraphMatching::Graph::Graph

Inherits:
RGL::AdjacencyGraph
  • Object
show all
Defined in:
lib/graph_matching/graph/graph.rb

Overview

Base class for all graphs.

Direct Known Subclasses

Bigraph, WeightedGraph

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(*args) ⇒ Graph

Returns a new instance of Graph.



19
20
21
22
 
# File 'lib/graph_matching/graph/graph.rb', line 19

def initialize(*args)
  super
  vertexes_must_be_integers
end

Class Method Details

.[](*args) ⇒ Object 



15
16
17
 
# File 'lib/graph_matching/graph/graph.rb', line 15

def self.[](*args)
  super.tap(&:vertexes_must_be_integers)
end

Instance Method Details

#adjacent_vertex_set(v) ⇒ Object

‘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).



28
29
30
31
32
 
# 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? ⇒ Boolean

Returns:

  • (Boolean) 


34
35
36
37
38
 
# File 'lib/graph_matching/graph/graph.rb', line 34

def connected?
  count = 0
  each_connected_component { count += 1 }
  count == 1
end

#max_v ⇒ Object 



44
45
46
 
# File 'lib/graph_matching/graph/graph.rb', line 44

def max_v
  vertexes.max
end

#maximum_cardinality_matching ⇒ Object 



40
41
42
 
# File 'lib/graph_matching/graph/graph.rb', line 40

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

#print ⇒ Object 



48
49
50
51
 
# File 'lib/graph_matching/graph/graph.rb', line 48

def print
  base_filename = SecureRandom.hex(16)
  Visualize.new(self).png(base_filename)
end

#vertexes ⇒ Object 



53
54
55
 
# File 'lib/graph_matching/graph/graph.rb', line 53

def vertexes
  to_a
end

#vertexes_must_be_integers ⇒ Object

Raises:

  • (ArgumentError) 


57
58
59
60
 
# 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