如何获得给定顶点的最小子图？

Question

我有一个图表。我想提取一个子图，其中包含列表中的节点以及链接到列表中节点的其他节点。

示例：一个图有 4 个节点：1、2、3、4，边为 1-2、2-3、1-4、3-4。如果我的列表有节点 1,4，那么子图应该是 1-2、1-4 和 3-4

python py2neo 等库中是否有用于此目的的函数？

Answer 1

对于 neo4j，您可以使用 Cypher queries 从数据库中提取子图。您可以只使用查询的 MATCH 子句来表达您要查找的模式。

在 python 中，您可能会使用 py2neo 到运行密码查询。在这里，我假设您拥有的节点列表是节点 ID。你可以这样做：

from py2neo import Graph
graph = Graph()
targets = [1,4]
for target in targets:
    results = graph.cypher.execute("MATCH (n {id: %d})-[:foo]->(otherNode) RETURN n, otherNode" % target)
    # process results

有一点需要注意。您的图表指定 1 连接到 4，但 3 也是如此。这实际上会使连接的子图组件 1-3-4，而不是 1-4 和 3-4。因为您是这样指定的，请注意我上面所做的匹配只为您提供了从您正在搜索的节点开始的一跳。

Answer 2

以下是使用 Gremlin 的方法。

如果你想得到树的结果：

gremlin> g.v(1,4).both().tree().cap().next()
==>v[1]={v[2]={}, v[4]={}}
==>v[4]={v[1]={}, v[3]={}}

或者，如果您更喜欢真正的子图，请使用 recipe from the GremlinDocs:

gremlin> sg = new TinkerGraph()
==>tinkergraph[vertices:0 edges:0]
gremlin> goc = { v, g ->
gremlin>   g.getVertex(v.id) ?: g.addVertex(v.id, ElementHelper.getProperties(v))
gremlin> }
==>groovysh_evaluate$_run_closure1@5118388b
gremlin> g.E().filter { it.bothV().retain(g.v(1,4).toList()).hasNext() }.sideEffect {
gremlin>  sg.addEdge(it.id, goc(it.outV.next(), sg), goc(it.inV.next(), sg), it.label,
gremlin>      ElementHelper.getProperties(it))
gremlin> }.iterate()
==>null
gremlin> sg.V()
==>v[1]
==>v[2]
==>v[3]
==>v[4]
gremlin> sg.E()
==>e[0][1-link->2]
==>e[2][1-link->4]
==>e[3][3-link->4]

我不熟悉 Python 库，但我想如果您使用的是 Bulbs.

，那几乎只是复制和粘贴

如何获得给定顶点的最小子图？

How to get minimum subgraph for given vertices?

python

neo4j

graph-databases

titan