bridges(G, root=None)
A bridge in a graph is an edge whose removal causes the number of connected components of the graph to increase. Equivalently, a bridge is an edge that does not belong to any cycle. Bridges are also known as cut-edges, isthmuses, or cut arcs.
This is an implementation of the algorithm described in . An edge is a bridge if and only if it is not contained in any chain. Chains are found using the networkx.chain_decomposition
function.
The algorithm described in requires a simple graph. If the provided graph is a multigraph, we convert it to a simple graph and verify that any bridges discovered by the chain decomposition algorithm are not multi-edges.
Ignoring polylogarithmic factors, the worst-case time complexity is the same as the networkx.chain_decomposition
function, $O(m + n)$, where $n$ is the number of nodes in the graph and $m$ is the number of edges.
A node in the graph G. If specified, only the bridges in the connected component containing this node will be returned.
If :None:None:`root` is not in the graph G.
If G is a directed graph.
Generate all bridges in a graph.
An edge in the graph whose removal disconnects the graph (or causes the number of connected components to increase).
The barbell graph with parameter zero has a single bridge:
>>> G = nx.barbell_graph(10, 0)See :
... list(nx.bridges(G)) [(9, 10)]
The following pages refer to to this document either explicitly or contain code examples using this.
networkx.algorithms.bridges.bridges
Hover to see nodes names; edges to Self not shown, Caped at 50 nodes.
Using a canvas is more power efficient and can get hundred of nodes ; but does not allow hyperlinks; , arrows or text (beyond on hover)
SVG is more flexible but power hungry; and does not scale well to 50 + nodes.
All aboves nodes referred to, (or are referred from) current nodes; Edges from Self to other have been omitted (or all nodes would be connected to the central node "self" which is not useful). Nodes are colored by the library they belong to, and scaled with the number of references pointing them