Class: Graph

Inherits:
Object
  • Object
show all
Defined in:
lib/rbutils/graph/graph.rb

Direct Known Subclasses

BFS, DFS, Dijkstra

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ Graph

Returns a new instance of Graph.



8
9
10
11
12
 
# File 'lib/rbutils/graph/graph.rb', line 8

def initialize
  @nodes = Set.new
  @edges = Array.new
  @connections = Hash.new
end

Instance Attribute Details

#connections ⇒ Object

Returns the value of attribute connections.



6
7
8
 
# File 'lib/rbutils/graph/graph.rb', line 6

def connections
  @connections
end

#edges ⇒ Object

Returns the value of attribute edges.



5
6
7
 
# File 'lib/rbutils/graph/graph.rb', line 5

def edges
  @edges
end

#nodes ⇒ Object

Returns the value of attribute nodes.



4
5
6
 
# File 'lib/rbutils/graph/graph.rb', line 4

def nodes
  @nodes
end

Instance Method Details

#add_adjacency(n1, n2) ⇒ Object

for BFS and DFS



25
26
27
28
 
# File 'lib/rbutils/graph/graph.rb', line 25

def add_adjacency(n1, n2)
  n1.adjacents << n2
  n2.adjacents << n1
end

#add_edge(source, dest, weight) ⇒ Object

adds an edge dest the graph



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

def add_edge(source, dest, weight)
  edges << Edge.new(source, dest, weight)
end

#add_node(node) ⇒ Object 



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

def add_node(node)
  nodes << node
  node.graph = self
end

#adjacents(node) ⇒ Object 



64
65
66
 
# File 'lib/rbutils/graph/graph.rb', line 64

def adjacents node
  @connections[node]
end

#connect(node1, node2) ⇒ Object

connects two nodes in the graph



31
32
33
34
35
36
37
38
39
40
41
 
# File 'lib/rbutils/graph/graph.rb', line 31

def connect node1, node2
  if !Set.new([node1, node2]).subset? @nodes
    raise BadNodeInput, 'The graph does not have either ' + node1 + ' or ' + node2
  end
  @connections[node1] ||= Array.new
  @connections[node1].push node2
  unless node1.eql? node2
    @connections[node2] ||= Array.new
    @connections[node2].push node1
  end
end

#degree(node) ⇒ Object

returns the degree of the specified node



53
54
55
56
57
58
59
60
61
62
 
# File 'lib/rbutils/graph/graph.rb', line 53

def degree node
  d = 0
  if (@connections[node].is_a? (Array)) && nodes.include?(node)
    d = @connections[node].count
    if @connections[node].include?(node)
      d += 1
    end
  end
  return d
end

#disconnect(node1, node2) ⇒ Object

disconnects two nodes in the graph



44
45
46
47
48
49
50
 
# File 'lib/rbutils/graph/graph.rb', line 44

def disconnect node1, node2
  if !nodes.include?(node1) || !nodes.include?(node2)
    raise NodeContainsException, 'The graph does not contain either ' + node1 + ' or ' + node2
  end
  @connections[node1].delete node2
  @connections[node2].delete node1
end