### comparison env/lib/python3.9/site-packages/networkx/classes/graphviews.py @ 0:4f3585e2f14bdraftdefaulttip

author shellac Mon, 22 Mar 2021 18:12:50 +0000
comparison
equal inserted replaced
-1:000000000000 0:4f3585e2f14b
1 """View of Graphs as SubGraph, Reverse, Directed, Undirected.
2
3 In some algorithms it is convenient to temporarily morph
4 a graph to exclude some nodes or edges. It should be better
5 to do that via a view than to remove and then re-add.
6 In other algorithms it is convenient to temporarily morph
7 a graph to reverse directed edges, or treat a directed graph
8 as undirected, etc. This module provides those graph views.
9
10 The resulting views are essentially read-only graphs that
11 report data from the orignal graph object. We provide an
12 attribute G._graph which points to the underlying graph object.
13
14 Note: Since graphviews look like graphs, one can end up with
15 view-of-view-of-view chains. Be careful with chains because
16 they become very slow with about 15 nested views.
17 For the common simple case of node induced subgraphs created
18 from the graph class, we short-cut the chain by returning a
19 subgraph of the original graph directly rather than a subgraph
20 of a subgraph. We are careful not to disrupt any edge filter in
21 the middle subgraph. In general, determining how to short-cut
22 the chain is tricky and much harder with restricted_views than
23 with induced subgraphs.
24 Often it is easiest to use .copy() to avoid chains.
25 """
26 from networkx.classes.coreviews import (
29 FilterAtlas,
32 )
33 from networkx.classes.filters import no_filter
34 from networkx.exception import NetworkXError
35 from networkx.utils import not_implemented_for
36
37 import networkx as nx
38
39 __all__ = ["generic_graph_view", "subgraph_view", "reverse_view"]
40
41
42 def generic_graph_view(G, create_using=None):
43 if create_using is None:
44 newG = G.__class__()
45 else:
46 newG = nx.empty_graph(0, create_using)
47 if G.is_multigraph() != newG.is_multigraph():
48 raise NetworkXError("Multigraph for G must agree with create_using")
49 newG = nx.freeze(newG)
50
51 # create view by assigning attributes from G
52 newG._graph = G
53 newG.graph = G.graph
54
55 newG._node = G._node
56 if newG.is_directed():
57 if G.is_directed():
58 newG._succ = G._succ
59 newG._pred = G._pred
61 else:
65 elif G.is_directed():
66 if G.is_multigraph():
68 else:
70 else:
72 return newG
73
74
75 def subgraph_view(G, filter_node=no_filter, filter_edge=no_filter):
76 """ View of `G` applying a filter on nodes and edges.
77
78 `subgraph_view` provides a read-only view of the input graph that excludes
79 nodes and edges based on the outcome of two filter functions `filter_node`
80 and `filter_edge`.
81
82 The `filter_node` function takes one argument --- the node --- and returns
83 `True` if the node should be included in the subgraph, and `False` if it
84 should not be included.
85
86 The `filter_edge` function takes two (or three arguments if `G` is a
87 multi-graph) --- the nodes describing an edge, plus the edge-key if
88 parallel edges are possible --- and returns `True` if the edge should be
89 included in the subgraph, and `False` if it should not be included.
90
91 Both node and edge filter functions are called on graph elements as they
92 are queried, meaning there is no up-front cost to creating the view.
93
94 Parameters
95 ----------
96 G : networkx.Graph
97 A directed/undirected graph/multigraph
98
99 filter_node : callable, optional
100 A function taking a node as input, which returns `True` if the node
101 should appear in the view.
102
103 filter_edge : callable, optional
104 A function taking as input the two nodes describing an edge (plus the
105 edge-key if `G` is a multi-graph), which returns `True` if the edge
106 should appear in the view.
107
108 Returns
109 -------
110 graph : networkx.Graph
111 A read-only graph view of the input graph.
112
113 Examples
114 --------
115 >>> G = nx.path_graph(6)
116
117 Filter functions operate on the node, and return `True` if the node should
118 appear in the view:
119
120 >>> def filter_node(n1):
121 ... return n1 != 5
122 ...
123 >>> view = nx.subgraph_view(G, filter_node=filter_node)
124 >>> view.nodes()
125 NodeView((0, 1, 2, 3, 4))
126
127 We can use a closure pattern to filter graph elements based on additional
128 data --- for example, filtering on edge data attached to the graph:
129
130 >>> G[3][4]["cross_me"] = False
131 >>> def filter_edge(n1, n2):
132 ... return G[n1][n2].get("cross_me", True)
133 ...
134 >>> view = nx.subgraph_view(G, filter_edge=filter_edge)
135 >>> view.edges()
136 EdgeView([(0, 1), (1, 2), (2, 3), (4, 5)])
137
138 >>> view = nx.subgraph_view(G, filter_node=filter_node, filter_edge=filter_edge,)
139 >>> view.nodes()
140 NodeView((0, 1, 2, 3, 4))
141 >>> view.edges()
142 EdgeView([(0, 1), (1, 2), (2, 3)])
143 """
144 newG = nx.freeze(G.__class__())
145 newG._NODE_OK = filter_node
146 newG._EDGE_OK = filter_edge
147
148 # create view by assigning attributes from G
149 newG._graph = G
150 newG.graph = G.graph
151
152 newG._node = FilterAtlas(G._node, filter_node)
153 if G.is_multigraph():
155
156 def reverse_edge(u, v, k):
157 return filter_edge(v, u, k)
158
159 else:
161
162 def reverse_edge(u, v):
163 return filter_edge(v, u)
164
165 if G.is_directed():
166 newG._succ = Adj(G._succ, filter_node, filter_edge)
167 newG._pred = Adj(G._pred, filter_node, reverse_edge)
169 else:
171 return newG
172
173
174 @not_implemented_for("undirected")
175 def reverse_view(G):
176 """ View of `G` with edge directions reversed
177
178 `reverse_view` returns a read-only view of the input graph where
179 edge directions are reversed.
180
181 Identical to digraph.reverse(copy=False)
182
183 Parameters
184 ----------
185 G : networkx.DiGraph
186
187 Returns
188 -------
189 graph : networkx.DiGraph
190
191 Examples
192 --------
193 >>> G = nx.DiGraph()