On 6/28/06, Phil T. [email protected] wrote:
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