Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/generators/line.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 """Functions for generating line graphs.""" | |
2 from itertools import combinations | |
3 from collections import defaultdict | |
4 | |
5 import networkx as nx | |
6 from networkx.utils import arbitrary_element, generate_unique_node | |
7 from networkx.utils.decorators import not_implemented_for | |
8 | |
9 __all__ = ["line_graph", "inverse_line_graph"] | |
10 | |
11 | |
12 def line_graph(G, create_using=None): | |
13 r"""Returns the line graph of the graph or digraph `G`. | |
14 | |
15 The line graph of a graph `G` has a node for each edge in `G` and an | |
16 edge joining those nodes if the two edges in `G` share a common node. For | |
17 directed graphs, nodes are adjacent exactly when the edges they represent | |
18 form a directed path of length two. | |
19 | |
20 The nodes of the line graph are 2-tuples of nodes in the original graph (or | |
21 3-tuples for multigraphs, with the key of the edge as the third element). | |
22 | |
23 For information about self-loops and more discussion, see the **Notes** | |
24 section below. | |
25 | |
26 Parameters | |
27 ---------- | |
28 G : graph | |
29 A NetworkX Graph, DiGraph, MultiGraph, or MultiDigraph. | |
30 create_using : NetworkX graph constructor, optional (default=nx.Graph) | |
31 Graph type to create. If graph instance, then cleared before populated. | |
32 | |
33 Returns | |
34 ------- | |
35 L : graph | |
36 The line graph of G. | |
37 | |
38 Examples | |
39 -------- | |
40 >>> G = nx.star_graph(3) | |
41 >>> L = nx.line_graph(G) | |
42 >>> print(sorted(map(sorted, L.edges()))) # makes a 3-clique, K3 | |
43 [[(0, 1), (0, 2)], [(0, 1), (0, 3)], [(0, 2), (0, 3)]] | |
44 | |
45 Notes | |
46 ----- | |
47 Graph, node, and edge data are not propagated to the new graph. For | |
48 undirected graphs, the nodes in G must be sortable, otherwise the | |
49 constructed line graph may not be correct. | |
50 | |
51 *Self-loops in undirected graphs* | |
52 | |
53 For an undirected graph `G` without multiple edges, each edge can be | |
54 written as a set `\{u, v\}`. Its line graph `L` has the edges of `G` as | |
55 its nodes. If `x` and `y` are two nodes in `L`, then `\{x, y\}` is an edge | |
56 in `L` if and only if the intersection of `x` and `y` is nonempty. Thus, | |
57 the set of all edges is determined by the set of all pairwise intersections | |
58 of edges in `G`. | |
59 | |
60 Trivially, every edge in G would have a nonzero intersection with itself, | |
61 and so every node in `L` should have a self-loop. This is not so | |
62 interesting, and the original context of line graphs was with simple | |
63 graphs, which had no self-loops or multiple edges. The line graph was also | |
64 meant to be a simple graph and thus, self-loops in `L` are not part of the | |
65 standard definition of a line graph. In a pairwise intersection matrix, | |
66 this is analogous to excluding the diagonal entries from the line graph | |
67 definition. | |
68 | |
69 Self-loops and multiple edges in `G` add nodes to `L` in a natural way, and | |
70 do not require any fundamental changes to the definition. It might be | |
71 argued that the self-loops we excluded before should now be included. | |
72 However, the self-loops are still "trivial" in some sense and thus, are | |
73 usually excluded. | |
74 | |
75 *Self-loops in directed graphs* | |
76 | |
77 For a directed graph `G` without multiple edges, each edge can be written | |
78 as a tuple `(u, v)`. Its line graph `L` has the edges of `G` as its | |
79 nodes. If `x` and `y` are two nodes in `L`, then `(x, y)` is an edge in `L` | |
80 if and only if the tail of `x` matches the head of `y`, for example, if `x | |
81 = (a, b)` and `y = (b, c)` for some vertices `a`, `b`, and `c` in `G`. | |
82 | |
83 Due to the directed nature of the edges, it is no longer the case that | |
84 every edge in `G` should have a self-loop in `L`. Now, the only time | |
85 self-loops arise is if a node in `G` itself has a self-loop. So such | |
86 self-loops are no longer "trivial" but instead, represent essential | |
87 features of the topology of `G`. For this reason, the historical | |
88 development of line digraphs is such that self-loops are included. When the | |
89 graph `G` has multiple edges, once again only superficial changes are | |
90 required to the definition. | |
91 | |
92 References | |
93 ---------- | |
94 * Harary, Frank, and Norman, Robert Z., "Some properties of line digraphs", | |
95 Rend. Circ. Mat. Palermo, II. Ser. 9 (1960), 161--168. | |
96 * Hemminger, R. L.; Beineke, L. W. (1978), "Line graphs and line digraphs", | |
97 in Beineke, L. W.; Wilson, R. J., Selected Topics in Graph Theory, | |
98 Academic Press Inc., pp. 271--305. | |
99 | |
100 """ | |
101 if G.is_directed(): | |
102 L = _lg_directed(G, create_using=create_using) | |
103 else: | |
104 L = _lg_undirected(G, selfloops=False, create_using=create_using) | |
105 return L | |
106 | |
107 | |
108 def _node_func(G): | |
109 """Returns a function which returns a sorted node for line graphs. | |
110 | |
111 When constructing a line graph for undirected graphs, we must normalize | |
112 the ordering of nodes as they appear in the edge. | |
113 | |
114 """ | |
115 if G.is_multigraph(): | |
116 | |
117 def sorted_node(u, v, key): | |
118 return (u, v, key) if u <= v else (v, u, key) | |
119 | |
120 else: | |
121 | |
122 def sorted_node(u, v): | |
123 return (u, v) if u <= v else (v, u) | |
124 | |
125 return sorted_node | |
126 | |
127 | |
128 def _edge_func(G): | |
129 """Returns the edges from G, handling keys for multigraphs as necessary. | |
130 | |
131 """ | |
132 if G.is_multigraph(): | |
133 | |
134 def get_edges(nbunch=None): | |
135 return G.edges(nbunch, keys=True) | |
136 | |
137 else: | |
138 | |
139 def get_edges(nbunch=None): | |
140 return G.edges(nbunch) | |
141 | |
142 return get_edges | |
143 | |
144 | |
145 def _sorted_edge(u, v): | |
146 """Returns a sorted edge. | |
147 | |
148 During the construction of a line graph for undirected graphs, the data | |
149 structure can be a multigraph even though the line graph will never have | |
150 multiple edges between its nodes. For this reason, we must make sure not | |
151 to add any edge more than once. This requires that we build up a list of | |
152 edges to add and then remove all duplicates. And so, we must normalize | |
153 the representation of the edges. | |
154 | |
155 """ | |
156 return (u, v) if u <= v else (v, u) | |
157 | |
158 | |
159 def _lg_directed(G, create_using=None): | |
160 """Returns the line graph L of the (multi)digraph G. | |
161 | |
162 Edges in G appear as nodes in L, represented as tuples of the form (u,v) | |
163 or (u,v,key) if G is a multidigraph. A node in L corresponding to the edge | |
164 (u,v) is connected to every node corresponding to an edge (v,w). | |
165 | |
166 Parameters | |
167 ---------- | |
168 G : digraph | |
169 A directed graph or directed multigraph. | |
170 create_using : NetworkX graph constructor, optional | |
171 Graph type to create. If graph instance, then cleared before populated. | |
172 Default is to use the same graph class as `G`. | |
173 | |
174 """ | |
175 L = nx.empty_graph(0, create_using, default=G.__class__) | |
176 | |
177 # Create a graph specific edge function. | |
178 get_edges = _edge_func(G) | |
179 | |
180 for from_node in get_edges(): | |
181 # from_node is: (u,v) or (u,v,key) | |
182 L.add_node(from_node) | |
183 for to_node in get_edges(from_node[1]): | |
184 L.add_edge(from_node, to_node) | |
185 | |
186 return L | |
187 | |
188 | |
189 def _lg_undirected(G, selfloops=False, create_using=None): | |
190 """Returns the line graph L of the (multi)graph G. | |
191 | |
192 Edges in G appear as nodes in L, represented as sorted tuples of the form | |
193 (u,v), or (u,v,key) if G is a multigraph. A node in L corresponding to | |
194 the edge {u,v} is connected to every node corresponding to an edge that | |
195 involves u or v. | |
196 | |
197 Parameters | |
198 ---------- | |
199 G : graph | |
200 An undirected graph or multigraph. | |
201 selfloops : bool | |
202 If `True`, then self-loops are included in the line graph. If `False`, | |
203 they are excluded. | |
204 create_using : NetworkX graph constructor, optional (default=nx.Graph) | |
205 Graph type to create. If graph instance, then cleared before populated. | |
206 | |
207 Notes | |
208 ----- | |
209 The standard algorithm for line graphs of undirected graphs does not | |
210 produce self-loops. | |
211 | |
212 """ | |
213 L = nx.empty_graph(0, create_using, default=G.__class__) | |
214 | |
215 # Graph specific functions for edges and sorted nodes. | |
216 get_edges = _edge_func(G) | |
217 sorted_node = _node_func(G) | |
218 | |
219 # Determine if we include self-loops or not. | |
220 shift = 0 if selfloops else 1 | |
221 | |
222 edges = set() | |
223 for u in G: | |
224 # Label nodes as a sorted tuple of nodes in original graph. | |
225 nodes = [sorted_node(*x) for x in get_edges(u)] | |
226 | |
227 if len(nodes) == 1: | |
228 # Then the edge will be an isolated node in L. | |
229 L.add_node(nodes[0]) | |
230 | |
231 # Add a clique of `nodes` to graph. To prevent double adding edges, | |
232 # especially important for multigraphs, we store the edges in | |
233 # canonical form in a set. | |
234 for i, a in enumerate(nodes): | |
235 edges.update([_sorted_edge(a, b) for b in nodes[i + shift :]]) | |
236 | |
237 L.add_edges_from(edges) | |
238 return L | |
239 | |
240 | |
241 @not_implemented_for("directed") | |
242 @not_implemented_for("multigraph") | |
243 def inverse_line_graph(G): | |
244 """ Returns the inverse line graph of graph G. | |
245 | |
246 If H is a graph, and G is the line graph of H, such that H = L(G). | |
247 Then H is the inverse line graph of G. | |
248 | |
249 Not all graphs are line graphs and these do not have an inverse line graph. | |
250 In these cases this generator returns a NetworkXError. | |
251 | |
252 Parameters | |
253 ---------- | |
254 G : graph | |
255 A NetworkX Graph | |
256 | |
257 Returns | |
258 ------- | |
259 H : graph | |
260 The inverse line graph of G. | |
261 | |
262 Raises | |
263 ------ | |
264 NetworkXNotImplemented | |
265 If G is directed or a multigraph | |
266 | |
267 NetworkXError | |
268 If G is not a line graph | |
269 | |
270 Notes | |
271 ----- | |
272 This is an implementation of the Roussopoulos algorithm. | |
273 | |
274 If G consists of multiple components, then the algorithm doesn't work. | |
275 You should invert every component seperately: | |
276 | |
277 >>> K5 = nx.complete_graph(5) | |
278 >>> P4 = nx.Graph([("a", "b"), ("b", "c"), ("c", "d")]) | |
279 >>> G = nx.union(K5, P4) | |
280 >>> root_graphs = [] | |
281 >>> for comp in nx.connected_components(G): | |
282 ... root_graphs.append(nx.inverse_line_graph(G.subgraph(comp))) | |
283 >>> len(root_graphs) | |
284 2 | |
285 | |
286 References | |
287 ---------- | |
288 * Roussopolous, N, "A max {m, n} algorithm for determining the graph H from | |
289 its line graph G", Information Processing Letters 2, (1973), 108--112. | |
290 | |
291 """ | |
292 if G.number_of_nodes() == 0: | |
293 a = generate_unique_node() | |
294 H = nx.Graph() | |
295 H.add_node(a) | |
296 return H | |
297 elif G.number_of_nodes() == 1: | |
298 v = list(G)[0] | |
299 a = (v, 0) | |
300 b = (v, 1) | |
301 H = nx.Graph([(a, b)]) | |
302 return H | |
303 elif G.number_of_nodes() > 1 and G.number_of_edges() == 0: | |
304 msg = ( | |
305 "inverse_line_graph() doesn't work on an edgeless graph. " | |
306 "Please use this function on each component seperately." | |
307 ) | |
308 raise nx.NetworkXError(msg) | |
309 | |
310 starting_cell = _select_starting_cell(G) | |
311 P = _find_partition(G, starting_cell) | |
312 # count how many times each vertex appears in the partition set | |
313 P_count = {u: 0 for u in G.nodes()} | |
314 for p in P: | |
315 for u in p: | |
316 P_count[u] += 1 | |
317 | |
318 if max(P_count.values()) > 2: | |
319 msg = "G is not a line graph (vertex found in more " "than two partition cells)" | |
320 raise nx.NetworkXError(msg) | |
321 W = tuple([(u,) for u in P_count if P_count[u] == 1]) | |
322 H = nx.Graph() | |
323 H.add_nodes_from(P) | |
324 H.add_nodes_from(W) | |
325 for a, b in combinations(H.nodes(), 2): | |
326 if len(set(a).intersection(set(b))) > 0: | |
327 H.add_edge(a, b) | |
328 return H | |
329 | |
330 | |
331 def _triangles(G, e): | |
332 """ Return list of all triangles containing edge e""" | |
333 u, v = e | |
334 if u not in G: | |
335 raise nx.NetworkXError(f"Vertex {u} not in graph") | |
336 if v not in G[u]: | |
337 raise nx.NetworkXError(f"Edge ({u}, {v}) not in graph") | |
338 triangle_list = [] | |
339 for x in G[u]: | |
340 if x in G[v]: | |
341 triangle_list.append((u, v, x)) | |
342 return triangle_list | |
343 | |
344 | |
345 def _odd_triangle(G, T): | |
346 """ Test whether T is an odd triangle in G | |
347 | |
348 Parameters | |
349 ---------- | |
350 G : NetworkX Graph | |
351 T : 3-tuple of vertices forming triangle in G | |
352 | |
353 Returns | |
354 ------- | |
355 True is T is an odd triangle | |
356 False otherwise | |
357 | |
358 Raises | |
359 ------ | |
360 NetworkXError | |
361 T is not a triangle in G | |
362 | |
363 Notes | |
364 ----- | |
365 An odd triangle is one in which there exists another vertex in G which is | |
366 adjacent to either exactly one or exactly all three of the vertices in the | |
367 triangle. | |
368 | |
369 """ | |
370 for u in T: | |
371 if u not in G.nodes(): | |
372 raise nx.NetworkXError(f"Vertex {u} not in graph") | |
373 for e in list(combinations(T, 2)): | |
374 if e[0] not in G[e[1]]: | |
375 raise nx.NetworkXError(f"Edge ({e[0]}, {e[1]}) not in graph") | |
376 | |
377 T_neighbors = defaultdict(int) | |
378 for t in T: | |
379 for v in G[t]: | |
380 if v not in T: | |
381 T_neighbors[v] += 1 | |
382 for v in T_neighbors: | |
383 if T_neighbors[v] in [1, 3]: | |
384 return True | |
385 return False | |
386 | |
387 | |
388 def _find_partition(G, starting_cell): | |
389 """ Find a partition of the vertices of G into cells of complete graphs | |
390 | |
391 Parameters | |
392 ---------- | |
393 G : NetworkX Graph | |
394 starting_cell : tuple of vertices in G which form a cell | |
395 | |
396 Returns | |
397 ------- | |
398 List of tuples of vertices of G | |
399 | |
400 Raises | |
401 ------ | |
402 NetworkXError | |
403 If a cell is not a complete subgraph then G is not a line graph | |
404 """ | |
405 G_partition = G.copy() | |
406 P = [starting_cell] # partition set | |
407 G_partition.remove_edges_from(list(combinations(starting_cell, 2))) | |
408 # keep list of partitioned nodes which might have an edge in G_partition | |
409 partitioned_vertices = list(starting_cell) | |
410 while G_partition.number_of_edges() > 0: | |
411 # there are still edges left and so more cells to be made | |
412 u = partitioned_vertices[-1] | |
413 deg_u = len(G_partition[u]) | |
414 if deg_u == 0: | |
415 # if u has no edges left in G_partition then we have found | |
416 # all of its cells so we do not need to keep looking | |
417 partitioned_vertices.pop() | |
418 else: | |
419 # if u still has edges then we need to find its other cell | |
420 # this other cell must be a complete subgraph or else G is | |
421 # not a line graph | |
422 new_cell = [u] + list(G_partition[u]) | |
423 for u in new_cell: | |
424 for v in new_cell: | |
425 if (u != v) and (v not in G_partition[u]): | |
426 msg = ( | |
427 "G is not a line graph" | |
428 "(partition cell not a complete subgraph)" | |
429 ) | |
430 raise nx.NetworkXError(msg) | |
431 P.append(tuple(new_cell)) | |
432 G_partition.remove_edges_from(list(combinations(new_cell, 2))) | |
433 partitioned_vertices += new_cell | |
434 return P | |
435 | |
436 | |
437 def _select_starting_cell(G, starting_edge=None): | |
438 """ Select a cell to initiate _find_partition | |
439 | |
440 Parameters | |
441 ---------- | |
442 G : NetworkX Graph | |
443 starting_edge: an edge to build the starting cell from | |
444 | |
445 Returns | |
446 ------- | |
447 Tuple of vertices in G | |
448 | |
449 Raises | |
450 ------ | |
451 NetworkXError | |
452 If it is determined that G is not a line graph | |
453 | |
454 Notes | |
455 ----- | |
456 If starting edge not specified then pick an arbitrary edge - doesn't | |
457 matter which. However, this function may call itself requiring a | |
458 specific starting edge. Note that the r, s notation for counting | |
459 triangles is the same as in the Roussopoulos paper cited above. | |
460 """ | |
461 if starting_edge is None: | |
462 e = arbitrary_element(list(G.edges())) | |
463 else: | |
464 e = starting_edge | |
465 if e[0] not in G[e[1]]: | |
466 msg = f"starting_edge ({e[0]}, {e[1]}) is not in the Graph" | |
467 raise nx.NetworkXError(msg) | |
468 e_triangles = _triangles(G, e) | |
469 r = len(e_triangles) | |
470 if r == 0: | |
471 # there are no triangles containing e, so the starting cell is just e | |
472 starting_cell = e | |
473 elif r == 1: | |
474 # there is exactly one triangle, T, containing e. If other 2 edges | |
475 # of T belong only to this triangle then T is starting cell | |
476 T = e_triangles[0] | |
477 a, b, c = T | |
478 # ab was original edge so check the other 2 edges | |
479 ac_edges = [x for x in _triangles(G, (a, c))] | |
480 bc_edges = [x for x in _triangles(G, (b, c))] | |
481 if len(ac_edges) == 1: | |
482 if len(bc_edges) == 1: | |
483 starting_cell = T | |
484 else: | |
485 return _select_starting_cell(G, starting_edge=(b, c)) | |
486 else: | |
487 return _select_starting_cell(G, starting_edge=(a, c)) | |
488 else: | |
489 # r >= 2 so we need to count the number of odd triangles, s | |
490 s = 0 | |
491 odd_triangles = [] | |
492 for T in e_triangles: | |
493 if _odd_triangle(G, T): | |
494 s += 1 | |
495 odd_triangles.append(T) | |
496 if r == 2 and s == 0: | |
497 # in this case either triangle works, so just use T | |
498 starting_cell = T | |
499 elif r - 1 <= s <= r: | |
500 # check if odd triangles containing e form complete subgraph | |
501 # there must be exactly s+2 of them | |
502 # and they must all be connected | |
503 triangle_nodes = set() | |
504 for T in odd_triangles: | |
505 for x in T: | |
506 triangle_nodes.add(x) | |
507 if len(triangle_nodes) == s + 2: | |
508 for u in triangle_nodes: | |
509 for v in triangle_nodes: | |
510 if u != v and (v not in G[u]): | |
511 msg = ( | |
512 "G is not a line graph (odd triangles " | |
513 "do not form complete subgraph)" | |
514 ) | |
515 raise nx.NetworkXError(msg) | |
516 # otherwise then we can use this as the starting cell | |
517 starting_cell = tuple(triangle_nodes) | |
518 else: | |
519 msg = ( | |
520 "G is not a line graph (odd triangles " | |
521 "do not form complete subgraph)" | |
522 ) | |
523 raise nx.NetworkXError(msg) | |
524 else: | |
525 msg = ( | |
526 "G is not a line graph (incorrect number of " | |
527 "odd triangles around starting edge)" | |
528 ) | |
529 raise nx.NetworkXError(msg) | |
530 return starting_cell |