Yes. I meant BFS. I tried it with incremental cost so it behaves like DFS, to make sure the priority queue size was not a bottleneck, but results are similar.
On Tuesday, June 23, 2015 at 2:57:37 AM UTC-4, Anton Persson wrote: > > 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] > <javascript:>> 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.
