Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/components/weakly_connected.py: 29%

1"""Weakly connected components.""" 

2import networkx as nx 

3from networkx.utils.decorators import not_implemented_for 

4 

5__all__ = [ 

6 "number_weakly_connected_components", 

7 "weakly_connected_components", 

8 "is_weakly_connected", 

9] 

10 

11 

12@not_implemented_for("undirected") 

13@nx._dispatch 

14def weakly_connected_components(G): 

15 """Generate weakly connected components of G. 

16 

17 Parameters 

18 ---------- 

19 G : NetworkX graph 

20 A directed graph 

21 

22 Returns 

23 ------- 

24 comp : generator of sets 

25 A generator of sets of nodes, one for each weakly connected 

26 component of G. 

27 

28 Raises 

29 ------ 

30 NetworkXNotImplemented 

31 If G is undirected. 

32 

33 Examples 

34 -------- 

35 Generate a sorted list of weakly connected components, largest first. 

36 

37 >>> G = nx.path_graph(4, create_using=nx.DiGraph()) 

38 >>> nx.add_path(G, [10, 11, 12]) 

39 >>> [ 

40 ... len(c) 

41 ... for c in sorted(nx.weakly_connected_components(G), key=len, reverse=True) 

42 ... ] 

43 [4, 3] 

44 

45 If you only want the largest component, it's more efficient to 

46 use max instead of sort: 

47 

48 >>> largest_cc = max(nx.weakly_connected_components(G), key=len) 

49 

50 See Also 

51 -------- 

52 connected_components 

53 strongly_connected_components 

54 

55 Notes 

56 ----- 

57 For directed graphs only. 

58 

59 """ 

60 seen = set() 

61 for v in G: 

62 if v not in seen: 

63 c = set(_plain_bfs(G, v)) 

64 seen.update(c) 

65 yield c 

66 

67 

68@not_implemented_for("undirected") 

69@nx._dispatch 

70def number_weakly_connected_components(G): 

71 """Returns the number of weakly connected components in G. 

72 

73 Parameters 

74 ---------- 

75 G : NetworkX graph 

76 A directed graph. 

77 

78 Returns 

79 ------- 

80 n : integer 

81 Number of weakly connected components 

82 

83 Raises 

84 ------ 

85 NetworkXNotImplemented 

86 If G is undirected. 

87 

88 Examples 

89 -------- 

90 >>> G = nx.DiGraph([(0, 1), (2, 1), (3, 4)]) 

91 >>> nx.number_weakly_connected_components(G) 

92 2 

93 

94 See Also 

95 -------- 

96 weakly_connected_components 

97 number_connected_components 

98 number_strongly_connected_components 

99 

100 Notes 

101 ----- 

102 For directed graphs only. 

103 

104 """ 

105 return sum(1 for wcc in weakly_connected_components(G)) 

106 

107 

108@not_implemented_for("undirected") 

109@nx._dispatch 

110def is_weakly_connected(G): 

111 """Test directed graph for weak connectivity. 

112 

113 A directed graph is weakly connected if and only if the graph 

114 is connected when the direction of the edge between nodes is ignored. 

115 

116 Note that if a graph is strongly connected (i.e. the graph is connected 

117 even when we account for directionality), it is by definition weakly 

118 connected as well. 

119 

120 Parameters 

121 ---------- 

122 G : NetworkX Graph 

123 A directed graph. 

124 

125 Returns 

126 ------- 

127 connected : bool 

128 True if the graph is weakly connected, False otherwise. 

129 

130 Raises 

131 ------ 

132 NetworkXNotImplemented 

133 If G is undirected. 

134 

135 Examples 

136 -------- 

137 >>> G = nx.DiGraph([(0, 1), (2, 1)]) 

138 >>> G.add_node(3) 

139 >>> nx.is_weakly_connected(G) # node 3 is not connected to the graph 

140 False 

141 >>> G.add_edge(2, 3) 

142 >>> nx.is_weakly_connected(G) 

143 True 

144 

145 See Also 

146 -------- 

147 is_strongly_connected 

148 is_semiconnected 

149 is_connected 

150 is_biconnected 

151 weakly_connected_components 

152 

153 Notes 

154 ----- 

155 For directed graphs only. 

156 

157 """ 

158 if len(G) == 0: 

159 raise nx.NetworkXPointlessConcept( 

160 """Connectivity is undefined for the null graph.""" 

161 ) 

162 

163 return len(next(weakly_connected_components(G))) == len(G) 

164 

165 

166def _plain_bfs(G, source): 

167 """A fast BFS node generator 

168 

169 The direction of the edge between nodes is ignored. 

170 

171 For directed graphs only. 

172 

173 """ 

174 n = len(G) 

175 Gsucc = G._succ 

176 Gpred = G._pred 

177 seen = {source} 

178 nextlevel = [source] 

179 

180 yield source 

181 while nextlevel: 

182 thislevel = nextlevel 

183 nextlevel = [] 

184 for v in thislevel: 

185 for w in Gsucc[v]: 

186 if w not in seen: 

187 seen.add(w) 

188 nextlevel.append(w) 

189 yield w 

190 for w in Gpred[v]: 

191 if w not in seen: 

192 seen.add(w) 

193 nextlevel.append(w) 

194 yield w 

195 if len(seen) == n: 

196 return