Matthew S. schrieb:

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