我一直在使用 Python 和 Networkx 包来尝试检测项目实体图中的桥。我不熟悉 Python 中的生成器对象,这是我目前的障碍。由于我有大量断开连接的节点,因此我的方法是在图的连接组件中应用桥检测算法,而不是在整个图中应用它。
连接组件函数返回一个生成器对象:
>>> conn = nx.connected_components(G)
>>> type(conn)
<type 'generator'>
我知道我可以使用以下方法迭代并获取每个组件:
>>> for component in conn:
>>> print component
但我的问题是,我需要对每个返回的组件执行操作,例如边缘删除以及稍后的重新添加、BFS 或 DFS,而且我不确定如何做到这一点。当我尝试迭代每个组件时,什么也没有发生。另外,我不确定如何才能迭代每个连接组件的边缘。
有什么想法吗?
最佳答案
您可能更喜欢connected_component_subgraphs()
,因为它会为您提供子图而不仅仅是节点。
In [1]: import networkx as nx
In [2]: G = nx.Graph()
In [3]: G.add_path([1,2,3,4])
In [4]: G.add_path([10,20,30,40])
In [5]: components = nx.connected_component_subgraphs(G)
In [6]: components
Out[6]:
[<networkx.classes.graph.Graph at 0x102ca7790>,
<networkx.classes.graph.Graph at 0x102ca77d0>]
In [7]: for graph in components:
...: print graph.edges()
...:
[(1, 2), (2, 3), (3, 4)]
[(40, 30), (10, 20), (20, 30)]
关于Python Networkx 桥接检测,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/28966239/