13

サイファーを使用してかなりのサイズのグラフでサイクルを検出する最良の方法は何ですか?

約 250000 のノードと約 270000 の関係を持つグラフがあり、約 10k のノードと 100k の関係を含むサブグラフでサイクルを検出したいと考えています。私が書いたサイファーは

start 
      n = node:node_auto_index(some lucene query that returns about 10k nodes)

match
    p =  n-[:r1|r2|r3*]->n
return p

ただし、これは非常に効率的であることが判明していません。

誰かがこれを行うためのより良い方法を提案できますか?

4

2 に答える 2

0

1) フラグの付いていないノードを数える
2) 発信関係のないノードにフラグを立てる (リーフ)
3) 着信関係の
ないノードにフラグを付ける (ルート) 4) 2 または 3 でフラグが立てられたノードがある場合は、ステップ 1 に戻る

5) フラグの付いていないノードが残っている場合は、少なくとも 1 サイクルあります

サイクルは、フラグが設定されていないノードのセットになります。
[in|out] エッジが最も少ないノードを調べると、
サイクルを特定するにはまだ多すぎる場合に役立ちます。

于 2016-08-16T23:22:53.950 に答える