Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 7 of 7

Thread: All the paths between 2 nodes in a graph

  1. #1
    Junior Member
    Join Date
    May 2012
    Posts
    3
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default 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
    //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
    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
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    22,252
    Thanks
    56
    Thanked 2,372 Times in 2,343 Posts

    Default Re: All the paths between 2 nodes in a graph

    If you don't understand my answer, don't ignore it, ask a question.

  3. #3
    Junior Member
    Join Date
    May 2012
    Posts
    3
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default 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.
    Last edited by Alhazred; May 15th, 2012 at 04:37 AM.

  4. #4
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    22,252
    Thanks
    56
    Thanked 2,372 Times in 2,343 Posts

    Default Re: All the paths between 2 nodes in a graph

    I was telling the other volunteers about the other posts so they don't waste time answering questions that have already been answered.
    If you don't understand my answer, don't ignore it, ask a question.

  5. #5
    Junior Member
    Join Date
    May 2012
    Posts
    3
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default 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.

  6. #6
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    22,252
    Thanks
    56
    Thanked 2,372 Times in 2,343 Posts

    Default 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?
    If you don't understand my answer, don't ignore it, ask a question.

  7. #7
    Administrator copeg's Avatar
    Join Date
    Oct 2009
    Location
    US
    Posts
    5,370
    Thanks
    183
    Thanked 836 Times in 779 Posts
    Blog Entries
    5

    Default Re: All the paths between 2 nodes in a graph

    Suggested reading:
    The problems with cross-posting

Similar Threads

  1. Need help with Java's Paths class
    By mshock79 in forum What's Wrong With My Code?
    Replies: 1
    Last Post: April 16th, 2012, 02:41 PM
  2. Euler Paths with dfs algorithm problem
    By claudio.r in forum Algorithms & Recursion
    Replies: 18
    Last Post: March 22nd, 2012, 05:39 PM
  3. Replies: 1
    Last Post: February 11th, 2012, 07:38 AM
  4. Java Bar graph takes user input to create graph?
    By kenjiro310 in forum What's Wrong With My Code?
    Replies: 1
    Last Post: March 31st, 2011, 08:37 AM
  5. Probelm in Path and Paths Classes
    By neo_2010 in forum File I/O & Other I/O Streams
    Replies: 4
    Last Post: July 14th, 2009, 11:39 AM