ioftools / networkxMiCe / networkxmaster / networkx / algorithms / bridges.py @ 5cef0f13
History  View  Annotate  Download (5.38 KB)
1 
# * coding: utf8 *


2 
# bridges.py  bridgefinding algorithms

3 
#

4 
# Copyright 20042019 NetworkX developers.

5 
#

6 
# This file is part of NetworkX.

7 
#

8 
# NetworkX is distributed under a BSD license; see LICENSE.txt for more

9 
# information.

10 
"""Bridgefinding algorithms."""

11 
from itertools import chain 
12  
13 
import networkx as nx 
14 
from networkx.utils import not_implemented_for 
15  
16 
__all__ = ['bridges', 'has_bridges', 'local_bridges'] 
17  
18  
19 
@not_implemented_for('multigraph') 
20 
@not_implemented_for('directed') 
21 
def bridges(G, root=None): 
22 
"""Generate all bridges in a graph.

23 

24 
A *bridge* in a graph is an edge whose removal causes the number of

25 
connected components of the graph to increase. Equivalently, a bridge is an

26 
edge that does not belong to any cycle.

27 

28 
Parameters

29 


30 
G : undirected graph

31 

32 
root : node (optional)

33 
A node in the graph `G`. If specified, only the bridges in the

34 
connected component containing this node will be returned.

35 

36 
Yields

37 


38 
e : edge

39 
An edge in the graph whose removal disconnects the graph (or

40 
causes the number of connected components to increase).

41 

42 
Raises

43 


44 
NodeNotFound

45 
If `root` is not in the graph `G`.

46 

47 
Examples

48 


49 
The barbell graph with parameter zero has a single bridge:

50 

51 
>>> G = nx.barbell_graph(10, 0)

52 
>>> list(nx.bridges(G))

53 
[(9, 10)]

54 

55 
Notes

56 


57 
This is an implementation of the algorithm described in _[1]. An edge is a

58 
bridge if and only if it is not contained in any chain. Chains are found

59 
using the :func:`networkx.chain_decomposition` function.

60 

61 
Ignoring polylogarithmic factors, the worstcase 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.

65 

66 
References

67 


68 
.. [1] https://en.wikipedia.org/wiki/Bridge_%28graph_theory%29#BridgeFinding_with_Chain_Decompositions

69 
"""

70 
chains = nx.chain_decomposition(G, root=root) 
71 
chain_edges = set(chain.from_iterable(chains))

72 
for u, v in G.edges(): 
73 
if (u, v) not in chain_edges and (v, u) not in chain_edges: 
74 
yield u, v

75  
76  
77 
@not_implemented_for('multigraph') 
78 
@not_implemented_for('directed') 
79 
def has_bridges(G, root=None): 
80 
"""Decide whether a graph has any bridges.

81 

82 
A *bridge* in a graph is an edge whose removal causes the number of

83 
connected components of the graph to increase.

84 

85 
Parameters

86 


87 
G : undirected graph

88 

89 
root : node (optional)

90 
A node in the graph `G`. If specified, only the bridges in the

91 
connected component containing this node will be considered.

92 

93 
Returns

94 


95 
bool

96 
Whether the graph (or the connected component containing `root`)

97 
has any bridges.

98 

99 
Raises

100 


101 
NodeNotFound

102 
If `root` is not in the graph `G`.

103 

104 
Examples

105 


106 
The barbell graph with parameter zero has a single bridge::

107 

108 
>>> G = nx.barbell_graph(10, 0)

109 
>>> nx.has_bridges(G)

110 
True

111 

112 
On the other hand, the cycle graph has no bridges::

113 

114 
>>> G = nx.cycle_graph(5)

115 
>>> nx.has_bridges(G)

116 
False

117 

118 
Notes

119 


120 
This implementation uses the :func:`networkx.bridges` function, so

121 
it shares its worstcase time complexity, $O(m + n)$, ignoring

122 
polylogarithmic factors, where $n$ is the number of nodes in the

123 
graph and $m$ is the number of edges.

124 

125 
"""

126 
try:

127 
next(bridges(G))

128 
except StopIteration: 
129 
return False 
130 
else:

131 
return True 
132  
133  
134 
@not_implemented_for('multigraph') 
135 
@not_implemented_for('directed') 
136 
def local_bridges(G, with_span=True, weight=None): 
137 
"""Iterate over local bridges of `G` optionally computing the span

138 

139 
A *local bridge* is an edge whose endpoints have no common neighbors.

140 
That is, the edge is not part of a triangle in the graph.

141 

142 
The *span* of a *local bridge* is the shortest path length between

143 
the endpoints if the local bridge is removed.

144 

145 
Parameters

146 


147 
G : undirected graph

148 

149 
with_span : bool

150 
If True, yield a 3tuple `(u, v, span)`

151 

152 
weight : function, string or None (default: None)

153 
If function, used to compute edge weights for the span.

154 
If string, the edge data attribute used in calculating span.

155 
If None, all edges have weight 1.

156 

157 
Yields

158 


159 
e : edge

160 
The local bridges as an edge 2tuple of nodes `(u, v)` or

161 
as a 3tuple `(u, v, span)` when `with_span is True`.

162 

163 
Examples

164 


165 
A cycle graph has every edge a local bridge with span N1.

166 

167 
>>> G = nx.cycle_graph(9)

168 
>>> (0, 8, 8) in set(nx.local_bridges(G))

169 
True

170 
"""

171 
if with_span is not True: 
172 
for u, v in G.edges: 
173 
if not (set(G[u]) & set(G[v])): 
174 
yield u, v

175 
else:

176 
wt = nx.weighted._weight_function(G, weight) 
177 
for u, v in G.edges: 
178 
if not (set(G[u]) & set(G[v])): 
179 
enodes = {u, v} 
180  
181 
def hide_edge(n, nbr, d): 
182 
if n not in enodes or nbr not in enodes: 
183 
return wt(n, nbr, d)

184 
return None 
185  
186 
try:

187 
span = nx.shortest_path_length(G, u, v, weight=hide_edge) 
188 
yield u, v, span

189 
except nx.NetworkXNoPath:

190 
yield u, v, float('inf') 