Getting number of unique paths traversed while traversing using Neo4j traversal API

Question

I have created following basic graph:

CREATE (:NodeType1 {prop1:'value1'})-[:RelType1 {prop2:'value2'}]->(:NodeType2 {prop3:'value3'})-[:RelType2 {prop4:'value4'}]->(:NodeType3 {prop5:'value5'})-[:RelType3 {prop6:'value6'}]->(:NodeType4 {prop7:'value7'})

CREATE (:NodeType1 {prop1:'value8'})-[:RelType1 {prop2:'value9'}]->(:NodeType2 {prop3:'value10'})-[:RelType2 {prop4:'value11'}]->(:NodeType3 {prop5:'value12'})-[:RelType3 {prop6:'value13'}]->(:NodeType4 {prop7:'value14'})

MATCH path=(n:NodeType1 {prop1:'value1'})-[*]->(m:NodeType4 {prop7:'value7'})
CREATE (n)-[:RelType1 {prop2:'value15'}]->(:NodeType2 {prop3:'value16'})-[:RelType2 {prop4:'value17'}]->(:NodeType3 {prop5:'value18'})-[:RelType3 {prop6:'value19'}]->(m)

The graph looks like this:

When I run following cypher:

MATCH path=(a:NodeType1 {prop1:"value1"})-[:RelType1]->(b)-[:RelType2]->(c)-[:RelType3]->(d)
RETURN count(nodes(path))

I get 2 as the output. It seems that nodes() doesnt actually return the number nodes in the path but simply the number of rows in the returned result, since if I return the path:

MATCH path=(a:NodeType1 {prop1:"value1"})-[:RelType1]->(b)-[:RelType2]->(c)-[:RelType3]->(d)
RETURN path

I get two rows in the returned result:

Now I am guessing how can I get the same output when doing traversal using Neo4J traversal API. I get number of unique nodes in the cypher as follows:

MATCH path=(a:NodeType1 {prop1:"value1"})-[:RelType1]->(b)-[:RelType2]->(c)-[:RelType3]->(d)
RETURN size(collect(distinct a))+size(collect(distinct b))+size(collect(distinct c))+size(collect(distinct d))

Above query correctly returns 6.

Same can be done in the traversal API by having static counter inside path expander which is incremented each time expand() is called. (Is there any better approach for this?)

public class MyPathExpander implements PathExpander{
    static int nodeCount = 0;

    @Override
    public Iterable expand(Path path, BranchState state) {
        Node lastNode = path.endNode();

        nodeCount++;  //**increment the count of nodes visited

        if(lastNode.hasLabel(MyLabels.NodeType1))
            return lastNode.getRelationships(MyRelations.RelType1, Direction.OUTGOING);
        else if (lastNode.hasRelationship(MyRelations.RelType1, Direction.INCOMING))
            return lastNode.getRelationships(MyRelations.RelType2, Direction.OUTGOING);
        else if (lastNode.hasRelationship(MyRelations.RelType2, Direction.INCOMING))
            return lastNode.getRelationships(MyRelations.RelType3, Direction.OUTGOING);
        else if (lastNode.hasRelationship(MyRelations.RelType3, Direction.INCOMING))
            return null;
        return null;
    }
}

However I am not able to think of way which will tell me number of unique paths followed during traversal while using Traversal API (equivalent to above RETURN count(nodes(path))). How can I do this? Is it not possible with traversal API?

PS: By unique path I mean unique permutations of order of nodes visited while traversing. For example, all a-b-c, a-c-b and a-b-c-d are unique.

nodes(path) return array of nodes from path, not count of nodes... — stdob--

stdob-- stdob-- · Accepted Answer · 2017-02-15T16:44:22

This query not return count of unique path, but count of all paths return by query:

MATCH path=(a:NodeType1 {prop1:"value1"})-[:RelType1]->(b)
           -[:RelType2]->(c)-[:RelType3]->(d)
RETURN count(nodes(path))

If you want to count the number of unique nodes in the query, you can do so:

MATCH path=(a:NodeType1 {prop1:"value1"})-[:RelType1]->(b)
           -[:RelType2]->(c)-[:RelType3]->(d)
UNWIND nodes(path) AS N
RETURN count(distinct N)

One way to count the number of unique paths will be (for each path calculates its unique fingerprint, it will not be difficult to repeat by traversal API):

MATCH path=(a:NodeType1 {prop1:"value1"})-[:RelType1]->(b)
           -[:RelType2]->(c)-[:RelType3]->(d)
WITH path, 
     REDUCE(acc="", x in nodes(path) | acc + id(x)) +
     REDUCE(acc="", x in rels(path) | acc + id(x)) as uniID    
RETURN count(distinct uniID)

Getting number of unique paths traversed while traversing using Neo4j traversal API

1 Answers