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.html#M000067):

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