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
