2011/11/25 Petar Dobrev <petar.dob...@myphilanthropedia.org> > Thanks for the explanation, Mattias! > > So, if I understand this correctly, due to some of > the optimizations, shortestPath algo might miss some paths when used > with findPathsOnMaxDepthOnly. > And that's "by design" so to speak, it's not a bug or something, correct? >
Correct, it finds paths on that depth only. If other paths are encountered along the way they aren't returned. > > Thanks! > > Petar > > On Thu, Nov 24, 2011 at 8:36 PM, Mattias Persson > <matt...@neotechnology.com>wrote: > > > 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 > > > > > > -- > Petar Dobrev > Engineer > Philanthropedia > http://www.myphilanthropedia.org > _______________________________________________ > 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
