Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-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""" 

26import networkx as nx 

27from networkx.classes.coreviews import ( 

28 FilterAdjacency, 

29 FilterAtlas, 

30 FilterMultiAdjacency, 

31 UnionAdjacency, 

32 UnionMultiAdjacency, 

33) 

34from networkx.classes.filters import no_filter 

35from networkx.exception import NetworkXError 

36from networkx.utils import deprecate_positional_args, not_implemented_for 

37 

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

39 

40 

41def generic_graph_view(G, create_using=None): 

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

43 

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

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

46 

47 Parameters 

48 ---------- 

49 G : graph 

50 A directed/undirected graph/multigraph. 

51 

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

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

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

55 

56 Returns 

57 ------- 

58 newG : graph 

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

60 the `create_using` class. 

61 

62 Raises 

63 ------ 

64 NetworkXError 

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

66 

67 Notes 

68 ----- 

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

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

71 

72 Examples 

73 -------- 

74 >>> G = nx.Graph() 

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

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

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

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

79 

80 The view exposes the attributes from the original graph. 

81 

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

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

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

85 

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

87 

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

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

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

91 

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

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

94 

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

96 

97 >>> type(G) 

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

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

100 >>> type(viewDG) 

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

102 """ 

103 if create_using is None: 

104 newG = G.__class__() 

105 else: 

106 newG = nx.empty_graph(0, create_using) 

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

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

109 newG = nx.freeze(newG) 

110 

111 # create view by assigning attributes from G 

112 newG._graph = G 

113 newG.graph = G.graph 

114 

115 newG._node = G._node 

116 if newG.is_directed(): 

117 if G.is_directed(): 

118 newG._succ = G._succ 

119 newG._pred = G._pred 

120 # newG._adj is synced with _succ 

121 else: 

122 newG._succ = G._adj 

123 newG._pred = G._adj 

124 # newG._adj is synced with _succ 

125 elif G.is_directed(): 

126 if G.is_multigraph(): 

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

128 else: 

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

130 else: 

131 newG._adj = G._adj 

132 return newG 

133 

134 

135@deprecate_positional_args(version="3.4") 

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 ... 

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

185 >>> view.nodes() 

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

187 

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

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

190 

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

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

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

194 ... 

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

196 >>> view.edges() 

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

198 

199 >>> view = nx.subgraph_view(G, filter_node=filter_node, filter_edge=filter_edge,) 

200 >>> view.nodes() 

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

202 >>> view.edges() 

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

204 """ 

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

206 newG._NODE_OK = filter_node 

207 newG._EDGE_OK = filter_edge 

208 

209 # create view by assigning attributes from G 

210 newG._graph = G 

211 newG.graph = G.graph 

212 

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

214 if G.is_multigraph(): 

215 Adj = FilterMultiAdjacency 

216 

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

218 return filter_edge(v, u, k) 

219 

220 else: 

221 Adj = FilterAdjacency 

222 

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

224 return filter_edge(v, u) 

225 

226 if G.is_directed(): 

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

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

229 # newG._adj is synced with _succ 

230 else: 

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

232 return newG 

233 

234 

235@not_implemented_for("undirected") 

236def reverse_view(G): 

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

238 

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

240 edge directions are reversed. 

241 

242 Identical to digraph.reverse(copy=False) 

243 

244 Parameters 

245 ---------- 

246 G : networkx.DiGraph 

247 

248 Returns 

249 ------- 

250 graph : networkx.DiGraph 

251 

252 Examples 

253 -------- 

254 >>> G = nx.DiGraph() 

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

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

257 >>> G.edges() 

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

259 

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

261 >>> view.edges() 

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

263 """ 

264 newG = generic_graph_view(G) 

265 newG._succ, newG._pred = G._pred, G._succ 

266 # newG._adj is synced with _succ 

267 return newG