首页 文章

TinkerPop图中的深度优先树遍历

提问于
浏览 次
2

给定一个树形结构的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;
}

（N.b.这个例子使用Vavr流，但Java流版本类似，只是稍微冗长 . ）

我假设一个图本机实现会更高效，特别是在内存中的TinkerGraph以外的数据库上 .

但是，当我看到TinkerPop tree recipes时， repeat() / until() 等的哪个组合是正确的做我想做的事情并不明显 .

如果我想再找到那些具有特定标签的顶点（叶子或分支），我再次看到如何用上面的函数做到：

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

但是很明显这是有效的，我认为必须有一个更好的图本地方法 .

java graph-databases gremlin tinkerpop3

2 回答

  • 4

    如果您正在使用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]
    回复于
  • 0

    在经过一定程度的试验和错误之后，这就是我最终得到的结果：

    GraphTraversal<Vertex, Vertex> traversal = 
  graph.traversal().V(parent)
    .repeat(out(PARENT_CHILD))     // follow only edges labeled PARENT_CHILD
    .emit()
    .hasLabel("myLabel");          // filter for vertices labeled "myLabel"

    请注意，这与原始问题中的递归版本略有不同，因为我意识到我实际上并不想在结果中包含父级 . （我想，从Repeat Step docs开始，我可以通过在 repeat() 之前放置 emit() 来包含父级，但我还没有尝试过 . ）

    回复于

相关问题