Package networkx :: Module operators
[hide private]
[frames] | no frames]

Source Code for Module networkx.operators

  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  #    Copyright (C) 2004-2006 by  
 10  #    Aric Hagberg <hagberg@lanl.gov> 
 11  #    Dan Schult <dschult@colgate.edu> 
 12  #    Pieter Swart <swart@lanl.gov> 
 13  #    Distributed under the terms of the GNU Lesser General Public License 
 14  #    http://www.gnu.org/copyleft/lesser.html 
 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 # rename graph to obtain disjoint node labels 80 # note that for objects w/o succinct __name__, 81 # the new labels can be quite verbose 82 # See also disjoint_union 83 Gname={} 84 Hname={} 85 if rename: # create new string labels 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 # node name check 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 # node names OK, now build union 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
131 -def disjoint_union(G,H):
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
150 -def cartesian_product(G,H):
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
209 -def complement(G,create_using=None,name=None):
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
239 -def create_empty_copy(G,with_nodes=True):
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
254 -def convert_to_undirected(G):
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
265 -def convert_to_directed(G):
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
275 -def relabel_nodes(G,mapping):
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__"): # if we are a dict 314 map_func=mapping.__getitem__ # call as a function 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
336 -def relabel_nodes_with_function(G, func):
337 """Deprecated: call relabel_nodes(G,func).""" 338 return relabel_nodes(G,func)
339 340
341 -def convert_node_labels_to_integers(G,first_label=0, 342 ordering="default", 343 discard_old_labels=True):
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 # This function strips information attached to the nodes and/or 370 # edges of a graph, and returns a graph with appropriate integer 371 # labels. One can view this as a re-labeling of the nodes. Be 372 # warned that the term "labeled graph" has a loaded meaning 373 # in graph theory. The fundamental issue is whether the names 374 # (labels) of the nodes (and edges) matter in deciding when two 375 # graphs are the same. For example, in problems of graph enumeration 376 # there is a distinct difference in techniques required when 377 # counting labeled vs. unlabeled graphs. 378 379 # When implementing graph 380 # algorithms it is often convenient to strip off the original node 381 # and edge information and appropriately relabel the n nodes with 382 # the integer values 1,..,n. This is the purpose of this function, 383 # and it provides the option (see discard_old_labels variable) to either 384 # preserve the original labels in separate dicts (these are not 385 # returned but made an attribute of the new graph. 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() # in-place sort from lowest to highest degree 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() # in-place sort from lowest to highest degree 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
415 -def _test_suite():
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 # 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()) 431