## Finding all paths

2009-01-29
2013-05-29
• James Shailes - 2009-01-29

Hi. I've been reading the documentation and can't seem to find the an implementation that returns Set<List<Edge>> (or something similar) in order to find all of the paths from one vertex to another (as opposed to just the shortest path). I'm suprised if there isn't one already but if this is the case I'm happy to write something and submit it. Maybe everyone just see's this as too simpler task!

James

• James:

The reason why this doesn't exist in the library is that finding all paths requires time exponential in the size of the graph.

I doubt you actually want _all_ paths.  What problem are you trying to solve?

Joshua

• James Shailes - 2009-01-30

Hi Joshua,

Thanks for your reply. We are currently trying to model the uk rail infrastructure in which there are many routes from one signal to another (albeit only 1 or two)

-------------------------F--H---J---------------------------
/   /   /
-----------1------A---E-G--I-------D--------------2---
\&nbsp;           /
---------------------B---------C-------------------------

Hopefully my diagram above can illustrate this: the train could move from signal 1 through to 2 via:
1-A
A-E
E-G
G-I
I-D
D-2

or

1-A
A-B
B-C
C-D
D-2

I need to return only the prefered route, which in this case is not the shortest path - the train would rather stay on the same line. If I could return all routes then I could analyse them to find out which route uses the minimum number of lines.

Does that make any sense?

• James:

There are an exponential number of paths in the general case, so even iterating through them all would require exponential time.

That said, you've clarified something that I expected: that you're actually trying to solve an optimization problem that simply happens to look a lot like a shortest path problem.

JUNG can provide the infrastructure--the graph representation over which the algorithm will run--but you'll need to write the 'preferred route' algorithm yourself.

If I correctly understand what you're proposing (and you haven't left out any constraints) then you might be able to solve this most readily as follows:

Create a new graph in which each _line_ is represented by a single vertex, and two vertices are connected if you can transfer from one line to the other.  Then this becomes a shortest-path problem on the reduced graph.  (Once you've got that path, you still need to figure out where to transfer from one line to the other, and there are other constraints in practice, e.g., schedules and time spent in transit, but that at least solves the stated problem, I think.)

Joshua

• James Shailes - 2009-01-30

I forgot to mention something rather fundamental: A path is dismissed if it goes through a numbered node (signal node) that is not the signal node we are looking for. So for example if F in the example above had been signal node 3 then the search for a path between 1 and 2 would be dismissed and backtracking would then take place to try another path.
My apologies for not mentioning that sooner, I believe this is what makes the algorithm non-exponential.

Regards,

James