使用图形数据库查找图形上两个节点之间的所有可能路径

Question

我有一组节点组成一个 DAG（有向无环图），不保证有循环。我想将节点存储在数据库中并让数据库执行搜索以显示两个节点之间的所有路径。

例如，您可能认为我有一个复杂项目的 git 历史。

每个节点都可以用一个 JSON 对象来描述，该对象具有：

  {'id':'id',
   'outbound':['id1','id2','id3']}
  }

所以如果我在数据库中有这些节点：

  {'id':'id0',
   'outbound':['id1','id2']}
  }

  {'id':'id1',
   'outbound':['id2','id3','id4','id5,'id6']}
  }

  {'id':'id2',
   'outbound':['id2','id3'}
  }

如果我想知道连接 id0 和 id3 的所有路径，我想得到三个列表：

   id0 -> id1 -> id3
   id0 -> id2 -> id3
   id0 -> id1 -> id2 -> id3

我今天有几千个这样的节点，明天我会有几万个。但是数据库中有很多个DAG，典型的DAG只有5-10个节点，所以这个问题就是tractable.

我认为没有办法有效地做到这一点 MySQL（现在所有对象都存储在 table 的 JSON 列中），但是我相信可以在像 Neo4j 这样的图形数据库中高效地完成它。

我看过Neo4J documentation on Path Finding Algorithms and perhaps I'm confused, but the examples don't really look like working examples. I found a MySQL example which uses stored procedures and it doesn't look like it parallelizes very well. I'm not even sure what Amazon Neptune在做什么；我认为它正在使用 Spark GraphX。

我不知道从哪里开始。

Answer 1

Graph Data Science 库寻路算法旨在找到最短的加权路径，并使用类似于 Dijkstra 的算法来找到它们。在您的情况下，您似乎正在处理有向未加权图，并且可以使用本机密码 allShortestPath 过程：

例如：

MATCH (n1:Node{id:"A"}),(n2:Node{id:"B"})
MATCH path=allShortestPaths((n1)-[*..10]->(n2))
RETURN [n in nodes(path) | n.id] as outbound_nodes_id

检查 Cypher refcard 以了解 Neo4j 中 Cypher 的可用功能总是有用的

Answer 2

使用 Neo4j 完全可行。

导入json数据

[
  {"id":"id0",
   "outbound":["id1","id2"]
  },
  {"id":"id1",
   "outbound":["id2","id3","id4","id5","id6"]
  },
  {"id":"id2",
   "outbound":["id2","id3"]
  }
]

CALL apoc.load.json("graph.json") 
YIELD value
MERGE (n:Node {id: value.id})
WITH n, value.outbound AS outbound
UNWIND outbound AS o
MERGE (n2:Node {id: o}) 
MERGE (n)-[:Edge]->(n2)

Apparently the data you provided is not acyclic...

获取两个节点之间的所有路径

由于您没有提到最短路径，而是所有路径，因此不需要特定算法：

MATCH p=(:Node {id: "id0"})-[:Edge*]->(:Node {id: "id3"}) RETURN nodes(p)

"[{""id"":id0},{""id"":id1},{""id"":id3}]"
"[{""id"":id0},{""id"":id2},{""id"":id3}]"
"[{""id"":id0},{""id"":id1},{""id"":id2},{""id"":id3}]"
"[{""id"":id0},{""id"":id2},{""id"":id2},{""id"":id3}]"
"[{""id"":id0},{""id"":id1},{""id"":id2},{""id"":id2},{""id"":id3}]"

比较MySql

见how-much-faster-is-a-graph-database-really

使用图形数据库查找图形上两个节点之间的所有可能路径

Find all possible paths between two nodes on graph using a graph database

mysql

graph

neo4j

spark-graphx