Re^7: Finding All Paths From a Graph From a Given Source and End Node

[BrowserUk]

Did you also benchmark other code? Like in this post?

No.Here's the 5 million path tree, the command line and timing, but from a cursory glance at code you reference, you're going to require a lot (10GB or more) of memory.

c:\test>868031 -S=7529 A Z
{
  A => ["N", "W", "J", "L", "C", "E", "X", "T", "O", "H"],
  C => ["Z", "J", "Q", "U", "S", "T", "N", "P", "D", "O"],
  E => ["P", "G", "U", "F", "X", "A", "Y", "K"],
  H => ["W", "O", "J"],
  J => ["Z", "U", "B", "Q", "N", "I", "V", "F", "C", "P"],
  K => ["X", "H", "J", "C", "P", "W", "E", "S", "Q"],
  L => ["C", "B", "V", "A", "S", "J", "O", "H"],
  N => ["R", "G", "K", "N", "Q", "W", "C", "U", "E", "V"],
  O => ["K", "G", "X", "A", "Z", "W"],
  P => ["O", "G", "F", "T", "E", "U", "L", "H", "B", "R"],
  Q => ["V", "N", "X", "U", "D", "M", "S", "C", "R", "G"],
  R => ["D", "S", "K", "X", "O", "U"],
  S => ["Q", "E", "T", "P", "G", "Z"],
  U => ["Y", "V", "U", "X", "R", "W", "M", "G", "K", "N", "A"],
  W => ["P", "E", "G", "Y"],
  X => ["Z", "H", "R", "L", "J", "W", "A", "E", "X", "T", "D"],
  Y => ["J", "X", "G"],
  Z => ["K", "A", "Z"],
}

5014604 FP2 took 981.75 secs for 5014604 paths

If you prefer the 10,000 path graph as a test:

c:\test>868031 -S=7367 A Z
{
  A => ["F", "B", "U", "Z", "J", "C", "Q", "H"],
  D => ["W", "X", "F", "M", "K", "Y"],
  G => ["E", "P", "U"],
  H => ["K", "Q", "S", "T", "X", "G", "D", "B"],
  I => ["U", "Q", "K", "D"],
  K => ["O", "R", "A", "L", "X", "N", "C", "M"],
  L => ["G", "I", "A", "O", "N", "J", "D", "S", "R", "V", "M"],
  N => ["K", "L", "V", "Z", "U"],
  O => ["W", "K", "D", "I", "A", "J", "M", "T", "Y", "Z", "P"],
  P => ["B", "G"],
  R => ["V", "B", "G", "P"],
  T => ["M", "I", "N", "K", "D", "U", "A", "V", "W"],
  U => ["V", "Z", "J", "A", "E"],
  V => ["M", "G", "O", "F", "W", "Y", "P", "S"],
  X => ["K", "S", "B", "P", "N", "T", "W", "Z", "H", "R", "F"],
  Y => ["Q", "K", "J", "U", "G", "M", "P"],
  Z => ["A", "M", "Z", "Q", "W", "N", "G", "J", "L", "H"],
}

10062   FP2 took 2.10 secs for 10062 paths

(I can't see the point in copying around the %seen hash 1) or even the current path of a DFS. :) Furthermore this code can be easily linearized to avoid the function-call overhead...In general there are still plenty of possible optimizations left to speed up such a search.

Improvements or alternatives welcome :) . I'm not claiming the fastest on the block, just better than my own previous efforts.

neversaint expressed his interest in the time complexity of my previous version, so I set out to improve it. Given the combinatorial explosion that can result from the all-paths traversal of apparently quite simple graphs, moving to an iterator rather than an accumulating generator seemed the logical route.

[LanX]

> but from a cursory glance at code you reference, you're going to require a lot (10GB or more) of memory.

Why?

I'm just running it on my busy netbook with actually 4080000 at sec 1230! ¹

1) actually I don't immediately know how to cleverly monitor memory consumption of perls datastructures but ps -aux is stable:

USER       PID %CPU %MEM    VSZ   RSS TTY      STAT START
lanx     23724 99.4  0.2   5384  2492 pts/0    Rs+  15:30  16:24 /usr/
+bin/perl -w /tmp/graph_path.pl

update: 5014604 in 1562 secs

[BrowserUk]

Why?

Because to be useful, you generally have to do something more than just print the path out as a string.

To make it useful, you'd have to either:

• accumulate all the paths as (say) an array of arrays:

  5 million paths with an average of roughly 20 items per.

• or turn it into an iterator, so the code using the routines results can operate on the one at a time.

  Which is what I did with mine.

• or; write all 5 million paths to disk as strings and then read them all back in again.

  In addition to the ovrhead of the IO, you also have to join them and then split them again.

I'd try your routine here,but I can't work out where I supply the start and end?

[LanX]

I'd try your routine here,but I can't work out where I supply the start and end?

Globals! See the post before. (there is no point in passing them as long as you don't use any divide and conquer approach)

or just:

Read more... (4 kB)

Of course @path could be global too and the recursion could be liniarized...

Not talking about nifty short circuit algorithms...

[LanX]

ehm? :)

Z => ["K", "A", "Z"],

[BrowserUk]

ehm? :) Z => "K", "A", "Z",

I assume from that you are complaining that the graph has a self-referential node?

But why? A graph with self referencing nodes is still a graph, and algorithms have to handle them.

Is my (currently running) run of your algorithm ever going to stop

It did.! Just counting, it took 12% longer than mine which invokes a callback for each path.

c:\test>junk
5014604
458

[LanX]

It did.! Just counting, it took 12% longer than mine which invokes a callback for each path.

interesting ... I'll take a look at it tomorrow!

UPDATE: I expected this part { %$seen } to be quite expensive .... does it even make sense?