1. ホーム
  2. 質問と答え
  3. cypherの総パスコストを計算し、関係の方向性を考慮に入れて

cypherの総パスコストを計算し、関係の方向性を考慮に入れて

2012-11-15 4 views
9

neo4jのCypherクエリを使用して、有向グラフでは、深度レベルごとにソートするBFSクエリとターゲットノードが必要です。内深度ソートするcypherの総パスコストを計算し、関係の方向性を考慮に入れて

、カスタム「総経路コスト関数」を使用しなければならない、すべての関係は、開始と終了ノードとの間r.followrank属性

  • に基づいて算出。
  • 関係指向（followrankていない場合、それはエンド・ノード、または0に向かって指している場合）

任意検索深度レベルnで、レベルn-m, m>0で高ランクのノードに接続されたノードは、そのノードよりも高くランク付けされるべきですレベルがn-mの低位ノードに接続されています。逆方向性は0ランクになるはずです（つまり、ノードとそのサブツリーは依然としてランク付けの一部です）。

私はneo4j community-1.9.M01を使用しています。私がこれまでに取ってきたアプローチは、各エンドノードへの最短経路のフォロランク配列を抽出することでした。

私はこのクエリの最初のアイデアを思いついたと思っていますが、ポイント。

私のクエリは次のとおりです。

それは私が必要なものに似ていますが、問題は

  1. ノード8、9、10、11ある

    ==> +-----------------------------------------------------------------+ 
==> | ID(tgt) | rank     | extract(n in nodes(p): ID(n)) | 
==> +-----------------------------------------------------------------+ 
==> | 14  | [1.0]     | [7,14]      | 
==> | 15  | [1.0,1.0]    | [7,14,15]      | 
==> | 11  | [1.0,1.0,1.0]   | [7,14,15,11]     | 
==> | 8  | [1.0,1.0,1.0,1.0,0.0] | [7,14,15,11,7,8]    | 
==> | 9  | [1.0,1.0,1.0,1.0,0.0] | [7,14,15,11,7,9]    | 
==> | 10  | [1.0,1.0,1.0,1.0,0.0] | [7,14,15,11,7,10]    | 
==> | 12  | [1.0,1.0,1.0,0.0]  | [7,14,15,11,12]    | 
==> | 8  | [0.0]     | [7,8]       | 
==> | 9  | [0.0]     | [7,9]       | 
==> | 10  | [0.0]     | [7,10]      | 
==> | 11  | [1.0]     | [7,11]      | 
==> | 15  | [1.0,1.0]    | [7,11,15]      | 
==> | 14  | [1.0,1.0,1.0]   | [7,11,15,14]     | 
==> | 8  | [1.0,1.0,1.0,1.0,0.0] | [7,11,15,14,7,8]    | 
==> | 9  | [1.0,1.0,1.0,1.0,0.0] | [7,11,15,14,7,9]    | 
==> | 10  | [1.0,1.0,1.0,1.0,0.0] | [7,11,15,14,7,10]    | 
==> | 12  | [1.0,0.0]    | [7,11,12]      | 
==> +-----------------------------------------------------------------+ 
==> 17 rows 
==> 38 ms

    を出力 

    START strt=node(7) 
MATCH p=strt-[*1..]-tgt 
WHERE not(tgt=strt) 
RETURN ID(tgt), extract(r in rels(p): r.followrank*length(strt-[*0..]-()-[r]->())) as rank, extract(n in nodes(p): ID(n));

    7と同じ関係の方向を持っている！逆のクエリ結果...*length(strt-[*0..]-()-[r]->())...も見知らぬように見えます。下のクエリを参照してください。

  2. 私は1

に方向length()式の結果を正規化する方法がわからない。だから私の質問はあり

START strt=node(7) 
MATCH p=strt-[*1..]-tgt 
WHERE not(tgt=strt) 
RETURN ID(tgt), extract(rr in rels(p): rr.followrank*length(strt-[*0..]-()<-[rr]-())) as rank, extract(n in nodes(p): ID(n)); 
==> +-----------------------------------------------------------------+ 
==> | ID(tgt) | rank     | extract(n in nodes(p): ID(n)) | 
==> +-----------------------------------------------------------------+ 
==> | 14  | [1.0]     | [7,14]      | 
==> | 15  | [1.0,1.0]    | [7,14,15]      | 
==> | 11  | [1.0,1.0,1.0]   | [7,14,15,11]     | 
==> | 8  | [1.0,1.0,1.0,1.0,3.0] | [7,14,15,11,7,8]    | 
==> | 9  | [1.0,1.0,1.0,1.0,3.0] | [7,14,15,11,7,9]    | 
==> | 10  | [1.0,1.0,1.0,1.0,3.0] | [7,14,15,11,7,10]    | 
==> | 12  | [1.0,1.0,1.0,2.0]  | [7,14,15,11,12]    | 
==> | 8  | [3.0]     | [7,8]       | 
==> | 9  | [3.0]     | [7,9]       | 
==> | 10  | [3.0]     | [7,10]      | 
==> | 11  | [1.0]     | [7,11]      | 
==> | 15  | [1.0,1.0]    | [7,11,15]      | 
==> | 14  | [1.0,1.0,1.0]   | [7,11,15,14]     | 
==> | 8  | [1.0,1.0,1.0,1.0,3.0] | [7,11,15,14,7,8]    | 
==> | 9  | [1.0,1.0,1.0,1.0,3.0] | [7,11,15,14,7,9]    | 
==> | 10  | [1.0,1.0,1.0,1.0,3.0] | [7,11,15,14,7,10]    | 
==> | 12  | [1.0,2.0]    | [7,11,12]      | 
==> +-----------------------------------------------------------------+ 
==> 17 rows 
==> 30 ms

：

START strt=node(7) 
MATCH strt<-[r]-m 
RETURN ID(m), r.followrank; 
==> +----------------------+ 
==> | ID(m) | r.followrank | 
==> +----------------------+ 
==> | 8  | 1   | 
==> | 9  | 1   | 
==> | 10 | 1   | 
==> | 11 | 1   | 
==> +----------------------+ 
==> 4 rows 
==> 0 ms 
START strt=node(7) 
MATCH strt-[r]->m 
RETURN ID(m), r.followrank; 
==> +----------------------+ 
==> | ID(m) | r.followrank | 
==> +----------------------+ 
==> | 14 | 1   | 
==> +----------------------+ 
==> 1 row 
==> 0 ms

逆クエリを

  1. このクエリでは何が起こっていますか？
  2. 実際のアプローチはありますか？

詳細については、min（length（path））アグリゲータを知っていますが、ここではベストヒットに関する情報を抽出しようとしています。最高のヒットについては結果が再び分かれるだろう - 私はそれがサイファーの限界だと思う。

出典

2012-11-15 bebbi

+0

を

// allshortestpaths to get all non-cyclic paths MATCH path=allshortestpaths((a{id:"1"})-[*]-(b{id:"2"})) // Find rank worthy relationships WITH path, filter(rl in relationships(path) WHERE apoc.coll.indexOf(path, startnode(rl))<apoc.coll.indexOf(path, endnode(rl)))) as comply // Filter results RETURN path, REDUCE(rk = 0, rl in comply | rk+rl.followrank) as rank ORDER BY rank DESC

（あなたはAPOCの手順に代わり、パスの各ノード（パス）を渡す必要がある場合がありますので、私は、APOCの一部をテストすることはできません）、これを確認します。http ：//console.neo4j.org/r/gm59jt対http://console.neo4j.org/r/nvbdud。マッチパートで方向を定義していない場合は、移動アルゴリズムが1つのノードに移動し、開始ノードに戻ってくるよりも、単純に別のノードに移動するよりも、開始ノードからネクストとネクストに向かうような、より長いパスについても同じカウントが、2倍以上であり、別の場所では同じです。これはグラフ理論に反するものではなく、実際には正しい動作です。 – ulkas

+0

実際には申し訳ありませんが、実際にはこれが問題である可能性があります。しかし、なぜその道にはこれが反映されないでしょうか？たとえノード（p）の代わりにパスp全体を返しても、そのようなルーティングの兆候はありません。 "x-> z-> x-> y"と長さ（p）= 3と言うパスを期待します。これはneo4jバグですか？ – bebbi

+0

は、関係方向のneo4j実装のほうがよいでしょう。たとえば、グラフを作成してもその関係の方向を設定しない場合、neo4jは方向そのものを追加します。これはいくつかの歴史的な理由によるものです。私は、3種類（発信、送信、非指向）よりも2種類のrels（発信とingoin）で計算するとパフォーマンスが優れていると思います。したがって、私はあなたの結果が、現在のいくつかのrelsを参照していますが、原点で定義されていないので、パスのrelsの方向を示していないと仮定します。 – ulkas

答えて

0

基本的には、「パスフローとの関係」を考慮してランクのみを実行する必要があります。残念ながら、 "パスフロー"をテストするには、各リレーションシップの開始ノードと終了ノードのパスインデックスを確認する必要があります。これは、現在はAPOCでのみ行うことができます。あなたの質問の最初の部分に

出典

2017-06-02 19:18:33 Tezra

関連する問題

 関連する問題