Gremlin：如何有效地在有向无环图中找到根？ [英] Gremlin: How to efficiently find "roots" in directed acyclic graph?

问题描述

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

任务：给定一个根节点，交付一个映射，其中包含下游节点的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]]   
  

这篇关于Gremlin：如何有效地在有向无环图中找到根？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！