Гремлин: найти все узлы из одного набора с подключением к другому

Учитывая два запроса Gremlin q1 и q2 и их результаты ri = qi.toSet(), я хочу найти все узлы в r1, которые имеют соединение с узлом в r2 - игнорируя метки кромок и направление.

Мой текущий подход включал вычисление кратчайших путей между двумя наборами результатов:

q1.shortestPath().with_(ShortestPath.target, q2).toList()

Однако я обнаружил, что вычисление кратчайшего пути в Tinkerpop не подходит для этой цели, потому что результат будет пустым, если в r1 есть узлы без какого-либо соединения с каким-либо узлом в r2.

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

У вас есть предложения, как я могу решить эту проблему в gremlin-python?


gremlin gremlinpython
person Green    schedule 27.12.2019    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Вот один из способов сделать то, что вам нужно, в Gremlin Python. Это может быть или не быть эффективным в зависимости от размера и формы вашего графика. В моем тестовом графе только вершины 1, 2 и 3 имеют путь к 12 или 13. Этот пример не показывает вам, как вы туда попали, просто существует по крайней мере один путь (если он существует).

>>> ids = g.V('1','2','3','99999').id().toList()
>>> ids
['1', '2', '3', '99999']
>>> ids2 = g.V('12','13').id().toList()
>>> ids2
['12', '13']

>>> g.V(ids).filter(__.repeat(__.out().simplePath()).until(__.hasId(within(ids2))).limit(1)).toList()
[v[1], v[2], v[3]]

Вы также можете использовать dedup () вместо simplePath () и limit (), если вам важно только то, что существует какой-либо маршрут.

g.V(ids).filter(__.repeat(__.out().dedup()).until(__.hasId(within(ids2)))).toList()
person Kelvin Lawrence    schedule 27.12.2019
comment
Спасибо за ваше предложение. Поскольку меня интересуют оба направления, я заменил out() на both(). К сожалению, я получаю тайм-аут, если начальный набор (т.е. g.V (ids)) больше 3. Мой граф состоит примерно из 7000 узлов и 19000 ребер. - person Green; 28.12.2019
comment
Не могли бы вы рассказать немного больше о форме / схеме вашего графа? Я протестировал запрос, используя граф с 4 КБ вершинами и 50 КБ ребер, и у меня не было проблем. Я пробовал разное количество исходных и целевых вершин. Я также отредактировал свой ответ, чтобы показать альтернативный способ написания запроса. - person Kelvin Lawrence; 28.12.2019
comment
Форма dedup () будет более производительной в тех случаях, когда вы просто хотите знать, что существует хотя бы один маршрут между каждой исходной вершиной и одной из целевых вершин. - person Kelvin Lawrence; 28.12.2019
comment
Граф состоял из нескольких полносвязных компонентов, я подозревал, что в этом графе может быть слишком много путей. - person Green; 01.02.2020