Flexible graph library - sans hash

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.

regards.

-a

On 6/28/06, [email protected] [email protected] wrote:

i’m coding a FSM class so i need to be able to have multiple labeled edges
from u -->> v.

Try Graphviz - Graph Visualization Software (http://www.graphviz.org/)
it is driven by a simple text language, which is easy to generate and
drive from Ruby.

pth

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.

Phil

Wow I feel stupid, not enough sleep and the word graph, I thought you
were trying to visualize a FSM. Implementing a graph – I have used a
hash of arrays and other times I have used a list of lists (when my
states had a numeric or at least sequential index).

Good thing I am off on vacation, good luck
pth

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

Phil

On Thu, 29 Jun 2006, Patrick H. wrote:

Wow I feel stupid, not enough sleep and the word graph, I thought you
were trying to visualize a FSM. Implementing a graph – I have used a
hash of arrays and other times I have used a list of lists (when my
states had a numeric or at least sequential index).

Good thing I am off on vacation, good luck
pth

no problem - i was actually trying to both. i’ve built something on top
of
robert felt’s graphing toolkit which includes simple visulization, dsl
for
building state machines, and a blocking thread-safe state change
notification.

roberts toolkit had support for multiple edges with metadata between
states.

i’ll try to put out a release soon.

regards.

-a

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

This forum is not affiliated to the Ruby language, Ruby on Rails framework, nor any Ruby applications discussed here.

| Privacy Policy | Terms of Service | Remote Ruby Jobs