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

Page 1 of 1

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

### #1 Alhazred

• D.I.C Head

Reputation: 9
• Posts: 191
• Joined: 25-July 07

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

Posted 18 June 2012 - 11:07 AM

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

• Games, Graphs, and Auctions

Reputation: 11449
• Posts: 43,160
• 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

• D.I.C Head

Reputation: 9
• Posts: 191
• 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

• Cabbage

Reputation: 2244
• Posts: 4,722
• 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

• D.I.C Head

Reputation: 9
• Posts: 191
• 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

• Cabbage

Reputation: 2244
• Posts: 4,722
• 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

• Cabbage

Reputation: 2244
• Posts: 4,722
• 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

• D.I.C Head

Reputation: 9
• Posts: 191
• 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

• Cabbage

Reputation: 2244
• Posts: 4,722
• 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

 .related ul { list-style-type: circle; font-size: 12px; font-weight: bold; } .related li { margin-bottom: 5px; background-position: left 7px !important; margin-left: -35px; } .related h2 { font-size: 18px; font-weight: bold; } .related a { color: blue; }