Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1"""Bridge-finding algorithms."""
3from itertools import chain
5import networkx as nx
6from networkx.utils import not_implemented_for
8__all__ = ["bridges", "has_bridges", "local_bridges"]
11@not_implemented_for("directed")
12@nx._dispatchable
13def bridges(G, root=None):
14 """Generate all bridges in a graph.
16 A *bridge* in a graph is an edge whose removal causes the number of
17 connected components of the graph to increase. Equivalently, a bridge is an
18 edge that does not belong to any cycle. Bridges are also known as cut-edges,
19 isthmuses, or cut arcs.
21 Parameters
22 ----------
23 G : undirected graph
25 root : node (optional)
26 A node in the graph `G`. If specified, only the bridges in the
27 connected component containing this node will be returned.
29 Yields
30 ------
31 e : edge
32 An edge in the graph whose removal disconnects the graph (or
33 causes the number of connected components to increase).
35 Raises
36 ------
37 NodeNotFound
38 If `root` is not in the graph `G`.
40 NetworkXNotImplemented
41 If `G` is a directed graph.
43 Examples
44 --------
45 The barbell graph with parameter zero has a single bridge:
47 >>> G = nx.barbell_graph(10, 0)
48 >>> list(nx.bridges(G))
49 [(9, 10)]
51 Notes
52 -----
53 This is an implementation of the algorithm described in [1]_. An edge is a
54 bridge if and only if it is not contained in any chain. Chains are found
55 using the :func:`networkx.chain_decomposition` function.
57 The algorithm described in [1]_ requires a simple graph. If the provided
58 graph is a multigraph, we convert it to a simple graph and verify that any
59 bridges discovered by the chain decomposition algorithm are not multi-edges.
61 Ignoring polylogarithmic factors, the worst-case time complexity is the
62 same as the :func:`networkx.chain_decomposition` function,
63 $O(m + n)$, where $n$ is the number of nodes in the graph and $m$ is
64 the number of edges.
66 References
67 ----------
68 .. [1] https://en.wikipedia.org/wiki/Bridge_%28graph_theory%29#Bridge-Finding_with_Chain_Decompositions
69 """
70 multigraph = G.is_multigraph()
71 H = nx.Graph(G) if multigraph else G
72 chains = nx.chain_decomposition(H, root=root)
73 chain_edges = set(chain.from_iterable(chains))
74 if root is not None:
75 H = H.subgraph(nx.node_connected_component(H, root)).copy()
76 for u, v in H.edges():
77 if (u, v) not in chain_edges and (v, u) not in chain_edges:
78 if multigraph and len(G[u][v]) > 1:
79 continue
80 yield u, v
83@not_implemented_for("directed")
84@nx._dispatchable
85def has_bridges(G, root=None):
86 """Decide whether a graph has any bridges.
88 A *bridge* in a graph is an edge whose removal causes the number of
89 connected components of the graph to increase.
91 Parameters
92 ----------
93 G : undirected graph
95 root : node (optional)
96 A node in the graph `G`. If specified, only the bridges in the
97 connected component containing this node will be considered.
99 Returns
100 -------
101 bool
102 Whether the graph (or the connected component containing `root`)
103 has any bridges.
105 Raises
106 ------
107 NodeNotFound
108 If `root` is not in the graph `G`.
110 NetworkXNotImplemented
111 If `G` is a directed graph.
113 Examples
114 --------
115 The barbell graph with parameter zero has a single bridge::
117 >>> G = nx.barbell_graph(10, 0)
118 >>> nx.has_bridges(G)
119 True
121 On the other hand, the cycle graph has no bridges::
123 >>> G = nx.cycle_graph(5)
124 >>> nx.has_bridges(G)
125 False
127 Notes
128 -----
129 This implementation uses the :func:`networkx.bridges` function, so
130 it shares its worst-case time complexity, $O(m + n)$, ignoring
131 polylogarithmic factors, where $n$ is the number of nodes in the
132 graph and $m$ is the number of edges.
134 """
135 try:
136 next(bridges(G, root=root))
137 except StopIteration:
138 return False
139 else:
140 return True
143@not_implemented_for("multigraph")
144@not_implemented_for("directed")
145@nx._dispatchable(edge_attrs="weight")
146def local_bridges(G, with_span=True, weight=None):
147 """Iterate over local bridges of `G` optionally computing the span
149 A *local bridge* is an edge whose endpoints have no common neighbors.
150 That is, the edge is not part of a triangle in the graph.
152 The *span* of a *local bridge* is the shortest path length between
153 the endpoints if the local bridge is removed.
155 Parameters
156 ----------
157 G : undirected graph
159 with_span : bool
160 If True, yield a 3-tuple `(u, v, span)`
162 weight : function, string or None (default: None)
163 If function, used to compute edge weights for the span.
164 If string, the edge data attribute used in calculating span.
165 If None, all edges have weight 1.
167 Yields
168 ------
169 e : edge
170 The local bridges as an edge 2-tuple of nodes `(u, v)` or
171 as a 3-tuple `(u, v, span)` when `with_span is True`.
173 Raises
174 ------
175 NetworkXNotImplemented
176 If `G` is a directed graph or multigraph.
178 Examples
179 --------
180 A cycle graph has every edge a local bridge with span N-1.
182 >>> G = nx.cycle_graph(9)
183 >>> (0, 8, 8) in set(nx.local_bridges(G))
184 True
185 """
186 if with_span is not True:
187 for u, v in G.edges:
188 if not (set(G[u]) & set(G[v])):
189 yield u, v
190 else:
191 wt = nx.weighted._weight_function(G, weight)
192 for u, v in G.edges:
193 if not (set(G[u]) & set(G[v])):
194 enodes = {u, v}
196 def hide_edge(n, nbr, d):
197 if n not in enodes or nbr not in enodes:
198 return wt(n, nbr, d)
199 return None
201 try:
202 span = nx.shortest_path_length(G, u, v, weight=hide_edge)
203 yield u, v, span
204 except nx.NetworkXNoPath:
205 yield u, v, float("inf")