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