Получить все узлы, которые могут быть достигнуты определенным узлом в ориентированном графе

Question

Учитывая график в Neo4j, который направлен (но возможно иметь циклы), как я могу извлечь все узлы, которые доступны из определенного узла с Cypher?

(Также: как долго можно ожидать, что запрос, подобный этому, займет, если у моего графа 2 миллиона узлов, а с расширением 48 миллионов узлов? Грубая шкала будет делать, например, меньше минуты, несколько минут, час)

Answer 1

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

В библиотеке APOC есть несколько процедур расширения путей , которые направленыв этих случаях использования.

Если вы пытаетесь найти все достижимые узлы из начального узла, пересекая отношения в любом направлении, вы можете использовать apoc.path.subgraphNodes(), например, используя график фильмов в качестве примера:

MATCH (n:Movie {title:"The Matrix"})
CALL apoc.path.subgraphNodes(n, {}) YIELD node
RETURN node

Если вам нужны только достижимые узлы, идущие в определенном направлении (скажем, исходящие), то вы можете использовать для этого атрибут RelationsFilter.Вы также можете добавить тип, если это важно, но если бы мы хотели, чтобы достижимость была возможной только через какие-либо исходящие отношения, запрос будет выглядеть так:

MATCH (n:Movie {title:"The Matrix"})
CALL apoc.path.subgraphNodes(n, {relationshipFilter:'>'}) YIELD node
RETURN node

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

Answer 2

Посмотрите здесь , где используется алгоритм для обнаружения сообщества.

Вы можете использовать что-то вроде

match (n:Movie {title:"The Matrix"})-[r*1..50]-(m) return distinct id(m)

, но медленно Кроме того, это также зависит от того, как связан ваш набор данных, например, nr отношений.