ioftools / networkxMiCe / networkxmaster / networkx / algorithms / bipartite / basic.py @ 5cef0f13
History  View  Annotate  Download (7.85 KB)
1 
# * coding: utf8 *


2 
"""

3 
==========================

4 
Bipartite Graph Algorithms

5 
==========================

6 
"""

7 
# Copyright (C) 20132019 by

8 
# Aric Hagberg <hagberg@lanl.gov>

9 
# Dan Schult <dschult@colgate.edu>

10 
# Pieter Swart <swart@lanl.gov>

11 
# All rights reserved.

12 
# BSD license.

13 
import networkx as nx 
14 
__author__ = """\n""".join(['Jordi Torrents <jtorrents@milnou.net>', 
15 
'Aric Hagberg <aric.hagberg@gmail.com>'])

16 
__all__ = ['is_bipartite',

17 
'is_bipartite_node_set',

18 
'color',

19 
'sets',

20 
'density',

21 
'degrees']

22  
23  
24 
def color(G): 
25 
"""Returns a twocoloring of the graph.

26 

27 
Raises an exception if the graph is not bipartite.

28 

29 
Parameters

30 


31 
G : NetworkX graph

32 

33 
Returns

34 


35 
color : dictionary

36 
A dictionary keyed by node with a 1 or 0 as data for each node color.

37 

38 
Raises

39 


40 
exc:`NetworkXError` if the graph is not twocolorable.

41 

42 
Examples

43 


44 
>>> from networkx.algorithms import bipartite

45 
>>> G = nx.path_graph(4)

46 
>>> c = bipartite.color(G)

47 
>>> print(c)

48 
{0: 1, 1: 0, 2: 1, 3: 0}

49 

50 
You can use this to set a node attribute indicating the biparite set:

51 

52 
>>> nx.set_node_attributes(G, c, 'bipartite')

53 
>>> print(G.nodes[0]['bipartite'])

54 
1

55 
>>> print(G.nodes[1]['bipartite'])

56 
0

57 
"""

58 
if G.is_directed():

59 
import itertools 
60  
61 
def neighbors(v): 
62 
return itertools.chain.from_iterable([G.predecessors(v),

63 
G.successors(v)]) 
64 
else:

65 
neighbors = G.neighbors 
66  
67 
color = {} 
68 
for n in G: # handle disconnected graphs 
69 
if n in color or len(G[n]) == 0: # skip isolates 
70 
continue

71 
queue = [n] 
72 
color[n] = 1 # nodes seen with color (1 or 0) 
73 
while queue:

74 
v = queue.pop() 
75 
c = 1  color[v] # opposite color of node v 
76 
for w in neighbors(v): 
77 
if w in color: 
78 
if color[w] == color[v]:

79 
raise nx.NetworkXError("Graph is not bipartite.") 
80 
else:

81 
color[w] = c 
82 
queue.append(w) 
83 
# color isolates with 0

84 
color.update(dict.fromkeys(nx.isolates(G), 0)) 
85 
return color

86  
87  
88 
def is_bipartite(G): 
89 
""" Returns True if graph G is bipartite, False if not.

90 

91 
Parameters

92 


93 
G : NetworkX graph

94 

95 
Examples

96 


97 
>>> from networkx.algorithms import bipartite

98 
>>> G = nx.path_graph(4)

99 
>>> print(bipartite.is_bipartite(G))

100 
True

101 

102 
See Also

103 


104 
color, is_bipartite_node_set

105 
"""

106 
try:

107 
color(G) 
108 
return True 
109 
except nx.NetworkXError:

110 
return False 
111  
112  
113 
def is_bipartite_node_set(G, nodes): 
114 
"""Returns True if nodes and G/nodes are a bipartition of G.

115 

116 
Parameters

117 


118 
G : NetworkX graph

119 

120 
nodes: list or container

121 
Check if nodes are a one of a bipartite set.

122 

123 
Examples

124 


125 
>>> from networkx.algorithms import bipartite

126 
>>> G = nx.path_graph(4)

127 
>>> X = set([1,3])

128 
>>> bipartite.is_bipartite_node_set(G,X)

129 
True

130 

131 
Notes

132 


133 
For connected graphs the bipartite sets are unique. This function handles

134 
disconnected graphs.

135 
"""

136 
S = set(nodes)

137 
for CC in nx.connected_component_subgraphs(G): 
138 
X, Y = sets(CC) 
139 
if not ((X.issubset(S) and Y.isdisjoint(S)) or 
140 
(Y.issubset(S) and X.isdisjoint(S))):

141 
return False 
142 
return True 
143  
144  
145 
def sets(G, top_nodes=None): 
146 
"""Returns bipartite node sets of graph G.

147 

148 
Raises an exception if the graph is not bipartite or if the input

149 
graph is disconnected and thus more than one valid solution exists.

150 
See :mod:`bipartite documentation <networkx.algorithms.bipartite>`

151 
for further details on how bipartite graphs are handled in NetworkX.

152 

153 
Parameters

154 


155 
G : NetworkX graph

156 

157 
top_nodes : container

158 

159 
Container with all nodes in one bipartite node set. If not supplied

160 
it will be computed. But if more than one solution exists an exception

161 
will be raised.

162 

163 
Returns

164 


165 
(X,Y) : twotuple of sets

166 
One set of nodes for each part of the bipartite graph.

167 

168 
Raises

169 


170 
AmbiguousSolution : Exception

171 

172 
Raised if the input bipartite graph is disconnected and no container

173 
with all nodes in one bipartite set is provided. When determining

174 
the nodes in each bipartite set more than one valid solution is

175 
possible if the input graph is disconnected.

176 

177 
NetworkXError: Exception

178 

179 
Raised if the input graph is not bipartite.

180 

181 
Examples

182 


183 
>>> from networkx.algorithms import bipartite

184 
>>> G = nx.path_graph(4)

185 
>>> X, Y = bipartite.sets(G)

186 
>>> list(X)

187 
[0, 2]

188 
>>> list(Y)

189 
[1, 3]

190 

191 
See Also

192 


193 
color

194 

195 
"""

196 
if G.is_directed():

197 
is_connected = nx.is_weakly_connected 
198 
else:

199 
is_connected = nx.is_connected 
200 
if top_nodes is not None: 
201 
X = set(top_nodes)

202 
Y = set(G)  X

203 
else:

204 
if not is_connected(G): 
205 
msg = 'Disconnected graph: Ambiguous solution for bipartite sets.'

206 
raise nx.AmbiguousSolution(msg)

207 
c = color(G) 
208 
X = {n for n, is_top in c.items() if is_top} 
209 
Y = {n for n, is_top in c.items() if not is_top} 
210 
return (X, Y)

211  
212  
213 
def density(B, nodes): 
214 
"""Returns density of bipartite graph B.

215 

216 
Parameters

217 


218 
G : NetworkX graph

219 

220 
nodes: list or container

221 
Nodes in one node set of the bipartite graph.

222 

223 
Returns

224 


225 
d : float

226 
The bipartite density

227 

228 
Examples

229 


230 
>>> from networkx.algorithms import bipartite

231 
>>> G = nx.complete_bipartite_graph(3,2)

232 
>>> X=set([0,1,2])

233 
>>> bipartite.density(G,X)

234 
1.0

235 
>>> Y=set([3,4])

236 
>>> bipartite.density(G,Y)

237 
1.0

238 

239 
Notes

240 


241 
The container of nodes passed as argument must contain all nodes

242 
in one of the two bipartite node sets to avoid ambiguity in the

243 
case of disconnected graphs.

244 
See :mod:`bipartite documentation <networkx.algorithms.bipartite>`

245 
for further details on how bipartite graphs are handled in NetworkX.

246 

247 
See Also

248 


249 
color

250 
"""

251 
n = len(B)

252 
m = nx.number_of_edges(B) 
253 
nb = len(nodes)

254 
nt = n  nb 
255 
if m == 0: # includes cases n==0 and n==1 
256 
d = 0.0

257 
else:

258 
if B.is_directed():

259 
d = m / (2.0 * float(nb * nt)) 
260 
else:

261 
d = m / float(nb * nt)

262 
return d

263  
264  
265 
def degrees(B, nodes, weight=None): 
266 
"""Returns the degrees of the two node sets in the bipartite graph B.

267 

268 
Parameters

269 


270 
G : NetworkX graph

271 

272 
nodes: list or container

273 
Nodes in one node set of the bipartite graph.

274 

275 
weight : string or None, optional (default=None)

276 
The edge attribute that holds the numerical value used as a weight.

277 
If None, then each edge has weight 1.

278 
The degree is the sum of the edge weights adjacent to the node.

279 

280 
Returns

281 


282 
(degX,degY) : tuple of dictionaries

283 
The degrees of the two bipartite sets as dictionaries keyed by node.

284 

285 
Examples

286 


287 
>>> from networkx.algorithms import bipartite

288 
>>> G = nx.complete_bipartite_graph(3,2)

289 
>>> Y=set([3,4])

290 
>>> degX,degY=bipartite.degrees(G,Y)

291 
>>> dict(degX)

292 
{0: 2, 1: 2, 2: 2}

293 

294 
Notes

295 


296 
The container of nodes passed as argument must contain all nodes

297 
in one of the two bipartite node sets to avoid ambiguity in the

298 
case of disconnected graphs.

299 
See :mod:`bipartite documentation <networkx.algorithms.bipartite>`

300 
for further details on how bipartite graphs are handled in NetworkX.

301 

302 
See Also

303 


304 
color, density

305 
"""

306 
bottom = set(nodes)

307 
top = set(B)  bottom

308 
return (B.degree(top, weight), B.degree(bottom, weight))
