Beefy Boxes and Bandwidth Generously Provided by pair Networks
We don't bite newbies here... much
 
PerlMonks  

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

by LanX (Cardinal)
on Nov 02, 2010 at 14:53 UTC ( #869006=note: print w/replies, xml ) Need Help??


in reply to Re^7: Finding All Paths From a Graph From a Given Source and End Node
in thread Finding All Paths From a Graph From a Given Source and End Node

> 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!

Cheers Rolf

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

  • Comment on Re^8: Finding All Paths From a Graph From a Given Source and End Node
  • Download Code

Replies are listed 'Best First'.
Re^9: Finding All Paths From a Graph From a Given Source and End Node
by BrowserUk (Pope) on Nov 02, 2010 at 15:12 UTC
    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?


    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.
      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:

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

      Not talking about nifty short circuit algorithms...

      Cheers Rolf

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://869006]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others lurking in the Monastery: (6)
As of 2021-01-19 18:39 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    Notices?