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
Index: src/test/java/org/neo4j/graphalgo/shortestPath/FindPathTest.java
===================================================================
--- src/test/java/org/neo4j/graphalgo/shortestPath/FindPathTest.java
(revision 3628)
+++ src/test/java/org/neo4j/graphalgo/shortestPath/FindPathTest.java
(working copy)
@@ -80,6 +80,7 @@
graph.makeEdge( "a", "c", "cost", (double) 1 );
graph.makeEdge( "c", "d", "cost", (double) 1 );
graph.makeEdge( "b", "d", "cost", (double) 1 );
+ graph.makeEdge( "d", "e", "cost", (double) 1 );
FindPath findPath = new FindPath( graph.getNode( "a" ), graph
.getNode( "d" ), 0, Direction.OUTGOING, MyRelTypes.R1 );
List<List<PropertyContainer>> paths = findPath.getPaths();
@@ -90,6 +91,10 @@
assertTrue( findPath.getCost() == 2 );
assertTrue( findPath.getPathAsNodes().size() == 3 );
assertTrue( findPath.getPathAsRelationships().size() == 2 );
+
+ findPath = new FindPath( graph.getNode( "a" ), graph
+ .getNode( "e" ), 1, Direction.OUTGOING, MyRelTypes.R1 );
+ assertTrue( findPath.getPaths().isEmpty() );
}
public void testFindPathChain()
{
_______________________________________________
Neo mailing list
[email protected]
https://lists.neo4j.org/mailman/listinfo/user
