2
Operations on graphs including union, intersection, difference,
5
# Copyright (C) 2004-2010 by
6
# Aric Hagberg <hagberg@lanl.gov>
7
# Dan Schult <dschult@colgate.edu>
8
# Pieter Swart <swart@lanl.gov>
11
__author__ = """\n""".join(['Aric Hagberg (hagberg@lanl.gov)',
12
'Pieter Swart (swart@lanl.gov)',
13
'Dan Schult(dschult@colgate.edu)'])
15
__all__ = ['union', 'cartesian_product',
16
'compose', 'complement',
17
'disjoint_union', 'intersection',
18
'difference', 'symmetric_difference']
21
from networkx.utils import is_string_like
24
def union(G,H,create_using=None,rename=False,name=None):
25
""" Return the union of graphs G and H.
27
Graphs G and H must be disjoint, otherwise an exception is raised.
34
create_using : NetworkX graph
35
Use specified graph for result. Otherwise a new graph is created
36
with the same type as G.
38
rename : bool (default=False)
39
Node names of G and H can be changed be specifying the tuple
40
rename=('G-','H-') (for example). Node u in G is then renamed
41
"G-u" and v in H is renamed "H-v".
44
Specify the name for the union graph
48
To force a disjoint union with node relabeling, use
49
disjoint_union(G,H) or convert_node_labels_to integers().
51
Graph, edge, and node attributes are propagated from G and H
52
to the union graph. If a graph attribute is present in both
53
G and H the value from G is used.
62
name="union( %s, %s )"%(G.name,H.name)
63
if create_using is None:
70
# rename graph to obtain disjoint node labels
71
if rename: # create new string labels
86
G=nx.relabel_nodes(G,add_prefix0)
87
H=nx.relabel_nodes(H,add_prefix1)
90
raise nx.NetworkXError(\
91
"""The node sets of G and H are not disjoint.
92
Use appropriate rename=('Gprefix','Hprefix') or use disjoint_union(G,H).""")
93
# node names OK, now build union
96
R.add_edges_from(e for e in G.edges_iter(keys=True,data=True))
98
R.add_edges_from(e for e in G.edges_iter(data=True))
100
if H.is_multigraph():
101
R.add_edges_from(e for e in H.edges_iter(keys=True,data=True))
103
R.add_edges_from(e for e in H.edges_iter(data=True))
105
# add node attributes
106
R.node.update(G.node)
107
R.node.update(H.node)
108
# add graph attributes, G attributes take precedent over H attributes
109
R.graph.update(H.graph)
110
R.graph.update(G.graph)
114
def disjoint_union(G,H):
115
""" Return the disjoint union of graphs G and H, forcing distinct integer node labels.
124
A new graph is created, of the same class as G. It is recommended
125
that G and H be either both directed or both undirected.
128
R1=nx.convert_node_labels_to_integers(G)
129
R2=nx.convert_node_labels_to_integers(H,first_label=len(R1))
131
R.name="disjoint_union( %s, %s )"%(G.name,H.name)
135
def intersection(G,H,create_using=None ):
136
"""Return a new graph that contains only the edges that exist in both G and H.
138
The node sets of H and G must be the same.
143
A NetworkX graph. G and H must have the same node sets.
145
create_using : NetworkX graph
146
Use specified graph for result. Otherwise a new graph is created
147
with the same type as G.
151
Attributes from the graph, nodes, and edges are not copied to the new
152
graph. If you want a new graph of the intersection of G and H
153
with the attributes (including edge data) from G use remove_nodes_from()
156
>>> G=nx.path_graph(3)
157
>>> H=nx.path_graph(5)
159
>>> R.remove_nodes_from(n for n in G if n not in H)
163
if create_using is None: # Graph object of the same type as G
164
R=nx.create_empty_copy(G)
165
else: # user specified graph
169
R.name="Intersection of (%s and %s)"%(G.name, H.name)
172
raise nx.NetworkXError("Node sets of graphs are not equal")
174
if G.number_of_edges()<=H.number_of_edges():
175
if G.is_multigraph():
176
edges=G.edges_iter(keys=True)
183
if H.is_multigraph():
184
edges=H.edges_iter(keys=True)
193
def difference(G,H,create_using=None):
194
"""Return a new graph that contains the edges that exist in G
197
The node sets of H and G must be the same.
202
A NetworkX graph. G and H must have the same node sets.
204
create_using : NetworkX graph
205
Use specified graph for result. Otherwise a new graph is created
206
with the same type as G.
210
Attributes from the graph, nodes, and edges are not copied to the new
211
graph. If you want a new graph of the difference of G and H with
212
with the attributes (including edge data) from G use remove_nodes_from()
215
>>> G=nx.path_graph(3)
216
>>> H=nx.path_graph(5)
218
>>> R.remove_nodes_from(n for n in G if n in H)
222
if create_using is None: # Graph object of the same type as G
223
R=nx.create_empty_copy(G)
224
else: # user specified graph
228
R.name="Difference of (%s and %s)"%(G.name, H.name)
231
raise nx.NetworkXError("Node sets of graphs not equal")
233
if G.is_multigraph():
234
edges=G.edges_iter(keys=True)
238
if not H.has_edge(*e):
242
def symmetric_difference(G,H,create_using=None ):
243
"""Return new graph with edges that exist in either G or H but not both.
245
The node sets of H and G must be the same.
250
A NetworkX graph. G and H must have the same node sets.
252
create_using : NetworkX graph
253
Use specified graph for result. Otherwise a new graph is created
254
with the same type as G.
258
Attributes from the graph, nodes, and edges are not copied to the new
262
if create_using is None: # Graph object of the same type as G
263
R=nx.create_empty_copy(G)
264
else: # user specified graph
268
R.name="Symmetric difference of (%s and %s)"%(G.name, H.name)
271
raise nx.NetworkXError("Node sets of graphs not equal")
273
gnodes=set(G) # set of nodes in G
274
hnodes=set(H) # set of nodes in H
275
nodes=gnodes.symmetric_difference(hnodes)
276
R.add_nodes_from(nodes)
278
if G.is_multigraph():
279
edges=G.edges_iter(keys=True)
282
# we could copy the data here but then this function doesn't
283
# match intersection and difference
285
if not H.has_edge(*e):
288
if H.is_multigraph():
289
edges=H.edges_iter(keys=True)
293
if not G.has_edge(*e):
297
def cartesian_product(G,H,create_using=None):
298
""" Return the Cartesian product of G and H.
305
create_using : NetworkX graph
306
Use specified graph for result. Otherwise a new graph is created
307
with the same type as G.
311
Only tested with Graph class. Graph, node, and edge attributes
312
are not copied to the new graph.
314
if create_using is None:
324
if G.is_multigraph():
325
Prod.add_edges_from( (((v,w1),(v,w2),k,d)
327
in H.edges_iter(keys=True,data=True)
329
Prod.add_edges_from( (((v1,w),(v2,w),k,d)
331
in G.edges_iter(keys=True,data=True)
335
Prod.add_edges_from( (((v,w1),(v,w2),d)
336
for w1,w2,d in H.edges_iter(data=True)
338
Prod.add_edges_from( (((v1,w),(v2,w),d)
339
for v1,v2,d in G.edges_iter(data=True)
342
Prod.name="Cartesian Product("+G.name+","+H.name+")"
346
def compose(G,H,create_using=None, name=None):
347
""" Return a new graph of G composed with H.
349
Composition is the simple union of the node sets and edge sets.
350
The node sets of G and H need not be disjoint.
357
create_using : NetworkX graph
358
Use specified graph for result. Otherwise a new graph is created
359
with the same type as G
362
Specify name for new graph
366
A new graph is returned, of the same class as G. It is
367
recommended that G and H be either both directed or both
368
undirected. Attributes from G take precedent over attributes
373
name="compose( %s, %s )"%(G.name,H.name)
374
if create_using is None:
380
R.add_nodes_from(H.nodes())
381
R.add_nodes_from(G.nodes())
382
if H.is_multigraph():
383
R.add_edges_from(H.edges_iter(keys=True,data=True))
385
R.add_edges_from(H.edges_iter(data=True))
386
if G.is_multigraph():
387
R.add_edges_from(G.edges_iter(keys=True,data=True))
389
R.add_edges_from(G.edges_iter(data=True))
391
# add node attributes, G attributes take precedent over H attributes
392
R.node.update(H.node)
393
R.node.update(G.node)
394
# add graph attributes, G attributes take precedent over H attributes
395
R.graph.update(H.graph)
396
R.graph.update(G.graph)
401
def complement(G,create_using=None,name=None):
402
""" Return graph complement of G.
409
create_using : NetworkX graph
410
Use specified graph for result. Otherwise a new graph is created.
413
Specify name for new graph
417
Note that complement() does not create self-loops and also
418
does not produce parallel edges for MultiGraphs.
420
Graph, node, and edge data are not propagated to the new graph.
423
name="complement(%s)"%(G.name)
424
if create_using is None:
431
R.add_edges_from( ((n,n2)
432
for n,nbrs in G.adjacency_iter()
433
for n2 in G if n2 not in nbrs
added
removed
networkx/algorithms/operators.py
