On 6/28/06, Phil Tomson <rubyfan / gmail.com> wrote:
> On 6/28/06, ara.t.howard / noaa.gov <ara.t.howard / noaa.gov> wrote:
> >
> > anyone out there know of a graph library that doesn't use a hash in the impl,
> > thereby restricting only one edge from u -->> v?  i've used rgl extensively in
> > the past but it uses a hash under the hood and has this restriction.
> >
> > i'm coding a FSM class so i need to be able to have multiple labeled edges
> > from u -->> v.
> >
>
> Why can't you use a hash of arrays?
>
> graph = { 'a'=>['b','c'],
>              'b'=>['a'],
>              'c'=>['b', 'c']  }
>
> I've used that sort of structure for FSMs in the past.
>

Oh, now that I reread the request, it seems you need to do something like:

graph = { 'a' => ['b', 'b', 'c'] ...}

correct?  But then maybe this hash of arrays isn't all that useful, or
perhaps you need one more level, like:

graph = { 'a' => [ { 'b' => 'label1'}, {'b'=>'label2'}, {'c'=>'labelA2C'}] ... }


I can't remember how many times I've implemented FSM classes (I've
lost count), but the big question always seems to be do I need an Edge
class of some sort or are the edges implicit in the graph data
structure (it can go either way depending on what you need to do with
the graph).
It's kind of like looking at one of those optical illusions where at
one moment the ink defines what you perceive and at another moment
it's the whitespace... or something like that.  But in this case where
you can have multiple edges going from u-->v  maybe it would be
probably be helpful to have an edge class.


If you had Nodes and Edges, like so:

class Node
  def initialize(name, &action)
    @name = name
    @action = action
  end
  def do_action
    @action.call
  end
  attr_accessor :name
end

class Edge
  #you could probably also put conditions
  #here as in the condition that will
  #activate this transition from the 'from'
  #state to the 'to' state
  def initialize(from, to, label)
    @from, @to = from,to
  end
  attr_accessor :from, :to, :label
end

#and an FSM class to keep track of it all:
class FSM
  attr_accessor :nodes, :graph
  def initialize( *nodes) #note: starting node should be first
    @start = start_node
    @nodes = nodes
    @graph = Hash.new {|hash,key| hash[key] = [] }
  end
  def add_edge edge
    @graph[edge.from] << edge
  end

end

... or something along those lines.  Then you have a hash keyed by the
nodes where each node points to a list of edges which start from that
node (and you can always get the destination node from the edge).

Phil