CODEWITHSUNDEEP
neo4jcypher
Antoan Milkov
Antoan Milkov

Reputation: 2228

Longest path based on relationship property

I need to find the longest path in Neo4j graph based on order of specific property of the relationship.

Imagine that the relationship has property date of integer type like that
[:Like {date:20140812}]

Consider the path: A-[r1:Like]->B-[r2:Like]->C

This is valid path only if r1.date < r2.date

The question is how to find the longest path with Cypher.

Upvotes: 2

Views: 1312

Answers (1)

Michael Hunger
Michael Hunger

Reputation: 41676

You can do something like this but it won't be very efficient in cypher. I would still limit the max-path-length to prevent it from exploding.

I'd probably use the Java API to achieve something like that.

You can try to run it with the new query planner in Neo4j 2.1 with the cypher 2.1.experimental prefix.

MATCH (a:Label {prop:value})
MATCH path = (a)-[r:Like*10]->(b)
WHERE ALL(idx in range(1,length(path)-1) WHERE r[idx-1].date < r[idx].date)
RETURN path, length(path) as len
ORDER BY len DESC
LIMIT 1

In Java it would be something like this:

    TraversalDescription traversal = db.traversalDescription().depthFirst().evaluator(new PathEvaluator.Adapter<Long>() {
        @Override
        public Evaluation evaluate(Path path, BranchState<Long> state) {
            if (path.length() == 0) return Evaluation.INCLUDE_AND_CONTINUE;
            Long date = (Long) path.lastRelationship().getProperty("date");
            Long stateDate = state.getState();
            state.setState(date);
            if (stateDate != null) {
                return stateDate < date ? Evaluation.INCLUDE_AND_CONTINUE : Evaluation.EXCLUDE_AND_PRUNE;
            }
            return Evaluation.INCLUDE_AND_CONTINUE;
        }
    });
    int length = 0;
    Path result;
    for (Path path : traversal.traverse(startNode)) {
        if (path.length() > length) {
            result = path;
            length = path.length();
        }
    }

Upvotes: 2

Related Questions