Python Networkx Bridge Detection

Question

I have been using Python and Networkx package in an attempt to detect bridges in a entity graph for a project. I am not familiar with generator objects in Python, and that is kind of my blocker at this point. My approach, since I have a large amount of disconnected nodes is to apply a bridge detection algorithm in the connected components of the graph instead of applying it in the entire graph.

The connected components function returns a generator object:

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

I know I can iterate and get each component using:

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

but my issue is that I need to perform actions on each returned component such as edge removal and later on re-addition, BFS or DFS, and I am not sure how I could do that. When I try to iterate over each component nothing happens. Also I am not sure how can someone can iterate over each connected component's edges.

Any ideas?

Aric Aric · Accepted Answer · 2015-03-10T16:26:08

You might like connected_component_subgraphs() better since it will give you subgraphs instead of just the nodes.

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 Bridge Detection

1 Answers