Neo4J：特定の関係タイプを持つ最短経路シーケンス制約

Question

ノード間の最短経路を見つける必要がありますが、良好な経路の関係タイプにはいくつかの制限があります。

Iは、2つの関係タイプを有する：

グッドパス：それはタイプBの2つの以上の連続した関係を有する場合& 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クエリで解決できますか？

私は、組み込みの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：は、このソリューションは非常に効率的ですか？またはどのように改善する？

私のアプリケーションはPHPで書かれており、Neo4jサーバーとRESTプロトコルでやりとりします。

Q3：いくつかのRESTクエリでこのソリューションを実行するにはどうすればよいですか？

Answer 1

インテリジェントな人は私に答えないでしょう。だから私は自分自身を試してみる。

A1：この問題は、標準のCypherクエリでは解決できません。 （私のNeo4jのバージョン3.1.1）

A2：このソリューションは非常に効率的ではないいくつかの理由のために：

1. 標準機能shortestPathは、より 効率的双方向 BFSを使用して実装されます。
2. 解決方法が見つかった場合、このトラバーサルの説明には停止条件は含まれません。 トラバーサルは、最大深度が になるまで続きます。

さらに、この解決策では1つのパスしか検出されません。同じ長さの他のパスは見つかりません。

A3：extending Neo4jでJavaコードソリューションをサーバーに追加できます。 user-defined procedures：

my/app/RelTypeを使用して問題を解決します。Javaの：

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

いくつかの単語についてコンパイルとインストールのプラグイン：

Javaの初心者として、私はユーティリティEclipseとMavenが重すぎると判断しました。今、私たちはサイファークエリを実行することができます

$ 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 

：私はシンプルのjavac & 瓶を使用することを好む

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