Neo4J: shortest paths with specific relation types sequence constrain

Question

I need to find shortest paths between nodes, but with some restrictions on relations types in good paths.

I have two relation types: A & B. Path is considered bad if it has two or more consecutive relation of type B:

Good path: ()-A->()-A->()<-A-()-B->()-A->()-B->()
Bad path: ()-A->()-A->()<-A-()-B->()<-B-()-A->()

The Cypher query:

MATCH path=allShortestPaths( (p:P{idp:123})-[rel:A|B*]-(p2:P{idp:124}) )
WHERE *some-predicate-on-path-or-rel*
RETURN path

is not a solution because the shortest good path may be longer than shortest bad paths.

Q1: Can this problem be solved by some Cypher query?

I can solve my problem with the embedded Java Neo4J API:

GraphDatabaseService graphDb = new GraphDatabaseFactory().newEmbeddedDatabase("db/store/dir/path");
TraversalDescription td = graphDb.traversalDescription()
    .breadthFirst()
    .evaluator(Evaluators.toDepth(max_depth))
    .evaluator(Evaluators.endNodeIs(Evaluation.INCLUDE_AND_PRUNE, Evaluation.EXCLUDE_AND_CONTINUE, endNode))
    .evaluator(new DoubleB_PruneEvaluator());

static class DoubleB_PruneEvaluator implements Evaluator {
    @Override
    public Evaluation evaluate(final Path path) {
        Iterator<Relationship> lRels = path.reverseRelationships().iterator();
        if (lRels.hasNext()  &&  lRels.next().isType(MyRelTypes.B)) {
            if (lRels.hasNext()  &&  lRels.next().isType(MyRelTypes.B))
                return Evaluation.EXCLUDE_AND_PRUNE;
        }
        return Evaluation.INCLUDE_AND_CONTINUE;
    }
}

Q2: Is this solution is quite efficient? Or how to improve?

But my application is written on PHP and interacts with Neo4j server via REST protocol.

Q3: How can I run this solution by some REST query?

Kit Kit · Accepted Answer · 2017-03-31T15:31:12

No intelligent person wouldn't answer me. So I will try myself.

A1: This problem cannot be solved by standard Cypher query. (My Neo4j version 3.1.1)

A2: This solution is not quite efficient for several reasons:

The standard function shortestPath is implemented by using more efficient Bidirectional BFS.
This traversal description does not contain a stop condition when the solution is found. The traversal will continue until the maximum depth.

In addition, this solution finds only one path. The other paths of the same length will not be found.

A3: Java coded solutions can be added to a server by extending Neo4j. I solve my problem using user-defined procedures:

my/app/RelType.java:

package my.app;

import org.neo4j.graphdb.*;

public enum RelType implements RelationshipType {
    A, B
}

my/app/DoubleB_PruneEvaluator.java:

package my.app;

import java.util.*;
import org.neo4j.graphdb.*;
import org.neo4j.graphdb.traversal.*;

public class DoubleB_PruneEvaluator implements Evaluator {
    @Override
    public Evaluation evaluate(final Path path) {
        Iterator<Relationship> lRels = path.reverseRelationships().iterator();
        if (lRels.hasNext()  &&  lRels.next().isType(RelType.marry)) {
            if (lRels.hasNext()  &&  lRels.next().isType(RelType.marry))
                return Evaluation.EXCLUDE_AND_PRUNE;
        }
        return Evaluation.INCLUDE_AND_CONTINUE;
    }
}

my/app/Procedures.java:

package my.app;

import java.util.stream.Stream;

import org.neo4j.graphdb.*;
import org.neo4j.procedure.*;
import org.neo4j.graphdb.traversal.*;

public class Procedures {
    @Context
    public GraphDatabaseService db;

    @Procedure
    public Stream<PathHit> shortestWo2B( 
                                @Name("from") Node fromNode,
                                @Name("to")   Node toNode,
                                @Name("maxDepth") long maxDepth)
    {
        TraversalDescription td = db.traversalDescription()
            .breadthFirst()
            .relationships(RelType.A)
            .relationships(RelType.B)
            .evaluator(Evaluators.toDepth((int)maxDepth))
            .evaluator(Evaluators.endNodeIs(Evaluation.INCLUDE_AND_PRUNE, Evaluation.EXCLUDE_AND_CONTINUE, toNode))
            .evaluator(new DoubleB_PruneEvaluator());

        return td.traverse(fromNode)
                .stream()
                .map( PathHit::new );
    }

    public static class PathHit {
        public Path path;

        public PathHit(Path path) {
            this.path = path;
        }
    }
}

Doc: https://neo4j.com/docs/java-reference/3.1/javadocs/index.html?org/neo4j/procedure/Procedure.html

A few words about the compilation and installation plugin:

As a beginner in Java, I decided that utilities Eclipse and Maven is too heavy. I prefer to use simple javac & jar:

$ export CLASSPATH=/path/to/neo4j-install-dir/lib/*:.
$ javac my/app/*.java
$ jar -cf my-neo4j-plugin.jar my/app/*.class
$ cp my-neo4j-plugin.jar /path/to/neo4j-install-dir/plugins/
$ /path/to/neo4j-install-dir/bin/neo4j restart

Now we can run the Cypher query:

MATCH (p1:P{idp:123}) 
MATCH (p2:P{idp:124})
CALL my.app.shortestWo2B(p1,p2,100) YIELD path 
RETURN path;

Neo4J: shortest paths with specific relation types sequence constrain

1 Answers