5
5
__author__ = """Aric Hagberg (hagberg@lanl.gov)\nPieter Swart (swart@lanl.gov)\nDan Schult(dschult@colgate.edu)"""
6
__date__ = "$Date: 2007-07-18 15:23:23 -0600 (Wed, 18 Jul 2007) $"
8
__revision__ = "$Revision: 1024 $"
9
# Copyright (C) 2004-2006 by
6
# Copyright (C) 2004-2008 by
10
7
# Aric Hagberg <hagberg@lanl.gov>
11
8
# Dan Schult <dschult@colgate.edu>
12
9
# Pieter Swart <swart@lanl.gov>
13
10
# Distributed under the terms of the GNU Lesser General Public License
14
11
# http://www.gnu.org/copyleft/lesser.html
13
__all__ = ['union', 'cartesian_product', 'compose', 'complement',
14
'disjoint_union', 'create_empty_copy', 'subgraph',
15
'convert_node_labels_to_integers', 'relabel_nodes']
17
18
from networkx.utils import is_string_like
19
def subgraph(G, nbunch, inplace=False, create_using=None):
20
def subgraph(G, nbunch, copy=True):
21
22
Return the subgraph induced on nodes in nbunch.
25
26
of nodes. (It can be an iterable or an iterator, e.g. a list,
26
27
set, graph, file, numeric array, etc.)
28
Setting inplace=True will return the induced subgraph in the
29
Setting copy=False will return the induced subgraph in the
29
30
original graph by deleting nodes not in nbunch. This overrides
30
31
create_using. Warning: this can destroy the graph.
32
Unless otherwise specified, return a new graph of the same
33
type as self. Use (optional) create_using=R to return the
34
resulting subgraph in R. R can be an existing graph-like
35
object (to be emptied) or R is a call to a graph object,
36
e.g. create_using=DiGraph(). See documentation for
39
Implemented for Graph, DiGraph, XGraph, XDiGraph
41
33
Note: subgraph(G) calls G.subgraph()
44
H = G.subgraph(nbunch, inplace, create_using)
36
return G.subgraph(nbunch, copy)
47
38
def union(G,H,create_using=None,rename=False,name=None):
48
39
""" Return the union of graphs G and H.
62
53
both directed or both undirected.
64
55
A new name can be specified in the form
65
X=graph_union(G,H,name="new_name")
56
X=union(G,H,name="new_name")
67
58
Implemented for Graph, DiGraph, XGraph, XDiGraph.
80
71
# note that for objects w/o succinct __name__,
81
72
# the new labels can be quite verbose
82
73
# See also disjoint_union
85
74
if rename: # create new string labels
87
78
if is_string_like(v):
88
Gname.setdefault(v,rename[0]+v)
90
Gname.setdefault(v,rename[0]+repr(v))
81
Gname[v]=rename[0]+repr(v)
92
83
if is_string_like(v):
93
Hname.setdefault(v,rename[1]+v)
95
Hname.setdefault(v,rename[1]+repr(v))
86
Hname[v]=rename[1]+repr(v)
100
Hname.setdefault(v,v)
88
Gname=dict( ((v,v) for v in G) )
89
Hname=dict( ((v,v) for v in H) )
103
for n in Gname.values():
104
if n in Hname.values():
92
Hnames=set(Hname.values())
93
Gnames=set(Gname.values())
105
95
raise networkx.NetworkXError,\
106
96
"node sets of G and H are not disjoint. Use appropriate rename=('Gprefix','Hprefix')"
107
97
# node names OK, now build union
110
G_edges=G.edges_iter()
114
R.add_edge(Gname[u],Gname[v])
117
R.add_edge(Gname[u],Gname[v],x)
120
H_edges=H.edges_iter()
124
R.add_edge(Hname[u],Hname[v])
127
R.add_edge(Hname[u],Hname[v],x)
98
R.add_nodes_from(Gnames)
99
R.add_edges_from( ( (Gname[u],Gname[v],x) for u,v,x in G.edges_iter(data=True) ))
100
R.add_nodes_from(Hnames)
101
R.add_edges_from( ( (Hname[u],Hname[v],x) for u,v,x in H.edges_iter(data=True) ))
161
135
Prod.add_node((v,w))
163
H_edges=H.edges_iter()
164
for (w1,w2) in H_edges:
166
Prod.add_edge((v,w1),(v,w2))
168
G_edges=G.edges_iter()
169
for (v1,v2) in G_edges:
171
Prod.add_edge((v1,w),(v2,w))
137
Prod.add_edges_from( (((v,w1),(v,w2),d) for w1,w2,d in H.edges_iter(data=True) for v in G) )
138
Prod.add_edges_from( (((v1,w),(v2,w),d) for v1,v2,d in G.edges_iter(data=True) for w in H) )
173
140
Prod.name="Cartesian Product("+G.name+","+H.name+")"
177
144
def compose(G,H,create_using=None, name=None):
178
145
""" Return a new graph of G composed with H.
147
Composition is the simple union of the node sets and edge sets.
180
148
The node sets of G and H need not be disjoint.
182
150
A new graph is returned, of the same class as G.
195
163
name="compose( %s, %s )"%(G.name,H.name)
196
164
if create_using is None:
197
R=create_empty_copy(G,with_nodes=False)
202
R.add_nodes_from([v for v in G.nodes() ])
203
R.add_edges_from(G.edges())
204
R.add_nodes_from([v for v in H.nodes() ])
205
R.add_edges_from(H.edges())
171
R.add_edges_from(G.edges_iter(data=True))
173
R.add_edges_from(H.edges_iter(data=True))
215
183
emptied) or R can be a call to a graph object,
216
184
e.g. create_using=DiGraph(). See documentation for empty_graph()
218
Implemented for Graph, DiGraph, XGraph, XDiGraph.
219
Note that complement() is not well-defined for XGraph and XDiGraph
220
objects that allow multiple edges or self-loops.
186
Note that complement() does not create self-loops and also
187
does not produce parallel edges for MultiGraphs.
224
191
name="complement(%s)"%(G.name)
225
192
if create_using is None:
226
R=create_empty_copy(G,with_nodes=False)
231
R.add_nodes_from([v for v in G.nodes() ])
234
if not G.has_edge(v,u):
199
R.add_edges_from( ((n,n2) for n,nbrs in G.adjacency_iter() for n2 in G
200
if n2 not in nbrs if n is not n2) )
254
216
def convert_to_undirected(G):
255
217
"""Return a new undirected representation of the graph G.
257
Works for Graph, DiGraph, XGraph, XDiGraph.
219
Works for Graph, DiGraph, MultiGraph, MultiDiGraph.
259
221
Note: convert_to_undirected(G)=G.to_undirected()
265
227
def convert_to_directed(G):
266
228
"""Return a new directed representation of the graph G.
268
Works for Graph, DiGraph, XGraph, XDiGraph.
230
Works for Graph, DiGraph, MultiGraph, MultiDiGraph.
270
232
Note: convert_to_directed(G)=G.to_directed()
273
235
return G.to_directed()
275
238
def relabel_nodes(G,mapping):
276
239
"""Return a copy of G with node labels transformed by mapping.
284
247
mapping as dictionary:
286
>>> G=path_graph(3) # nodes 0-1-2
252
>>> G=nx.path_graph(3) # nodes 0-1-2
287
253
>>> mapping={0:'a',1:'b',2:'c'}
288
>>> H=relabel_nodes(G,mapping)
254
>>> H=nx.relabel_nodes(G,mapping)
289
255
>>> print H.nodes()
292
>>> G=path_graph(26) # nodes 0..25
258
>>> G=nx.path_graph(26) # nodes 0..25
293
259
>>> mapping=dict(zip(G.nodes(),"abcdefghijklmnopqrstuvwxyz"))
294
>>> H=relabel_nodes(G,mapping) # nodes a..z
260
>>> H=nx.relabel_nodes(G,mapping) # nodes a..z
295
261
>>> mapping=dict(zip(G.nodes(),xrange(1,27)))
296
>>> G1=relabel_nodes(G,mapping) # nodes 1..26
262
>>> G1=nx.relabel_nodes(G,mapping) # nodes 1..26
298
264
mapping as function
266
>>> G=nx.path_graph(3)
301
267
>>> def mapping(x):
303
>>> H=relabel_nodes(G,mapping)
269
>>> H=nx.relabel_nodes(G,mapping)
304
270
>>> print H.nodes()
307
273
Also see convert_node_labels_to_integers.
310
H=create_empty_copy(G,with_nodes=False)
311
277
H.name="(%s)" % G.name
313
279
if hasattr(mapping,"__getitem__"): # if we are a dict
322
288
raise networkx.NetworkXError,\
323
289
"relabeling function cannot be applied to node %s" % node
325
for e in G.edges_iter():
291
#for n1,n2,d in G.edges_iter(data=True):
295
H.add_edges_from( (map_func(n1),map_func(n2),d) for (n1,n2,d) in G.edges_iter(data=True))
393
357
mapping=dict(zip(nlist,range(first_label,N)))
394
358
elif ordering=="increasing degree":
395
dv_pairs=[(G.degree(n),n) for n in G]
359
dv_pairs=[(d,n) for (n,d) in G.degree_iter()]
396
360
dv_pairs.sort() # in-place sort from lowest to highest degree
397
361
mapping=dict(zip([n for d,n in dv_pairs],range(first_label,N)))
398
362
elif ordering=="decreasing degree":
399
dv_pairs=[(G.degree(n),n) for n in G]
363
dv_pairs=[(d,n) for (n,d) in G.degree_iter()]
400
364
dv_pairs.sort() # in-place sort from lowest to highest degree
401
365
dv_pairs.reverse()
402
366
mapping=dict(zip([n for d,n in dv_pairs],range(first_label,N)))
410
374
if not discard_old_labels:
411
375
H.node_labels=mapping
417
suite = doctest.DocFileSuite('tests/operators.txt',package='networkx')
420
if __name__ == "__main__":
424
if sys.version_info[:2] < (2, 4):
425
print "Python version 2.4 or later required for tests (%d.%d detected)." % sys.version_info[:2]
427
# directory of networkx package (relative to this)
428
nxbase=sys.path[0]+os.sep+os.pardir
429
sys.path.insert(0,nxbase) # prepend to search path
430
unittest.TextTestRunner().run(_test_suite())
added
removed
networkx/operators.py
