1""" 2Graph products. 3""" 4from itertools import product 5 6import networkx as nx 7from networkx.utils import not_implemented_for 8 9__all__ = [ 10 "tensor_product", 11 "cartesian_product", 12 "lexicographic_product", 13 "strong_product", 14 "power", 15 "rooted_product", 16] 17 18 19def _dict_product(d1, d2): 20 return {k: (d1.get(k), d2.get(k)) for k in set(d1) | set(d2)} 21 22 23# Generators for producting graph products 24def _node_product(G, H): 25 for u, v in product(G, H): 26 yield ((u, v), _dict_product(G.nodes[u], H.nodes[v])) 27 28 29def _directed_edges_cross_edges(G, H): 30 if not G.is_multigraph() and not H.is_multigraph(): 31 for u, v, c in G.edges(data=True): 32 for x, y, d in H.edges(data=True): 33 yield (u, x), (v, y), _dict_product(c, d) 34 if not G.is_multigraph() and H.is_multigraph(): 35 for u, v, c in G.edges(data=True): 36 for x, y, k, d in H.edges(data=True, keys=True): 37 yield (u, x), (v, y), k, _dict_product(c, d) 38 if G.is_multigraph() and not H.is_multigraph(): 39 for u, v, k, c in G.edges(data=True, keys=True): 40 for x, y, d in H.edges(data=True): 41 yield (u, x), (v, y), k, _dict_product(c, d) 42 if G.is_multigraph() and H.is_multigraph(): 43 for u, v, j, c in G.edges(data=True, keys=True): 44 for x, y, k, d in H.edges(data=True, keys=True): 45 yield (u, x), (v, y), (j, k), _dict_product(c, d) 46 47 48def _undirected_edges_cross_edges(G, H): 49 if not G.is_multigraph() and not H.is_multigraph(): 50 for u, v, c in G.edges(data=True): 51 for x, y, d in H.edges(data=True): 52 yield (v, x), (u, y), _dict_product(c, d) 53 if not G.is_multigraph() and H.is_multigraph(): 54 for u, v, c in G.edges(data=True): 55 for x, y, k, d in H.edges(data=True, keys=True): 56 yield (v, x), (u, y), k, _dict_product(c, d) 57 if G.is_multigraph() and not H.is_multigraph(): 58 for u, v, k, c in G.edges(data=True, keys=True): 59 for x, y, d in H.edges(data=True): 60 yield (v, x), (u, y), k, _dict_product(c, d) 61 if G.is_multigraph() and H.is_multigraph(): 62 for u, v, j, c in G.edges(data=True, keys=True): 63 for x, y, k, d in H.edges(data=True, keys=True): 64 yield (v, x), (u, y), (j, k), _dict_product(c, d) 65 66 67def _edges_cross_nodes(G, H): 68 if G.is_multigraph(): 69 for u, v, k, d in G.edges(data=True, keys=True): 70 for x in H: 71 yield (u, x), (v, x), k, d 72 else: 73 for u, v, d in G.edges(data=True): 74 for x in H: 75 if H.is_multigraph(): 76 yield (u, x), (v, x), None, d 77 else: 78 yield (u, x), (v, x), d 79 80 81def _nodes_cross_edges(G, H): 82 if H.is_multigraph(): 83 for x in G: 84 for u, v, k, d in H.edges(data=True, keys=True): 85 yield (x, u), (x, v), k, d 86 else: 87 for x in G: 88 for u, v, d in H.edges(data=True): 89 if G.is_multigraph(): 90 yield (x, u), (x, v), None, d 91 else: 92 yield (x, u), (x, v), d 93 94 95def _edges_cross_nodes_and_nodes(G, H): 96 if G.is_multigraph(): 97 for u, v, k, d in G.edges(data=True, keys=True): 98 for x in H: 99 for y in H: 100 yield (u, x), (v, y), k, d 101 else: 102 for u, v, d in G.edges(data=True): 103 for x in H: 104 for y in H: 105 if H.is_multigraph(): 106 yield (u, x), (v, y), None, d 107 else: 108 yield (u, x), (v, y), d 109 110 111def _init_product_graph(G, H): 112 if not G.is_directed() == H.is_directed(): 113 msg = "G and H must be both directed or both undirected" 114 raise nx.NetworkXError(msg) 115 if G.is_multigraph() or H.is_multigraph(): 116 GH = nx.MultiGraph() 117 else: 118 GH = nx.Graph() 119 if G.is_directed(): 120 GH = GH.to_directed() 121 return GH 122 123 124def tensor_product(G, H): 125 r"""Returns the tensor product of G and H. 126 127 The tensor product $P$ of the graphs $G$ and $H$ has a node set that 128 is the tensor product of the node sets, $V(P)=V(G) \times V(H)$. 129 $P$ has an edge $((u,v), (x,y))$ if and only if $(u,x)$ is an edge in $G$ 130 and $(v,y)$ is an edge in $H$. 131 132 Tensor product is sometimes also referred to as the categorical product, 133 direct product, cardinal product or conjunction. 134 135 136 Parameters 137 ---------- 138 G, H: graphs 139 Networkx graphs. 140 141 Returns 142 ------- 143 P: NetworkX graph 144 The tensor product of G and H. P will be a multi-graph if either G 145 or H is a multi-graph, will be a directed if G and H are directed, 146 and undirected if G and H are undirected. 147 148 Raises 149 ------ 150 NetworkXError 151 If G and H are not both directed or both undirected. 152 153 Notes 154 ----- 155 Node attributes in P are two-tuple of the G and H node attributes. 156 Missing attributes are assigned None. 157 158 Examples 159 -------- 160 >>> G = nx.Graph() 161 >>> H = nx.Graph() 162 >>> G.add_node(0, a1=True) 163 >>> H.add_node("a", a2="Spam") 164 >>> P = nx.tensor_product(G, H) 165 >>> list(P) 166 [(0, 'a')] 167 168 Edge attributes and edge keys (for multigraphs) are also copied to the 169 new product graph 170 """ 171 GH = _init_product_graph(G, H) 172 GH.add_nodes_from(_node_product(G, H)) 173 GH.add_edges_from(_directed_edges_cross_edges(G, H)) 174 if not GH.is_directed(): 175 GH.add_edges_from(_undirected_edges_cross_edges(G, H)) 176 return GH 177 178 179def cartesian_product(G, H): 180 r"""Returns the Cartesian product of G and H. 181 182 The Cartesian product $P$ of the graphs $G$ and $H$ has a node set that 183 is the Cartesian product of the node sets, $V(P)=V(G) \times V(H)$. 184 $P$ has an edge $((u,v),(x,y))$ if and only if either $u$ is equal to $x$ 185 and both $v$ and $y$ are adjacent in $H$ or if $v$ is equal to $y$ and 186 both $u$ and $x$ are adjacent in $G$. 187 188 Parameters 189 ---------- 190 G, H: graphs 191 Networkx graphs. 192 193 Returns 194 ------- 195 P: NetworkX graph 196 The Cartesian product of G and H. P will be a multi-graph if either G 197 or H is a multi-graph. Will be a directed if G and H are directed, 198 and undirected if G and H are undirected. 199 200 Raises 201 ------ 202 NetworkXError 203 If G and H are not both directed or both undirected. 204 205 Notes 206 ----- 207 Node attributes in P are two-tuple of the G and H node attributes. 208 Missing attributes are assigned None. 209 210 Examples 211 -------- 212 >>> G = nx.Graph() 213 >>> H = nx.Graph() 214 >>> G.add_node(0, a1=True) 215 >>> H.add_node("a", a2="Spam") 216 >>> P = nx.cartesian_product(G, H) 217 >>> list(P) 218 [(0, 'a')] 219 220 Edge attributes and edge keys (for multigraphs) are also copied to the 221 new product graph 222 """ 223 GH = _init_product_graph(G, H) 224 GH.add_nodes_from(_node_product(G, H)) 225 GH.add_edges_from(_edges_cross_nodes(G, H)) 226 GH.add_edges_from(_nodes_cross_edges(G, H)) 227 return GH 228 229 230def lexicographic_product(G, H): 231 r"""Returns the lexicographic product of G and H. 232 233 The lexicographical product $P$ of the graphs $G$ and $H$ has a node set 234 that is the Cartesian product of the node sets, $V(P)=V(G) \times V(H)$. 235 $P$ has an edge $((u,v), (x,y))$ if and only if $(u,v)$ is an edge in $G$ 236 or $u==v$ and $(x,y)$ is an edge in $H$. 237 238 Parameters 239 ---------- 240 G, H: graphs 241 Networkx graphs. 242 243 Returns 244 ------- 245 P: NetworkX graph 246 The Cartesian product of G and H. P will be a multi-graph if either G 247 or H is a multi-graph. Will be a directed if G and H are directed, 248 and undirected if G and H are undirected. 249 250 Raises 251 ------ 252 NetworkXError 253 If G and H are not both directed or both undirected. 254 255 Notes 256 ----- 257 Node attributes in P are two-tuple of the G and H node attributes. 258 Missing attributes are assigned None. 259 260 Examples 261 -------- 262 >>> G = nx.Graph() 263 >>> H = nx.Graph() 264 >>> G.add_node(0, a1=True) 265 >>> H.add_node("a", a2="Spam") 266 >>> P = nx.lexicographic_product(G, H) 267 >>> list(P) 268 [(0, 'a')] 269 270 Edge attributes and edge keys (for multigraphs) are also copied to the 271 new product graph 272 """ 273 GH = _init_product_graph(G, H) 274 GH.add_nodes_from(_node_product(G, H)) 275 # Edges in G regardless of H designation 276 GH.add_edges_from(_edges_cross_nodes_and_nodes(G, H)) 277 # For each x in G, only if there is an edge in H 278 GH.add_edges_from(_nodes_cross_edges(G, H)) 279 return GH 280 281 282def strong_product(G, H): 283 r"""Returns the strong product of G and H. 284 285 The strong product $P$ of the graphs $G$ and $H$ has a node set that 286 is the Cartesian product of the node sets, $V(P)=V(G) \times V(H)$. 287 $P$ has an edge $((u,v), (x,y))$ if and only if 288 $u==v$ and $(x,y)$ is an edge in $H$, or 289 $x==y$ and $(u,v)$ is an edge in $G$, or 290 $(u,v)$ is an edge in $G$ and $(x,y)$ is an edge in $H$. 291 292 Parameters 293 ---------- 294 G, H: graphs 295 Networkx graphs. 296 297 Returns 298 ------- 299 P: NetworkX graph 300 The Cartesian product of G and H. P will be a multi-graph if either G 301 or H is a multi-graph. Will be a directed if G and H are directed, 302 and undirected if G and H are undirected. 303 304 Raises 305 ------ 306 NetworkXError 307 If G and H are not both directed or both undirected. 308 309 Notes 310 ----- 311 Node attributes in P are two-tuple of the G and H node attributes. 312 Missing attributes are assigned None. 313 314 Examples 315 -------- 316 >>> G = nx.Graph() 317 >>> H = nx.Graph() 318 >>> G.add_node(0, a1=True) 319 >>> H.add_node("a", a2="Spam") 320 >>> P = nx.strong_product(G, H) 321 >>> list(P) 322 [(0, 'a')] 323 324 Edge attributes and edge keys (for multigraphs) are also copied to the 325 new product graph 326 """ 327 GH = _init_product_graph(G, H) 328 GH.add_nodes_from(_node_product(G, H)) 329 GH.add_edges_from(_nodes_cross_edges(G, H)) 330 GH.add_edges_from(_edges_cross_nodes(G, H)) 331 GH.add_edges_from(_directed_edges_cross_edges(G, H)) 332 if not GH.is_directed(): 333 GH.add_edges_from(_undirected_edges_cross_edges(G, H)) 334 return GH 335 336 337@not_implemented_for("directed") 338@not_implemented_for("multigraph") 339def power(G, k): 340 """Returns the specified power of a graph. 341 342 The $k$th power of a simple graph $G$, denoted $G^k$, is a 343 graph on the same set of nodes in which two distinct nodes $u$ and 344 $v$ are adjacent in $G^k$ if and only if the shortest path 345 distance between $u$ and $v$ in $G$ is at most $k$. 346 347 Parameters 348 ---------- 349 G : graph 350 A NetworkX simple graph object. 351 352 k : positive integer 353 The power to which to raise the graph `G`. 354 355 Returns 356 ------- 357 NetworkX simple graph 358 `G` to the power `k`. 359 360 Raises 361 ------ 362 ValueError 363 If the exponent `k` is not positive. 364 365 NetworkXNotImplemented 366 If `G` is not a simple graph. 367 368 Examples 369 -------- 370 The number of edges will never decrease when taking successive 371 powers: 372 373 >>> G = nx.path_graph(4) 374 >>> list(nx.power(G, 2).edges) 375 [(0, 1), (0, 2), (1, 2), (1, 3), (2, 3)] 376 >>> list(nx.power(G, 3).edges) 377 [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)] 378 379 The `k`th power of a cycle graph on *n* nodes is the complete graph 380 on *n* nodes, if `k` is at least ``n // 2``: 381 382 >>> G = nx.cycle_graph(5) 383 >>> H = nx.complete_graph(5) 384 >>> nx.is_isomorphic(nx.power(G, 2), H) 385 True 386 >>> G = nx.cycle_graph(8) 387 >>> H = nx.complete_graph(8) 388 >>> nx.is_isomorphic(nx.power(G, 4), H) 389 True 390 391 References 392 ---------- 393 .. [1] J. A. Bondy, U. S. R. Murty, *Graph Theory*. Springer, 2008. 394 395 Notes 396 ----- 397 This definition of "power graph" comes from Exercise 3.1.6 of 398 *Graph Theory* by Bondy and Murty [1]_. 399 400 """ 401 if k <= 0: 402 raise ValueError("k must be a positive integer") 403 H = nx.Graph() 404 H.add_nodes_from(G) 405 # update BFS code to ignore self loops. 406 for n in G: 407 seen = {} # level (number of hops) when seen in BFS 408 level = 1 # the current level 409 nextlevel = G[n] 410 while nextlevel: 411 thislevel = nextlevel # advance to next level 412 nextlevel = {} # and start a new list (fringe) 413 for v in thislevel: 414 if v == n: # avoid self loop 415 continue 416 if v not in seen: 417 seen[v] = level # set the level of vertex v 418 nextlevel.update(G[v]) # add neighbors of v 419 if k <= level: 420 break 421 level += 1 422 H.add_edges_from((n, nbr) for nbr in seen) 423 return H 424 425 426@not_implemented_for("multigraph") 427def rooted_product(G, H, root): 428 """Return the rooted product of graphs G and H rooted at root in H. 429 430 A new graph is constructed representing the rooted product of 431 the inputted graphs, G and H, with a root in H. 432 A rooted product duplicates H for each nodes in G with the root 433 of H corresponding to the node in G. Nodes are renamed as the direct 434 product of G and H. The result is a subgraph of the cartesian product. 435 436 Parameters 437 ---------- 438 G,H : graph 439 A NetworkX graph 440 root : node 441 A node in H 442 443 Returns 444 ------- 445 R : The rooted product of G and H with a specified root in H 446 447 Notes 448 ----- 449 The nodes of R are the Cartesian Product of the nodes of G and H. 450 The nodes of G and H are not relabeled. 451 """ 452 if root not in H: 453 raise nx.NetworkXError("root must be a vertex in H") 454 455 R = nx.Graph() 456 R.add_nodes_from(product(G, H)) 457 458 R.add_edges_from(((e[0], root), (e[1], root)) for e in G.edges()) 459 R.add_edges_from(((g, e[0]), (g, e[1])) for g in G for e in H.edges()) 460 461 return R 462