Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/classes/graphviews.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
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 ( | |
27 UnionAdjacency, | |
28 UnionMultiAdjacency, | |
29 FilterAtlas, | |
30 FilterAdjacency, | |
31 FilterMultiAdjacency, | |
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 | |
60 newG._adj = G._succ | |
61 else: | |
62 newG._succ = G._adj | |
63 newG._pred = G._adj | |
64 newG._adj = G._adj | |
65 elif G.is_directed(): | |
66 if G.is_multigraph(): | |
67 newG._adj = UnionMultiAdjacency(G._succ, G._pred) | |
68 else: | |
69 newG._adj = UnionAdjacency(G._succ, G._pred) | |
70 else: | |
71 newG._adj = G._adj | |
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(): | |
154 Adj = FilterMultiAdjacency | |
155 | |
156 def reverse_edge(u, v, k): | |
157 return filter_edge(v, u, k) | |
158 | |
159 else: | |
160 Adj = FilterAdjacency | |
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) | |
168 newG._adj = newG._succ | |
169 else: | |
170 newG._adj = Adj(G._adj, filter_node, filter_edge) | |
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() | |
194 >>> G.add_edge(1, 2) | |
195 >>> G.add_edge(2, 3) | |
196 >>> G.edges() | |
197 OutEdgeView([(1, 2), (2, 3)]) | |
198 | |
199 >>> view = nx.reverse_view(G) | |
200 >>> view.edges() | |
201 OutEdgeView([(2, 1), (3, 2)]) | |
202 """ | |
203 newG = generic_graph_view(G) | |
204 newG._succ, newG._pred = G._pred, G._succ | |
205 newG._adj = newG._succ | |
206 return newG |