Обход дерева в глубину в графе TinkerPop

Учитывая древовидный граф 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 аналогична, только немного более подробна .)

Я предполагаю, что реализация на основе графа будет более производительной, особенно в базах данных, отличных от TinkerGraph в памяти.

Однако, когда я смотрю на древовидные рецепты TinkerPop, не совсем понятно, какие комбинация repeat() / until() и т. д. является правильной, чтобы делать то, что я хочу.

Если я затем хочу найти только те вершины (лист или ветвь) с определенной меткой, я снова могу увидеть, как это сделать с помощью функции выше:

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

но далеко не очевидно, что это эффективно, и я предполагаю, что должен быть лучший подход, основанный на графах.


java gremlin tinkerpop3 graph-databases
person David Moles    schedule 16.12.2017    source источник

Ответы (2)


arrow_upward
5
arrow_downward

Если вы используете 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()

Чтобы найти всех потомков «А», просто выполните:

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

Приведенный выше обход в основном говорит: «Начать с вершины 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]
person stephen mallette    schedule 17.12.2017
comment
Что, если я хочу просматривать не все отношения, а только те, у которых есть указанная метка? - person David Moles; 17.12.2017
comment
Также: где действует фильтр на вашем последнем шаге? Означает ли это, что вы смотрите только на внешние отношения вершин, прошедших фильтр? Поскольку вы заметите, что в рекурсивной версии в вопросе фильтр применяется только к результату полного обхода. - person David Moles; 17.12.2017
comment
если вы хотите фильтровать по ярлыку, измените дополнительный обход фильтрации в emit(). вместо подсчета ребер просто оцените метку: emit(hasLabel('label-i-care-about')) Фильтр не применяется на out(). Если бы это было так, он бы не прошел за вершину B и не получил бы возврата. Это только фильтрация вершин, которые испускаются из repeat() в результате полного обхода. - person stephen mallette; 17.12.2017
comment
Здесь задействованы две метки: метка на ребрах (идентифицирующая единственные ребра, по которым я хочу следовать) и метка на вершинах (идентифицирующая единственные ребра, которые я хочу получить). - person David Moles; 18.12.2017
comment
Вы можете создать любой фильтр в emit(), какой захотите. Тогда в вашем распоряжении весь гремлинский язык. Если вам нужны метки ребер и вершин, то: emit(both('edges-i-care-about').hasLabel('vertices-i-care-about')) - person stephen mallette; 18.12.2017

arrow_upward
0
arrow_downward

Вот что у меня получилось после определенного количества проб и ошибок:

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, что я мог бы включить родителя, поставив emit() перед repeat(), но я не пробовал.)

person David Moles    schedule 21.12.2017