8 Replies - 11549 Views - Last Post: 19 June 2012 - 09:58 AM

#1 Alhazred  Icon User is offline

  • D.I.C Head

Reputation: 9
  • View blog
  • Posts: 181
  • Joined: 25-July 07

How to find all the paths between two nodes of a multigraph

Posted 18 June 2012 - 11:07 AM

Posted Image
This image represents an ipotetical subway network.
Letters are stations' names, numbers are lines' names.

I want to create an app for Android, but before I need to solve this problem (creating a normal Java application, so no Android API):
given 2 random stations I have to find all the routes between them, discarding those which make me change alternatively a line.
In example from A to F
A --(line 1)--> B --(line 1)--> C --(line 2)--> F
is a good route
A --(line 2)--> B --(line 1)--> C --(line 2)--> F
must be discarded

This part shouldn't be difficult since I've wrote the code to manage a simple graph and it works.
My problem start when the network becomes a multigraph, I'm working on it by days and can't think anything good to modify my code.

My solution for a simple graph has been to use a BFS in this way (part of the code and support classes are omitted):
public List<Path> bfs(GraphImpl<String,Integer> g,
                              LinkedList<VertexImpl<String>> visited,
                           List<Path> paths,
                           VertexImpl<String> destination) {

        //vertices reachable from the current vertx
        Collection<VertexImpl<String>> nodes = g.outVertices(visited.getLast());
        //check the adjacent vertices
        for (VertexImpl<String> node : nodes) {
            if (visited.contains(node)) { //if the current vertex has already been visited
                continue;
            }

            if (node.equals(destination)) { //if the current vertex is the destination
                visited.add(node);

                boolean buono   = true;        //says if the path is good
                boolean inarray = false;    //says if a line is already into the array

                Iterator<VertexImpl<String>> li = visited.iterator();
                VertexImpl<String> v1 = null;
                VertexImpl<String> v2 = null;
                String lineaTemp = ""; //last line used
                String[] linee = new String[20];
                for(int k=0; k<20; k++) linee[k] = ""; //initialize the lines' array
                int i = 0;

                v1 = li.next(); //starting vertex in the segment
                while(li.hasNext()) {
                    v2 = li.next(); //arrivel vertex in the segment

                    EdgeImpl<String,Integer> edge = g.getEdge(v1,v2); //edge which liks v1 and v2

                    if(lineaTemp.equals("")) { //this is the 1st segment
                        lineaTemp = edge.getLine();
                        linee[i]  = edge.getLine();
                        i++;
                    } else { //non è la prima tratta
                        if(!lineaTemp.equals(edge.getLine())) {         //if the current line is different from the previous (there has been a line change)
                               for(int j=0;j<linee.length;j++) {             //for each line already used
                                   if(linee[j].equals(edge.getLine())) {     //if one is equal to the current
                                       inarray = true;                        //match found
                                   }
                               }
                               if(!inarray) { //if the current line was not already used
                                   lineaTemp = edge.getLine(); //update the last line used
                                   linee[i]  = edge.getLine(); //add the line to the used lines' array
                                   i++;
                               } else { //I'm using again a line from which I changed
                                   buono = false;     //the path is not good
                                   inarray = false; //reset inarray variable
                               }
                        } else { //the path is good
                            buono = true;
                            inarray = false;
                        }
                    }

                    v1 = v2; //arrival station become the start for the next segment
                }

                if(buono) { //if the path is good, add it to the paths list
                    //omitted for brevity
                }

                   visited.removeLast(); //remove the last visited station
                break;
            }
        }

        //BFS recursion
        for (VertexImpl<String> node : nodes) { //for each vertices reachable from the current
            if (visited.contains(node) || node.equals(destination)) { //if it was already visited or it is the destination
                continue;
            }
            visited.addLast(node); //mark as visited
            bfs(g, visited, paths, destination); //recursive call to the BFS
            visited.removeLast(); //remove the last visited vertex
        }

        return paths; //return the found paths
    }



List<Path> percorsi = new ArrayList<Path>();

//code which starts the search
LinkedList<VertexImpl<String>> visited = new LinkedList<VertexImpl<String>>();
visited.add(a); //add the start station to the visited vertices

//starts the search, f is the destination
List<Path> paths = new GraphUtil().bfs(gra, visited, percorsi, f);


If needed I can supply the whole code to make you try it.

This post has been edited by Alhazred: 18 June 2012 - 11:34 AM


Is This A Good Question/Topic? 1
  • +

Replies To: How to find all the paths between two nodes of a multigraph

#2 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10803
  • View blog
  • Posts: 40,260
  • Joined: 27-December 08

Re: How to find all the paths between two nodes of a multigraph

Posted 18 June 2012 - 12:52 PM

Quote

I want to create an app for Android, but before I need to solve this problem (creating a normal Java application, so no Android API):
given 2 random stations I have to find all the routes between them, discarding those which make me change alternatively a line.

Just to make sure I understand correctly, would the following be legal or illegal? Can we change lines multiple times? Can you more specifically outline the rules of the traversal?

A --(1)--> B --(2)--> E --(3)--> F
A --(2)--> B --(2)--> E --(3)--> F
Was This Post Helpful? 0
  • +
  • -

#3 Alhazred  Icon User is offline

  • D.I.C Head

Reputation: 9
  • View blog
  • Posts: 181
  • Joined: 25-July 07

Re: How to find all the paths between two nodes of a multigraph

Posted 18 June 2012 - 03:42 PM

Yes, they are legal.
Any route is legal except in one case: if I leave a line, I can't take it again for another segment.

From A to F, all the legal routes are:
A --(1)--> B --(2)--> E --(3)--> F
A --(1)--> B --(3)--> E --(3)--> F
A --(2)--> B --(2)--> E --(3)--> F
A --(2)--> B --(3)--> E --(3)--> F

A --(1)--> B --(1)--> C --(2)--> F

A --(1)--> B --(1)--> C --(2)--> E --(3)--> F

A --(1)--> B --(1)--> C --(1)--> D --(1)--> F
A --(2)--> B --(1)--> C --(1)--> D --(1)--> F

A --(1)--> B --(2)--> E --(2)--> C --(2)--> F
A --(1)--> B --(3)--> E --(2)--> C --(2)--> F
A --(2)--> B --(2)--> E --(2)--> C --(2)--> F
Was This Post Helpful? 0
  • +
  • -

#4 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 2069
  • View blog
  • Posts: 4,307
  • Joined: 11-December 07

Re: How to find all the paths between two nodes of a multigraph

Posted 18 June 2012 - 05:54 PM

I was thinking of a solution and found a problem. Are cycles such as these legal?

A --(1)--> B --(1)--> C --(1)--> E --(2)--> B --(3)--> E --(3)--> F
A --(1)--> B --(1)--> C --(1)--> D --(1)--> F --(1)--> G --(2)--> F

etc...
Was This Post Helpful? 0
  • +
  • -

#5 Alhazred  Icon User is offline

  • D.I.C Head

Reputation: 9
  • View blog
  • Posts: 181
  • Joined: 25-July 07

Re: How to find all the paths between two nodes of a multigraph

Posted 18 June 2012 - 11:12 PM

Well, they are not legal, I didn't took those routes into consideration because the BFS itself discards them since you visit twice one of the nodes and in that case the BFS passes over.

By the way, if the solution for this problem requires to use something different from a BFS, those routes must be discarded as well.

In any case, the second route would be wrong, it should stop at the first time that F is visited, that's the destination in the example.
Was This Post Helpful? 0
  • +
  • -

#6 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 2069
  • View blog
  • Posts: 4,307
  • Joined: 11-December 07

Re: How to find all the paths between two nodes of a multigraph

Posted 19 June 2012 - 01:57 AM

OK. A slightly modified BFS or DFS would do the job nicely. Any time you transition to a different line, mark all the edges of the line you came from as visited.
Was This Post Helpful? 0
  • +
  • -

#7 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 2069
  • View blog
  • Posts: 4,307
  • Joined: 11-December 07

Re: How to find all the paths between two nodes of a multigraph

Posted 19 June 2012 - 03:41 AM

Or better yet, have a map from Line Number to a boolean representing if it has already been used, and use this value when you check if an edge is allowed in your search. This will make it easier to roll back.
Was This Post Helpful? 0
  • +
  • -

#8 Alhazred  Icon User is offline

  • D.I.C Head

Reputation: 9
  • View blog
  • Posts: 181
  • Joined: 25-July 07

Re: How to find all the paths between two nodes of a multigraph

Posted 19 June 2012 - 04:25 AM

I know how to decide if a route is legal or not, I already do that and it works.

My problem with the multigraph is that the code, as it is now, only consider the 1st edge between two vertices.
In example to go from A to B, only Line 1 is used, Line 2 is never explored, and the same happens between B-E (only line 2 used) and F-G (only line 1 used).

I need to modify my code to make it explore all the edges so that in example it finds both
A --(1)--> B --(2)--> E --(3)--> F
A --(2)--> B --(2)--> E --(3)--> F

at the moment only the first is found.

This post has been edited by Alhazred: 19 June 2012 - 04:26 AM

Was This Post Helpful? 0
  • +
  • -

#9 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 2069
  • View blog
  • Posts: 4,307
  • Joined: 11-December 07

Re: How to find all the paths between two nodes of a multigraph

Posted 19 June 2012 - 09:58 AM

Here is how I would approach this. Apologies if it is what you are already doing.

Give each edge another field for line number.

Add all the edges into the same graph. (I suspect this is where you have been going wrong).

Have an array/list/set with the state of each line. This could be a simple boolean to represent weather it has been used yet or a new class if you think it should contain more information or methods.

Use a standard BFS or DFS algorithm (whichever you find easiest to code).

Modify it so that when you transition from one line to the other, it flips the state in the boolean array.

Use the value from the boolean array, in combination with weather an edge has been use already, to determine which edges are available for use.

When you roll back, remember to flip the bit in the line array.
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1