#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    May 2012
    Posts
    2
    Rep Power
    0

    [Solved] 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?
  2. #2
  3. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    May 2012
    Posts
    2
    Rep Power
    0
    Problem solved.

IMN logo majestic logo threadwatch logo seochat tools logo