algorithm - 在 Neo4j 中查找通过给定节点的所有简单循环

Question

我正在处理图表并且最近知道 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

Answer 1

您可以使用以下查询在 Cypher 中执行此操作:

MATCH p=(n)-[*]->(n) RETURN nodes(p)

查询的文本表示是:

求出起始节点和结束节点相同且完整路径有出方向的路径

请注意，这是对中型/大型图的昂贵查询，您可以限制路径的深度，例如:

MATCH p=(n)-[*1..15]->(n) RETURN nodes(p)

也许您还希望最小深度为 2，因为与自身有关系的节点将返回深度 1 ;-)