Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / coloring / greedy_coloring.py @ 5cef0f13

History | View | Annotate | Download (12.9 KB)

1
# -*- coding: utf-8 -*-
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 random-access 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 min-degree.
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 min-degree 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`` **in-place** 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
    breadth-first 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
    depth-first 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
    breadth-first or depth-first traversal.
179

180
    ``traversal`` must be one of the strings ``'dfs'`` or ``'bfs'``,
181
    representing depth-first traversal or breadth-first 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 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
       * ``'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, 2-19, 2004.
324
       ISBN 0-8218-3458-4.
325
    .. [2] David W. Matula, and Leland L. Beck, "Smallest-last
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, 415-424, 1983.
330
       ISBN 0-486-45353-7.
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