## Mercurial > repos > shellac > sam_consensus_v3

### comparison env/lib/python3.9/site-packages/networkx/generators/line.py @ 0:4f3585e2f14b draft default tip

Find changesets by keywords (author, files, the commit message), revision
number or hash, or revset expression.

"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 |