Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / operators / binary.py @ 5cef0f13

History | View | Annotate | Download (11.1 KB)

1
"""
2
Operations on graphs including union, intersection, difference.
3
"""
4
#    Copyright (C) 2004-2019 by
5
#    Aric Hagberg <hagberg@lanl.gov>
6
#    Dan Schult <dschult@colgate.edu>
7
#    Pieter Swart <swart@lanl.gov>
8
#    All rights reserved.
9
#    BSD license.
10
import networkx as nx
11
from networkx.utils import is_string_like
12
__author__ = """\n""".join(['Aric Hagberg <aric.hagberg@gmail.com>',
13
                            'Pieter Swart (swart@lanl.gov)',
14
                            'Dan Schult(dschult@colgate.edu)'])
15
__all__ = ['union', 'compose', 'disjoint_union', 'intersection',
16
           'difference', 'symmetric_difference', 'full_join']
17

    
18

    
19
def union(G, H, rename=(None, None), name=None):
20
    """ Return the union of graphs G and H.
21

22
    Graphs G and H must be disjoint, otherwise an exception is raised.
23

24
    Parameters
25
    ----------
26
    G,H : graph
27
       A NetworkX graph
28

29
    rename : bool , default=(None, None)
30
       Node names of G and H can be changed by specifying the tuple
31
       rename=('G-','H-') (for example).  Node "u" in G is then renamed
32
       "G-u" and "v" in H is renamed "H-v".
33

34
    name : string
35
       Specify the name for the union graph
36

37
    Returns
38
    -------
39
    U : A union graph with the same type as G.
40

41
    Notes
42
    -----
43
    To force a disjoint union with node relabeling, use
44
    disjoint_union(G,H) or convert_node_labels_to integers().
45

46
    Graph, edge, and node attributes are propagated from G and H
47
    to the union graph.  If a graph attribute is present in both
48
    G and H the value from H is used.
49

50
    See Also
51
    --------
52
    disjoint_union
53
    """
54
    if not G.is_multigraph() == H.is_multigraph():
55
        raise nx.NetworkXError('G and H must both be graphs or multigraphs.')
56
    # Union is the same type as G
57
    R = G.__class__()
58
    # add graph attributes, H attributes take precedent over G attributes
59
    R.graph.update(G.graph)
60
    R.graph.update(H.graph)
61

    
62
    # rename graph to obtain disjoint node labels
63
    def add_prefix(graph, prefix):
64
        if prefix is None:
65
            return graph
66

    
67
        def label(x):
68
            if is_string_like(x):
69
                name = prefix + x
70
            else:
71
                name = prefix + repr(x)
72
            return name
73
        return nx.relabel_nodes(graph, label)
74
    G = add_prefix(G, rename[0])
75
    H = add_prefix(H, rename[1])
76
    if set(G) & set(H):
77
        raise nx.NetworkXError('The node sets of G and H are not disjoint.',
78
                               'Use appropriate rename=(Gprefix,Hprefix)'
79
                               'or use disjoint_union(G,H).')
80
    if G.is_multigraph():
81
        G_edges = G.edges(keys=True, data=True)
82
    else:
83
        G_edges = G.edges(data=True)
84
    if H.is_multigraph():
85
        H_edges = H.edges(keys=True, data=True)
86
    else:
87
        H_edges = H.edges(data=True)
88

    
89
    # add nodes
90
    R.add_nodes_from(G)
91
    R.add_edges_from(G_edges)
92
    # add edges
93
    R.add_nodes_from(H)
94
    R.add_edges_from(H_edges)
95
    # add node attributes
96
    for n in G:
97
        R.nodes[n].update(G.nodes[n])
98
    for n in H:
99
        R.nodes[n].update(H.nodes[n])
100

    
101
    return R
102

    
103

    
104
def disjoint_union(G, H):
105
    """ Return the disjoint union of graphs G and H.
106

107
    This algorithm forces distinct integer node labels.
108

109
    Parameters
110
    ----------
111
    G,H : graph
112
       A NetworkX graph
113

114
    Returns
115
    -------
116
    U : A union graph with the same type as G.
117

118
    Notes
119
    -----
120
    A new graph is created, of the same class as G.  It is recommended
121
    that G and H be either both directed or both undirected.
122

123
    The nodes of G are relabeled 0 to len(G)-1, and the nodes of H are
124
    relabeled len(G) to len(G)+len(H)-1.
125

126
    Graph, edge, and node attributes are propagated from G and H
127
    to the union graph.  If a graph attribute is present in both
128
    G and H the value from H is used.
129
    """
130
    R1 = nx.convert_node_labels_to_integers(G)
131
    R2 = nx.convert_node_labels_to_integers(H, first_label=len(R1))
132
    R = union(R1, R2)
133
    R.graph.update(G.graph)
134
    R.graph.update(H.graph)
135
    return R
136

    
137

    
138
def intersection(G, H):
139
    """Returns a new graph that contains only the edges that exist in
140
    both G and H.
141

142
    The node sets of H and G must be the same.
143

144
    Parameters
145
    ----------
146
    G,H : graph
147
       A NetworkX graph.  G and H must have the same node sets.
148

149
    Returns
150
    -------
151
    GH : A new graph with the same type as G.
152

153
    Notes
154
    -----
155
    Attributes from the graph, nodes, and edges are not copied to the new
156
    graph.  If you want a new graph of the intersection of G and H
157
    with the attributes (including edge data) from G use remove_nodes_from()
158
    as follows
159

160
    >>> G=nx.path_graph(3)
161
    >>> H=nx.path_graph(5)
162
    >>> R=G.copy()
163
    >>> R.remove_nodes_from(n for n in G if n not in H)
164
    """
165
    # create new graph
166
    R = nx.create_empty_copy(G)
167

    
168
    if not G.is_multigraph() == H.is_multigraph():
169
        raise nx.NetworkXError('G and H must both be graphs or multigraphs.')
170
    if set(G) != set(H):
171
        raise nx.NetworkXError("Node sets of graphs are not equal")
172

    
173
    if G.number_of_edges() <= H.number_of_edges():
174
        if G.is_multigraph():
175
            edges = G.edges(keys=True)
176
        else:
177
            edges = G.edges()
178
        for e in edges:
179
            if H.has_edge(*e):
180
                R.add_edge(*e)
181
    else:
182
        if H.is_multigraph():
183
            edges = H.edges(keys=True)
184
        else:
185
            edges = H.edges()
186
        for e in edges:
187
            if G.has_edge(*e):
188
                R.add_edge(*e)
189
    return R
190

    
191

    
192
def difference(G, H):
193
    """Returns a new graph that contains the edges that exist in G but not in H.
194

195
    The node sets of H and G must be the same.
196

197
    Parameters
198
    ----------
199
    G,H : graph
200
       A NetworkX graph.  G and H must have the same node sets.
201

202
    Returns
203
    -------
204
    D : A new graph with the same type as G.
205

206
    Notes
207
    -----
208
    Attributes from the graph, nodes, and edges are not copied to the new
209
    graph.  If you want a new graph of the difference of G and H with
210
    with the attributes (including edge data) from G use remove_nodes_from()
211
    as follows:
212

213
    >>> G = nx.path_graph(3)
214
    >>> H = nx.path_graph(5)
215
    >>> R = G.copy()
216
    >>> R.remove_nodes_from(n for n in G if n in H)
217
    """
218
    # create new graph
219
    if not G.is_multigraph() == H.is_multigraph():
220
        raise nx.NetworkXError('G and H must both be graphs or multigraphs.')
221
    R = nx.create_empty_copy(G)
222

    
223
    if set(G) != set(H):
224
        raise nx.NetworkXError("Node sets of graphs not equal")
225

    
226
    if G.is_multigraph():
227
        edges = G.edges(keys=True)
228
    else:
229
        edges = G.edges()
230
    for e in edges:
231
        if not H.has_edge(*e):
232
            R.add_edge(*e)
233
    return R
234

    
235

    
236
def symmetric_difference(G, H):
237
    """Returns new graph with edges that exist in either G or H but not both.
238

239
    The node sets of H and G must be the same.
240

241
    Parameters
242
    ----------
243
    G,H : graph
244
       A NetworkX graph.  G and H must have the same node sets.
245

246
    Returns
247
    -------
248
    D : A new graph with the same type as G.
249

250
    Notes
251
    -----
252
    Attributes from the graph, nodes, and edges are not copied to the new
253
    graph.
254
    """
255
    # create new graph
256
    if not G.is_multigraph() == H.is_multigraph():
257
        raise nx.NetworkXError('G and H must both be graphs or multigraphs.')
258
    R = nx.create_empty_copy(G)
259

    
260
    if set(G) != set(H):
261
        raise nx.NetworkXError("Node sets of graphs not equal")
262

    
263
    gnodes = set(G)  # set of nodes in G
264
    hnodes = set(H)  # set of nodes in H
265
    nodes = gnodes.symmetric_difference(hnodes)
266
    R.add_nodes_from(nodes)
267

    
268
    if G.is_multigraph():
269
        edges = G.edges(keys=True)
270
    else:
271
        edges = G.edges()
272
    # we could copy the data here but then this function doesn't
273
    # match intersection and difference
274
    for e in edges:
275
        if not H.has_edge(*e):
276
            R.add_edge(*e)
277

    
278
    if H.is_multigraph():
279
        edges = H.edges(keys=True)
280
    else:
281
        edges = H.edges()
282
    for e in edges:
283
        if not G.has_edge(*e):
284
            R.add_edge(*e)
285
    return R
286

    
287

    
288
def compose(G, H):
289
    """Returns a new graph of G composed with H.
290

291
    Composition is the simple union of the node sets and edge sets.
292
    The node sets of G and H do not need to be disjoint.
293

294
    Parameters
295
    ----------
296
    G, H : graph
297
       A NetworkX graph
298

299
    Returns
300
    -------
301
    C: A new graph  with the same type as G
302

303
    Notes
304
    -----
305
    It is recommended that G and H be either both directed or both undirected.
306
    Attributes from H take precedent over attributes from G.
307

308
    For MultiGraphs, the edges are identified by incident nodes AND edge-key.
309
    This can cause surprises (i.e., edge `(1, 2)` may or may not be the same
310
    in two graphs) if you use MultiGraph without keeping track of edge keys.
311
    """
312
    if not G.is_multigraph() == H.is_multigraph():
313
        raise nx.NetworkXError('G and H must both be graphs or multigraphs.')
314

    
315
    R = G.__class__()
316
    # add graph attributes, H attributes take precedent over G attributes
317
    R.graph.update(G.graph)
318
    R.graph.update(H.graph)
319

    
320
    R.add_nodes_from(G.nodes(data=True))
321
    R.add_nodes_from(H.nodes(data=True))
322

    
323
    if G.is_multigraph():
324
        R.add_edges_from(G.edges(keys=True, data=True))
325
    else:
326
        R.add_edges_from(G.edges(data=True))
327
    if H.is_multigraph():
328
        R.add_edges_from(H.edges(keys=True, data=True))
329
    else:
330
        R.add_edges_from(H.edges(data=True))
331
    return R
332

    
333

    
334
def full_join(G, H, rename=(None, None)):
335
    """Returns the full join of graphs G and H.
336

337
    Full join is the union of G and H in which all edges between
338
    G and H are added.
339
    The node sets of G and H must be disjoint,
340
    otherwise an exception is raised.
341

342
    Parameters
343
    ----------
344
    G, H : graph
345
       A NetworkX graph
346

347
    rename : bool , default=(None, None)
348
       Node names of G and H can be changed by specifying the tuple
349
       rename=('G-','H-') (for example).  Node "u" in G is then renamed
350
       "G-u" and "v" in H is renamed "H-v".
351

352
    Returns
353
    -------
354
    U : The full join graph with the same type as G.
355

356
    Notes
357
    -----
358
    It is recommended that G and H be either both directed or both undirected.
359

360
    If G is directed, then edges from G to H are added as well as from H to G.
361

362
    Note that full_join() does not produce parallel edges for MultiGraphs.
363

364
    The full join operation of graphs G and H is the same as getting
365
    their complement, performing a disjoint union, and finally getting
366
    the complement of the resulting graph.
367

368
    Graph, edge, and node attributes are propagated from G and H
369
    to the union graph.  If a graph attribute is present in both
370
    G and H the value from H is used.
371

372
    See Also
373
    --------
374
    union
375
    disjoint_union
376
    """
377
    R = union(G, H, rename)
378

    
379
    def add_prefix(graph, prefix):
380
        if prefix is None:
381
            return graph
382

    
383
        def label(x):
384
            if is_string_like(x):
385
                name = prefix + x
386
            else:
387
                name = prefix + repr(x)
388
            return name
389
        return nx.relabel_nodes(graph, label)
390
    G = add_prefix(G, rename[0])
391
    H = add_prefix(H, rename[1])
392

    
393
    for i in G:
394
        for j in H:
395
            R.add_edge(i, j)
396
    if R.is_directed():
397
        for i in H:
398
            for j in G:
399
                R.add_edge(i, j)
400

    
401
    return R