[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.ruby

rgl and vertices on path

meruby

2/1/2006 3:51:00 AM

How can get list of vertices from start node to end node in rgl?

For example:

require 'rgl/adjacency'
dg=RGL::DirectedAdjacencyGraph[1,2 ,2,3 ,2,4, 4,5, 6,4, 1,6]

How to do following?
get_path(1,5) should give [1,2,4,5] or [1,6,4,5] or both

Thanks in advance
2 Answers

Matthew Smillie

2/2/2006 12:10:00 AM

0


On Feb 1, 2006, at 21:49, meruby@gmail.com wrote:

> How can get list of vertices from start node to end node in rgl?
>
> For example:
>
> require 'rgl/adjacency'
> dg=RGL::DirectedAdjacencyGraph[1,2 ,2,3 ,2,4, 4,5, 6,4, 1,6]
>
> How to do following?
> get_path(1,5) should give [1,2,4,5] or [1,6,4,5] or both
>
> Thanks in advance

If you just to find one or two paths per graph, you can use breadth-
first search, keeping track of visited nodes at each step.

There's a breadth-first iterator in rgl which might help with this,
combined with a graph visitor to track the visited nodes. Remember
that not all directed graphs have paths between all nodes.

If you know something about the structure of the graphs you're
expecting, you might be able to come up with something slightly
better, but the breadth-first search will work.

matthew smillie.

Horst Duchene

2/6/2006 1:52:00 PM

0

Matthew Smillie schrieb:

> On Feb 1, 2006, at 21:49, meruby@gmail.com wrote:
>
> > How can get list of vertices from start node to end node in rgl?
> >
> > For example:
> >
> > require 'rgl/adjacency'
> > dg=RGL::DirectedAdjacencyGraph[1,2 ,2,3 ,2,4, 4,5, 6,4, 1,6]
> >
> > How to do following?
> > get_path(1,5) should give [1,2,4,5] or [1,6,4,5] or both
> >
> > Thanks in advance
>
> If you just to find one or two paths per graph, you can use breadth-
> first search, keeping track of visited nodes at each step.
>
> There's a breadth-first iterator in rgl which might help with this,
> combined with a graph visitor to track the visited nodes. Remember
> that not all directed graphs have paths between all nodes.
>
Using BFS is the right way. As an example usage have a look at the
method RGL::Graph#bfs_search_tree_from
(http://rgl.rubyforge.org/rgl/classes/RGL/Graph.ht...):

Returns a DirectedAdjacencyGraph, which represents a BFS search tree
starting at v. This method uses the tree_edge_event of BFSIterator to
record all tree edges of the search tree in the result.

# File lib/rgl/traversal.rb, line 238
238: def bfs_search_tree_from (v)
239: require 'rgl/adjacency'
240: bfs = bfs_iterator(v)
241: tree = DirectedAdjacencyGraph.new
242: bfs.set_tree_edge_event_handler { |from, to|
243: tree.add_edge(from, to)
244: }
245: bfs.set_to_end # does the search
246: tree
247: end

However you will not get all paths between two given nodes, but only a
single one which is determined by the actual sequence of the neigbors
of the visited vertices. If the adjacency list is a set, this sequence
is undefined. Getting all paths between two vertices is an exhaustive
search, which is very inefficient for larger graphs.

Horst Duchêne