Neo4J : 특정 관계 유형이있는 최단 경로 시퀀스 제한

Question

노드 사이의 최단 경로를 찾아야하지만 올바른 경로의 관계 유형에 대한 제한 사항이 있습니다.

나는 두 가지 관계 유형이 : 그것은 B 형의 두 개 이상의 연속적인 관계가 경우 & B. 경로가 나쁜 것으로 간주됩니다 :

좋은 경로 :() -A ->() - A->() < -A -() - B ->() - A ->() - B ->()
잘못된 경로 :() - A ->() - A ->() < -A-) -B ->() < -B-() - A ->()

사이퍼 쿼리

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

은 최단 경로가 최단 경로보다 길기 때문에 해결 방법이 아닙니다.

1 : 일부 Cypher 쿼리에서이 문제를 해결할 수 있습니까?

나는 임베디드 자바 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 :이 솔루션은 매우 효율적인가요? 아니면 개선하는 방법?

그러나 내 응용 프로그램은 PHP로 작성되었으며 REST 프로토콜을 통해 Neo4j 서버와 상호 작용합니다.

Q3 : 일부 REST 쿼리로 어떻게이 솔루션을 실행할 수 있습니까?

Answer 1

지적인 사람이 나를 대답하지 않을 것입니다. 그래서 나는 나 자신을 시험 할 것이다.

A1 :이 문제는 표준 Cypher 쿼리로 해결할 수 없습니다. (내 Neo4j 버전 3.1.1)

A2 :이 솔루션은 매우 효율적이지 않습니다 몇 가지 이유 :

1. 표준 기능 shortestPath 더 효율적인 양방향 BFS를 사용하여 구현됩니다.
2. 해결책을 찾으면이 탐색 설명에 중지 조건이 포함되지 않습니다. 탐색은 최대 깊이까지 계속됩니다.

또한이 솔루션은 경로를 하나만 찾습니다. 같은 길이의 다른 경로는 찾을 수 없습니다.

A3 :extending Neo4j으로 Java 코드 솔루션을 서버에 추가 할 수 있습니다. user-defined procedures :

my/app/RelType을 사용하여 문제를 해결합니다.자바 :

package my.app; 

import org.neo4j.graphdb.*; 

public enum RelType implements RelationshipType { 
    A, B 
} 

내/응용 프로그램/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; 
    } 
} 

내/응용 프로그램/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

몇 단어에 대한 컴파일 및 설치 플러그인 :

자바 초보자로서 Eclipse 및 Maven 유틸리티가 너무 무겁다는 결론을 내 렸습니다. 나는 간단하게 사용하는 것을 선호 javac의 & 항아리 :

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

:

$ 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 

이제 우리는 사이퍼 쿼리를 실행할 수 있습니다