java - TinkerPop 图中的深度优先树遍历

Question

给定一个树形结构的 TinkerPop 图，其顶点通过标记的父子关系 ([parent-PARENT_CHILD->child]) 连接，遍历并查找所有这些节点的惯用方法是什么？

我是图形遍历的新手，因此使用递归函数遍历它们似乎或多或少简单:

Stream<Vertex> depthFirst(Vertex v) {
  Stream<Vertex> selfStream = Stream.of(v);
  Iterator<Vertex> childIterator = v.vertices(Direction.OUT, PARENT_CHILD);
  if (childIterator.hasNext()) {
    return selfStream.appendAll(
      Stream.ofAll(() -> childIterator)
        .flatMap(this::depthFirst)
    );
  }
  return selfStream;
}

_{(注意，此示例使用 Vavr 流，但 Java 流版本类似，只是稍微更详细。)}

我认为图 native 实现的性能会更高，尤其是在内存 TinkerGraph 以外的数据库上。

但是，当我查看 TinkerPop tree recipes 时，目前尚不清楚 repeat()/until() 等的哪种组合最适合执行我想要的操作。

如果我只想查找具有特定标签的顶点(叶子或分支)，我可以再次了解如何使用上面的函数来做到这一点:

Stream<Vertex> nodesWithMyLabel = depthFirst(root)
  .filter(v -> "myLabel".equals(v.label()));

但这是否有效还远非显而易见，我认为一定有更好的图原生方法。

Answer 1

如果您使用 TinkerPop，最好只使用 Gremlin 编写遍历。让我们使用配方中描述的树:

g.addV().property(id, 'A').as('a').
  addV().property(id, 'B').as('b').
  addV().property(id, 'C').as('c').
  addV().property(id, 'D').as('d').
  addV().property(id, 'E').as('e').
  addV().property(id, 'F').as('f').
  addV().property(id, 'G').as('g').
  addE('hasParent').from('a').to('b').
  addE('hasParent').from('b').to('c').
  addE('hasParent').from('d').to('c').
  addE('hasParent').from('c').to('e').
  addE('hasParent').from('e').to('f').
  addE('hasParent').from('g').to('f').iterate()

要查找“A”的所有子级，您只需执行以下操作:

gremlin> g.V('A').repeat(out()).emit()
==>v[B]
==>v[C]
==>v[E]
==>v[F]

上面的遍历基本上是说，“从‘A’顶点开始，遍历出边，直到没有更多的边，哦，顺便说一句，当你去的时候发出每个子顶点。”如果你也想这样做得到“A”的根，然后你只需要稍微改变一下:

gremlin> g.V('A').emit().repeat(out())
==>v[A]
==>v[B]
==>v[C]
==>v[E]
==>v[F]

更进一步，如果您只想根据某个过滤器(在您指定的标签中的问题中)发出某些顶点，您只需为 emit() 提供一个过滤参数即可。在这种情况下，我只发出那些具有多个传入边的顶点:

gremlin> g.V('A').emit(inE().count().is(gt(1))).repeat(out())
==>v[C]
==>v[F]