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


2 
# Copyright (C) 2014 by

3 
# Christian Olsson <chro@itu.dk>

4 
# Jan Aagaard Meier <jmei@itu.dk>

5 
# Henrik Haugbølle <hhau@itu.dk>

6 
# Arya McCarthy <admccarthy@smu.edu>

7 
# All rights reserved.

8 
# BSD license.

9 
"""

10 
Greedy graph coloring using various strategies.

11 
"""

12 
from collections import defaultdict, deque 
13 
import itertools 
14  
15 
import networkx as nx 
16 
from networkx.utils import arbitrary_element 
17 
from networkx.utils import py_random_state 
18 
from . import greedy_coloring_with_interchange as _interchange 
19  
20 
__all__ = ['greedy_color', 'strategy_connected_sequential', 
21 
'strategy_connected_sequential_bfs',

22 
'strategy_connected_sequential_dfs', 'strategy_independent_set', 
23 
'strategy_largest_first', 'strategy_random_sequential', 
24 
'strategy_saturation_largest_first', 'strategy_smallest_last'] 
25  
26  
27 
def strategy_largest_first(G, colors): 
28 
"""Returns a list of the nodes of ``G`` in decreasing order by

29 
degree.

30 

31 
``G`` is a NetworkX graph. ``colors`` is ignored.

32 

33 
"""

34 
return sorted(G, key=G.degree, reverse=True) 
35  
36  
37 
@py_random_state(2) 
38 
def strategy_random_sequential(G, colors, seed=None): 
39 
"""Returns a random permutation of the nodes of ``G`` as a list.

40 

41 
``G`` is a NetworkX graph. ``colors`` is ignored.

42 

43 
seed : integer, random_state, or None (default)

44 
Indicator of random number generation state.

45 
See :ref:`Randomness<randomness>`.

46 
"""

47 
nodes = list(G)

48 
seed.shuffle(nodes) 
49 
return nodes

50  
51  
52 
def strategy_smallest_last(G, colors): 
53 
"""Returns a deque of the nodes of ``G``, "smallest" last.

54 

55 
Specifically, the degrees of each node are tracked in a bucket queue.

56 
From this, the node of minimum degree is repeatedly popped from the

57 
graph, updating its neighbors' degrees.

58 

59 
``G`` is a NetworkX graph. ``colors`` is ignored.

60 

61 
This implementation of the strategy runs in $O(n + m)$ time

62 
(ignoring polylogarithmic factors), where $n$ is the number of nodes

63 
and $m$ is the number of edges.

64 

65 
This strategy is related to :func:`strategy_independent_set`: if we

66 
interpret each node removed as an independent set of size one, then

67 
this strategy chooses an independent set of size one instead of a

68 
maximal independent set.

69 

70 
"""

71 
H = G.copy() 
72 
result = deque() 
73  
74 
# Build initial degree list (i.e. the bucket queue data structure)

75 
degrees = defaultdict(set) # set(), for fast randomaccess removals 
76 
lbound = float('inf') 
77 
for node, d in H.degree(): 
78 
degrees[d].add(node) 
79 
lbound = min(lbound, d) # Lower bound on mindegree. 
80  
81 
def find_min_degree(): 
82 
# Save time by starting the iterator at `lbound`, not 0.

83 
# The value that we find will be our new `lbound`, which we set later.

84 
return next(d for d in itertools.count(lbound) if d in degrees) 
85  
86 
for _ in G: 
87 
# Pop a mindegree node and add it to the list.

88 
min_degree = find_min_degree() 
89 
u = degrees[min_degree].pop() 
90 
if not degrees[min_degree]: # Clean up the degree list. 
91 
del degrees[min_degree]

92 
result.appendleft(u) 
93  
94 
# Update degrees of removed node's neighbors.

95 
for v in H[u]: 
96 
degree = H.degree(v) 
97 
degrees[degree].remove(v) 
98 
if not degrees[degree]: # Clean up the degree list. 
99 
del degrees[degree]

100 
degrees[degree  1].add(v)

101  
102 
# Finally, remove the node.

103 
H.remove_node(u) 
104 
lbound = min_degree  1 # Subtract 1 in case of tied neighbors. 
105  
106 
return result

107  
108  
109 
def _maximal_independent_set(G): 
110 
"""Returns a maximal independent set of nodes in ``G`` by repeatedly

111 
choosing an independent node of minimum degree (with respect to the

112 
subgraph of unchosen nodes).

113 

114 
"""

115 
result = set()

116 
remaining = set(G)

117 
while remaining:

118 
G = G.subgraph(remaining) 
119 
v = min(remaining, key=G.degree)

120 
result.add(v) 
121 
remaining = set(G[v])  {v}

122 
return result

123  
124  
125 
def strategy_independent_set(G, colors): 
126 
"""Uses a greedy independent set removal strategy to determine the

127 
colors.

128 

129 
This function updates ``colors`` **inplace** and return ``None``,

130 
unlike the other strategy functions in this module.

131 

132 
This algorithm repeatedly finds and removes a maximal independent

133 
set, assigning each node in the set an unused color.

134 

135 
``G`` is a NetworkX graph.

136 

137 
This strategy is related to :func:`strategy_smallest_last`: in that

138 
strategy, an independent set of size one is chosen at each step

139 
instead of a maximal independent set.

140 

141 
"""

142 
remaining_nodes = set(G)

143 
while len(remaining_nodes) > 0: 
144 
nodes = _maximal_independent_set(G.subgraph(remaining_nodes)) 
145 
remaining_nodes = nodes 
146 
for v in nodes: 
147 
yield v

148  
149  
150 
def strategy_connected_sequential_bfs(G, colors): 
151 
"""Returns an iterable over nodes in ``G`` in the order given by a

152 
breadthfirst traversal.

153 

154 
The generated sequence has the property that for each node except

155 
the first, at least one neighbor appeared earlier in the sequence.

156 

157 
``G`` is a NetworkX graph. ``colors`` is ignored.

158 

159 
"""

160 
return strategy_connected_sequential(G, colors, 'bfs') 
161  
162  
163 
def strategy_connected_sequential_dfs(G, colors): 
164 
"""Returns an iterable over nodes in ``G`` in the order given by a

165 
depthfirst traversal.

166 

167 
The generated sequence has the property that for each node except

168 
the first, at least one neighbor appeared earlier in the sequence.

169 

170 
``G`` is a NetworkX graph. ``colors`` is ignored.

171 

172 
"""

173 
return strategy_connected_sequential(G, colors, 'dfs') 
174  
175  
176 
def strategy_connected_sequential(G, colors, traversal='bfs'): 
177 
"""Returns an iterable over nodes in ``G`` in the order given by a

178 
breadthfirst or depthfirst traversal.

179 

180 
``traversal`` must be one of the strings ``'dfs'`` or ``'bfs'``,

181 
representing depthfirst traversal or breadthfirst traversal,

182 
respectively.

183 

184 
The generated sequence has the property that for each node except

185 
the first, at least one neighbor appeared earlier in the sequence.

186 

187 
``G`` is a NetworkX graph. ``colors`` is ignored.

188 

189 
"""

190 
if traversal == 'bfs': 
191 
traverse = nx.bfs_edges 
192 
elif traversal == 'dfs': 
193 
traverse = nx.dfs_edges 
194 
else:

195 
raise nx.NetworkXError("Please specify one of the strings 'bfs' or" 
196 
" 'dfs' for connected sequential ordering")

197 
for component in nx.connected_component_subgraphs(G): 
198 
source = arbitrary_element(component) 
199 
# Yield the source node, then all the nodes in the specified

200 
# traversal order.

201 
yield source

202 
for (_, end) in traverse(component, source): 
203 
yield end

204  
205  
206 
def strategy_saturation_largest_first(G, colors): 
207 
"""Iterates over all the nodes of ``G`` in "saturation order" (also

208 
known as "DSATUR").

209 

210 
``G`` is a NetworkX graph. ``colors`` is a dictionary mapping nodes of

211 
``G`` to colors, for those nodes that have already been colored.

212 

213 
"""

214 
distinct_colors = {v: set() for v in G} 
215 
for i in range(len(G)): 
216 
# On the first time through, simply choose the node of highest degree.

217 
if i == 0: 
218 
node = max(G, key=G.degree)

219 
yield node

220 
# Add the color 0 to the distinct colors set for each

221 
# neighbors of that node.

222 
for v in G[node]: 
223 
distinct_colors[v].add(0)

224 
else:

225 
# Compute the maximum saturation and the set of nodes that

226 
# achieve that saturation.

227 
saturation = {v: len(c) for v, c in distinct_colors.items() 
228 
if v not in colors} 
229 
# Yield the node with the highest saturation, and break ties by

230 
# degree.

231 
node = max(saturation, key=lambda v: (saturation[v], G.degree(v))) 
232 
yield node

233 
# Update the distinct color sets for the neighbors.

234 
color = colors[node] 
235 
for v in G[node]: 
236 
distinct_colors[v].add(color) 
237  
238  
239 
#: Dictionary mapping name of a strategy as a string to the strategy function.

240 
STRATEGIES = { 
241 
'largest_first': strategy_largest_first,

242 
'random_sequential': strategy_random_sequential,

243 
'smallest_last': strategy_smallest_last,

244 
'independent_set': strategy_independent_set,

245 
'connected_sequential_bfs': strategy_connected_sequential_bfs,

246 
'connected_sequential_dfs': strategy_connected_sequential_dfs,

247 
'connected_sequential': strategy_connected_sequential,

248 
'saturation_largest_first': strategy_saturation_largest_first,

249 
'DSATUR': strategy_saturation_largest_first,

250 
} 
251  
252  
253 
def greedy_color(G, strategy='largest_first', interchange=False): 
254 
"""Color a graph using various strategies of greedy graph coloring.

255 

256 
Attempts to color a graph using as few colors as possible, where no

257 
neighbours of a node can have same color as the node itself. The

258 
given strategy determines the order in which nodes are colored.

259 

260 
The strategies are described in [1]_, and smallestlast is based on

261 
[2]_.

262 

263 
Parameters

264 


265 
G : NetworkX graph

266 

267 
strategy : string or function(G, colors)

268 
A function (or a string representing a function) that provides

269 
the coloring strategy, by returning nodes in the ordering they

270 
should be colored. ``G`` is the graph, and ``colors`` is a

271 
dictionary of the currently assigned colors, keyed by nodes. The

272 
function must return an iterable over all the nodes in ``G``.

273 

274 
If the strategy function is an iterator generator (that is, a

275 
function with ``yield`` statements), keep in mind that the

276 
``colors`` dictionary will be updated after each ``yield``, since

277 
this function chooses colors greedily.

278 

279 
If ``strategy`` is a string, it must be one of the following,

280 
each of which represents one of the builtin strategy functions.

281 

282 
* ``'largest_first'``

283 
* ``'random_sequential'``

284 
* ``'smallest_last'``

285 
* ``'independent_set'``

286 
* ``'connected_sequential_bfs'``

287 
* ``'connected_sequential_dfs'``

288 
* ``'connected_sequential'`` (alias for the previous strategy)

289 
* ``'strategy_saturation_largest_first'``

290 
* ``'DSATUR'`` (alias for the previous strategy)

291 

292 
interchange: bool

293 
Will use the color interchange algorithm described by [3]_ if set

294 
to ``True``.

295 

296 
Note that ``strategy_saturation_largest_first`` and

297 
``strategy_independent_set`` do not work with

298 
interchange. Furthermore, if you use interchange with your own

299 
strategy function, you cannot rely on the values in the

300 
``colors`` argument.

301 

302 
Returns

303 


304 
A dictionary with keys representing nodes and values representing

305 
corresponding coloring.

306 

307 
Examples

308 


309 
>>> G = nx.cycle_graph(4)

310 
>>> d = nx.coloring.greedy_color(G, strategy='largest_first')

311 
>>> d in [{0: 0, 1: 1, 2: 0, 3: 1}, {0: 1, 1: 0, 2: 1, 3: 0}]

312 
True

313 

314 
Raises

315 


316 
NetworkXPointlessConcept

317 
If ``strategy`` is ``strategy_saturation_largest_first`` or

318 
``strategy_independent_set`` and ``interchange`` is ``True``.

319 

320 
References

321 


322 
.. [1] Adrian Kosowski, and Krzysztof Manuszewski,

323 
Classical Coloring of Graphs, Graph Colorings, 219, 2004.

324 
ISBN 0821834584.

325 
.. [2] David W. Matula, and Leland L. Beck, "Smallestlast

326 
ordering and clustering and graph coloring algorithms." *J. ACM* 30,

327 
3 (July 1983), 417–427. <https://doi.org/10.1145/2402.322385>

328 
.. [3] Maciej M. Sysło, Marsingh Deo, Janusz S. Kowalik,

329 
Discrete Optimization Algorithms with Pascal Programs, 415424, 1983.

330 
ISBN 0486453537.

331 

332 
"""

333 
if len(G) == 0: 
334 
return {}

335 
# Determine the strategy provided by the caller.

336 
strategy = STRATEGIES.get(strategy, strategy) 
337 
if not callable(strategy): 
338 
raise nx.NetworkXError('strategy must be callable or a valid string. ' 
339 
'{0} not valid.'.format(strategy))

340 
# Perform some validation on the arguments before executing any

341 
# strategy functions.

342 
if interchange:

343 
if strategy is strategy_independent_set: 
344 
msg = 'interchange cannot be used with strategy_independent_set'

345 
raise nx.NetworkXPointlessConcept(msg)

346 
if strategy is strategy_saturation_largest_first: 
347 
msg = ('interchange cannot be used with'

348 
' strategy_saturation_largest_first')

349 
raise nx.NetworkXPointlessConcept(msg)

350 
colors = {} 
351 
nodes = strategy(G, colors) 
352 
if interchange:

353 
return _interchange.greedy_coloring_with_interchange(G, nodes)

354 
for u in nodes: 
355 
# Set to keep track of colors of neighbours

356 
neighbour_colors = {colors[v] for v in G[u] if v in colors} 
357 
# Find the first unused color.

358 
for color in itertools.count(): 
359 
if color not in neighbour_colors: 
360 
break

361 
# Assign the new color to the current node.

362 
colors[u] = color 
363 
return colors
