如何得到给定顶点的最小子图？
如何得到给定顶点的最小子图？
提问于 2015-01-11 13:51:34
我有个图表。我希望提取一个包含列表中节点的子图，以及链接到列表中节点的其他节点。
例子:图有4个节点: 1,2,3,4有边1-2，2-3，1-4，3-4.如果我的列表有节点1,4，那么子图应该是1-2，1-4和3-4。
在像py2neo这样的python库中有这样的函数吗？
回答 2
Stack Overflow用户
回答已采纳
发布于 2015-01-11 15:04:37
对于neo4j，可以使用Cypher查询从数据库中提取子图。您只需使用查询的MATCH子句来表示正在寻找的模式。
在python中，您可能会使用py2neo来运行密码查询。在这里，我假设您拥有的节点列表是节点I。你可能会做这样的事情：
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。因为您是这样指定的，所以请注意，我上面所做的匹配只给出了您要搜索的节点的一跳。
Stack Overflow用户
发布于 2015-01-11 21:41:17
下面是用Gremlin做这件事的方法。
如果您想以树的形式获得结果：
gremlin> g.v(1,4).both().tree().cap().next()
==>v[1]={v[2]={}, v[4]={}}
==>v[4]={v[1]={}, v[3]={}}或者，如果您喜欢真正的子图，请使用来自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库，但我想，如果您使用鳞茎，它几乎只能复制和粘贴。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/27887825
复制相关文章
相似问题
腾讯云开发者
