# All the paths between 2 nodes in a graph

• May 14th, 2012, 06:16 PM
Alhazred
All the paths between 2 nodes in a graph
I have a graph with not directed and which have cycles.
I need to find all the paths between 2 given nodes.

I've been able to write the code to find one path using BFS algorithm, but I can' modify it to make it return a list of all the paths.

This is my graph class
Code :

```//unuseful methods omitted to shorten the code public class Graph<V,E> {   HashMap<Vertex<V>, List<Edge<V,E>>> graph;   public Graph() { graph = new HashMap<Vertex<V>, List<Edge<V,E>>>(); }   /** * @return true if 2 nodes are adjacent */ public boolean areAdjacent(Vertex<V> source, Vertex<V> destination)   /** * @return all the edges in the graph */ public Collection<Edge<V,E>> edges()   /** * @return edge between 2 vertices */ public Edge<V,E> getEdge(Vertex<V> source, Vertex<V> destination)   /** * @return edges outgoing from source */ public Collection<Edge<V,E>> outEdges(Vertex<V> source)   /**   * @return vertices reachable from source */ public Collection<Vertex<V>> outVertices(Vertex<V> source)   /** * @return all the vertices in the graph */ public Collection<Vertex<V>> vertices() }```

This is the BFS function
Code :

```public static List<Vertex<String>> bfs(Graph<String,Integer> g, Vertex<String> source, Vertex<String> destination) { Queue<Vertex<String>> queue = new ArrayDeque<Vertex<String>>(); HashSet<Vertex<String>> marked = new HashSet<Vertex<String>>();   List<Vertex<String>> path = new ArrayList<Vertex<String>>(); //will contain the vertices in the path found   queue.add(source); marked.add(source); while(!queue.isEmpty()) { Vertex<String> u = queue.remove();   path.add(u);   if(u.equals(destination)) { break; }   for(Vertex<String> v : g.outVertices(u)) { if(!marked.contains(v)) { queue.add(v); marked.add(v); } } } return path; }```
It returns the list of vertices conteined in the first path found.
How do I have to modify the BFS function to make it find all the paths between the 2 given vertices and return a list of all those paths?
• May 14th, 2012, 06:52 PM
Norm
Re: All the paths between 2 nodes in a graph
• May 15th, 2012, 03:28 AM
Alhazred
Re: All the paths between 2 nodes in a graph
And that's another forum, what's the problem?
Crossposting is inside the same forum not between different.

I think everybody is free to ask the same question to different persons, isn't it?
I fyou have something else to tell me, plese send me a private message, so that the thread will not go OT.
Thank you.
• May 15th, 2012, 05:34 AM
Norm
Re: All the paths between 2 nodes in a graph
• May 15th, 2012, 06:14 AM
Alhazred
Re: All the paths between 2 nodes in a graph
Thanks to have heard to my request to reply by private message...

By the way I've solved by myself.
• May 15th, 2012, 06:15 AM
Norm
Re: All the paths between 2 nodes in a graph
That is what you are supposed to do.

Did you post that on the other forums so volunteers there know the problem is solved?
• May 15th, 2012, 07:49 AM
copeg
Re: All the paths between 2 nodes in a graph