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

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