Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / 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 multi-graph if either G
152
     or H is a multi-graph, 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 two-tuple 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 multi-graph if either G
204
     or H is a multi-graph. 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 two-tuple 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 multi-graph if either G
254
     or H is a multi-graph. 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 two-tuple 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 multi-graph if either G
308
     or H is a multi-graph. 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 two-tuple 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