All,
In this node, neversaint asks how to find all paths between two nodes in a graph. The example graph is not weighted and since we are only interested in paths and not costs, this doesn't come into play. While the example graph is directed, I don't believe it matters.

Graph appears to have a method but it is unclear to me if it only finds all the shortest paths or all paths (I haven't tested). The straight forward approach is a depth first search (DFS). My question is if it is possible to efficiently short-circuit the search.

I have provided a short circuiting solution though I am not positive it is correct (limited test set). I also don't know if it is very efficient (optimizing for run time). The basic idea is this: At each node, a handful of conditions can apply.

• No nodes can be reached
• All of the reachable nodes are already part of the current path (cycle)
• We are at our destination (end point)
• More nodes can be reached

My short circuiting applies to the first two cases. If later on, I reach any node in this path again I can stop descending if my current path has all the same nodes as the completed path (any order) at the point the completed path is entered. I will try and provide an example of what I mean but also refer to the code.

R -> X -> T -> Y -> M -> F # Considered complete

R -> I -> T -> A -> X -> Y # Candidate for pruning
[download]

Since Y is in a path considered dead, I can short circuit if my path has an R, X and T in any order. I have only tested this hypothesis on two graphs. If this is not a safe assumption, please provide an example that disproves it and also offer any suggestions for short circuiting that you know to be viable.

Now assuming you have made it this far, the problem is that Y may be part of many completed paths. In order to determine if I can short circuit, I have to go through all of them until I find a match or reach the end. Depending on a number of factors (the graph, order of traversal, end points, etc), it can be more expensive keeping track of completed paths then just enumerating all of them. The thing that bothers me is that when more than one completed path share a single non-end point node in common then if one fails they all fail. Unfortunately, I haven't figured out how to group them together this way and still loop over all of them. Can you think of a way to do this more efficiently or do you know of an entirely different approach that is more efficient?

---

---

Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!

Titles consisting of a single word are discouraged, and in most cases are disallowed outright.

Read Where should I post X? if you're not absolutely sure you're posting in the right place.

Please read these before you post! —

• How do I compose an effective node title?
• How do I post a question effectively?
• Markup in the Monastery

Posts may use any of the Perl Monks Approved HTML tags:

a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr

You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)

	For:		Use:
	&		&
	<		&lt;
	>		&gt;
	[		&#91;
	]		&#93;

Link using PerlMonks shortcuts! What shortcuts can I use for linking?

See Writeup Formatting Tips and other pages linked from there for more info.