Class: DataStructures::AdjacencyList

Inherits:
Object
  • Object
show all
Defined in:
lib/datastructures/adjacency_list.rb

Overview

Implements an Adjacency list with indexed nodes

Defined Under Namespace

Classes: ALNode

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(named = false) ⇒ AdjacencyList

Returns a new AdjacencyList Nodes are accessed with unique names if :named is true, otherwise they are accessed with integer indices (default).



13
14
15
16
 
# File 'lib/datastructures/adjacency_list.rb', line 13

def initialize(named=false)
  @nodes = {}
  @edges = {}
end

Instance Attribute Details

#edges ⇒ Object

Returns the value of attribute edges.



8
9
10
 
# File 'lib/datastructures/adjacency_list.rb', line 8

def edges
  @edges
end

Instance Method Details

#add(value, nodeidentifier, edges = Array.new) ⇒ Object

Assignment - adds a new node with :value, and :nodeidentifier, and optionally an array of identifiers of other nodes defining :edges. Returns self, so that assignments can be chained.



22
23
24
25
26
27
 
# File 'lib/datastructures/adjacency_list.rb', line 22

def add(value, nodeidentifier, edges=Array.new)
  node = ALNode.new(value)
  @nodes[nodeidentifier] = node
  @edges[nodeidentifier] = edges
  self
end

#add_edge(x, y) ⇒ Object

Adds an edge from node with identifier :x to node with identifier :y.



57
58
59
 
# File 'lib/datastructures/adjacency_list.rb', line 57

def add_edge(x, y)
  @edges[x] << y
end

#adjacent?(x, y) ⇒ Boolean

True if :x and :y are connected by an edge.

Returns:

  • (Boolean) 


62
63
64
 
# File 'lib/datastructures/adjacency_list.rb', line 62

def adjacent?(x, y)
  @edges[x].include?(y) || @edges[y].include?(x)
end

#delete(nodeidentifier) ⇒ Object

Removal - deletes the node at :nodeidentifier, which should be an integer index if this is an indexed adjacency list, or the name of the node if this is a names adjacency list.



32
33
34
35
36
 
# File 'lib/datastructures/adjacency_list.rb', line 32

def delete(nodeidentifier)
  node = @nodes[nodeidentifier]
  @nodes[nodeidentifier] = nil
  @edges.delete node
end

#delete_edge(nodeidentifier, *edges) ⇒ Object

Removal - deletes the edge(s) :edges connected to the node referenced by :nodeidentifer.



40
41
42
43
 
# File 'lib/datastructures/adjacency_list.rb', line 40

def delete_edge(nodeidentifier, *edges)
  alledges = @edges[nodeidentifier]
  edges.each { |edge| alledges.delete edge }
end

#get_node_value(nodeidentifier) ⇒ Object

Returns the value of the node with :nodeidentifier



46
47
48
 
# File 'lib/datastructures/adjacency_list.rb', line 46

def get_node_value nodeidentifier
  @nodes[nodeidentifier].value
end

#neighbours(nodeidentifier) ⇒ Object

Return an array of identifiers of all nodes connected to node at :nodeidentifier by edges.



68
69
70
 
# File 'lib/datastructures/adjacency_list.rb', line 68

def neighbours nodeidentifier
  @edges[nodeidentifier]
end

#set_node_value(nodeidentifier, value) ⇒ Object

Set with value of node at :nodeidentifier to :value



51
52
53
 
# File 'lib/datastructures/adjacency_list.rb', line 51

def set_node_value(nodeidentifier, value)
  @nodes[nodeidentifier].value = value
end

#to_s ⇒ Object

Return a string representation of the graph



73
74
75
76
77
78
79
 
# File 'lib/datastructures/adjacency_list.rb', line 73

def to_s
  s = ""
  @nodes.each do |identifier, node|
    s += "#{identifier} (#{node.value}) => #{@edges[identifier]} \n"
  end
  s
end