1 """
2 Operations on graphs; including union, complement, subgraph.
3
4 """
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) $"
7 __credits__ = """"""
8 __revision__ = "$Revision: 1024 $"
9
10
11
12
13
14
15
16 import networkx
17 from networkx.utils import is_string_like
18
19 -def subgraph(G, nbunch, inplace=False, create_using=None):
20 """
21 Return the subgraph induced on nodes in nbunch.
22
23 nbunch: can be a singleton node, a string (which is treated
24 as a singleton node), or any iterable container of
25 of nodes. (It can be an iterable or an iterator, e.g. a list,
26 set, graph, file, numeric array, etc.)
27
28 Setting inplace=True will return the induced subgraph in the
29 original graph by deleting nodes not in nbunch. This overrides
30 create_using. Warning: this can destroy the graph.
31
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
37 empty_graph.
38
39 Implemented for Graph, DiGraph, XGraph, XDiGraph
40
41 Note: subgraph(G) calls G.subgraph()
42
43 """
44 H = G.subgraph(nbunch, inplace, create_using)
45 return H
46
47 -def union(G,H,create_using=None,rename=False,name=None):
48 """ Return the union of graphs G and H.
49
50 Graphs G and H must be disjoint, otherwise an exception is raised.
51
52 Node names of G and H can be changed be specifying the tuple
53 rename=('G-','H-') (for example).
54 Node u in G is then renamed "G-u" and v in H is renamed "H-v".
55
56 To force a disjoint union with node relabeling, use
57 disjoint_union(G,H) or convert_node_labels_to integers().
58
59 Optional create_using=R returns graph R filled in with the
60 union of G and H. Otherwise a new graph is created, of the
61 same class as G. It is recommended that G and H be either
62 both directed or both undirected.
63
64 A new name can be specified in the form
65 X=graph_union(G,H,name="new_name")
66
67 Implemented for Graph, DiGraph, XGraph, XDiGraph.
68
69 """
70 if name is None:
71 name="union( %s, %s )"%(G.name,H.name)
72 if create_using is None:
73 R=create_empty_copy(G,with_nodes=False)
74 else:
75 R=create_using
76 R.clear()
77 R.name=name
78
79
80
81
82
83 Gname={}
84 Hname={}
85 if rename:
86 for v in G:
87 if is_string_like(v):
88 Gname.setdefault(v,rename[0]+v)
89 else:
90 Gname.setdefault(v,rename[0]+repr(v))
91 for v in H:
92 if is_string_like(v):
93 Hname.setdefault(v,rename[1]+v)
94 else:
95 Hname.setdefault(v,rename[1]+repr(v))
96 else:
97 for v in G:
98 Gname.setdefault(v,v)
99 for v in H:
100 Hname.setdefault(v,v)
101
102
103 for n in Gname.values():
104 if n in Hname.values():
105 raise networkx.NetworkXError,\
106 "node sets of G and H are not disjoint. Use appropriate rename=('Gprefix','Hprefix')"
107
108 for v in G:
109 R.add_node(Gname[v])
110 G_edges=G.edges_iter()
111 for e in G_edges:
112 if len(e)==2:
113 u,v=e
114 R.add_edge(Gname[u],Gname[v])
115 else:
116 u,v,x=e
117 R.add_edge(Gname[u],Gname[v],x)
118 for v in H:
119 R.add_node(Hname[v])
120 H_edges=H.edges_iter()
121 for e in H_edges:
122 if len(e)==2:
123 u,v=e
124 R.add_edge(Hname[u],Hname[v])
125 else:
126 u,v,x=e
127 R.add_edge(Hname[u],Hname[v],x)
128 return R
129
130
132 """ Return the disjoint union of graphs G and H, forcing distinct integer
133 node labels.
134
135 A new graph is created, of the same class as G.
136 It is recommended that G and H be either both directed or both
137 undirected.
138
139 Implemented for Graph, DiGraph, XGraph, XDiGraph.
140
141 """
142
143 R1=convert_node_labels_to_integers(G)
144 R2=convert_node_labels_to_integers(H,first_label=networkx.number_of_nodes(R1))
145 R=union(R1,R2)
146 R.name="disjoint_union( %s, %s )"%(G.name,H.name)
147 return R
148
149
151 """ Return the Cartesian product of G and H.
152
153 Tested only on Graph class.
154
155 """
156
157 Prod=networkx.Graph()
158
159 for v in G:
160 for w in H:
161 Prod.add_node((v,w))
162
163 H_edges=H.edges_iter()
164 for (w1,w2) in H_edges:
165 for v in G:
166 Prod.add_edge((v,w1),(v,w2))
167
168 G_edges=G.edges_iter()
169 for (v1,v2) in G_edges:
170 for w in H:
171 Prod.add_edge((v1,w),(v2,w))
172
173 Prod.name="Cartesian Product("+G.name+","+H.name+")"
174 return Prod
175
176
177 -def compose(G,H,create_using=None, name=None):
178 """ Return a new graph of G composed with H.
179
180 The node sets of G and H need not be disjoint.
181
182 A new graph is returned, of the same class as G.
183 It is recommended that G and H be either both directed or both
184 undirected.
185
186 Optional create_using=R returns graph R filled in with the
187 compose(G,H). Otherwise a new graph is created, of the
188 same class as G. It is recommended that G and H be either
189 both directed or both undirected.
190
191 Implemented for Graph, DiGraph, XGraph, XDiGraph
192
193 """
194 if name is None:
195 name="compose( %s, %s )"%(G.name,H.name)
196 if create_using is None:
197 R=create_empty_copy(G,with_nodes=False)
198 else:
199 R=create_using
200 R.clear()
201 R.name=name
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())
206 return R
207
208
210 """ Return graph complement of G.
211
212 Unless otherwise specified, return a new graph of the same type as
213 self. Use (optional) create_using=R to return the resulting
214 subgraph in R. R can be an existing graph-like object (to be
215 emptied) or R can be a call to a graph object,
216 e.g. create_using=DiGraph(). See documentation for empty_graph()
217
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.
221
222 """
223 if name is None:
224 name="complement(%s)"%(G.name)
225 if create_using is None:
226 R=create_empty_copy(G,with_nodes=False)
227 else:
228 R=create_using
229 R.clear()
230 R.name=name
231 R.add_nodes_from([v for v in G.nodes() ])
232 for v in G.nodes():
233 for u in G.nodes():
234 if not G.has_edge(v,u):
235 R.add_edge(v,u)
236 return R
237
238
240 """Return a copy of the graph G with all of the edges removed.
241
242 """
243 if hasattr(G,'allow_multiedges')==True:
244 H=G.__class__(multiedges=G.multiedges,selfloops=G.selfloops)
245 else:
246 H=G.__class__()
247
248 H.name='empty '+G.name
249 if with_nodes:
250 H.add_nodes_from(G)
251 return H
252
253
255 """Return a new undirected representation of the graph G.
256
257 Works for Graph, DiGraph, XGraph, XDiGraph.
258
259 Note: convert_to_undirected(G)=G.to_undirected()
260
261 """
262 return G.to_undirected()
263
264
266 """Return a new directed representation of the graph G.
267
268 Works for Graph, DiGraph, XGraph, XDiGraph.
269
270 Note: convert_to_directed(G)=G.to_directed()
271
272 """
273 return G.to_directed()
274
276 """Return a copy of G with node labels transformed by mapping.
277
278 mapping is either
279 - a dictionary with the old labels as keys and new labels as values
280 - a function transforming an old label with a new label
281
282 In either case, the new labels must be hashable Python objects.
283
284 mapping as dictionary:
285
286 >>> G=path_graph(3) # nodes 0-1-2
287 >>> mapping={0:'a',1:'b',2:'c'}
288 >>> H=relabel_nodes(G,mapping)
289 >>> print H.nodes()
290 ['a', 'c', 'b']
291
292 >>> G=path_graph(26) # nodes 0..25
293 >>> mapping=dict(zip(G.nodes(),"abcdefghijklmnopqrstuvwxyz"))
294 >>> H=relabel_nodes(G,mapping) # nodes a..z
295 >>> mapping=dict(zip(G.nodes(),xrange(1,27)))
296 >>> G1=relabel_nodes(G,mapping) # nodes 1..26
297
298 mapping as function
299
300 >>> G=path_graph(3)
301 >>> def mapping(x):
302 ... return x**2
303 >>> H=relabel_nodes(G,mapping)
304 >>> print H.nodes()
305 [0, 1, 4]
306
307 Also see convert_node_labels_to_integers.
308
309 """
310 H=create_empty_copy(G,with_nodes=False)
311 H.name="(%s)" % G.name
312
313 if hasattr(mapping,"__getitem__"):
314 map_func=mapping.__getitem__
315 else:
316 map_func=mapping
317
318 for node in G:
319 try:
320 H.add_node(map_func(node))
321 except:
322 raise networkx.NetworkXError,\
323 "relabeling function cannot be applied to node %s" % node
324
325 for e in G.edges_iter():
326 u=map_func(e[0])
327 v=map_func(e[1])
328 if len(e)==2:
329 H.add_edge(u,v)
330 else:
331 H.add_edge(u,v,e[2])
332
333 return H
334
335
337 """Deprecated: call relabel_nodes(G,func)."""
338 return relabel_nodes(G,func)
339
340
344 """ Return a copy of G, with n node labels replaced with integers,
345 starting at first_label.
346
347 first_label: (optional, default=0)
348
349 An integer specifying the offset in numbering nodes.
350 The n new integer labels are numbered first_label, ..., n+first_label.
351
352 ordering: (optional, default="default")
353
354 A string specifying how new node labels are ordered.
355 Possible values are:
356
357 "default" : inherit node ordering from G.nodes()
358 "sorted" : inherit node ordering from sorted(G.nodes())
359 "increasing degree" : nodes are sorted by increasing degree
360 "decreasing degree" : nodes are sorted by decreasing degree
361
362 *discard_old_labels*
363 if True (default) discard old labels
364 if False, create a dict self.node_labels that maps new
365 labels to old labels
366
367 Works for Graph, DiGraph, XGraph, XDiGraph
368 """
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387 N=G.number_of_nodes()+first_label
388 if ordering=="default":
389 mapping=dict(zip(G.nodes(),range(first_label,N)))
390 elif ordering=="sorted":
391 nlist=G.nodes()
392 nlist.sort()
393 mapping=dict(zip(nlist,range(first_label,N)))
394 elif ordering=="increasing degree":
395 dv_pairs=[(G.degree(n),n) for n in G]
396 dv_pairs.sort()
397 mapping=dict(zip([n for d,n in dv_pairs],range(first_label,N)))
398 elif ordering=="decreasing degree":
399 dv_pairs=[(G.degree(n),n) for n in G]
400 dv_pairs.sort()
401 dv_pairs.reverse()
402 mapping=dict(zip([n for d,n in dv_pairs],range(first_label,N)))
403 else:
404 raise networkx.NetworkXError,\
405 "unknown value of node ordering variable: ordering"
406
407 H=relabel_nodes(G,mapping)
408
409 H.name="("+G.name+")_with_int_labels"
410 if not discard_old_labels:
411 H.node_labels=mapping
412 return H
413
414
416 import doctest
417 suite = doctest.DocFileSuite('tests/operators.txt',package='networkx')
418 return suite
419
420 if __name__ == "__main__":
421 import os
422 import sys
423 import unittest
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]
426 sys.exit(-1)
427
428 nxbase=sys.path[0]+os.sep+os.pardir
429 sys.path.insert(0,nxbase)
430 unittest.TextTestRunner().run(_test_suite())
431