Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

# Source code for networkx.algorithms.operators.binary

"""
Operations on graphs including union, intersection, difference.
"""
#    Aric Hagberg <hagberg@lanl.gov>
#    Dan Schult <dschult@colgate.edu>
#    Pieter Swart <swart@lanl.gov>
import networkx as nx
from networkx.utils import is_string_like
__author__ = """\n""".join(['Aric Hagberg <aric.hagberg@gmail.com>',
'Pieter Swart (swart@lanl.gov)',
'Dan Schult(dschult@colgate.edu)'])
__all__ = ['union', 'compose', 'disjoint_union', 'intersection',
'difference', 'symmetric_difference']

[docs]def union(G, H, rename=(None, None), name=None):
""" Return the union of graphs G and H.

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

Parameters
----------
G,H : graph
A NetworkX graph

create_using : NetworkX graph
Use specified graph for result.  Otherwise

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

name : string
Specify the name for the union graph

Returns
-------
U : A union graph with the same type as G.

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

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

--------
disjoint_union
"""
if not G.is_multigraph() == H.is_multigraph():
raise nx.NetworkXError('G and H must both be graphs or multigraphs.')
# Union is the same type as G
R = G.__class__()
if name is None:
name = "union( %s, %s )" % (G.name, H.name)
R.name = name

# rename graph to obtain disjoint node labels
if prefix is None:
return graph

def label(x):
if is_string_like(x):
name = prefix + x
else:
name = prefix + repr(x)
return name
return nx.relabel_nodes(graph, label)
if set(G) & set(H):
raise nx.NetworkXError('The node sets of G and H are not disjoint.',
'Use appropriate rename=(Gprefix,Hprefix)'
'or use disjoint_union(G,H).')
if G.is_multigraph():
G_edges = G.edges_iter(keys=True, data=True)
else:
G_edges = G.edges_iter(data=True)
if H.is_multigraph():
H_edges = H.edges_iter(keys=True, data=True)
else:
H_edges = H.edges_iter(data=True)

R.node.update(G.node)
R.node.update(H.node)
# add graph attributes, H attributes take precedent over G attributes
R.graph.update(G.graph)
R.graph.update(H.graph)

return R

[docs]def disjoint_union(G, H):
""" Return the disjoint union of graphs G and H.

This algorithm forces distinct integer node labels.

Parameters
----------
G,H : graph
A NetworkX graph

Returns
-------
U : A union graph with the same type as G.

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

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

Graph, edge, and node attributes are propagated from G and H
to the union graph.  If a graph attribute is present in both
G and H the value from H is used.
"""
R1 = nx.convert_node_labels_to_integers(G)
R2 = nx.convert_node_labels_to_integers(H, first_label=len(R1))
R = union(R1, R2)
R.name = "disjoint_union( %s, %s )" % (G.name, H.name)
R.graph.update(G.graph)
R.graph.update(H.graph)
return R

[docs]def intersection(G, H):
"""Return a new graph that contains only the edges that exist in
both G and H.

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

Parameters
----------
G,H : graph
A NetworkX graph.  G and H must have the same node sets.

Returns
-------
GH : A new graph with the same type as G.

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

>>> G=nx.path_graph(3)
>>> H=nx.path_graph(5)
>>> R=G.copy()
>>> R.remove_nodes_from(n for n in G if n not in H)
"""
# create new graph
R = nx.create_empty_copy(G)

R.name = "Intersection of (%s and %s)" % (G.name, H.name)
if not G.is_multigraph() == H.is_multigraph():
raise nx.NetworkXError('G and H must both be graphs or multigraphs.')
if set(G) != set(H):
raise nx.NetworkXError("Node sets of graphs are not equal")

if G.number_of_edges() <= H.number_of_edges():
if G.is_multigraph():
edges = G.edges_iter(keys=True)
else:
edges = G.edges_iter()
for e in edges:
if H.has_edge(*e):
else:
if H.is_multigraph():
edges = H.edges_iter(keys=True)
else:
edges = H.edges_iter()
for e in edges:
if G.has_edge(*e):

return R

[docs]def difference(G, H):
"""Return a new graph that contains the edges that exist in G but not in H.

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

Parameters
----------
G,H : graph
A NetworkX graph.  G and H must have the same node sets.

Returns
-------
D : A new graph with the same type as G.

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

>>> G = nx.path_graph(3)
>>> H = nx.path_graph(5)
>>> R = G.copy()
>>> R.remove_nodes_from(n for n in G if n in H)
"""
# create new graph
if not G.is_multigraph() == H.is_multigraph():
raise nx.NetworkXError('G and H must both be graphs or multigraphs.')
R = nx.create_empty_copy(G)
R.name = "Difference of (%s and %s)" % (G.name, H.name)

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

if G.is_multigraph():
edges = G.edges_iter(keys=True)
else:
edges = G.edges_iter()
for e in edges:
if not H.has_edge(*e):
return R

[docs]def symmetric_difference(G, H):
"""Return new graph with edges that exist in either G or H but not both.

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

Parameters
----------
G,H : graph
A NetworkX graph.  G and H must have the same node sets.

Returns
-------
D : A new graph with the same type as G.

Notes
-----
Attributes from the graph, nodes, and edges are not copied to the new
graph.
"""
# create new graph
if not G.is_multigraph() == H.is_multigraph():
raise nx.NetworkXError('G and H must both be graphs or multigraphs.')
R = nx.create_empty_copy(G)
R.name = "Symmetric difference of (%s and %s)" % (G.name, H.name)

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

gnodes = set(G)  # set of nodes in G
hnodes = set(H)  # set of nodes in H
nodes = gnodes.symmetric_difference(hnodes)

if G.is_multigraph():
edges = G.edges_iter(keys=True)
else:
edges = G.edges_iter()
# we could copy the data here but then this function doesn't
# match intersection and difference
for e in edges:
if not H.has_edge(*e):

if H.is_multigraph():
edges = H.edges_iter(keys=True)
else:
edges = H.edges_iter()
for e in edges:
if not G.has_edge(*e):
return R

[docs]def compose(G, H, name=None):
"""Return a new graph of G composed with H.

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

Parameters
----------
G,H : graph
A NetworkX graph

name : string
Specify name for new graph

Returns
-------
C: A new graph  with the same type as G

Notes
-----
It is recommended that G and H be either both directed or both undirected.
Attributes from H take precedent over attributes from G.
"""
if not G.is_multigraph() == H.is_multigraph():
raise nx.NetworkXError('G and H must both be graphs or multigraphs.')

if name is None:
name = "compose( %s, %s )" % (G.name, H.name)
R = G.__class__()
R.name = name
if G.is_multigraph():
else: