Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/coloring/greedy_coloring.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:4f3585e2f14b |
---|---|
1 """ | |
2 Greedy graph coloring using various strategies. | |
3 """ | |
4 from collections import defaultdict, deque | |
5 import itertools | |
6 | |
7 import networkx as nx | |
8 from networkx.utils import arbitrary_element | |
9 from networkx.utils import py_random_state | |
10 from . import greedy_coloring_with_interchange as _interchange | |
11 | |
12 __all__ = [ | |
13 "greedy_color", | |
14 "strategy_connected_sequential", | |
15 "strategy_connected_sequential_bfs", | |
16 "strategy_connected_sequential_dfs", | |
17 "strategy_independent_set", | |
18 "strategy_largest_first", | |
19 "strategy_random_sequential", | |
20 "strategy_saturation_largest_first", | |
21 "strategy_smallest_last", | |
22 ] | |
23 | |
24 | |
25 def strategy_largest_first(G, colors): | |
26 """Returns a list of the nodes of ``G`` in decreasing order by | |
27 degree. | |
28 | |
29 ``G`` is a NetworkX graph. ``colors`` is ignored. | |
30 | |
31 """ | |
32 return sorted(G, key=G.degree, reverse=True) | |
33 | |
34 | |
35 @py_random_state(2) | |
36 def strategy_random_sequential(G, colors, seed=None): | |
37 """Returns a random permutation of the nodes of ``G`` as a list. | |
38 | |
39 ``G`` is a NetworkX graph. ``colors`` is ignored. | |
40 | |
41 seed : integer, random_state, or None (default) | |
42 Indicator of random number generation state. | |
43 See :ref:`Randomness<randomness>`. | |
44 """ | |
45 nodes = list(G) | |
46 seed.shuffle(nodes) | |
47 return nodes | |
48 | |
49 | |
50 def strategy_smallest_last(G, colors): | |
51 """Returns a deque of the nodes of ``G``, "smallest" last. | |
52 | |
53 Specifically, the degrees of each node are tracked in a bucket queue. | |
54 From this, the node of minimum degree is repeatedly popped from the | |
55 graph, updating its neighbors' degrees. | |
56 | |
57 ``G`` is a NetworkX graph. ``colors`` is ignored. | |
58 | |
59 This implementation of the strategy runs in $O(n + m)$ time | |
60 (ignoring polylogarithmic factors), where $n$ is the number of nodes | |
61 and $m$ is the number of edges. | |
62 | |
63 This strategy is related to :func:`strategy_independent_set`: if we | |
64 interpret each node removed as an independent set of size one, then | |
65 this strategy chooses an independent set of size one instead of a | |
66 maximal independent set. | |
67 | |
68 """ | |
69 H = G.copy() | |
70 result = deque() | |
71 | |
72 # Build initial degree list (i.e. the bucket queue data structure) | |
73 degrees = defaultdict(set) # set(), for fast random-access removals | |
74 lbound = float("inf") | |
75 for node, d in H.degree(): | |
76 degrees[d].add(node) | |
77 lbound = min(lbound, d) # Lower bound on min-degree. | |
78 | |
79 def find_min_degree(): | |
80 # Save time by starting the iterator at `lbound`, not 0. | |
81 # The value that we find will be our new `lbound`, which we set later. | |
82 return next(d for d in itertools.count(lbound) if d in degrees) | |
83 | |
84 for _ in G: | |
85 # Pop a min-degree node and add it to the list. | |
86 min_degree = find_min_degree() | |
87 u = degrees[min_degree].pop() | |
88 if not degrees[min_degree]: # Clean up the degree list. | |
89 del degrees[min_degree] | |
90 result.appendleft(u) | |
91 | |
92 # Update degrees of removed node's neighbors. | |
93 for v in H[u]: | |
94 degree = H.degree(v) | |
95 degrees[degree].remove(v) | |
96 if not degrees[degree]: # Clean up the degree list. | |
97 del degrees[degree] | |
98 degrees[degree - 1].add(v) | |
99 | |
100 # Finally, remove the node. | |
101 H.remove_node(u) | |
102 lbound = min_degree - 1 # Subtract 1 in case of tied neighbors. | |
103 | |
104 return result | |
105 | |
106 | |
107 def _maximal_independent_set(G): | |
108 """Returns a maximal independent set of nodes in ``G`` by repeatedly | |
109 choosing an independent node of minimum degree (with respect to the | |
110 subgraph of unchosen nodes). | |
111 | |
112 """ | |
113 result = set() | |
114 remaining = set(G) | |
115 while remaining: | |
116 G = G.subgraph(remaining) | |
117 v = min(remaining, key=G.degree) | |
118 result.add(v) | |
119 remaining -= set(G[v]) | {v} | |
120 return result | |
121 | |
122 | |
123 def strategy_independent_set(G, colors): | |
124 """Uses a greedy independent set removal strategy to determine the | |
125 colors. | |
126 | |
127 This function updates ``colors`` **in-place** and return ``None``, | |
128 unlike the other strategy functions in this module. | |
129 | |
130 This algorithm repeatedly finds and removes a maximal independent | |
131 set, assigning each node in the set an unused color. | |
132 | |
133 ``G`` is a NetworkX graph. | |
134 | |
135 This strategy is related to :func:`strategy_smallest_last`: in that | |
136 strategy, an independent set of size one is chosen at each step | |
137 instead of a maximal independent set. | |
138 | |
139 """ | |
140 remaining_nodes = set(G) | |
141 while len(remaining_nodes) > 0: | |
142 nodes = _maximal_independent_set(G.subgraph(remaining_nodes)) | |
143 remaining_nodes -= nodes | |
144 yield from nodes | |
145 | |
146 | |
147 def strategy_connected_sequential_bfs(G, colors): | |
148 """Returns an iterable over nodes in ``G`` in the order given by a | |
149 breadth-first traversal. | |
150 | |
151 The generated sequence has the property that for each node except | |
152 the first, at least one neighbor appeared earlier in the sequence. | |
153 | |
154 ``G`` is a NetworkX graph. ``colors`` is ignored. | |
155 | |
156 """ | |
157 return strategy_connected_sequential(G, colors, "bfs") | |
158 | |
159 | |
160 def strategy_connected_sequential_dfs(G, colors): | |
161 """Returns an iterable over nodes in ``G`` in the order given by a | |
162 depth-first traversal. | |
163 | |
164 The generated sequence has the property that for each node except | |
165 the first, at least one neighbor appeared earlier in the sequence. | |
166 | |
167 ``G`` is a NetworkX graph. ``colors`` is ignored. | |
168 | |
169 """ | |
170 return strategy_connected_sequential(G, colors, "dfs") | |
171 | |
172 | |
173 def strategy_connected_sequential(G, colors, traversal="bfs"): | |
174 """Returns an iterable over nodes in ``G`` in the order given by a | |
175 breadth-first or depth-first traversal. | |
176 | |
177 ``traversal`` must be one of the strings ``'dfs'`` or ``'bfs'``, | |
178 representing depth-first traversal or breadth-first traversal, | |
179 respectively. | |
180 | |
181 The generated sequence has the property that for each node except | |
182 the first, at least one neighbor appeared earlier in the sequence. | |
183 | |
184 ``G`` is a NetworkX graph. ``colors`` is ignored. | |
185 | |
186 """ | |
187 if traversal == "bfs": | |
188 traverse = nx.bfs_edges | |
189 elif traversal == "dfs": | |
190 traverse = nx.dfs_edges | |
191 else: | |
192 raise nx.NetworkXError( | |
193 "Please specify one of the strings 'bfs' or" | |
194 " 'dfs' for connected sequential ordering" | |
195 ) | |
196 for component in nx.connected_components(G): | |
197 source = arbitrary_element(component) | |
198 # Yield the source node, then all the nodes in the specified | |
199 # traversal order. | |
200 yield source | |
201 for (_, end) in traverse(G.subgraph(component), source): | |
202 yield end | |
203 | |
204 | |
205 def strategy_saturation_largest_first(G, colors): | |
206 """Iterates over all the nodes of ``G`` in "saturation order" (also | |
207 known as "DSATUR"). | |
208 | |
209 ``G`` is a NetworkX graph. ``colors`` is a dictionary mapping nodes of | |
210 ``G`` to colors, for those nodes that have already been colored. | |
211 | |
212 """ | |
213 distinct_colors = {v: set() for v in G} | |
214 for i in range(len(G)): | |
215 # On the first time through, simply choose the node of highest degree. | |
216 if i == 0: | |
217 node = max(G, key=G.degree) | |
218 yield node | |
219 # Add the color 0 to the distinct colors set for each | |
220 # neighbors of that node. | |
221 for v in G[node]: | |
222 distinct_colors[v].add(0) | |
223 else: | |
224 # Compute the maximum saturation and the set of nodes that | |
225 # achieve that saturation. | |
226 saturation = { | |
227 v: len(c) for v, c in distinct_colors.items() if v not in colors | |
228 } | |
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 smallest-last 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 built-in 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 * ``'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 ``saturation_largest_first`` and ``independent_set`` | |
297 do not work with interchange. Furthermore, if you use | |
298 interchange with your own strategy function, you cannot rely | |
299 on the values in the ``colors`` argument. | |
300 | |
301 Returns | |
302 ------- | |
303 A dictionary with keys representing nodes and values representing | |
304 corresponding coloring. | |
305 | |
306 Examples | |
307 -------- | |
308 >>> G = nx.cycle_graph(4) | |
309 >>> d = nx.coloring.greedy_color(G, strategy="largest_first") | |
310 >>> d in [{0: 0, 1: 1, 2: 0, 3: 1}, {0: 1, 1: 0, 2: 1, 3: 0}] | |
311 True | |
312 | |
313 Raises | |
314 ------ | |
315 NetworkXPointlessConcept | |
316 If ``strategy`` is ``saturation_largest_first`` or | |
317 ``independent_set`` and ``interchange`` is ``True``. | |
318 | |
319 References | |
320 ---------- | |
321 .. [1] Adrian Kosowski, and Krzysztof Manuszewski, | |
322 Classical Coloring of Graphs, Graph Colorings, 2-19, 2004. | |
323 ISBN 0-8218-3458-4. | |
324 .. [2] David W. Matula, and Leland L. Beck, "Smallest-last | |
325 ordering and clustering and graph coloring algorithms." *J. ACM* 30, | |
326 3 (July 1983), 417–427. <https://doi.org/10.1145/2402.322385> | |
327 .. [3] Maciej M. Sysło, Marsingh Deo, Janusz S. Kowalik, | |
328 Discrete Optimization Algorithms with Pascal Programs, 415-424, 1983. | |
329 ISBN 0-486-45353-7. | |
330 | |
331 """ | |
332 if len(G) == 0: | |
333 return {} | |
334 # Determine the strategy provided by the caller. | |
335 strategy = STRATEGIES.get(strategy, strategy) | |
336 if not callable(strategy): | |
337 raise nx.NetworkXError( | |
338 "strategy must be callable or a valid string. " f"{strategy} not valid." | |
339 ) | |
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 independent_set" | |
345 raise nx.NetworkXPointlessConcept(msg) | |
346 if strategy is strategy_saturation_largest_first: | |
347 msg = "interchange cannot be used with" " saturation_largest_first" | |
348 raise nx.NetworkXPointlessConcept(msg) | |
349 colors = {} | |
350 nodes = strategy(G, colors) | |
351 if interchange: | |
352 return _interchange.greedy_coloring_with_interchange(G, nodes) | |
353 for u in nodes: | |
354 # Set to keep track of colors of neighbours | |
355 neighbour_colors = {colors[v] for v in G[u] if v in colors} | |
356 # Find the first unused color. | |
357 for color in itertools.count(): | |
358 if color not in neighbour_colors: | |
359 break | |
360 # Assign the new color to the current node. | |
361 colors[u] = color | |
362 return colors |