Gremlin 查询获取 "dependency graph" 类图的顺序

Question

有下图：

g.addV("entity").property(id, "A")
 .addV("entity").property(id, "B")
 .addV("entity").property(id, "C")
 .addV("entity").property(id, "D")
 .addV("entity").property(id, "E")
 .addV("entity").property(id, "F")
 .addV("entity").property(id, "G")
 .addV("entity").property(id, "H")
 .addE("needs").from(g.V("A")).to(g.V("B"))
 .addE("needs").from(g.V("A")).to(g.V("C"))
 .addE("needs").from(g.V("A")).to(g.V("D"))
 .addE("needs").from(g.V("A")).to(g.V("E"))
 .addE("needs").from(g.V("C")).to(g.V("F"))
 .addE("needs").from(g.V("D")).to(g.V("F"))
 .addE("needs").from(g.V("E")).to(g.V("G"))
 .addE("needs").from(g.V("F")).to(g.V("H"))

正确顺序的一种变体是

[[B, H, G], [F, E], [C, D], [A]]

或者只是

[B, H, G, F, E, C, D, A]

“组”内的顺序（例如 [B, H, G] 与 [H, G, B]）并不重要。

如果这些节点存在于依赖关系图中，我如何检索正确的顺序来解析这些节点？

我对该算法的思考与以下两种解决方案之一类似：

A) 从叶节点开始遍历到父节点

检索所有叶顶点（无出边），追加到结果集，并放入current和resolved。
遍历所有 current 并查看它们的所有子节点（它们引用的顶点）是否都包含在 resolved 中。如果是，则将当前顶点保存到 resolved 并附加到结果集。将顶点的父项保存到 current.
如果current有元素，转到2，否则结束。

B) 简化了从叶节点开始但每次迭代都查看整个图

检索所有叶顶点（无出边），附加到结果集，并放入resolved。
查找所有未包含在 resolved 中且在 resolved 中没有任何引用顶点的顶点。将这些附加到结果集中。如果没有顶点，return 结果集，否则重复 2.

这可能吗？如果是这样，如何？我可以在遍历时使用这些 current 和 resolved 集合吗？

Answer 1

在大图中，这可能不是一个有效的查询，但这是一个解决方案。请注意，初始集合之后的列表与您的问题的顺序相反，因为这是遇到这些顶点的顺序。一种更有效的方法可能是反转“树”并从已知的根而不是“所有叶子”开始。

gremlin> g.V().where(__.not(out())).store('a').
......1>       repeat(__.in()).emit().
......2>       until(__.not(__.in())).
......3>       dedup().
......4>       union(cap('a'),identity()).
......5>       fold()    

==>[[v[A1],v[A4]],v[A0],v[A3],v[A2]]

已更新

鉴于您的新数据集，我不得不采取不同的方法。我之前的查询使用的是广度优先搜索，但这并没有产生您需要的排序。我更改了使用 index 步骤的方法，对于找到的每个顶点，只保留在路径中找到的具有最高索引值的顶点。结果列表就是您需要的列表，只是顺序相反。我们还可以添加到查询中以反转列表 - 如下所示。

gremlin>     g.V().where(__.not(out())).
......1>     repeat(__.in()).
......2>     until(__.not(__.in())).path().index().unfold().
......3>     order().by(tail(local),desc).limit(local,1).dedup().fold()

==>[v[A],v[C],v[D],v[E],v[F],v[B],v[G],v[H]]

如果您想在查询过程中反转列表，您也可以这样做。

gremlin> g.V().where(__.not(out())).
......1> repeat(__.in()).
......2> until(__.not(__.in())).path().index().unfold().
......3> order().by(tail(local),desc).limit(local,1).dedup().fold().index().
......4> unfold().order().by(tail(local),desc).limit(local,1).fold()

==>[v[H],v[G],v[B],v[F],v[E],v[D],v[C],v[A]]

Gremlin 查询获取 "dependency graph" 类图的顺序

Gremlin query for getting the order for a "dependency graph" like graph

gremlin

graph-databases

tinkerpop

tinkerpop3

amazon-neptune

A) 从叶节点开始遍历到父节点

B) 简化了从叶节点开始但每次迭代都查看整个图