Hi Peter
Ideally I would like to stop traversal as soon as the max. cost limit is
reached as we know there are no negative edges. That would probable be good
performance-wise for huge graphs. Attached is a patch for my attempt at
implementing the cost limit option. Its not thoroughly tested though I have
added some tests as well that pass. But it would be great of it can be tested a
little more if you decide to apply it.
Let me know what you think.
Regards
Nabeel Mukhtar
----- Original Message ----
From: Peter Neubauer <[email protected]>
To: Neo user discussions <[email protected]>
Sent: Wed, January 27, 2010 3:29:06 AM
Subject: Re: [Neo] Cost limit option in Dijkstra Algorithm
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
Index: src/test/java/org/neo4j/graphalgo/shortestPath/FindPathTest.java
===================================================================
--- src/test/java/org/neo4j/graphalgo/shortestPath/FindPathTest.java
(revision 3636)
+++ src/test/java/org/neo4j/graphalgo/shortestPath/FindPathTest.java
(working copy)
@@ -80,16 +80,29 @@
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 );
+ graph.makeEdge( "e", "f", "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 );
+ .getNode( "d" ), 2, Direction.OUTGOING, MyRelTypes.R1 );
assertTrue( findPath.getCost() == 2 );
assertTrue( findPath.getPathAsNodes().size() == 3 );
assertTrue( findPath.getPathAsRelationships().size() == 2 );
+
+ findPath = new FindPath( graph.getNode( "a" ), graph
+ .getNode( "e" ), 2, Direction.OUTGOING, MyRelTypes.R1 );
+ assertNull( findPath.getCost() );
+ assertTrue( findPath.getPaths().isEmpty() );
+
+ findPath = new FindPath( graph.getNode( "a" ), graph
+ .getNode( "e" ), 3, Direction.OUTGOING, MyRelTypes.R1 );
+ assertTrue( findPath.getCost() == 3 );
+ assertTrue( findPath.getPathAsNodes().size() == 4 );
+ assertTrue( findPath.getPathAsRelationships().size() == 3 );
}
public void testFindPathChain()
{
Index: src/main/java/org/neo4j/graphalgo/shortestpath/FindPath.java
===================================================================
--- src/main/java/org/neo4j/graphalgo/shortestpath/FindPath.java
(revision 3628)
+++ src/main/java/org/neo4j/graphalgo/shortestpath/FindPath.java
(working copy)
@@ -180,9 +180,9 @@
dijkstra.setStartNode( startNode );
}
- public void limitMaxCostToTraverse( MaxCostEvaluator<Integer> evaluator )
+ public void limitMaxCostToTraverse( Integer cost )
{
- dijkstra.limitMaxCostToTraverse( evaluator );
+ dijkstra.limitMaxCostToTraverse( cost );
}
/**
@@ -223,12 +223,6 @@
RelationshipType... costRelationTypes )
{
this(startNode, endNode, relationDirection, costRelationTypes);
- MaxCostEvaluator<Integer> maxCostComparator = new
MaxCostEvaluator<Integer>() {
-
- public boolean maxCostExceeded(Integer currentCost) {
- return currentCost > maxCost;
- }
- };
- dijkstra.limitMaxCostToTraverse(maxCostComparator);
+ dijkstra.limitMaxCostToTraverse(maxCost);
}
}
Index: src/main/java/org/neo4j/graphalgo/shortestpath/Dijkstra.java
===================================================================
--- src/main/java/org/neo4j/graphalgo/shortestpath/Dijkstra.java
(revision 3628)
+++ src/main/java/org/neo4j/graphalgo/shortestpath/Dijkstra.java
(working copy)
@@ -65,14 +65,7 @@
protected long numberOfTraversedRelationShips = 0;
protected long maxNodesToTraverse = -1;
protected long numberOfNodesTraversed = 0;
- protected MaxCostEvaluator<CostType> maxCostEvaluator = new
MaxCostEvaluator<CostType>()
- {
- //this will not limit the path length
- public boolean maxCostExceeded( CostType currentCost )
- {
- return false;
- }
- };
+ protected CostType maxCost = null;
/**
* @return True if the set limits for the calculation has been reached (but
@@ -92,6 +85,22 @@
}
return false;
}
+
+ protected boolean limitReached(CostType cost1, CostType cost2)
+ {
+ if ( maxCost != null )
+ {
+ CostType totalCost = costAccumulator.addCosts( cost1, cost2 );
+ if (costComparator.compare( totalCost, maxCost ) > 0)
+ {
+ foundPathsMiddleNodes = null;
+ foundPathsCost = null;
+ return true;
+ }
+ }
+
+ return false;
+ }
// Result data
protected boolean doneCalculation = false;
@@ -281,10 +290,6 @@
{
return null;
}
- if ( maxCostEvaluator.maxCostExceeded( currentCost ) )
- {
- return null;
- }
if ( limitReached() )
{
return null;
@@ -478,6 +483,8 @@
seen1, seen2, dists1, dists2, false );
DijstraIterator iter2 = new DijstraIterator( endNode, predecessors2,
seen2, seen1, dists2, dists1, true );
+ Node node1 = null;
+ Node node2 = null;
while ( iter1.hasNext() && iter2.hasNext() )
{
if ( limitReached() )
@@ -486,7 +493,8 @@
}
if ( iter1.hasNext() )
{
- if ( iter1.next() == null )
+ node1 = iter1.next();
+ if ( node1 == null )
{
break;
}
@@ -497,16 +505,22 @@
}
if ( !iter1.isDone() && iter2.hasNext() )
{
- if ( iter2.next() == null )
+ node2 = iter2.next();
+ if ( node2 == null )
{
break;
}
}
+ if ( limitReached( seen1.get( node1 ), seen2.get( node2 ) ) )
+ {
+ break;
+ }
if ( iter1.isDone() || iter2.isDone() ) // A path was found
{
return true;
}
}
+
return false;
}
@@ -778,8 +792,8 @@
*
* @param evaluator The evaluator for
*/
- public void limitMaxCostToTraverse( MaxCostEvaluator<CostType> evaluator )
+ public void limitMaxCostToTraverse( CostType maxCost )
{
- this.maxCostEvaluator = evaluator;
+ this.maxCost = maxCost;
}
}
_______________________________________________
Neo mailing list
[email protected]
https://lists.neo4j.org/mailman/listinfo/user
