Mercurial > repos > shellac > guppy_basecaller

comparison env/lib/python3.7/site-packages/networkx/classes/graphviews.py @ 0:26e78fe6e8c4 draft

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