Nabeel, your patch is applied in trunk now :) Thanks again! 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 - The terminal to the Giant Global Graph. On Sun, Jan 31, 2010 at 4:05 PM, Peter Neubauer <[email protected]> wrote: > Nabeel, > the patch looks good, will apply it and test a bit hopefully tonight, > so you can find it in trunk tomorrow... thanks for the work! > > 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 - The terminal to the Giant Global Graph. > > > > On Wed, Jan 27, 2010 at 2:45 PM, Nabeel Siddiqui > <[email protected]> wrote: >> 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 >> >> >> >> >> _______________________________________________ >> Neo mailing list >> [email protected] >> https://lists.neo4j.org/mailman/listinfo/user >> >> > _______________________________________________ Neo mailing list [email protected] https://lists.neo4j.org/mailman/listinfo/user
