class DataStructures::AdjacencyList
Implements an Adjacency list with indexed nodes
Constants
- ALNode
Attributes
Public Class Methods
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
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
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
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
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
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
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
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 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
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