Perl Monk, Perl Meditation  
PerlMonks 
Re: Short Circuiting DFS Graph Traversalby LanX (Archbishop) 
on Oct 31, 2010 at 12:05 UTC ( #868576=note: print w/replies, xml )  Need Help?? 
A little demonstration why trying to calculate _all_ path is a dangerous thing. let Nx be the graph of a x dimensional cube where the edges are bidirectionally connections of 2^x nodes representing the corners.
When calculating paths between extremal corners you will see: N2 (the square) has 4 corners and 2 such paths N3 (the normal cube) has 8 corners and 18 paths (e.g. 000>001>011>010>110>100>101>111 ) N4 has 16 corners and already 6432 paths N5 has 32 corners and the program to calculate all paths is still running and will likely never finish! I really doubt that such a general question is a clever approach. (for comparison the number of _shortest_ paths is "only" x! i.e. 5!=120 for N5) IMHO not only a clear case of an XY question but already XYZ, any underlying question is either far more trivially answered¹ or is simply not solvable. This approach to precalculate all path will potentially damage the hardware.
Cheers Rolf ¹) e.g. can a node K be part of a path from B to E?
In Section
Seekers of Perl Wisdom

