在 Neo4j 中查找通过给定节点的所有简单循环
Find all simple cycles through a given node in Neo4j
我正在处理图表,最近才知道 neo4j。
neo4j 可以帮助我找到通过图中给定节点的所有简单循环吗?
我已经可以通过实现 a modification of Johnson's algorithm.
在 java
/python
代码中做到这一点
这只是我创建的一个图表示例,是可以在 neo4j 数据库上执行的 Cypher 代码:
CREATE (John:Person { name : '@john',facebook: 'facebook.com/john'})
CREATE (Josh:Person { name : '@josh',facebook: 'facebook.com/josh'})
CREATE (Dan:Person { name : '@dan',facebook: 'facebook.com/dan'})
CREATE (Kenny:Person { name : '@kenny',facebook: 'facebook.com/kenny'})
CREATE (Bart:Person { name : '@bart',facebook: 'facebook.com/bart'})
CREATE (Mike:Person { name : '@mike',facebook: 'facebook.com/mike'})
CREATE (Jenny:Person { name : '@jenny',facebook: 'facebook.com/jenny'})
CREATE (Frank:Person { name : '@frank',facebook: 'facebook.com/frank'})
CREATE (Erick:Person { name : '@erick',facebook: 'facebook.com/erick'})
CREATE (Lynda:Person { name : '@lynda',facebook: 'facebook.com/lynda'})
CREATE (Lynda)-[:KNOWS]-> (Josh)
CREATE (Lynda)-[:KNOWS]-> (Frank)
CREATE (Lynda)-[:KNOWS]-> (Bart)
CREATE (Josh)-[:KNOWS]-> (Erick)
CREATE (Josh)-[:KNOWS]-> (Jenny)
CREATE (Josh)-[:KNOWS]-> (Dan)
CREATE (Dan)-[:KNOWS]-> (Lynda)
CREATE (Dan)-[:KNOWS]-> (Josh)
CREATE (Dan)-[:KNOWS]-> (Mike)
CREATE (Dan)-[:KNOWS]-> (Kenny)
CREATE (Mike)-[:KNOWS]-> (Kenny)
CREATE (Kenny)-[:KNOWS]-> (Bart)
CREATE (Bart)-[:KNOWS]-> (Josh)
CREATE (Frank)-[:KNOWS]-> (Erick)
CREATE (Erick)-[:KNOWS]-> (Frank)
...这些是图中的所有循环:
Josh->Dan->Lynda->Josh
Josh->Dan->Lynda->Bart->Josh
Josh->Dan->Josh
Josh->Dan->Mike->Kenny->Bart->Josh
Josh->Dan->Kenny->Bart->Josh
这里是简单测试用例的列表:
1- input: Josh
output (all the cycles):
Josh->Dan->Lynda->Josh
Josh->Dan->Lynda->Bart->Josh
Josh->Dan->Josh
Josh->Dan->Mike->Kenny->Bart->Josh
Josh->Dan->Kenny->Bart->Josh
2- input: Lynda
output:
Josh->Dan->Lynda->Josh
Josh->Dan->Lynda->Bart->Josh
您可以使用以下查询在 Cypher 中执行此操作:
MATCH p=(n)-[*]->(n) RETURN nodes(p)
查询的文本表示是:
求出起始节点和结束节点相同且完整路径有出方向的路径
请注意,这是对 medium/large 图的昂贵查询,您可以限制路径的深度,例如:
MATCH p=(n)-[*1..15]->(n) RETURN nodes(p)
也许您还希望最小深度为 2,因为与自身有关系的节点将返回深度 1 ;-)
我正在处理图表,最近才知道 neo4j。
neo4j 可以帮助我找到通过图中给定节点的所有简单循环吗?
我已经可以通过实现 a modification of Johnson's algorithm.
在java
/python
代码中做到这一点
这只是我创建的一个图表示例,是可以在 neo4j 数据库上执行的 Cypher 代码:
CREATE (John:Person { name : '@john',facebook: 'facebook.com/john'})
CREATE (Josh:Person { name : '@josh',facebook: 'facebook.com/josh'})
CREATE (Dan:Person { name : '@dan',facebook: 'facebook.com/dan'})
CREATE (Kenny:Person { name : '@kenny',facebook: 'facebook.com/kenny'})
CREATE (Bart:Person { name : '@bart',facebook: 'facebook.com/bart'})
CREATE (Mike:Person { name : '@mike',facebook: 'facebook.com/mike'})
CREATE (Jenny:Person { name : '@jenny',facebook: 'facebook.com/jenny'})
CREATE (Frank:Person { name : '@frank',facebook: 'facebook.com/frank'})
CREATE (Erick:Person { name : '@erick',facebook: 'facebook.com/erick'})
CREATE (Lynda:Person { name : '@lynda',facebook: 'facebook.com/lynda'})
CREATE (Lynda)-[:KNOWS]-> (Josh)
CREATE (Lynda)-[:KNOWS]-> (Frank)
CREATE (Lynda)-[:KNOWS]-> (Bart)
CREATE (Josh)-[:KNOWS]-> (Erick)
CREATE (Josh)-[:KNOWS]-> (Jenny)
CREATE (Josh)-[:KNOWS]-> (Dan)
CREATE (Dan)-[:KNOWS]-> (Lynda)
CREATE (Dan)-[:KNOWS]-> (Josh)
CREATE (Dan)-[:KNOWS]-> (Mike)
CREATE (Dan)-[:KNOWS]-> (Kenny)
CREATE (Mike)-[:KNOWS]-> (Kenny)
CREATE (Kenny)-[:KNOWS]-> (Bart)
CREATE (Bart)-[:KNOWS]-> (Josh)
CREATE (Frank)-[:KNOWS]-> (Erick)
CREATE (Erick)-[:KNOWS]-> (Frank)
...这些是图中的所有循环:
Josh->Dan->Lynda->Josh
Josh->Dan->Lynda->Bart->Josh
Josh->Dan->Josh
Josh->Dan->Mike->Kenny->Bart->Josh
Josh->Dan->Kenny->Bart->Josh
这里是简单测试用例的列表:
1- input: Josh
output (all the cycles):
Josh->Dan->Lynda->Josh
Josh->Dan->Lynda->Bart->Josh
Josh->Dan->Josh
Josh->Dan->Mike->Kenny->Bart->Josh
Josh->Dan->Kenny->Bart->Josh
2- input: Lynda
output:
Josh->Dan->Lynda->Josh
Josh->Dan->Lynda->Bart->Josh
您可以使用以下查询在 Cypher 中执行此操作:
MATCH p=(n)-[*]->(n) RETURN nodes(p)
查询的文本表示是:
求出起始节点和结束节点相同且完整路径有出方向的路径
请注意,这是对 medium/large 图的昂贵查询,您可以限制路径的深度,例如:
MATCH p=(n)-[*1..15]->(n) RETURN nodes(p)
也许您还希望最小深度为 2,因为与自身有关系的节点将返回深度 1 ;-)