ioftools / networkxMiCe / networkxmaster / networkx / algorithms / operators / product.py @ 5cef0f13
History  View  Annotate  Download (13.9 KB)
1 
# Copyright (C) 2011 by


2 
# Aric Hagberg <hagberg@lanl.gov>

3 
# Dan Schult <dschult@colgate.edu>

4 
# Pieter Swart <swart@lanl.gov>

5 
# All rights reserved.

6 
# BSD license.

7 
#

8 
# Authors:

9 
# Aric Hagberg <hagberg@lanl.gov>

10 
# Pieter Swart <swart@lanl.gov>

11 
# Dan Schult <dschult@colgate.edu>

12 
# Ben Edwards <bedwards@cs.unm.edu>

13 
"""

14 
Graph products.

15 
"""

16 
from itertools import product 
17  
18 
import networkx as nx 
19 
from networkx.utils import not_implemented_for 
20  
21 
__all__ = ['tensor_product', 'cartesian_product', 
22 
'lexicographic_product', 'strong_product', 'power', 
23 
'rooted_product']

24  
25  
26 
def _dict_product(d1, d2): 
27 
return dict((k, (d1.get(k), d2.get(k))) for k in set(d1)  set(d2)) 
28  
29  
30 
# Generators for producting graph products

31 
def _node_product(G, H): 
32 
for u, v in product(G, H): 
33 
yield ((u, v), _dict_product(G.nodes[u], H.nodes[v]))

34  
35  
36 
def _directed_edges_cross_edges(G, H): 
37 
if not G.is_multigraph() and not H.is_multigraph(): 
38 
for u, v, c in G.edges(data=True): 
39 
for x, y, d in H.edges(data=True): 
40 
yield (u, x), (v, y), _dict_product(c, d)

41 
if not G.is_multigraph() and H.is_multigraph(): 
42 
for u, v, c in G.edges(data=True): 
43 
for x, y, k, d in H.edges(data=True, keys=True): 
44 
yield (u, x), (v, y), k, _dict_product(c, d)

45 
if G.is_multigraph() and not H.is_multigraph(): 
46 
for u, v, k, c in G.edges(data=True, keys=True): 
47 
for x, y, d in H.edges(data=True): 
48 
yield (u, x), (v, y), k, _dict_product(c, d)

49 
if G.is_multigraph() and H.is_multigraph(): 
50 
for u, v, j, c in G.edges(data=True, keys=True): 
51 
for x, y, k, d in H.edges(data=True, keys=True): 
52 
yield (u, x), (v, y), (j, k), _dict_product(c, d)

53  
54  
55 
def _undirected_edges_cross_edges(G, H): 
56 
if not G.is_multigraph() and not H.is_multigraph(): 
57 
for u, v, c in G.edges(data=True): 
58 
for x, y, d in H.edges(data=True): 
59 
yield (v, x), (u, y), _dict_product(c, d)

60 
if not G.is_multigraph() and H.is_multigraph(): 
61 
for u, v, c in G.edges(data=True): 
62 
for x, y, k, d in H.edges(data=True, keys=True): 
63 
yield (v, x), (u, y), k, _dict_product(c, d)

64 
if G.is_multigraph() and not H.is_multigraph(): 
65 
for u, v, k, c in G.edges(data=True, keys=True): 
66 
for x, y, d in H.edges(data=True): 
67 
yield (v, x), (u, y), k, _dict_product(c, d)

68 
if G.is_multigraph() and H.is_multigraph(): 
69 
for u, v, j, c in G.edges(data=True, keys=True): 
70 
for x, y, k, d in H.edges(data=True, keys=True): 
71 
yield (v, x), (u, y), (j, k), _dict_product(c, d)

72  
73  
74 
def _edges_cross_nodes(G, H): 
75 
if G.is_multigraph():

76 
for u, v, k, d in G.edges(data=True, keys=True): 
77 
for x in H: 
78 
yield (u, x), (v, x), k, d

79 
else:

80 
for u, v, d in G.edges(data=True): 
81 
for x in H: 
82 
if H.is_multigraph():

83 
yield (u, x), (v, x), None, d 
84 
else:

85 
yield (u, x), (v, x), d

86  
87  
88 
def _nodes_cross_edges(G, H): 
89 
if H.is_multigraph():

90 
for x in G: 
91 
for u, v, k, d in H.edges(data=True, keys=True): 
92 
yield (x, u), (x, v), k, d

93 
else:

94 
for x in G: 
95 
for u, v, d in H.edges(data=True): 
96 
if G.is_multigraph():

97 
yield (x, u), (x, v), None, d 
98 
else:

99 
yield (x, u), (x, v), d

100  
101  
102 
def _edges_cross_nodes_and_nodes(G, H): 
103 
if G.is_multigraph():

104 
for u, v, k, d in G.edges(data=True, keys=True): 
105 
for x in H: 
106 
for y in H: 
107 
yield (u, x), (v, y), k, d

108 
else:

109 
for u, v, d in G.edges(data=True): 
110 
for x in H: 
111 
for y in H: 
112 
if H.is_multigraph():

113 
yield (u, x), (v, y), None, d 
114 
else:

115 
yield (u, x), (v, y), d

116  
117  
118 
def _init_product_graph(G, H): 
119 
if not G.is_directed() == H.is_directed(): 
120 
msg = "G and H must be both directed or both undirected"

121 
raise nx.NetworkXError(msg)

122 
if G.is_multigraph() or H.is_multigraph(): 
123 
GH = nx.MultiGraph() 
124 
else:

125 
GH = nx.Graph() 
126 
if G.is_directed():

127 
GH = GH.to_directed() 
128 
return GH

129  
130  
131 
def tensor_product(G, H): 
132 
r"""Returns the tensor product of G and H.

133 

134 
The tensor product $P$ of the graphs $G$ and $H$ has a node set that

135 
is the tensor product of the node sets, $V(P)=V(G) \times V(H)$.

136 
$P$ has an edge $((u,v), (x,y))$ if and only if $(u,x)$ is an edge in $G$

137 
and $(v,y)$ is an edge in $H$.

138 

139 
Tensor product is sometimes also referred to as the categorical product,

140 
direct product, cardinal product or conjunction.

141 

142 

143 
Parameters

144 


145 
G, H: graphs

146 
Networkx graphs.

147 

148 
Returns

149 


150 
P: NetworkX graph

151 
The tensor product of G and H. P will be a multigraph if either G

152 
or H is a multigraph, will be a directed if G and H are directed,

153 
and undirected if G and H are undirected.

154 

155 
Raises

156 


157 
NetworkXError

158 
If G and H are not both directed or both undirected.

159 

160 
Notes

161 


162 
Node attributes in P are twotuple of the G and H node attributes.

163 
Missing attributes are assigned None.

164 

165 
Examples

166 


167 
>>> G = nx.Graph()

168 
>>> H = nx.Graph()

169 
>>> G.add_node(0, a1=True)

170 
>>> H.add_node('a', a2='Spam')

171 
>>> P = nx.tensor_product(G, H)

172 
>>> list(P)

173 
[(0, 'a')]

174 

175 
Edge attributes and edge keys (for multigraphs) are also copied to the

176 
new product graph

177 
"""

178 
GH = _init_product_graph(G, H) 
179 
GH.add_nodes_from(_node_product(G, H)) 
180 
GH.add_edges_from(_directed_edges_cross_edges(G, H)) 
181 
if not GH.is_directed(): 
182 
GH.add_edges_from(_undirected_edges_cross_edges(G, H)) 
183 
return GH

184  
185  
186 
def cartesian_product(G, H): 
187 
r"""Returns the Cartesian product of G and H.

188 

189 
The Cartesian product $P$ of the graphs $G$ and $H$ has a node set that

190 
is the Cartesian product of the node sets, $V(P)=V(G) \times V(H)$.

191 
$P$ has an edge $((u,v),(x,y))$ if and only if either $u$ is equal to $x$

192 
and both $v$ and $y$ are adjacent in $H$ or if $v$ is equal to $y$ and

193 
both $u$ and $x$ are adjacent in $G$.

194 

195 
Parameters

196 


197 
G, H: graphs

198 
Networkx graphs.

199 

200 
Returns

201 


202 
P: NetworkX graph

203 
The Cartesian product of G and H. P will be a multigraph if either G

204 
or H is a multigraph. Will be a directed if G and H are directed,

205 
and undirected if G and H are undirected.

206 

207 
Raises

208 


209 
NetworkXError

210 
If G and H are not both directed or both undirected.

211 

212 
Notes

213 


214 
Node attributes in P are twotuple of the G and H node attributes.

215 
Missing attributes are assigned None.

216 

217 
Examples

218 


219 
>>> G = nx.Graph()

220 
>>> H = nx.Graph()

221 
>>> G.add_node(0, a1=True)

222 
>>> H.add_node('a', a2='Spam')

223 
>>> P = nx.cartesian_product(G, H)

224 
>>> list(P)

225 
[(0, 'a')]

226 

227 
Edge attributes and edge keys (for multigraphs) are also copied to the

228 
new product graph

229 
"""

230 
GH = _init_product_graph(G, H) 
231 
GH.add_nodes_from(_node_product(G, H)) 
232 
GH.add_edges_from(_edges_cross_nodes(G, H)) 
233 
GH.add_edges_from(_nodes_cross_edges(G, H)) 
234 
return GH

235  
236  
237 
def lexicographic_product(G, H): 
238 
r"""Returns the lexicographic product of G and H.

239 

240 
The lexicographical product $P$ of the graphs $G$ and $H$ has a node set

241 
that is the Cartesian product of the node sets, $V(P)=V(G) \times V(H)$.

242 
$P$ has an edge $((u,v), (x,y))$ if and only if $(u,v)$ is an edge in $G$

243 
or $u==v$ and $(x,y)$ is an edge in $H$.

244 

245 
Parameters

246 


247 
G, H: graphs

248 
Networkx graphs.

249 

250 
Returns

251 


252 
P: NetworkX graph

253 
The Cartesian product of G and H. P will be a multigraph if either G

254 
or H is a multigraph. Will be a directed if G and H are directed,

255 
and undirected if G and H are undirected.

256 

257 
Raises

258 


259 
NetworkXError

260 
If G and H are not both directed or both undirected.

261 

262 
Notes

263 


264 
Node attributes in P are twotuple of the G and H node attributes.

265 
Missing attributes are assigned None.

266 

267 
Examples

268 


269 
>>> G = nx.Graph()

270 
>>> H = nx.Graph()

271 
>>> G.add_node(0, a1=True)

272 
>>> H.add_node('a', a2='Spam')

273 
>>> P = nx.lexicographic_product(G, H)

274 
>>> list(P)

275 
[(0, 'a')]

276 

277 
Edge attributes and edge keys (for multigraphs) are also copied to the

278 
new product graph

279 
"""

280 
GH = _init_product_graph(G, H) 
281 
GH.add_nodes_from(_node_product(G, H)) 
282 
# Edges in G regardless of H designation

283 
GH.add_edges_from(_edges_cross_nodes_and_nodes(G, H)) 
284 
# For each x in G, only if there is an edge in H

285 
GH.add_edges_from(_nodes_cross_edges(G, H)) 
286 
return GH

287  
288  
289 
def strong_product(G, H): 
290 
r"""Returns the strong product of G and H.

291 

292 
The strong product $P$ of the graphs $G$ and $H$ has a node set that

293 
is the Cartesian product of the node sets, $V(P)=V(G) \times V(H)$.

294 
$P$ has an edge $((u,v), (x,y))$ if and only if

295 
$u==v$ and $(x,y)$ is an edge in $H$, or

296 
$x==y$ and $(u,v)$ is an edge in $G$, or

297 
$(u,v)$ is an edge in $G$ and $(x,y)$ is an edge in $H$.

298 

299 
Parameters

300 


301 
G, H: graphs

302 
Networkx graphs.

303 

304 
Returns

305 


306 
P: NetworkX graph

307 
The Cartesian product of G and H. P will be a multigraph if either G

308 
or H is a multigraph. Will be a directed if G and H are directed,

309 
and undirected if G and H are undirected.

310 

311 
Raises

312 


313 
NetworkXError

314 
If G and H are not both directed or both undirected.

315 

316 
Notes

317 


318 
Node attributes in P are twotuple of the G and H node attributes.

319 
Missing attributes are assigned None.

320 

321 
Examples

322 


323 
>>> G = nx.Graph()

324 
>>> H = nx.Graph()

325 
>>> G.add_node(0, a1=True)

326 
>>> H.add_node('a', a2='Spam')

327 
>>> P = nx.strong_product(G, H)

328 
>>> list(P)

329 
[(0, 'a')]

330 

331 
Edge attributes and edge keys (for multigraphs) are also copied to the

332 
new product graph

333 
"""

334 
GH = _init_product_graph(G, H) 
335 
GH.add_nodes_from(_node_product(G, H)) 
336 
GH.add_edges_from(_nodes_cross_edges(G, H)) 
337 
GH.add_edges_from(_edges_cross_nodes(G, H)) 
338 
GH.add_edges_from(_directed_edges_cross_edges(G, H)) 
339 
if not GH.is_directed(): 
340 
GH.add_edges_from(_undirected_edges_cross_edges(G, H)) 
341 
return GH

342  
343  
344 
@not_implemented_for('directed') 
345 
@not_implemented_for('multigraph') 
346 
def power(G, k): 
347 
"""Returns the specified power of a graph.

348 

349 
The $k$th power of a simple graph $G$, denoted $G^k$, is a

350 
graph on the same set of nodes in which two distinct nodes $u$ and

351 
$v$ are adjacent in $G^k$ if and only if the shortest path

352 
distance between $u$ and $v$ in $G$ is at most $k$.

353 

354 
Parameters

355 


356 
G : graph

357 
A NetworkX simple graph object.

358 

359 
k : positive integer

360 
The power to which to raise the graph `G`.

361 

362 
Returns

363 


364 
NetworkX simple graph

365 
`G` to the power `k`.

366 

367 
Raises

368 


369 
ValueError

370 
If the exponent `k` is not positive.

371 

372 
NetworkXNotImplemented

373 
If `G` is not a simple graph.

374 

375 
Examples

376 


377 
The number of edges will never decrease when taking successive

378 
powers:

379 

380 
>>> G = nx.path_graph(4)

381 
>>> list(nx.power(G, 2).edges)

382 
[(0, 1), (0, 2), (1, 2), (1, 3), (2, 3)]

383 
>>> list(nx.power(G, 3).edges)

384 
[(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]

385 

386 
The `k`th power of a cycle graph on *n* nodes is the complete graph

387 
on *n* nodes, if `k` is at least ``n // 2``:

388 

389 
>>> G = nx.cycle_graph(5)

390 
>>> H = nx.complete_graph(5)

391 
>>> nx.is_isomorphic(nx.power(G, 2), H)

392 
True

393 
>>> G = nx.cycle_graph(8)

394 
>>> H = nx.complete_graph(8)

395 
>>> nx.is_isomorphic(nx.power(G, 4), H)

396 
True

397 

398 
References

399 


400 
.. [1] J. A. Bondy, U. S. R. Murty, *Graph Theory*. Springer, 2008.

401 

402 
Notes

403 


404 
This definition of "power graph" comes from Exercise 3.1.6 of

405 
*Graph Theory* by Bondy and Murty [1]_.

406 

407 
"""

408 
if k <= 0: 
409 
raise ValueError('k must be a positive integer') 
410 
H = nx.Graph() 
411 
H.add_nodes_from(G) 
412 
# update BFS code to ignore self loops.

413 
for n in G: 
414 
seen = {} # level (number of hops) when seen in BFS

415 
level = 1 # the current level 
416 
nextlevel = G[n] 
417 
while nextlevel:

418 
thislevel = nextlevel # advance to next level

419 
nextlevel = {} # and start a new list (fringe)

420 
for v in thislevel: 
421 
if v == n: # avoid self loop 
422 
continue

423 
if v not in seen: 
424 
seen[v] = level # set the level of vertex v

425 
nextlevel.update(G[v]) # add neighbors of v

426 
if k <= level:

427 
break

428 
level += 1

429 
H.add_edges_from((n, nbr) for nbr in seen) 
430 
return H

431  
432  
433 
@not_implemented_for('multigraph') 
434 
def rooted_product(G, H, root): 
435 
""" Return the rooted product of graphs G and H rooted at root in H.

436 

437 
A new graph is constructed representing the rooted product of

438 
the inputted graphs, G and H, with a root in H.

439 
A rooted product duplicates H for each nodes in G with the root

440 
of H corresponding to the node in G. Nodes are renamed as the direct

441 
product of G and H. The result is a subgraph of the cartesian product.

442 

443 
Parameters

444 


445 
G,H : graph

446 
A NetworkX graph

447 
root : node

448 
A node in H

449 

450 
Returns

451 


452 
R : The rooted product of G and H with a specified root in H

453 

454 
Notes

455 


456 
The nodes of R are the Cartesian Product of the nodes of G and H.

457 
The nodes of G and H are not relabeled.

458 
"""

459 
if root not in H: 
460 
raise nx.NetworkXError('root must be a vertex in H') 
461  
462 
R = nx.Graph() 
463 
R.add_nodes_from(product(G, H)) 
464  
465 
R.add_edges_from(((e[0], root), (e[1], root)) for e in G.edges()) 
466 
R.add_edges_from(((g, e[0]), (g, e[1])) for g in G for e in H.edges()) 
467  
468 
return R
