Class: Graphsrb::BaseGraph

Inherits:
Object
  • Object
show all
Defined in:
lib/graphsrb/base_graph.rb

Overview

This class is the base clase for undirected and directed graphs.

Direct Known Subclasses

Digraph, Graph

Instance Method Summary collapse

Constructor Details

#initialize(args = {}) ⇒ BaseGraph

Returns a new instance of BaseGraph.



5
6
7
8
9
10
11
12
13
14
 
# File 'lib/graphsrb/base_graph.rb', line 5

def initialize(args={})
  @adj_table = {}
  args.fetch(:vertices,[]).each{|vertex_id| adj_table[vertex_id] = _create_adjacency_list }
  args.fetch(:edges,[]).each do |e|
    unless has_edge?(e[0], e[1])
      vertices_must_be_different!(e[0], e[1])
      add_edge(e[0], e[1], weight: e[2] || 1)
    end
  end
end

Instance Method Details

#add_edge(id1, id2, args = {}) ⇒ Object

Adds a new edge



111
112
113
114
115
116
117
118
 
# File 'lib/graphsrb/base_graph.rb', line 111

def add_edge(id1, id2, args={})
  vertices_must_be_different!(id1, id2)
  return nil if has_edge?(id1, id2)
  add_vertex(id1) unless has_vertex?(id1)
  add_vertex(id2) unless has_vertex?(id2)
  adj_table[id1] << _create_node(id2, args)
  true
end

#add_vertex(id) ⇒ Object

Adds a new vertex



104
105
106
107
108
 
# File 'lib/graphsrb/base_graph.rb', line 104

def add_vertex(id)
  return nil if has_vertex?(id)
  adj_table[id] = _create_adjacency_list
  true
end

#clear ⇒ Object

Removes all vertices and edges.



65
66
67
68
69
 
# File 'lib/graphsrb/base_graph.rb', line 65

def clear
  adj_table.each_value{|list| list.clear}
  @adj_table = {}
  true
end

#copy ⇒ Object

Creates a copy of the graph



72
73
74
 
# File 'lib/graphsrb/base_graph.rb', line 72

def copy
  Marshal::load(Marshal.dump(self))
end

#edge(v, u) ⇒ Object

Returns an edge



26
27
28
29
30
31
32
33
34
35
36
37
 
# File 'lib/graphsrb/base_graph.rb', line 26

def edge(v, u)
  id1, id2 = v.id, u.id
  if has_vertex?(id1)
    node = adj_table[id1].find(_create_node(id2))
    return _create_edge(id1, id2, weight:node.weight) if node
  end

  if has_vertex?(id2)
    node = adj_table[id2].find(_create_node(id1))
    return _create_edge(id1, id2, weight:node.weight) if node
  end
end

#edge_count ⇒ Object

Returns the number of edges in the graph



82
83
84
85
86
 
# File 'lib/graphsrb/base_graph.rb', line 82

def edge_count
  sum = 0
  adj_table.each_value{|list| sum += list.size}
  sum
end

#edges ⇒ Object

Returns edges of the graph



54
55
56
57
58
59
60
61
62
 
# File 'lib/graphsrb/base_graph.rb', line 54

def edges
  edges_array = []
  vertices.each do |vertex|
    adj_table[vertex.id].each do |node|
      edges_array << _create_edge(vertex.id, node.vertex.id, weight: node.weight)
    end
  end
  edges_array
end

#has_edge?(id1, id2) ⇒ Boolean Also known as: edge?

Checks whether the graph has an edge

Returns:

  • (Boolean) 


96
97
98
99
 
# File 'lib/graphsrb/base_graph.rb', line 96

def has_edge?(id1, id2)
  has_vertex?(id1) && adj_table[id1].has_node?(_create_node(id2)) ||
  has_vertex?(id2) && adj_table[id2].has_node?(_create_node(id1))
end

#has_vertex?(id) ⇒ Boolean Also known as: vertex?

Checks whether the graph has a vertex

Returns:

  • (Boolean) 


89
90
91
 
# File 'lib/graphsrb/base_graph.rb', line 89

def has_vertex?(id)
  not adj_table[id].nil?
end

#increase_weight(v, u, dw) ⇒ Object

Increases edge weight by dw



47
48
49
50
51
 
# File 'lib/graphsrb/base_graph.rb', line 47

def increase_weight(v, u, dw)
  id1, id2 = v.id, u.id
  adj_table[id1].increase_weight(_create_node(id2), dw) if has_vertex?(id1)
  adj_table[id2].increase_weight(_create_node(id1), dw) if has_vertex?(id2)
end

#remove_edge(v1, v2) ⇒ Object

Remove an edge from the graph



121
122
123
124
125
126
 
# File 'lib/graphsrb/base_graph.rb', line 121

def remove_edge(v1, v2)
  id1, id2 = v1.id, v2.id
  adj_table[id1].delete(_create_node(id2)) if has_vertex?(id1)
  adj_table[id2].delete(_create_node(id1)) if has_vertex?(id2)
  true
end

#remove_vertex(v) ⇒ Object

Remove a vertex from the graph



129
130
131
132
133
134
135
136
137
138
139
 
# File 'lib/graphsrb/base_graph.rb', line 129

def remove_vertex(v)
  id = v.id
  return nil unless has_vertex?(id)

  adj_table[id].clear
  adj_table.delete(id)

  node = _create_node(id)
  adj_table.each_value{|list| list.delete(node)}
  return v
end

#update_weight(v, u, w) ⇒ Object

Updates edge weight



40
41
42
43
44
 
# File 'lib/graphsrb/base_graph.rb', line 40

def update_weight(v, u, w)
  id1, id2 = v.id, u.id
  adj_table[id1].update_weight(_create_node(id2), w) if has_vertex?(id1)
  adj_table[id2].update_weight(_create_node(id1), w) if has_vertex?(id2)
end

#vertex_count ⇒ Object

Returns the number of vertices



77
78
79
 
# File 'lib/graphsrb/base_graph.rb', line 77

def vertex_count
  vertices.size
end

#vertices ⇒ Object

Returns vertices of the graph



17
18
19
20
21
22
23
 
# File 'lib/graphsrb/base_graph.rb', line 17

def vertices
  vertex_array = []
  adj_table.keys.each do |id|
    vertex_array << _create_vertex(id)
  end
  vertex_array
end