[Neo] Cost limit option in Dijkstra Algorithm

Nabeel Siddiqui nabeelmukhtar at yahoo.com
Tue Jan 26 10:06:16 CET 2010


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



      
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: patch_dijkstra_neo4j.txt
Url: http://lists.neo4j.org/pipermail/user/attachments/20100126/17db9f33/attachment-0001.txt 


More information about the User mailing list