Python Networkx 网桥检测

Question

我一直在使用 Python 和 Networkx 包来尝试检测项目实体图中的桥接。我不熟悉 Python 中的生成器对象，这是我目前的障碍。由于我有大量断开连接的节点，我的方法是在图中的连接组件中应用桥接检测算法，而不是在整个图中应用它。

连通分量函数returns生成器对象：

>>> conn = nx.connected_components(G) 
>>> type(conn)
<type 'generator'>

我知道我可以迭代并使用以下方法获取每个组件：

>>> for component in conn:
>>>     print component

但我的问题是我需要对每个返回的组件执行操作，例如边缘移除和稍后的重新添加、BFS 或 DFS，我不确定我该怎么做。当我尝试遍历每个组件时，什么也没有发生。此外，我不确定如何迭代每个连接组件的边缘。

有什么想法吗？

Answer 1

您可能更喜欢 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 网桥检测

Python Networkx Bridge Detection

python

graph

generator

networkx