Запрос на получение всех путей, проходимых из данной вершины

Я пытаюсь написать запрос, который извлекает все пути, достижимые из указанной вершины. Другими словами, я пытаюсь получить весь кластер / подграф, к которому подключена вершина. Еще пара ограничений на запрос:

  1. внутренние ребра должны быть пройдены и включены в результат (я ищу все пути, которые каким-либо образом связаны с корневой вершиной.
  2. поиск должен останавливаться на указанной глубине, скажем, в 10 шагах от корневой вершины.
  3. Бонусное ограничение: я бы предпочел, чтобы результат не включал пути, которые являются полными подпутьями других путей, возвращаемых в результате.

В настоящее время у меня есть следующие два запроса, которые, похоже, работают с небольшими игрушечными графами, на которых я их тестировал. Однако в нашем большом производственном графе, похоже, есть некоторые граничные случаи, которые не возвращают все пути / ребра / вершины, которые я ожидал бы, но я не могу объяснить, почему это происходит. Два запроса также иногда возвращают несколько отличных друг от друга вершин.

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

Запрос 1:

gV (uid) .repeat (bothE (). bothV (). simplePath ()). until (loops (). is_ (10)). emit (). dedup (). path (). by (valueMap (True) )

Запрос 2:

gV (uid) .repeat (bothE (). bothV (). simplePath ()). until (bothE (). simplePath (). count (). is_ (0) .or _ (). loops (). is_ (10 )). dedup (). path (). by (valueMap (True))


graph gremlin amazon-neptune
person KOB    schedule 15.09.2020    source источник
comment
Вы хотите вернуть все пути (которые будут содержать повторяющиеся вершины) или фактическую структуру подграфа?   -  person Kelvin Lawrence    schedule 15.09.2020
comment
Я открыт для любого. Что именно вы подразумеваете под «структурой подграфа»? Планируете ли вы использовать фактическую функцию Gremlin .subgraph()?   -  person KOB    schedule 15.09.2020
comment
У Gremlin есть шаг subgraph, который вернет подграф, посещенный запросом yes - так что в качестве альтернативы path вы можете выбрать возврат подграфа, если вы хотите исключить любую часть пути, дублирующуюся.   -  person Kelvin Lawrence    schedule 15.09.2020
comment
Не могли бы вы предоставить запрос, который обеспечил бы возврат всех достижимых ребер / вершин?   -  person KOB    schedule 15.09.2020
comment
Я добавил ответ ниже, показывающий пример как path, так и subgraph   -  person Kelvin Lawrence    schedule 15.09.2020

Ответы (1)


arrow_upward
3
arrow_downward

Использование этого простого двоичного дерева в качестве тестового графа

g.addV('root').property('data',9).as('root').
  addV('node').property('data',5).as('b').
  addV('node').property('data',2).as('c').
  addV('node').property('data',11).as('d').
  addV('node').property('data',15).as('e').
  addV('node').property('data',10).as('f').
  addV('node').property('data',1).as('g').
  addV('node').property('data',8).as('h').
  addV('node').property('data',22).as('i').
  addV('node').property('data',16).as('j').
  addV('node').property('data',7).as('k').
  addV('node').property('data',51).as('l').  
  addV('node').property('data',13).as('m'). 
  addV('node').property('data',4).as('n'). 
  addE('left').from('root').to('b').
  addE('left').from('b').to('c').
  addE('right').from('root').to('d').
  addE('right').from('d').to('e').
  addE('right').from('e').to('i').
  addE('left').from('i').to('j').
  addE('left').from('d').to('f').
  addE('right').from('b').to('h').
  addE('left').from('h').to('k').
  addE('right').from('i').to('l').
  addE('left').from('e').to('m').
  addE('right').from('c').to('n').
  addE('left').from('c').to('g').iterate()

Мы могли найти все пути, используя

gremlin>   g.V().hasLabel('root').
......1>   repeat(bothE().otherV().simplePath()).
......2>   until(__.not(bothE().simplePath())).
......3>   path().
......4>     by('data').
......5>     by(label) 

==>[9,right,11,left,10]
==>[9,left,5,left,2,left,1]
==>[9,left,5,left,2,right,4]
==>[9,left,5,right,8,left,7]
==>[9,right,11,right,15,left,13]
==>[9,right,11,right,15,right,22,left,16]
==>[9,right,11,right,15,right,22,right,51]

Обратите внимание, что я использовал bothE().otherV(), как вы сказали, в вашем случае у вас могут быть как входящие, так и исходящие ребра.

Мы также могли бы использовать шаг subgraph для возврата всего подграфа, содержащего как вершины, так и ребра. В этом примере выполняется поиск поддерева, которое начинается в вершине для значения 5.

gremlin>   g.V().has('data',5).
......1>   repeat(bothE().subgraph('sg').otherV().simplePath()).
......2>   until(__.not(bothE().simplePath())).
......3>   cap('sg') 
==>tinkergraph[vertices:14 edges:13]

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

person Kelvin Lawrence    schedule 15.09.2020
comment
Спасибо. Я использую gremlin_python, поэтому, к сожалению, не думаю, что метод подграфа будет работать, поскольку мне также нужны свойства ребер и вершин. Я рассмотрю ваш первый метод и посмотрю, как он соотносится с моими существующими решениями. Я также видел SubgraphStrategy и посмотрю, смогу ли я использовать это здесь, но я не думаю, что вы можете использовать такой сложный запрос, как эти, для SubgraphStrategy, просто простые условия. - person KOB; 16.09.2020
comment
Обратите внимание, что оба этих подхода предполагают, что все пути заканчиваются на листовых узлах. Я не думаю, что это сработает для меня, поскольку в моем графе следующий пример теоретически является подграфом, который может существовать. Ваше решение ничего не возвращает gremlify.com/inch15pmxli/1 - person KOB; 16.09.2020
comment
Есть ли способ сделать что-то вроде until(next_node_has_already_been_traversed)? (Но все же добавьте край к этому узлу) - person KOB; 16.09.2020
comment
Вы можете использовать что-то вроде until(cyclicPath()) - person Kelvin Lawrence; 16.09.2020
comment
Это дает результаты. Вы должны иметь возможность повозиться с этим, чтобы получить точные результаты, которые вы хотите (какие края и т. Д.) g.V().hasLabel('customer_1').repeat(bothE(). otherV()). until(__.not(outE()).or().cyclicPath()).path() - person Kelvin Lawrence; 16.09.2020
comment
Конечно, для вашего образца графа все, что вам действительно понадобится, это это, но я считаю, из вашего описания, что реальный граф будет иметь циклы, и вам нужно смотреть на ребра в обоих направлениях. g.V().hasLabel('customer_1'). repeat(outE().inV()). until(__.not(outE())). path( - person Kelvin Lawrence; 16.09.2020
comment
Спасибо за вашу помощь. Ваше решение с использованием cyclicPath () кажется именно тем, что мне нужно. Одна вещь в том, что он возвращает множество путей. Я хочу убедиться, что возвращены все ребра и вершины, но не каждый путь, содержащий их, нужно пройти (на самом деле, чем меньше путей, тем лучше). Я немного изменил ваше исходное решение: g.V().hasLabel('A').repeat(bothE().simplePath().otherV()).until(not(bothE().simplePath()).or().loops().is(5)).path().by(label). Что ты думаешь об этом? Вы можете вспомнить какие-нибудь случаи, когда это действовало бы не так, как я бы хотел? - person KOB; 16.09.2020
comment
Выглядит хорошо, и это как бы возврат к моему исходному ответу с добавленным loops. - person Kelvin Lawrence; 16.09.2020
comment
Да, единственное изменение - это перемещение первого простого пути после шага обхода кромки, так что будут включены обрезные кромки в циклах, но он перестанет обходиться, как только попадет в вершину, которая создает цикл (я думаю ...) - person KOB; 16.09.2020