python - 获取包含一定数量节点的networkx子图
问题描述
我有一个 networkx DiGraph,我想提取包含一定数量节点的子图。例如,有向图是 0-1-2-3-4-5。我想获取包含 3 个节点的所有子图。结果应该是:0-1-2、1-2-3、2-3-4、3-4-5。我怎样才能做到这一点?
解决方案
我不完全确定我是否理解正确:您的示例暗示您只想要连接的子图?在有向图中,存在不止一种连接(弱连接和强连接)。所以你必须决定你要找哪一个。
这可能有效:
import networkx as nx
from itertools import combinations
# The graph in your example (as I understand it)
G = nx.DiGraph((i, i+1) for i in range(5))
num_of_nodes = 3 # Number of nodes in the subgraphs (here 3, as in your example)
subgraphs = [] # List for collecting the required subgraphs
for nodes in combinations(G.nodes, num_of_nodes):
G_sub = G.subgraph(nodes) # Create subgraph induced by nodes
# Check for weak connectivity
if nx.is_weakly_connected(G_sub):
subgraphs.append(G_sub)
combinations(G.nodes, num_of_nodes)
遍历来自 的num_of_nodes
许多节点的所有唯一组合G
。
选定的子图正是您提到的子图:
print([H.nodes for H in subgraphs])
print([H.edges for H in subgraphs])
节目
[NodeView((0, 1, 2)), NodeView((1, 2, 3)), NodeView((2, 3, 4)), NodeView((3, 4, 5))]
[OutEdgeView([(0, 1), (1, 2)]), OutEdgeView([(1, 2), (2, 3)]), OutEdgeView([(2, 3), (3, 4)]), OutEdgeView([(3, 4), (4, 5)])]
如果您的图表是
G = nx.DiGraph([(i, i+1) for i in range(5)] + [(i+1, i) for i in range(5)])
并且您正在寻找强大的连接性,那么您必须使用
...
# Check for strong connectivity
if nx.is_strongly_connected(G_sub):
...
(通常的警告:G.subgraph()
只给你一个视图。)
推荐阅读
- autodesk-forge - Autodesk Forge 查看器将选择颜色设置为默认值
- c# - 如何在不使用 JS 的情况下打开新窗口
- javascript - 在 RabbitMQ 队列上发布的模块导出功能
- windows - 如何使用 NSIS 将程序添加到“打开方式”菜单
- jenkins - 在主动选择反应参数中参考主动选择参数返回值
- ansible - 如何循环遍历不同的 Clodformation 模板?
- sql - 将“nvarchar”列数据类型转换为“DateTime”
- excel - Excel:按列查找和排序匹配项
- vb.net - Visual Basic Threading.Thread 无法按我的意愿工作,我的代码有什么问题?
- html - 有没有办法避免为不同的锚标签()重复鼠标悬停/鼠标悬停功能,这些锚标签在悬停时会产生相同的视觉效果?