class DataStructures::AdjacencyList

Implements an Adjacency list with indexed nodes

Constants

ALNode

Attributes

edges[RW]

Public Class Methods

new(named=false) click to toggle source

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

# File lib/datastructures/adjacency_list.rb, line 13
def initialize(named=false)
  @nodes = {}
  @edges = {}
end

Public Instance Methods

add(value, nodeidentifier, edges=Array.new) click to toggle source

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.

# 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) click to toggle source

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

# File lib/datastructures/adjacency_list.rb, line 57
def add_edge(x, y)
  @edges[x] << y
end
adjacent?(x, y) click to toggle source

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

# File lib/datastructures/adjacency_list.rb, line 62
def adjacent?(x, y)
  @edges[x].include?(y) || @edges[y].include?(x)
end
delete(nodeidentifier) click to toggle source

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.

# 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) click to toggle source

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

# 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) click to toggle source

Returns the value of the node with :nodeidentifier

# File lib/datastructures/adjacency_list.rb, line 46
def get_node_value nodeidentifier
  @nodes[nodeidentifier].value
end
neighbours(nodeidentifier) click to toggle source

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

# File lib/datastructures/adjacency_list.rb, line 68
def neighbours nodeidentifier
  @edges[nodeidentifier]
end
set_node_value(nodeidentifier, value) click to toggle source

Set with value of node at :nodeidentifier to :value

# File lib/datastructures/adjacency_list.rb, line 51
def set_node_value(nodeidentifier, value)
  @nodes[nodeidentifier].value = value
end
to_s() click to toggle source

Return a string representation of the graph

# 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