Package networkx :: Package generators :: Module bipartite
[hide private]
[frames] | no frames]

Source Code for Module networkx.generators.bipartite

  1  # -*- coding: utf-8 -*- 
  2  """ 
  3  Generators and functions for bipartite graphs. 
  4   
  5  """ 
  6  #    Copyright (C) 2006 by  
  7  #    Aric Hagberg <hagberg@lanl.gov> 
  8  #    Dan Schult <dschult@colgate.edu> 
  9  #    Pieter Swart <swart@lanl.gov> 
 10  #    Distributed under the terms of the GNU Lesser General Public License 
 11  #    http://www.gnu.org/copyleft/lesser.html 
 12  __author__ = """Aric Hagberg (hagberg@lanl.gov)\nPieter Swart (swart@lanl.gov)\nDan Schult (dschult@colgate.edu)""" 
 13    
 14  import random 
 15  import sys 
 16  import networkx as NX 
 17   
18 -def bipartite_configuration_model(aseq, bseq, 19 create_using=None, 20 seed=None, 21 ):
22 """ 23 Return a random bipartite graph from two given degree sequences. 24 25 :Parameters: 26 - `aseq`: degree sequence for node set A 27 - `bseq`: degree sequence for node set B 28 29 Nodes from the set A are connected to nodes in the set B by 30 choosing randomly from the possible free stubs, one in A and 31 one in B. 32 33 The sum of the two sequences must be equal: sum(aseq)=sum(bseq) 34 35 If no graph type is specified use XGraph with parallel edges. 36 37 If you want a graph with no parallel edges use create_using=Graph() 38 but then the resulting degree sequences might not be exact. 39 40 """ 41 42 if create_using==None: 43 create_using=NX.XGraph(multiedges=True) 44 45 G=NX.empty_graph(0,create_using) 46 47 if not seed is None: 48 random.seed(seed) 49 50 # length and sum of each sequence 51 lena=len(aseq) 52 lenb=len(bseq) 53 suma=sum(aseq) 54 sumb=sum(bseq) 55 56 if not suma==sumb: 57 raise NX.NetworkXError, \ 58 'invalid degree sequences, sum(aseq)!=sum(bseq),%s,%s'\ 59 %(suma,sumb) 60 61 G.add_nodes_from(range(0,lena+lenb)) 62 63 if max(aseq)==0: return G # done if no edges 64 65 # build lists of degree-repeated vertex numbers 66 stubs=[] 67 stubs.extend([[v]*aseq[v] for v in range(0,lena)]) 68 astubs=[] 69 astubs=[x for subseq in stubs for x in subseq] 70 71 stubs=[] 72 stubs.extend([[v]*bseq[v-lena] for v in range(lena,lena+lenb)]) 73 bstubs=[] 74 bstubs=[x for subseq in stubs for x in subseq] 75 76 # shuffle lists 77 random.shuffle(astubs) 78 random.shuffle(bstubs) 79 80 G.add_edges_from([[astubs[i],bstubs[i]] for i in xrange(suma)]) 81 82 G.name="bipartite_configuration_model" 83 return G
84 85
86 -def bipartite_havel_hakimi_graph(aseq, bseq, 87 create_using=None, 88 ):
89 """ 90 Return a bipartite graph from two given degree sequences 91 using a Havel-Hakimi style construction. 92 93 :Parameters: 94 - `aseq`: degree sequence for node set A 95 - `bseq`: degree sequence for node set B 96 97 Nodes from the set A are connected to nodes in the set B by 98 connecting the highest degree nodes in set A to 99 the highest degree nodes in set B until all stubs are connected. 100 101 The sum of the two sequences must be equal: sum(aseq)=sum(bseq) 102 """ 103 if create_using==None: 104 create_using=NX.XGraph(multiedges=True) 105 106 G=NX.empty_graph(0,create_using) 107 108 # length of the each sequence 109 naseq=len(aseq) 110 nbseq=len(bseq) 111 112 suma=sum(aseq) 113 sumb=sum(bseq) 114 115 if not suma==sumb: 116 raise NX.NetworkXError, \ 117 'invalid degree sequences, sum(aseq)!=sum(bseq),%s,%s'\ 118 %(suma,sumb) 119 120 G.add_nodes_from(range(0,naseq)) # one vertex type (a) 121 G.add_nodes_from(range(naseq,naseq+nbseq)) # the other type (b) 122 123 if max(aseq)==0: return G # done if no edges 124 125 # build list of degree-repeated vertex numbers 126 astubs=[[aseq[v],v] for v in range(0,naseq)] 127 bstubs=[[bseq[v-naseq],v] for v in range(naseq,naseq+nbseq)] 128 astubs.sort() 129 while astubs: 130 (degree,u)=astubs.pop() # take of largest degree node in the a set 131 if degree==0: break # done, all are zero 132 # connect the source to largest degree nodes in the b set 133 bstubs.sort() 134 for target in bstubs[-degree:]: 135 v=target[1] 136 G.add_edge(u,v) 137 target[0] -= 1 # note this updates bstubs too. 138 if target[0]==0: 139 bstubs.remove(target) 140 141 G.name="bipartite_havel_hakimi_graph" 142 return G
143
144 -def bipartite_reverse_havel_hakimi_graph(aseq, bseq, 145 create_using=None, 146 ):
147 """ 148 Return a bipartite graph from two given degree sequences 149 using a "reverse" Havel-Hakimi style construction. 150 151 :Parameters: 152 - `aseq`: degree sequence for node set A 153 - `bseq`: degree sequence for node set B 154 155 Nodes from the set A are connected to nodes in the set B by 156 connecting the highest degree nodes in set A to 157 the lowest degree nodes in set B until all stubs are connected. 158 159 The sum of the two sequences must be equal: sum(aseq)=sum(bseq) 160 """ 161 if create_using==None: 162 create_using=NX.XGraph(multiedges=True) 163 164 G=NX.empty_graph(0,create_using) 165 166 167 # length of the each sequence 168 lena=len(aseq) 169 lenb=len(bseq) 170 suma=sum(aseq) 171 sumb=sum(bseq) 172 173 if not suma==sumb: 174 raise NX.NetworkXError, \ 175 'invalid degree sequences, sum(aseq)!=sum(bseq),%s,%s'\ 176 %(suma,sumb) 177 178 G.add_nodes_from(range(0,lena+lenb)) 179 180 181 if max(aseq)==0: return G # done if no edges 182 183 # build list of degree-repeated vertex numbers 184 astubs=[[aseq[v],v] for v in range(0,lena)] 185 bstubs=[[bseq[v-lena],v] for v in range(lena,lena+lenb)] 186 astubs.sort() 187 bstubs.sort() 188 while astubs: 189 (degree,u)=astubs.pop() # take of largest degree node in the a set 190 if degree==0: break # done, all are zero 191 # connect the source to the smallest degree nodes in the b set 192 for target in bstubs[0:degree]: 193 v=target[1] 194 G.add_edge(u,v) 195 target[0] -= 1 # note this updates bstubs too. 196 if target[0]==0: 197 bstubs.remove(target) 198 199 G.name="bipartite_reverse_havel_hakimi_graph" 200 return G
201 202
203 -def bipartite_alternating_havel_hakimi_graph(aseq, bseq, 204 create_using=None, 205 ):
206 """ 207 Return a bipartite graph from two given degree sequences 208 using a alternating Havel-Hakimi style construction. 209 210 :Parameters: 211 - `aseq`: degree sequence for node set A 212 - `bseq`: degree sequence for node set B 213 214 Nodes from the set A are connected to nodes in the set B by 215 connecting the highest degree nodes in set A to 216 alternatively the highest and the lowest degree nodes in set 217 B until all stubs are connected. 218 219 The sum of the two sequences must be equal: sum(aseq)=sum(bseq) 220 """ 221 if create_using==None: 222 create_using=NX.XGraph(multiedges=True) 223 224 G=NX.empty_graph(0,create_using) 225 226 # length of the each sequence 227 naseq=len(aseq) 228 nbseq=len(bseq) 229 suma=sum(aseq) 230 sumb=sum(bseq) 231 232 if not suma==sumb: 233 raise NX.NetworkXError, \ 234 'invalid degree sequences, sum(aseq)!=sum(bseq),%s,%s'\ 235 %(suma,sumb) 236 237 G.add_nodes_from(range(0,naseq)) # one vertex type (a) 238 G.add_nodes_from(range(naseq,naseq+nbseq)) # the other type (b) 239 240 if max(aseq)==0: return G # done if no edges 241 # build list of degree-repeated vertex numbers 242 astubs=[[aseq[v],v] for v in range(0,naseq)] 243 bstubs=[[bseq[v-naseq],v] for v in range(naseq,naseq+nbseq)] 244 while astubs: 245 astubs.sort() 246 (degree,u)=astubs.pop() # take of largest degree node in the a set 247 if degree==0: break # done, all are zero 248 bstubs.sort() 249 small=bstubs[0:degree/2] # add these low degree targets 250 large=bstubs[(-degree+degree/2):] # and these high degree targets 251 stubs=[x for z in zip(large,small) for x in z] # combine, sorry 252 if len(stubs)<len(small)+len(large): # check for zip truncation 253 stubs.append(large.pop()) 254 for target in stubs: 255 v=target[1] 256 G.add_edge(u,v) 257 target[0] -= 1 # note this updates bstubs too. 258 if target[0]==0: 259 bstubs.remove(target) 260 261 G.name="bipartite_alternating_havel_hakimi_graph" 262 return G
263
264 -def bipartite_preferential_attachment_graph(aseq,p, 265 create_using=None, 266 ):
267 """ 268 Create a bipartite graph with a preferential attachment model 269 from a given single "top" degree sequence. 270 271 :Parameters: 272 - `aseq`: degree sequence for node set A (top) 273 - `p`: probability that a new bottom node is added 274 275 276 Reference:: 277 278 @article{guillaume-2004-bipartite, 279 author = {Jean-Loup Guillaume and Matthieu Latapy}, 280 title = {Bipartite structure of all complex networks}, 281 journal = {Inf. Process. Lett.}, 282 volume = {90}, 283 number = {5}, 284 year = {2004}, 285 issn = {0020-0190}, 286 pages = {215--221}, 287 doi = {http://dx.doi.org/10.1016/j.ipl.2004.03.007}, 288 publisher = {Elsevier North-Holland, Inc.}, 289 address = {Amsterdam, The Netherlands, The Netherlands}, 290 } 291 292 """ 293 if create_using==None: 294 create_using=NX.XGraph(multiedges=True) 295 296 G=NX.empty_graph(0,create_using) 297 298 if p > 1: 299 raise NX.NetworkXError, "probability %s > 1"%(p) 300 301 naseq=len(aseq) 302 G.add_nodes_from(range(0,naseq)) 303 vv=[ [v]*aseq[v] for v in range(0,naseq)] 304 while vv: 305 while vv[0]: 306 source=vv[0][0] 307 vv[0].remove(source) 308 if random.random() < p or G.number_of_nodes() == naseq: 309 target=G.number_of_nodes() 310 G.add_edge(source,target) 311 else: 312 bb=[ [b]*G.degree(b) for b in range(naseq,G.number_of_nodes())] 313 # flatten the list of lists into a list. 314 bbstubs=reduce(lambda x,y: x+y, bb) 315 # choose preferentially a bottom node. 316 target=random.choice(bbstubs) 317 G.add_edge(source,target) 318 vv.remove(vv[0]) 319 G.name="bipartite_preferential_attachment_model" 320 return G
321 322
323 -def bipartite_random_regular_graph(d, n, 324 create_using=None, 325 ):
326 """ 327 UNTESTED:Generate a random bipartite graph of n nodes each with degree d. 328 329 Restrictions on n and d: 330 - n must be even 331 - n>=2*d 332 333 Nodes are numbered 0...n-1. 334 335 Algorithm inspired by random_regular_graph() 336 337 """ 338 # helper subroutine to check for suitable edges 339 def suitable(leftstubs,rightstubs): 340 for s in leftstubs: 341 for t in rightstubs: 342 if not t in seen_edges[s]: 343 return True 344 # else no suitable possible edges 345 return False
346 347 if not n*d%2==0: 348 print "n*d must be even" 349 return False 350 351 352 if not n%2==0: 353 print "n must be even" 354 return False 355 356 if not n>=2*d: 357 print "n must be >= 2*d" 358 return False 359 360 361 if create_using==None: 362 create_using=NX.XGraph(multiedges=True) 363 364 G=NX.empty_graph(0,create_using) 365 366 nodes=range(0,n) 367 G.add_nodes_from(nodes) 368 369 seen_edges={} 370 [seen_edges.setdefault(v,{}) for v in nodes] 371 372 vv=[ [v]*d for v in nodes ] # List of degree-repeated vertex numbers 373 stubs=reduce(lambda x,y: x+y ,vv) # flatten the list of lists to a list 374 375 leftstubs=stubs[:(n*d/2)] 376 rightstubs=stubs[n*d/2:] 377 378 while leftstubs: 379 source=random.choice(leftstubs) 380 target=random.choice(rightstubs) 381 if source!=target and not target in seen_edges[source]: 382 leftstubs.remove(source) 383 rightstubs.remove(target) 384 seen_edges[source][target]=1 385 seen_edges[target][source]=1 386 G.add_edge(source,target) 387 else: 388 # further check to see if suitable 389 if suitable(leftstubs,rightstubs)==False: 390 return False 391 return G 392 393
394 -def project(B,nodes,create_using=None):
395 """ 396 Returns a graph that is the projection of the bipartite graph B 397 onto the set of nodes given in list nodes. 398 399 The nodes retain their names and are connected if they share a 400 common node in the node set of {B not nodes }. 401 402 No attempt is made to verify that the input graph B is bipartite. 403 """ 404 405 if create_using==None: 406 create_using=NX.Graph() 407 408 G=NX.empty_graph(0,create_using) 409 410 for v in nodes: 411 G.add_node(v) 412 for cv in B.neighbors(v): 413 G.add_edges_from([(v,u) for u in B.neighbors(cv)]) 414 return G
415 416
417 -def bipartite_color(G):
418 color={} 419 for n in G.nodes(): #handle disconnected graphs 420 if n in color: continue 421 queue=[n] 422 color[n]=1 # nodes seen with color (1 or 0) 423 while queue: 424 v=queue.pop() 425 c=1-color[v] # opposite color of node v 426 for w in G.neighbors(v): 427 if w in color: 428 if color[w]==color[v]: 429 raise NX.NetworkXError, "graph is not bipartite" 430 else: 431 color[w]=c 432 queue.append(w) 433 return color
434
435 -def is_bipartite(G):
436 """ Returns True if graph G is bipartite, False if not. 437 438 Traverse the graph G with depth-first-search and color nodes. 439 """ 440 try: 441 bipartite_color(G) 442 return True 443 except: 444 return False
445
446 -def bipartite_sets(G):
447 """ 448 Returns (X,Y) where X and Y are the nodes in each bipartite set 449 of graph G. Fails with an error if graph is not bipartite. 450 """ 451 color=bipartite_color(G) 452 X=[n for n in color if color[n]==1] 453 Y=[n for n in color if color[n]==0] 454 return (X,Y)
455
456 -def _test_suite():
457 import doctest 458 suite = doctest.DocFileSuite('tests/generators/bipartite.txt', 459 package='networkx') 460 return suite
461 462 if __name__ == "__main__": 463 import sys 464 import unittest 465 if sys.version_info[:2] < (2, 4): 466 print "Python version 2.4 or later required for tests (%d.%d detected)."% sys.version_info[:2] 467 sys.exit(-1) 468 unittest.TextTestRunner().run(_test_suite()) 469