Nabeel, you are right, this is not going to work. I am prepared to take out the cost evaluation again since I don't want to have non-working code in there, and have no time to figure this out right now.
Is that ok with you, or would you like to figure out a better place to put the cost evaluation, maybe after a shortest path has been found in order to exclude it and continue or be done if it is cheaper than maxCost? I that case I wil be happy to apply a patch... Cheers, /peter neubauer COO and Sales, Neo Technology 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 - Your high performance graph database. http://gremlin.tinkerpop.com - PageRank in 2 lines of code. On Tue, Jan 26, 2010 at 10:06 AM, Nabeel Siddiqui <[email protected]> wrote: > Hi all > Thanks Peter for adding a cost limit option to the Dijkstra algorithm in the > graph algo package. However for some reason I could not make it to work as I > expected. > I see you have added some tests in FindPathTest#testMaxCost method (which is > given below): > public void testMaxCost() > { > graph.makeEdge( "a", "b", "cost", (double) 1 ); > graph.makeEdge( "a", "c", "cost", (double) 1 ); > graph.makeEdge( "c", "d", "cost", (double) 1 ); > graph.makeEdge( "b", "d", "cost", (double) 1 ); > FindPath findPath = new FindPath( graph.getNode( "a" ), graph > .getNode( "d" ), 0, Direction.OUTGOING, MyRelTypes.R1 ); > List<List<PropertyContainer>> paths = findPath.getPaths(); > assertTrue( paths.isEmpty() ); > assertNull( findPath.getCost() ); > findPath = new FindPath( graph.getNode( "a" ), graph > .getNode( "d" ), 1, Direction.OUTGOING, MyRelTypes.R1 ); > assertTrue( findPath.getCost() == 2 ); > assertTrue( findPath.getPathAsNodes().size() == 3 ); > assertTrue( findPath.getPathAsRelationships().size() == 2 ); > } > > However I expect the second test to fail as the maximum cost specified is 1 > but the cost from a to d is greater than 1. So no paths should be returned. > Interestingly If I add another edge: > graph.makeEdge( "d", "e", "cost", (double) 1 ); > > And search from a to e with max cost 1, it still returns the paths although > it should return empty list as the cost from a to e is obviously greater than > 1. What am I doing wrong?. As far as I know, the max cost check inside > DijstraIterator may not work as the algorithm uses two simultaneous iterators > and the total cost of both traversals may exceed the limit while the > individual cost is still under limit. > > I have attached a patch with the added test that fails. > Also it would be great to rename the test sub-package from shortestPath to > shortestpath (same as the source package) because it creates problems in > eclipse when both src and test are in the source path. > > Thanks for your help. > > Regards > Nabeel Mukhtar > > > > > _______________________________________________ > Neo mailing list > [email protected] > https://lists.neo4j.org/mailman/listinfo/user > > _______________________________________________ Neo mailing list [email protected] https://lists.neo4j.org/mailman/listinfo/user
