Beefy Boxes and Bandwidth Generously Provided by pair Networks
There's more than one way to do things
 
PerlMonks  

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

by BrowserUk (Pope)
on Nov 01, 2010 at 09:37 UTC ( #868713=note: print w/replies, xml ) Need Help??


in reply to Re^4: 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

What's the time complexity of findPaths()?

Um... O(lots) :). Honestly, I haven't got a clue how you go about assessing that.

It will be entirely dependant upon the complexity of the graph. Not just the number of nodes, but the number of connections at each node. And I don't have the math to make that kind of assessment.

I'd say that if your graphs are big enough for you to worry about it, then you'd probably be better of looking at an iterative solution rather than a recursive. Though often, iterative solutions that just emulate the recursion through manual stack handling are no more efficient, and often much less so.

I think the main cost of my routine is the memory allocations for the results sets. If your application only need to process one results set at a time, rather than having them all available, then I'd be looking for an iterator solution.

FWIW (which is not much IMO), the literature says that breadth-first and depth-first are both O(Bd) worst case.


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.
  • Comment on Re^5: Finding All Paths From a Graph From a Given Source and End Node

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others taking refuge in the Monastery: (8)
As of 2020-04-05 01:01 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    The most amusing oxymoron is:
















    Results (33 votes). Check out past polls.

    Notices?