Neo4J:具有特定关系类型序列约束的最短路径 [英] Neo4J: shortest paths with specific relation types sequence constrain

问题描述

我需要找到节点之间的最短路径，但是对良好路径中的关系类型有一些限制.

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

我有两种关系类型:A& B． 如果路径具有两个或两个以上B类型的连续关系，则认为该路径是错误的:

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

良好路径:()-A->()-A->()<-A-()-B->()-A->()-B->()
错误的路径:()-A->()-A->()<-A-() -B->()<-B-()-A->()

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

Cypher查询:

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.

问题1:此问题可以通过某些Cypher查询解决吗?

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

我可以使用嵌入式Java Neo4J API解决我的问题:

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?

但是我的应用程序是用PHP编写的，并通过REST协议与Neo4j服务器交互.

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

问题3:如何通过某些REST查询运行此解决方案?

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

推荐答案

没有聪明的人不会回答我.所以我会尝试一下.

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

A1::标准的Cypher查询无法解决此问题. (我的Neo4j版本3.1.1)

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

A2:该解决方案效率不高，原因如下:

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

1. 标准函数 shortestPath 通过使用更多实现 高效的双向 BFS.
2. 在以下情况下，此遍历描述不包含停止条件: 找到解决方案.遍历将持续到最大 深度.

1. The standard function shortestPath is implemented by using more efficient Bidirectional BFS.
2. 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 :可以通过扩展Neo4j . 我使用用户定义的过程来解决我的问题:

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:

my/app/RelType.java:

package my.app;

import org.neo4j.graphdb.*;

public enum RelType implements RelationshipType {
    A, B
}

my/app/DoubleB_PruneEvaluator.java:

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:

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;
        }
    }
}

文档: 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:

作为Java的初学者，我认为Eclipse和Maven实用程序太重了.我更喜欢使用简单的 javac & jar :

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

现在我们可以运行Cypher查询:

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:具有特定关系类型序列约束的最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！