1
2 """
3 Generators and functions for bipartite graphs.
4
5 """
6
7
8
9
10
11
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
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
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
64
65
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
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
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
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))
121 G.add_nodes_from(range(naseq,naseq+nbseq))
122
123 if max(aseq)==0: return G
124
125
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()
131 if degree==0: break
132
133 bstubs.sort()
134 for target in bstubs[-degree:]:
135 v=target[1]
136 G.add_edge(u,v)
137 target[0] -= 1
138 if target[0]==0:
139 bstubs.remove(target)
140
141 G.name="bipartite_havel_hakimi_graph"
142 return G
143
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
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
182
183
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()
190 if degree==0: break
191
192 for target in bstubs[0:degree]:
193 v=target[1]
194 G.add_edge(u,v)
195 target[0] -= 1
196 if target[0]==0:
197 bstubs.remove(target)
198
199 G.name="bipartite_reverse_havel_hakimi_graph"
200 return G
201
202
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
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))
238 G.add_nodes_from(range(naseq,naseq+nbseq))
239
240 if max(aseq)==0: return G
241
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()
247 if degree==0: break
248 bstubs.sort()
249 small=bstubs[0:degree/2]
250 large=bstubs[(-degree+degree/2):]
251 stubs=[x for z in zip(large,small) for x in z]
252 if len(stubs)<len(small)+len(large):
253 stubs.append(large.pop())
254 for target in stubs:
255 v=target[1]
256 G.add_edge(u,v)
257 target[0] -= 1
258 if target[0]==0:
259 bstubs.remove(target)
260
261 G.name="bipartite_alternating_havel_hakimi_graph"
262 return G
263
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
314 bbstubs=reduce(lambda x,y: x+y, bb)
315
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
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
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
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 ]
373 stubs=reduce(lambda x,y: x+y ,vv)
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
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
418 color={}
419 for n in G.nodes():
420 if n in color: continue
421 queue=[n]
422 color[n]=1
423 while queue:
424 v=queue.pop()
425 c=1-color[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
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
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
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