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

author shellac Mon, 22 Mar 2021 18:12:50 +0000
comparison
equal 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)
183 for to_node in get_edges(from_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.
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
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()
296 return H
297 elif G.number_of_nodes() == 1:
298 v = list(G)
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()
325 for a, b in combinations(H.nodes(), 2):
326 if len(set(a).intersection(set(b))) > 0:
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 not in G[e]:
375 raise nx.NetworkXError(f"Edge ({e}, {e}) 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 not in G[e]:
466 msg = f"starting_edge ({e}, {e}) 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
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:
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