Гремлин Все кратчайшие пути от нескольких вершин до одной вершины

Следующий вопрос о переполнении стека

Как повысить производительность кратчайшего пути с помощью Gremlin?

показывает, как найти кратчайший путь от начальной одной начальной вершины с идентификатором 687 до конечной вершины с идентификатором 1343 и делает это эффективно, гарантируя, что пути не повторяются с использованием store, without и aggregate

g.V(687).store('x').repeat(out().where(without('x')).aggregate('x')).until(hasId(1343)).limit(1).path()

Я хотел бы выполнить тот же запрос с тем же уровнем эффективности, однако мне нужны все кратчайшие пути от нескольких начальных вершин с одной и той же меткой к одной и той же конечной вершине, например, это будет выглядеть примерно так (хотя это не т работать)

g.V().hasLabel('label').store('x').repeat(out().where(without('x')).aggregate('x')).until(hasId(1343)).limit(1).path()

Я пробовал несколько конструкций с двумя повторениями в операторе, но не могу получить независимый store('x') для каждой начальной вершины. Я также использую платформу AWS Neptune, поэтому она ограничивает использование Gremlin там, где не разрешены циклы / скрипты. Все запросы gremlin должны начинаться с g. и состоять из команд, связанных вместе с .

https://docs.aws.amazon.com/neptune/latest/userguide/access-graph-gremlin-differences.html


gremlin tinkerpop3 amazon-neptune tinkerpop
person rossb83    schedule 10.09.2018    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Этот метод нельзя применить к нескольким стартовым вершинам. Однако вы можете просто начать с другой стороны, поскольку это единственная известная вершина:

g.V(1343).store('x').
  repeat(__.in().where(without('x')).aggregate('x')).
    until(hasLabel('label')).
  path()

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

g.V(1343).store('x').
  repeat(__.in().where(without('x')).aggregate('x')).
    emit(hasLabel('label')).
  path()
person Daniel Kuppitz    schedule 11.09.2018
comment
Разве это не работает с несколькими начальными вершинами, потому что BFS выполняется параллельно для каждого обхода? - person rossb83; 21.11.2018
comment
Вроде. Если вы попадаете в любую вершину X на одном пути, она добавляется в список исключенных ('x'); затем, если вы снова попадете в эту вершину позже на другом пути, переходники больше не будут следовать по этому пути и, таким образом, они могут не найти кратчайший (или любой) путь к целевой вершине. - person Daniel Kuppitz; 21.11.2018