Class: Algorithmable::Graphs::Undirected

Inherits:
Object
  • Object
show all
Defined in:
lib/algorithmable/graphs/undirected.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(vertices = 0) ⇒ Undirected


6
7
8
9
10
11
# File 'lib/algorithmable/graphs/undirected.rb', line 6

def initialize(vertices = 0)
  @vertices = vertices
  @edges = 0
  @adj = []
  @vertices.times { |i| @adj[i] = [] }
end

Instance Attribute Details

#edgesObject (readonly)

Returns the value of attribute edges


4
5
6
# File 'lib/algorithmable/graphs/undirected.rb', line 4

def edges
  @edges
end

#verticesObject (readonly)

Returns the value of attribute vertices


4
5
6
# File 'lib/algorithmable/graphs/undirected.rb', line 4

def vertices
  @vertices
end

Instance Method Details

#add_edge(left_vertex, right_vertex) ⇒ Object


13
14
15
16
17
18
19
# File 'lib/algorithmable/graphs/undirected.rb', line 13

def add_edge(left_vertex, right_vertex)
  @adj[left_vertex] ||= []
  @adj[right_vertex] ||= []
  @adj[left_vertex].push right_vertex
  @adj[right_vertex].push left_vertex
  @edges = @edges.next
end

#adjacency(vertex) ⇒ Object


21
22
23
# File 'lib/algorithmable/graphs/undirected.rb', line 21

def adjacency(vertex)
  @adj[vertex]
end

#degree(vertex) ⇒ Object


29
30
31
32
# File 'lib/algorithmable/graphs/undirected.rb', line 29

def degree(vertex)
  fail "Vertex #{vertex} is not valid." unless valid_vertex?(vertex)
  adjacency(vertex).size
end

#to_sObject


34
35
36
37
38
39
40
41
42
43
44
# File 'lib/algorithmable/graphs/undirected.rb', line 34

def to_s
  data = ''
  @vertices.times do |vertex|
    data += "( #{vertex} => "
    @adj[vertex].each do |neighbor|
      data += "#{neighbor} "
    end
    data += ') '
  end
  "#<#{self.class} @vertices=#{@vertices} @edges=#{@edges} @data=#{data}>"
end

#valid_vertex?(vertex) ⇒ Boolean


25
26
27
# File 'lib/algorithmable/graphs/undirected.rb', line 25

def valid_vertex?(vertex)
  !(0 > vertex || vertex >= @vertices)
end