laziness, impatience, and hubris PerlMonks

### Re: Short Circuiting DFS Graph Traversal

by LanX (Cardinal)
 on Oct 31, 2010 at 12:05 UTC ( #868576=note: print w/replies, xml ) Need Help??

in reply to Short Circuiting DFS Graph Traversal

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.

```  101--111
/:   /|
001--011|
|100·|110          N3
|·   |/
000--010

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?

Create A New User
Node Status?
node history
Node Type: note [id://868576]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others exploiting the Monastery: (7)
As of 2021-01-18 10:47 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
The STEM quote I most wish I'd made is:

Results (177 votes). Check out past polls.

Notices?