0
Gremlin/TinkerPopクエリ言語を使用すると、有向非循環グラフのトポロジカルな順序を計算する方法はありますか? a, b, e, c, d
、又はa, e, b, c, d
、又はe, a, b, c, d
:グレムリンでのトポロジカルソート
例えば、私は、次のトポロジカル順序のいずれかを取得したい次の縁
a -> b, a -> d, b -> c, c -> d, e -> c
有するグラフを与え。
g = TinkerGraph.open().traversal()
g.addV(id, "a").as("a").
addV(id, "b").as("b").
addV(id, "c").as("c").
addV(id, "d").as("d").
addV(id, "e").as("e").
addE("link").from("a").to("b").
addE("link").from("a").to("d").
addE("link").from("b").to("c").
addE("link").from("c").to("d").
addE("link").from("e").to("c").iterate()
をそして、これはグレムリンにKahn's algorithmを実装されています:
これは、例えばグラフ '与え、正しいトポロジカル順序を提供していません。 a、b、c、d 'であるが、正しい答えは' a、b、c、d 'である。 タイムアウトを起こさずにこのクエリを実行するために、私は巨大なDAGを持っているので、 'repeat(...)'の中で 'dedup()'を動かさなければなりませんでした。私はそれが意味的に同等であると思う。 – Federico
が更新されました。サンプルグラフと期待される結果は、多くの助けになりました。 –
ありがとう!グラフにループがあっても終了し、完璧です。 – Federico