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]
> <javascript:>> 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] <javascript:>.
>> 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.
