0

I'm trying to find all possible path between two nodes. I've used few cypher queries which does the required job but it take a lot of time if the hops increases. This is the query

match p = (n{name:"Node1"})-[:Route*1..5]-(b{name:"Node2"}) return p

Also if I use shortestpath it limits the result if a path with minimum hop is found. So I don't get the results with 2 or more than two hops if a direct connection (1 hop) is found between the nodes.

match p = shortestpath((n{name:"Node1"})-[:Route*1..5]-(b{name:"Node2"})) return p

and if I increase the hop to 2 or more it throws an exception.

shortestPath(...) does not support a minimal length different from 0 or 1 

Is there any other alternative framework or algorithm to get all path with minimum time ?

P.S. I'm looking for something in the order of ms. Currently all queries with hops greater than 3 takes few seconds to complete.

2 Answers 2

1

I gather you are trying to speed up your original query involving variable-length paths. The shortestpath function is not appropriate for your query, as it literally tries to find a shortest path -- not all paths up to a certain length.

The execution plan for your original query (using sample data) looks like this:

+-----------------------+----------------+------+---------+-------------------+---------------------------------------------+
| Operator              | Estimated Rows | Rows | DB Hits | Identifiers       | Other                                       |
+-----------------------+----------------+------+---------+-------------------+---------------------------------------------+
| +ProduceResults       |              0 |    1 |       0 | p                 | p                                           |
| |                     +----------------+------+---------+-------------------+---------------------------------------------+
| +Projection           |              0 |    1 |       0 | anon[30], b, n, p | ProjectedPath(Set(anon[30], n),) |
| |                     +----------------+------+---------+-------------------+---------------------------------------------+
| +Filter               |              0 |    1 |       2 | anon[30], b, n    | n.name == {  AUTOSTRING0}                   |
| |                     +----------------+------+---------+-------------------+---------------------------------------------+
| +VarLengthExpand(All) |              0 |    2 |       7 | anon[30], b, n    | (b)<-[:Route*]-(n)                          |
| |                     +----------------+------+---------+-------------------+---------------------------------------------+
| +Filter               |              0 |    1 |       3 | b                 | b.name == {  AUTOSTRING1}                   |
| |                     +----------------+------+---------+-------------------+---------------------------------------------+
| +AllNodesScan         |              3 |    3 |       4 | b                 |                                             |
+-----------------------+----------------+------+---------+-------------------+---------------------------------------------+

So, your original query is scanning through every node to find the node(s) that match the b pattern. Then, it expands all variable-length paths starting at b. And then it filters those paths to find the one(s) that end with a node that matches the pattern for n.

Here are a few suggestions that should speed up your query, although you'll have to test it on your data to see by how much:

  1. Give each node a label. For example, Foo.
  2. Create an index that can speed up the search for your end nodes. For example:

    CREATE INDEX ON :Foo(name);
    
  3. Modify your query to force the use of the index on both end nodes. For example:

    MATCH p =(n:Foo { name:"Node1" })-[:Route*1..5]-(b:Foo { name:"Node2" })
    USING INDEX n:Foo(name)
    USING INDEX b:Foo(name)
    RETURN p;
    

After the above changes, the execution plan is:

+-----------------+------+---------+-----------------------------+-----------------------------+
| Operator        | Rows | DB Hits | Identifiers                 | Other                       |
+-----------------+------+---------+-----------------------------+-----------------------------+
| +ColumnFilter   |    1 |       0 | p                           | keep columns p              |
| |               +------+---------+-----------------------------+-----------------------------+
| +ExtractPath    |    1 |       0 | anon[33], anon[34], b, n, p |                             |
| |               +------+---------+-----------------------------+-----------------------------+
| +PatternMatcher |    1 |       3 | anon[33], anon[34], b, n    |                             |
| |               +------+---------+-----------------------------+-----------------------------+
| +SchemaIndex    |    1 |       2 | b, n                        | {  AUTOSTRING1}; :Foo(name) |
| |               +------+---------+-----------------------------+-----------------------------+
| +SchemaIndex    |    1 |       2 | n                           | {  AUTOSTRING0}; :Foo(name) |
+-----------------+------+---------+-----------------------------+-----------------------------+

This query plan uses the index to directly get the b and n nodes -- without scanning. This, by itself, should provide a speed improvement. And then this plan uses the "PatternMatcher" to find the variable-length paths between those end nodes. You will have to try this query out to see how efficient the "PatternMatcher" is in doing that.

1
  • Thanks for the detailed analysis. It does reduce the time taken for getting paths with 1 and 2 hops. 3 and more hops are still taking time in seconds but the time has been reduced greatly.
    – Rahul
    Feb 8, 2016 at 16:17
1

From your description I assume that you want to get a shortest path based on some weight like a duration property on the :Route relationships.

If that is true using shortestPath in cypher is not helpful since it just takes into account the number of hops. Weighted shortest paths are not yet available in Cypher in an efficient way.

The Java API has support for weighted shortest paths via dijekstra or astar via the GraphAlgoFactory class. For the simple case that your cost function is just the value of a relationship property (as mentioned above) you can also use an existing REST endpoint.

1
  • Thanks for the response. I was not considering weights before but it seems it will reduce the time taken if I do consider weights.
    – Rahul
    Feb 8, 2016 at 16:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.