Adjacency list and graph

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(' ')}]"  endend

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]  endend

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.newgraph.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]