Mercurial > repos > shellac > sam_consensus_v3
comparison env/share/doc/networkx-2.5/examples/subclass/plot_antigraph.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 """ | |
2 ========= | |
3 Antigraph | |
4 ========= | |
5 | |
6 Complement graph class for small footprint when working on dense graphs. | |
7 | |
8 This class allows you to add the edges that *do not exist* in the dense | |
9 graph. However, when applying algorithms to this complement graph data | |
10 structure, it behaves as if it were the dense version. So it can be used | |
11 directly in several NetworkX algorithms. | |
12 | |
13 This subclass has only been tested for k-core, connected_components, | |
14 and biconnected_components algorithms but might also work for other | |
15 algorithms. | |
16 | |
17 """ | |
18 import networkx as nx | |
19 from networkx.exception import NetworkXError | |
20 import matplotlib.pyplot as plt | |
21 | |
22 | |
23 class AntiGraph(nx.Graph): | |
24 """ | |
25 Class for complement graphs. | |
26 | |
27 The main goal is to be able to work with big and dense graphs with | |
28 a low memory footprint. | |
29 | |
30 In this class you add the edges that *do not exist* in the dense graph, | |
31 the report methods of the class return the neighbors, the edges and | |
32 the degree as if it was the dense graph. Thus it's possible to use | |
33 an instance of this class with some of NetworkX functions. | |
34 """ | |
35 | |
36 all_edge_dict = {"weight": 1} | |
37 | |
38 def single_edge_dict(self): | |
39 return self.all_edge_dict | |
40 | |
41 edge_attr_dict_factory = single_edge_dict | |
42 | |
43 def __getitem__(self, n): | |
44 """Return a dict of neighbors of node n in the dense graph. | |
45 | |
46 Parameters | |
47 ---------- | |
48 n : node | |
49 A node in the graph. | |
50 | |
51 Returns | |
52 ------- | |
53 adj_dict : dictionary | |
54 The adjacency dictionary for nodes connected to n. | |
55 | |
56 """ | |
57 return { | |
58 node: self.all_edge_dict for node in set(self.adj) - set(self.adj[n]) - {n} | |
59 } | |
60 | |
61 def neighbors(self, n): | |
62 """Return an iterator over all neighbors of node n in the | |
63 dense graph. | |
64 | |
65 """ | |
66 try: | |
67 return iter(set(self.adj) - set(self.adj[n]) - {n}) | |
68 except KeyError as e: | |
69 raise NetworkXError(f"The node {n} is not in the graph.") from e | |
70 | |
71 def degree(self, nbunch=None, weight=None): | |
72 """Return an iterator for (node, degree) in the dense graph. | |
73 | |
74 The node degree is the number of edges adjacent to the node. | |
75 | |
76 Parameters | |
77 ---------- | |
78 nbunch : iterable container, optional (default=all nodes) | |
79 A container of nodes. The container will be iterated | |
80 through once. | |
81 | |
82 weight : string or None, optional (default=None) | |
83 The edge attribute that holds the numerical value used | |
84 as a weight. If None, then each edge has weight 1. | |
85 The degree is the sum of the edge weights adjacent to the node. | |
86 | |
87 Returns | |
88 ------- | |
89 nd_iter : iterator | |
90 The iterator returns two-tuples of (node, degree). | |
91 | |
92 See Also | |
93 -------- | |
94 degree | |
95 | |
96 Examples | |
97 -------- | |
98 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc | |
99 >>> list(G.degree(0)) # node 0 with degree 1 | |
100 [(0, 1)] | |
101 >>> list(G.degree([0, 1])) | |
102 [(0, 1), (1, 2)] | |
103 | |
104 """ | |
105 if nbunch is None: | |
106 nodes_nbrs = ( | |
107 ( | |
108 n, | |
109 { | |
110 v: self.all_edge_dict | |
111 for v in set(self.adj) - set(self.adj[n]) - {n} | |
112 }, | |
113 ) | |
114 for n in self.nodes() | |
115 ) | |
116 elif nbunch in self: | |
117 nbrs = set(self.nodes()) - set(self.adj[nbunch]) - {nbunch} | |
118 return len(nbrs) | |
119 else: | |
120 nodes_nbrs = ( | |
121 ( | |
122 n, | |
123 { | |
124 v: self.all_edge_dict | |
125 for v in set(self.nodes()) - set(self.adj[n]) - {n} | |
126 }, | |
127 ) | |
128 for n in self.nbunch_iter(nbunch) | |
129 ) | |
130 | |
131 if weight is None: | |
132 return ((n, len(nbrs)) for n, nbrs in nodes_nbrs) | |
133 else: | |
134 # AntiGraph is a ThinGraph so all edges have weight 1 | |
135 return ( | |
136 (n, sum((nbrs[nbr].get(weight, 1)) for nbr in nbrs)) | |
137 for n, nbrs in nodes_nbrs | |
138 ) | |
139 | |
140 def adjacency_iter(self): | |
141 """Return an iterator of (node, adjacency set) tuples for all nodes | |
142 in the dense graph. | |
143 | |
144 This is the fastest way to look at every edge. | |
145 For directed graphs, only outgoing adjacencies are included. | |
146 | |
147 Returns | |
148 ------- | |
149 adj_iter : iterator | |
150 An iterator of (node, adjacency set) for all nodes in | |
151 the graph. | |
152 | |
153 """ | |
154 for n in self.adj: | |
155 yield (n, set(self.adj) - set(self.adj[n]) - {n}) | |
156 | |
157 | |
158 # Build several pairs of graphs, a regular graph | |
159 # and the AntiGraph of it's complement, which behaves | |
160 # as if it were the original graph. | |
161 Gnp = nx.gnp_random_graph(20, 0.8, seed=42) | |
162 Anp = AntiGraph(nx.complement(Gnp)) | |
163 Gd = nx.davis_southern_women_graph() | |
164 Ad = AntiGraph(nx.complement(Gd)) | |
165 Gk = nx.karate_club_graph() | |
166 Ak = AntiGraph(nx.complement(Gk)) | |
167 pairs = [(Gnp, Anp), (Gd, Ad), (Gk, Ak)] | |
168 # test connected components | |
169 for G, A in pairs: | |
170 gc = [set(c) for c in nx.connected_components(G)] | |
171 ac = [set(c) for c in nx.connected_components(A)] | |
172 for comp in ac: | |
173 assert comp in gc | |
174 # test biconnected components | |
175 for G, A in pairs: | |
176 gc = [set(c) for c in nx.biconnected_components(G)] | |
177 ac = [set(c) for c in nx.biconnected_components(A)] | |
178 for comp in ac: | |
179 assert comp in gc | |
180 # test degree | |
181 for G, A in pairs: | |
182 node = list(G.nodes())[0] | |
183 nodes = list(G.nodes())[1:4] | |
184 assert G.degree(node) == A.degree(node) | |
185 assert sum(d for n, d in G.degree()) == sum(d for n, d in A.degree()) | |
186 # AntiGraph is a ThinGraph, so all the weights are 1 | |
187 assert sum(d for n, d in A.degree()) == sum(d for n, d in A.degree(weight="weight")) | |
188 assert sum(d for n, d in G.degree(nodes)) == sum(d for n, d in A.degree(nodes)) | |
189 | |
190 nx.draw(Gnp) | |
191 plt.show() |