There are several optimizations that the shortest path algo does that allSimplePaths doesn't, f.ex:
* Traversal is bidirectional (it starts from the start AND the end simultaneously, although in the same thread) which means that the deeper the traversal goes the more it gains compared to a single directional traversal * It stops on the depth it finds the first hit on Shortest path algo is implemented from scratch to be optimized for just that, but allSimplePaths uses traversal framework which doesn't support bidirectional traversals yet, although there have been some experiments with that too so perhaps soon! 2011/11/24 Peter Neubauer <peter.neuba...@neotechnology.com> > Petar, > very cool if this worked out. Maybe you could write up a testcase that > verifies that the results are the same, and then put this as a fork to > the graphalgo package? Sounds like a great addition if this works out? > > Cheers, > > /peter neubauer > > GTalk: neubauer.peter > Skype peter.neubauer > Phone +46 704 106975 > LinkedIn http://www.linkedin.com/in/neubauer > Twitter http://twitter.com/peterneubauer > > http://www.neo4j.org - NOSQL for the Enterprise. > http://startupbootcamp.org/ - Öresund - Innovation happens HERE. > > > > On Thu, Nov 24, 2011 at 11:42 AM, Petar Dobrev <peter.dob...@gmail.com> > wrote: > > Hi guys, > > > > I have a graph of about 2.5M nodes and 8M relationships and I am trying > to > > find all simple paths between two nodes with maximum depth of 8. > > > > The allSimplePaths graph algo works well for maximum depth of 5, but for > 8 > > it runs really long (I didn't even wait for it to finish). So I thought > > it's just that the graph is too complicated and the search operation is > > very expensive. > > > > On the other hand I noticed that shortestPath and pathsWithLength both > work > > fast. So I tried this experiment: > > > > - Run shortestPath and record the shortest length > > - Iterate from the shortest length to max_depth > > - Run pathsWithLength and append the results > > - > > > > And it turns out to be working really well.. much, much faster than the > > allSimplePaths solution, which I found quite baffling, since the latter > > solution should be doing more work to accomplish the same task. > > > > Maybe it's just with my graph, but it's still weird. > > > > Best regards, > > Petar > > _______________________________________________ > > Neo4j mailing list > > User@lists.neo4j.org > > https://lists.neo4j.org/mailman/listinfo/user > > > _______________________________________________ > Neo4j mailing list > User@lists.neo4j.org > https://lists.neo4j.org/mailman/listinfo/user > -- Mattias Persson, [matt...@neotechnology.com] Hacker, Neo Technology www.neotechnology.com _______________________________________________ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
