Gremlin 中的拓扑排序
Topological sort in Gremlin
使用Gremlin/TinkerPop查询语言,有没有办法计算有向无环图的拓扑排序?
例如,给定一个具有以下边的图
a -> b, a -> d, b -> c, c -> d, e -> c
我想获得以下拓扑排序之一:a, b, e, c, d
,或a, e, b, c, d
,或e, a, b, c, d
。
好的,让我们先创建您的示例图:
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 在 Gremlin 中实现的:
gremlin> g.V().not(__.inE()).store("x").
repeat(outE().store("e").inV().not(inE().where(without("e"))).store("x")).
cap("x")
==>[v[a],v[b],v[e],v[c],v[d]]
使用Gremlin/TinkerPop查询语言,有没有办法计算有向无环图的拓扑排序?
例如,给定一个具有以下边的图
a -> b, a -> d, b -> c, c -> d, e -> c
我想获得以下拓扑排序之一:a, b, e, c, d
,或a, e, b, c, d
,或e, a, b, c, d
。
好的,让我们先创建您的示例图:
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 在 Gremlin 中实现的:
gremlin> g.V().not(__.inE()).store("x").
repeat(outE().store("e").inV().not(inE().where(without("e"))).store("x")).
cap("x")
==>[v[a],v[b],v[e],v[c],v[d]]