Adjacency list and graph

Question

I'm trying to build a graph by adjacency list, which means I need a list for all the nodes, and inside every node class, I also need a data structure to hold all the adjacent nodes. Just wondering what the best structure would be to do this (a fast search for target node class). Would an array work?

Answer 1

Here's one way of building a directed graph in Ruby, where each node maintains references to its successors, but nodes can be referenced by name. First we'll need a class for the nodes:

class Node

  attr_reader :name

  def initialize(name)
    @name = name
    @successors = []
  end

  def add_edge(successor)
    @successors << successor
  end

  def to_s
    "#{@name} -> [#{@successors.map(&:name).join(' ')}]"
  end

end

Each node maintains references to its successors. Not knowing what kind of operations you need, I haven't defined any that actually do graph traversal, but each node having references to its successors makes traversing the graph trivial.

Now we'll create a class to represent the entire graph:

class Graph

  def initialize
    @nodes = {}
  end

  def add_node(node)
    @nodes[node.name] = node
  end

  def add_edge(predecessor_name, successor_name)
    @nodes[predecessor_name].add_edge(@nodes[successor_name])
  end

  def [](name)
    @nodes[name]
  end

end

This class keeps a hash of its nodes, keyed by name. This makes retrieval of a specific node easy.

Here's an example of a graph containing a cycle:

graph = Graph.new
graph.add_node(Node.new(:a))
graph.add_node(Node.new(:b))
graph.add_node(Node.new(:c))
graph.add_edge(:a, :b)
graph.add_edge(:b, :c)
graph.add_edge(:c, :a)
puts graph[:a]    #=> a -> [b]
puts graph[:b]    #=> b -> [c]
puts graph[:c]    #=> c -> [a]