shortestPath with findSinglePath

[Mirko Nasato]

Hi all,

Given

  PathFinder<Path> finder = GraphAlgoFactory.shortestPath(expander, 4);
  finder.findSinglePath(startNode, endNode);

seems like findSinglePath is not guaranteed to find the shortest path, it just returns the first path it finds with length <= 4.

So it can return a path of length 4 even though one of length 3 exists - and can be found using findAllPaths instead. Is that by design?

(I'm using Neo4j 1.7.)

Thanks

Mirko

[Mattias Persson]

Have you got an example where it returns a path that isn't the shortest? findSinglePath will by design return the shortest path. The maxLength (=4 in your case) parameter is just to limit how far it is allowed to go if it doesn't find any shorter path along the way.

2012/4/29 Mirko Nasato <mirko....@gmail.com>

--
Mattias Persson, [mat...@neotechnology.com]
Hacker, Neo Technology
www.neotechnology.com

[Mirko Nasato]

Hi Mattias,

Yes I did encounter an actual example where findSinglePath doesn't seem to return the shortest path. In fact it returns a path of length 4 with maxDepth = 4, and of length 3 with maxDepth = 3.

I have a graph of Wikipedia pages and their links. Recreating it is a bit involved because you need a Wikipedia dump to start with, but my code is on GitHub.

Here's what I see (using Groovy just for its interactive shell)

  groovy:000> println graphipedia.findPath("Microsoft", "Hotels.com", 4).join(" --> ")
  Microsoft --> Windows 7 --> Steven Sinofsky --> Cornell University --> Hotels.com

  groovy:000> println graphipedia.findPath("Microsoft", "Hotels.com", 3).join(" --> ")
  Microsoft --> Human Rights Campaign --> Cornell University --> Hotels.com

  groovy:000> graphipedia.findShortestPaths("Microsoft", "Hotels.com", 4).each { path -> println path.join(" --> ") }
  Microsoft --> Bill Gates --> Cornell University --> Hotels.com
  Microsoft --> Human Rights Campaign --> Cornell University --> Hotels.com

In GraphipediaService findPath calls findSinglePath and findShortestPaths calls findAllPaths.

Thanks

Mirko

[Mirko Nasato]

Reported as issue #478.

[Mattias Persson]

Thanks, I'll have a look at it as it seems to me like you've found a bug!

2012/4/30 Mirko Nasato <mirko....@gmail.com>

Reported as issue #478.