Gremlin：如何有效地在有向无环图中找到根？

本文介绍了Gremlin：如何有效地在有向无环图中找到根？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我正在尝试编写一个小精灵查询来有效地解决汇流河流问题(因为没有更好的名称，图论中可能有一个更好的名称？)。下面是一个例子：

任务：给定一个根节点，交付一个映射，其中包含下游节点的ID作为键，将它们的所有河根ID(即从当前节点再次向上移动所有路径到达的末端节点)作为值。

例如，在上面的示例图中，对于根节点0，结果应该是：

{ "0": ["0"], "1": ["0", "4"], "2": ["0", "5", "8"], "3": ["0", "4", "5", "8"], "6": ["0", "4"] }

我在这里特别担心多次行走的路径。例如，在计算了"；2"；的根之后，我想重复使用该结果来计算其下游节点"；3"；的根。

有什么线索可以用于大型有向无环图吗？

推荐答案

根据您的图表，我们可以创建以下图表。

g.addV('0').as('0'). addV('1').as('1'). addV('2').as('2'). addV('3').as('3'). addV('4').as('4'). addV('5').as('5'). addV('6').as('6'). addV('7').as('7'). addV('8').as('8'). addE('link').from('0').to('1'). addE('link').from('0').to('2'). addE('link').from('1').to('6'). addE('link').from('1').to('3'). addE('link').from('2').to('3'). addE('link').from('4').to('1'). addE('link').from('5').to('7'). addE('link').from('7').to('2'). addE('link').from('8').to('7').iterate() 下面的查询从‘0’开始，查找所有叶节点，然后向后查找所有根。输出不包括起始节点(‘0’)，但如有必要，可以调整查询以包括该节点。

gremlin> g.V().hasLabel('0'). ......1> repeat(out()).emit(). ......2> until(__.not(out())).dedup(). ......3> group(). ......4> by(label()). ......5> by(repeat(__.in('link')). ......6> until(__.not(__.in('link'))). ......7> label().dedup(). ......8> fold()) ==>[1:[0,4],2:[0,8,5],3:[0,8,4,5],6:[0,4]]

如果排序很重要，则可以更新查询以对列表进行排序。

更新

添加一个额外的示例，该示例还将"0"作为关键字包含在结果中。

gremlin> g.V().hasLabel('0'). ......1> emit().repeat(out()). ......2> until(__.not(out())).dedup(). ......3> group(). ......4> by(label()). ......5> by(coalesce( ......6> repeat(__.in('link')). ......7> until(__.not(__.in('link'))). ......8> label().dedup(). ......9> fold())) ==>[0:[],1:[0,4],2:[0,5,8],3:[0,4,5,8],6:[0,4]]