Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.11/site-packages/networkx/classes/graphviews.py: 21%

1"""View of Graphs as SubGraph, Reverse, Directed, Undirected. 

2 

3In some algorithms it is convenient to temporarily morph 

4a graph to exclude some nodes or edges. It should be better 

5to do that via a view than to remove and then re-add. 

6In other algorithms it is convenient to temporarily morph 

7a graph to reverse directed edges, or treat a directed graph 

8as undirected, etc. This module provides those graph views. 

9 

10The resulting views are essentially read-only graphs that 

11report data from the original graph object. We provide an 

12attribute G._graph which points to the underlying graph object. 

13 

14Note: Since graphviews look like graphs, one can end up with 

15view-of-view-of-view chains. Be careful with chains because 

16they become very slow with about 15 nested views. 

17For the common simple case of node induced subgraphs created 

18from the graph class, we short-cut the chain by returning a 

19subgraph of the original graph directly rather than a subgraph 

20of a subgraph. We are careful not to disrupt any edge filter in 

21the middle subgraph. In general, determining how to short-cut 

22the chain is tricky and much harder with restricted_views than 

23with induced subgraphs. 

24Often it is easiest to use .copy() to avoid chains. 

25""" 

26 

27import networkx as nx 

28from networkx.classes.coreviews import ( 

29 FilterAdjacency, 

30 FilterAtlas, 

31 FilterMultiAdjacency, 

32 UnionAdjacency, 

33 UnionMultiAdjacency, 

34) 

35from networkx.classes.filters import no_filter 

36from networkx.exception import NetworkXError 

37from networkx.utils import not_implemented_for 

38 

39__all__ = ["generic_graph_view", "subgraph_view", "reverse_view"] 

40 

41 

42def generic_graph_view(G, create_using=None): 

43 """Returns a read-only view of `G`. 

44 

45 The graph `G` and its attributes are not copied but viewed through the new graph object 

46 of the same class as `G` (or of the class specified in `create_using`). 

47 

48 Parameters 

49 ---------- 

50 G : graph 

51 A directed/undirected graph/multigraph. 

52 

53 create_using : NetworkX graph constructor, optional (default=None) 

54 Graph type to create. If graph instance, then cleared before populated. 

55 If `None`, then the appropriate Graph type is inferred from `G`. 

56 

57 Returns 

58 ------- 

59 newG : graph 

60 A view of the input graph `G` and its attributes as viewed through 

61 the `create_using` class. 

62 

63 Raises 

64 ------ 

65 NetworkXError 

66 If `G` is a multigraph (or multidigraph) but `create_using` is not, or vice versa. 

67 

68 Notes 

69 ----- 

70 The returned graph view is read-only (cannot modify the graph). 

71 Yet the view reflects any changes in `G`. The intent is to mimic dict views. 

72 

73 Examples 

74 -------- 

75 >>> G = nx.Graph() 

76 >>> G.add_edge(1, 2, weight=0.3) 

77 >>> G.add_edge(2, 3, weight=0.5) 

78 >>> G.edges(data=True) 

79 EdgeDataView([(1, 2, {'weight': 0.3}), (2, 3, {'weight': 0.5})]) 

80 

81 The view exposes the attributes from the original graph. 

82 

83 >>> viewG = nx.graphviews.generic_graph_view(G) 

84 >>> viewG.edges(data=True) 

85 EdgeDataView([(1, 2, {'weight': 0.3}), (2, 3, {'weight': 0.5})]) 

86 

87 Changes to `G` are reflected in `viewG`. 

88 

89 >>> G.remove_edge(2, 3) 

90 >>> G.edges(data=True) 

91 EdgeDataView([(1, 2, {'weight': 0.3})]) 

92 

93 >>> viewG.edges(data=True) 

94 EdgeDataView([(1, 2, {'weight': 0.3})]) 

95 

96 We can change the graph type with the `create_using` parameter. 

97 

98 >>> type(G) 

99 <class 'networkx.classes.graph.Graph'> 

100 >>> viewDG = nx.graphviews.generic_graph_view(G, create_using=nx.DiGraph) 

101 >>> type(viewDG) 

102 <class 'networkx.classes.digraph.DiGraph'> 

103 """ 

104 if create_using is None: 

105 newG = G.__class__() 

106 else: 

107 newG = nx.empty_graph(0, create_using) 

108 if G.is_multigraph() != newG.is_multigraph(): 

109 raise NetworkXError("Multigraph for G must agree with create_using") 

110 newG = nx.freeze(newG) 

111 

112 # create view by assigning attributes from G 

113 newG._graph = G 

114 newG.graph = G.graph 

115 

116 newG._node = G._node 

117 if newG.is_directed(): 

118 if G.is_directed(): 

119 newG._succ = G._succ 

120 newG._pred = G._pred 

121 # newG._adj is synced with _succ 

122 else: 

123 newG._succ = G._adj 

124 newG._pred = G._adj 

125 # newG._adj is synced with _succ 

126 elif G.is_directed(): 

127 if G.is_multigraph(): 

128 newG._adj = UnionMultiAdjacency(G._succ, G._pred) 

129 else: 

130 newG._adj = UnionAdjacency(G._succ, G._pred) 

131 else: 

132 newG._adj = G._adj 

133 return newG 

134 

135 

136def subgraph_view(G, *, filter_node=no_filter, filter_edge=no_filter): 

137 """View of `G` applying a filter on nodes and edges. 

138 

139 `subgraph_view` provides a read-only view of the input graph that excludes 

140 nodes and edges based on the outcome of two filter functions `filter_node` 

141 and `filter_edge`. 

142 

143 The `filter_node` function takes one argument --- the node --- and returns 

144 `True` if the node should be included in the subgraph, and `False` if it 

145 should not be included. 

146 

147 The `filter_edge` function takes two (or three arguments if `G` is a 

148 multi-graph) --- the nodes describing an edge, plus the edge-key if 

149 parallel edges are possible --- and returns `True` if the edge should be 

150 included in the subgraph, and `False` if it should not be included. 

151 

152 Both node and edge filter functions are called on graph elements as they 

153 are queried, meaning there is no up-front cost to creating the view. 

154 

155 Parameters 

156 ---------- 

157 G : networkx.Graph 

158 A directed/undirected graph/multigraph 

159 

160 filter_node : callable, optional 

161 A function taking a node as input, which returns `True` if the node 

162 should appear in the view. 

163 

164 filter_edge : callable, optional 

165 A function taking as input the two nodes describing an edge (plus the 

166 edge-key if `G` is a multi-graph), which returns `True` if the edge 

167 should appear in the view. 

168 

169 Returns 

170 ------- 

171 graph : networkx.Graph 

172 A read-only graph view of the input graph. 

173 

174 Examples 

175 -------- 

176 >>> G = nx.path_graph(6) 

177 

178 Filter functions operate on the node, and return `True` if the node should 

179 appear in the view: 

180 

181 >>> def filter_node(n1): 

182 ... return n1 != 5 

183 >>> view = nx.subgraph_view(G, filter_node=filter_node) 

184 >>> view.nodes() 

185 NodeView((0, 1, 2, 3, 4)) 

186 

187 We can use a closure pattern to filter graph elements based on additional 

188 data --- for example, filtering on edge data attached to the graph: 

189 

190 >>> G[3][4]["cross_me"] = False 

191 >>> def filter_edge(n1, n2): 

192 ... return G[n1][n2].get("cross_me", True) 

193 >>> view = nx.subgraph_view(G, filter_edge=filter_edge) 

194 >>> view.edges() 

195 EdgeView([(0, 1), (1, 2), (2, 3), (4, 5)]) 

196 

197 >>> view = nx.subgraph_view( 

198 ... G, 

199 ... filter_node=filter_node, 

200 ... filter_edge=filter_edge, 

201 ... ) 

202 >>> view.nodes() 

203 NodeView((0, 1, 2, 3, 4)) 

204 >>> view.edges() 

205 EdgeView([(0, 1), (1, 2), (2, 3)]) 

206 """ 

207 newG = nx.freeze(G.__class__()) 

208 newG._NODE_OK = filter_node 

209 newG._EDGE_OK = filter_edge 

210 

211 # create view by assigning attributes from G 

212 newG._graph = G 

213 newG.graph = G.graph 

214 

215 newG._node = FilterAtlas(G._node, filter_node) 

216 if G.is_multigraph(): 

217 Adj = FilterMultiAdjacency 

218 

219 def reverse_edge(u, v, k=None): 

220 return filter_edge(v, u, k) 

221 

222 else: 

223 Adj = FilterAdjacency 

224 

225 def reverse_edge(u, v, k=None): 

226 return filter_edge(v, u) 

227 

228 if G.is_directed(): 

229 newG._succ = Adj(G._succ, filter_node, filter_edge) 

230 newG._pred = Adj(G._pred, filter_node, reverse_edge) 

231 # newG._adj is synced with _succ 

232 else: 

233 newG._adj = Adj(G._adj, filter_node, filter_edge) 

234 return newG 

235 

236 

237@not_implemented_for("undirected") 

238def reverse_view(G): 

239 """View of `G` with edge directions reversed 

240 

241 `reverse_view` returns a read-only view of the input graph where 

242 edge directions are reversed. 

243 

244 Identical to digraph.reverse(copy=False) 

245 

246 Parameters 

247 ---------- 

248 G : networkx.DiGraph 

249 

250 Returns 

251 ------- 

252 graph : networkx.DiGraph 

253 

254 Examples 

255 -------- 

256 >>> G = nx.DiGraph() 

257 >>> G.add_edge(1, 2) 

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

259 >>> G.edges() 

260 OutEdgeView([(1, 2), (2, 3)]) 

261 

262 >>> view = nx.reverse_view(G) 

263 >>> view.edges() 

264 OutEdgeView([(2, 1), (3, 2)]) 

265 """ 

266 newG = generic_graph_view(G) 

267 newG._succ, newG._pred = G._pred, G._succ 

268 # newG._adj is synced with _succ 

269 return newG