Hi guys,
I played around some more with alternative approach and it turns out the
results are not equivalent.
Since I cannot test it with the desirable max depth of 8 on my setup, I ran
a test with max depth of 4.
For a given test case, allSimplePaths returned 2 paths of length 2 and 3:
(2624016)--[User_relation_6,9067449]-->(2161113)<--[PERSON_PERSON,7879807]--(2161112)
(2624016)--[User_relation_6,9067448]-->(142023)<--[PERSON_ORG,1982010]--(2161113)<--[PERSON_PERSON,7879807]--(2161112)
The alternative approach found only the first one.
(2624016)--[User_relation_6,9067449]-->(2161113)<--[PERSON_PERSON,7879807]--(2161112)
Interestingly, if I add another relationship to the source node, which does
not change the number of paths between the two nodes, the pathsWithLength
approach finds also the second one.
Am I doing something wrong or is it that pathsWithLength will not always
return all paths with that length due to some greedy approach?
The documentation for ShortestPath states that the algorithm will try to
find a path:
@param findPathsOnMaxDepthOnly if {@code true} then it will only try
to find paths on that particular depth ({@code maxDepth}).
Does that mean that it can also fail to find a path on the particular depth?
The source of the testing program is here: https://gist.github.com/1391654
Output before adding the additional relationship:
https://gist.github.com/1391668
Output after adding the additional relationship:
https://gist.github.com/1391661
Neo4j version: 1.5
Thanks!
Best regards,
Petar
On Thu, Nov 24, 2011 at 12:57 PM, Peter Neubauer <
peter.neuba...@neotechnology.com> wrote:
> 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
>
--
Petar Dobrev
Engineer
Philanthropedia
http://www.myphilanthropedia.org
_______________________________________________
Neo4j mailing list
User@lists.neo4j.org
https://lists.neo4j.org/mailman/listinfo/user
