Well noticed... Peter, will you have a look? 2010/1/26 Nabeel Siddiqui <[email protected]>: > 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 > >
-- Mattias Persson, [[email protected]] Neo Technology, www.neotechnology.com _______________________________________________ Neo mailing list [email protected] https://lists.neo4j.org/mailman/listinfo/user
