The performance difference is quite sad indeed. I'm currently working on improving Dijkstra and hopefully I will be finished with that quite soon.
ps. When using unit cost it will behave like BFS, I'm sure that's what you meant. On Mon, Jun 22, 2015 at 7:15 PM, mayank gupta <[email protected]> wrote: > Hi, > > I have a REST plugin to cut short dijkstra expansion. I also tested for > unit costs so that it behaves like DFS (except for the logn work spent on > queue operations) but the results are still significantly different than > allshortestpath ( 4sec (ASP) vs 30sec(Dijkstra) average times over 20 > random requests). This was to make sure that the algorithm was not spending > any time fetching the cost property. All the requests were made after > warming up the cache. > > My schema is: > > - (Person)-[attended]->(School) > - (Person)-[likes]->(Hobby) > - (Person)-[studied]->(Education) > - (Person)-[owns]->(Gaming console) > - (Person)-[plays]->(Game) > - (Game)-[runson]->(Gaming console) > > Each relationship type has a weight associated, which is used by Dijkstra. > eg: 8 for runson, 4 for likes etc. > > The majority of the nodes are of Person types (2.2M) or Game types(0.3M). > System information: > > - #CPU cores - 4 > - RAM - 32G > - GCCompiler - Concurrent Mark Sweep > - Page size - 10G > - DB version - 2.3.0 Community > > > > > DijkstraPlugin.java Method > > @Description( "Find the minimum cost path between two nodes using > dijkstra." ) > @PluginTarget( Node.class ) > public Path dijkstraSinglePath( > @Source Node source, > @Description( "The node to find the shortest path to." ) > @Parameter( name = "target" ) Node target, > @Description( "The relationship types to follow when searching > for the shortest path(s). " + > "Order is insignificant, if omitted all types are followed." ) > @Parameter( name = "types", optional = true ) String[] > types, > @Description( "The maximum path length to search for, default value (if > omitted) is 4." ) > @Parameter( name = "depth", optional = false ) Integer > depth , > @Description( "The relationship types to follow when searching for the > shortest path(s). " + > "Order is insignificant, if omitted all types are followed." ) > @Parameter( name = "cost_property", optional = false ) > String cost_property) > { > PathExpander<?> expander = new DepthLimitedExpander(depth); > Path path; > > try (Transaction tx = source.getGraphDatabase().beginTx()) > { > PathFinder<WeightedPath> shortestPath = > GraphAlgoFactory.dijkstra(expander, cost_property); > path = shortestPath.findSinglePath(source, target); > tx.success(); > } > return path; > } > > PathExpander > public class DepthLimitedExpander implements PathExpander > { > private final int depth; > DepthLimitedExpander ( int depth) > { > this.depth = depth; > } > @Override public Iterable<Relationship> expand(Path path, BranchState > state) { > if (path.length() > this.depth-1) { > return Collections.emptyList(); > } > > return path.endNode().getRelationships( ); > } > @Override public DepthLimitedExpander reverse() { > return new DepthLimitedExpander(this.depth); > } > } > > > > On Friday, June 19, 2015 at 6:25:27 PM UTC-4, Michael Hunger wrote: >> >> can you share your code, and how you ran dijkstra and your graph >> structure and perhaps your database? >> Otherwise it's impossible to reproduce. >> >> Michael >> >> On Fri, Jun 19, 2015 at 11:32 PM, mayank gupta <[email protected]> >> wrote: >> >>> Hi, >>> >>> I have a graph with 3M nodes and 10M edges. >>> I tried running Dijkstra to get all shortest path but it gets stuck >>> indefinitely. >>> I wrote a plugin to cut short Dijkstra for getting a single path upto a >>> certain depth and that gave me an average response time of 40 seconds for >>> depth 10. >>> >>> AllShortestPath however returns in average 4 seconds, sometimes >>> returning >100 different paths. Is there anything I am missing because the >>> performance difference seems significant. >>> >>> -- >>> You received this message because you are subscribed to the Google >>> Groups "Neo4j" group. >>> To unsubscribe from this group and stop receiving emails from it, send >>> an email to [email protected]. >>> For more options, visit https://groups.google.com/d/optout. >>> >> >> -- You received this message because you are subscribed to the Google Groups "Neo4j" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. For more options, visit https://groups.google.com/d/optout.
