检索有向图中特定节点可以到达的所有节点 [英] Retrieve All Nodes That Can Be Reached By A Specific Node In A Directed Graph
问题描述
给定Neo4j中的一个有向图(但可能有周期)，我该如何使用Cypher检索特定节点可到达的所有节点?
Given a graph in Neo4j that is directed (but possible to have cycles), how can I retrieve all nodes that are reachable from a specific node with Cypher?
(另外:如果我的图形有200万个节点，并且扩展到4800万个节点，我希望这样的查询要花多长时间?例如，一个粗略的量规将执行不到一分钟，几分钟，一个小时的操作)
(Also: how long can I expect a query like this to take if my graph has 2 million nodes, and by extension 48 million nodes? A rough gauge will do eg. less than a minute, few minutes, an hour)
推荐答案
Cypher的唯一性行为是，关系必须在每个路径上都是唯一的(每个关系只能在每个路径上遍历一次)，但这对于此类用例中，目标是找到不同的节点，因此一个节点总共只能访问一次(跨所有路径，而不是每个路径).
Cypher's uniqueness behavior is that relationships must be unique per path (each relationship can only be traversed once per path), but this isn't efficient for these kinds of use cases, where the goal is instead to find distinct nodes, so a node should only be visited once total (across all paths, not per path).
There are some path expander procedures in the APOC Procedures library that are directed at these use cases.
如果您试图从起始节点查找所有可到达的节点，并在任一方向上遍历关系，则可以像电影图一样使用apoc.path.subgraphNodes()进行操作，
If you're trying to find all reachable nodes from a starting node, traversing relationships in either direction, you can use apoc.path.subgraphNodes() like so, using the movies graph as an example:
MATCH (n:Movie {title:"The Matrix"})
CALL apoc.path.subgraphNodes(n, {}) YIELD node
RETURN node
如果您只希望可到达的节点沿着特定的方向(例如传出)进行操作，则可以使用RelationshipFilter来指定此方向.如果很重要，您也可以添加类型，但是如果我们只希望通过任何传出关系可访问，查询将类似于:
If you only wanted reachable nodes going a specific direction (let's say outgoing) then you can use a relationshipFilter to specify this. You can also add in the type too if that's important, but if we only wanted reachable via any outgoing relationship the query would look like:
MATCH (n:Movie {title:"The Matrix"})
CALL apoc.path.subgraphNodes(n, {relationshipFilter:'>'}) YIELD node
RETURN node
在任何一种情况下，这些方法都比单独使用Cypher更好，特别是在任何中等连通的图中，因为对于每个可达节点都只会考虑一条路径(将修剪掉已访问节点的替代路径，从而切断遍历遍历过程中可能探索的路径，这非常有效，因为我们不在乎此用例的这些替代路径.
In either case these approaches should work better than with Cypher alone, especially in any moderately connected graph, as there will only ever be a single path considered for every reachable node (alternate paths to an already visited node will be pruned, cutting down on the possible paths to explore during traversal, which is efficient as we don't care about these alternate paths for this use case).
这篇关于检索有向图中特定节点可以到达的所有节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
