# -*- coding: utf-8 -*-
# Copyright (C) 2014 by
# Christian Olsson <chro@itu.dk>
# Jan Aagaard Meier <jmei@itu.dk>
# Henrik Haugbølle <hhau@itu.dk>
# Arya McCarthy <admccarthy@smu.edu>
# All rights reserved.
# BSD license.
"""
Greedy graph coloring using various strategies.
"""
from collections import defaultdict, deque
import itertools
import random
import networkx as nx
from networkx.utils import arbitrary_element
from . import greedy_coloring_with_interchange as _interchange
__all__ = ['greedy_color', 'strategy_connected_sequential',
'strategy_connected_sequential_bfs',
'strategy_connected_sequential_dfs', 'strategy_independent_set',
'strategy_largest_first', 'strategy_random_sequential',
'strategy_saturation_largest_first', 'strategy_smallest_last']
[docs]def strategy_largest_first(G, colors):
"""Returns a list of the nodes of ``G`` in decreasing order by
degree.
``G`` is a NetworkX graph. ``colors`` is ignored.
"""
return sorted(G, key=G.degree, reverse=True)
[docs]def strategy_random_sequential(G, colors):
"""Returns a random permutation of the nodes of ``G`` as a list.
``G`` is a NetworkX graph. ``colors`` is ignored.
"""
nodes = list(G)
random.shuffle(nodes)
return nodes
[docs]def strategy_smallest_last(G, colors):
"""Returns a deque of the nodes of ``G``, "smallest" last.
Specifically, the degrees of each node are tracked in a bucket queue.
From this, the node of minimum degree is repeatedly popped from the
graph, updating its neighbors' degrees.
``G`` is a NetworkX graph. ``colors`` is ignored.
This implementation of the strategy runs in :math:`O(n + m)` time
(ignoring polylogarithmic factors), where *n* is the number of nodes
and *m* is the number of edges.
This strategy is related to :func:`strategy_independent_set`: if we
interpret each node removed as an independent set of size one, then
this strategy chooses an independent set of size one instead of a
maximal independent set.
"""
H = G.copy(with_data=False)
result = deque()
# Build initial degree list (i.e. the bucket queue data structure)
degrees = defaultdict(set) # set(), for fast random-access removals
lbound = float('inf')
for node, d in H.degree():
degrees[d].add(node)
lbound = min(lbound, d) # Lower bound on min-degree.
def find_min_degree():
# Save time by starting the iterator at `lbound`, not 0.
# The value that we find will be our new `lbound`, which we set later.
return next(d for d in itertools.count(lbound) if d in degrees)
for _ in G:
# Pop a min-degree node and add it to the list.
min_degree = find_min_degree()
u = degrees[min_degree].pop()
if not degrees[min_degree]: # Clean up the degree list.
del degrees[min_degree]
result.appendleft(u)
# Update degrees of removed node's neighbors.
for v in H[u]:
degree = H.degree(v)
degrees[degree].remove(v)
if not degrees[degree]: # Clean up the degree list.
del degrees[degree]
degrees[degree - 1].add(v)
# Finally, remove the node.
H.remove_node(u)
lbound = min_degree - 1 # Subtract 1 in case of tied neighbors.
return result
def _maximal_independent_set(G):
"""Returns a maximal independent set of nodes in ``G`` by repeatedly
choosing an independent node of minimum degree (with respect to the
subgraph of unchosen nodes).
"""
result = set()
remaining = set(G)
while remaining:
G = G.subgraph(remaining)
v = min(remaining, key=G.degree)
result.add(v)
remaining -= set(G[v]) | {v}
return result
[docs]def strategy_independent_set(G, colors):
"""Uses a greedy independent set removal strategy to determine the
colors.
This function updates ``colors`` **in-place** and return ``None``,
unlike the other strategy functions in this module.
This algorithm repeatedly finds and removes a maximal independent
set, assigning each node in the set an unused color.
``G`` is a NetworkX graph.
This strategy is related to :func:`strategy_smallest_last`: in that
strategy, an independent set of size one is chosen at each step
instead of a maximal independent set.
"""
remaining_nodes = set(G)
while len(remaining_nodes) > 0:
nodes = _maximal_independent_set(G.subgraph(remaining_nodes))
remaining_nodes -= nodes
for v in nodes:
yield v
[docs]def strategy_connected_sequential_bfs(G, colors):
"""Returns an iterable over nodes in ``G`` in the order given by a
breadth-first traversal.
The generated sequence has the property that for each node except
the first, at least one neighbor appeared earlier in the sequence.
``G`` is a NetworkX graph. ``colors`` is ignored.
"""
return strategy_connected_sequential(G, colors, 'bfs')
[docs]def strategy_connected_sequential_dfs(G, colors):
"""Returns an iterable over nodes in ``G`` in the order given by a
depth-first traversal.
The generated sequence has the property that for each node except
the first, at least one neighbor appeared earlier in the sequence.
``G`` is a NetworkX graph. ``colors`` is ignored.
"""
return strategy_connected_sequential(G, colors, 'dfs')
[docs]def strategy_connected_sequential(G, colors, traversal='bfs'):
"""Returns an iterable over nodes in ``G`` in the order given by a
breadth-first or depth-first traversal.
``traversal`` must be one of the strings ``'dfs'`` or ``'bfs'``,
representing depth-first traversal or breadth-first traversal,
respectively.
The generated sequence has the property that for each node except
the first, at least one neighbor appeared earlier in the sequence.
``G`` is a NetworkX graph. ``colors`` is ignored.
"""
if traversal == 'bfs':
traverse = nx.bfs_edges
elif traversal == 'dfs':
traverse = nx.dfs_edges
else:
raise nx.NetworkXError("Please specify one of the strings 'bfs' or"
" 'dfs' for connected sequential ordering")
for component in nx.connected_component_subgraphs(G):
source = arbitrary_element(component)
# Yield the source node, then all the nodes in the specified
# traversal order.
yield source
for (_, end) in traverse(component, source):
yield end
[docs]def strategy_saturation_largest_first(G, colors):
"""Iterates over all the nodes of ``G`` in "saturation order" (also
known as "DSATUR").
``G`` is a NetworkX graph. ``colors`` is a dictionary mapping nodes of
``G`` to colors, for those nodes that have already been colored.
"""
distinct_colors = {v: set() for v in G}
for i in range(len(G)):
# On the first time through, simply choose the node of highest degree.
if i == 0:
node = max(G, key=G.degree)
yield node
# Add the color 0 to the distinct colors set for each
# neighbors of that node.
for v in G[node]:
distinct_colors[v].add(0)
else:
# Compute the maximum saturation and the set of nodes that
# achieve that saturation.
saturation = {v: len(c) for v, c in distinct_colors.items()
if v not in colors}
# Yield the node with the highest saturation, and break ties by
# degree.
node = max(saturation, key=lambda v: (saturation[v], G.degree(v)))
yield node
# Update the distinct color sets for the neighbors.
color = colors[node]
for v in G[node]:
distinct_colors[v].add(color)
#: Dictionary mapping name of a strategy as a string to the strategy function.
STRATEGIES = {
'largest_first': strategy_largest_first,
'random_sequential': strategy_random_sequential,
'smallest_last': strategy_smallest_last,
'independent_set': strategy_independent_set,
'connected_sequential_bfs': strategy_connected_sequential_bfs,
'connected_sequential_dfs': strategy_connected_sequential_dfs,
'connected_sequential': strategy_connected_sequential,
'saturation_largest_first': strategy_saturation_largest_first,
'DSATUR': strategy_saturation_largest_first,
}
[docs]def greedy_color(G, strategy='largest_first', interchange=False):
"""Color a graph using various strategies of greedy graph coloring.
Attempts to color a graph using as few colors as possible, where no
neighbours of a node can have same color as the node itself. The
given strategy determines the order in which nodes are colored.
The strategies are described in [1]_, and smallest-last is based on
[2]_.
Parameters
----------
G : NetworkX graph
strategy : string or function(G, colors)
A function (or a string representing a function) that provides
the coloring strategy, by returning nodes in the ordering they
should be colored. ``G`` is the graph, and ``colors`` is a
dictionary of the currently assigned colors, keyed by nodes. The
function must return an iterable over all the nodes in ``G``.
If the strategy function is an iterator generator (that is, a
function with ``yield`` statements), keep in mind that the
``colors`` dictionary will be updated after each ``yield``, since
this function chooses colors greedily.
If ``strategy`` is a string, it must be one of the following,
each of which represents one of the built-in strategy functions.
* ``'largest_first'``
* ``'random_sequential'``
* ``'smallest_last'``
* ``'independent_set'``
* ``'connected_sequential_bfs'``
* ``'connected_sequential_dfs'``
* ``'connected_sequential'`` (alias for the previous strategy)
* ``'strategy_saturation_largest_first'``
* ``'DSATUR'`` (alias for the previous strategy)
interchange: bool
Will use the color interchange algorithm described by [3]_ if set
to ``True``.
Note that ``strategy_saturation_largest_first`` and
``strategy_independent_set`` do not work with
interchange. Furthermore, if you use interchange with your own
strategy function, you cannot rely on the values in the
``colors`` argument.
Returns
-------
A dictionary with keys representing nodes and values representing
corresponding coloring.
Examples
--------
>>> G = nx.cycle_graph(4)
>>> d = nx.coloring.greedy_color(G, strategy='largest_first')
>>> d in [{0: 0, 1: 1, 2: 0, 3: 1}, {0: 1, 1: 0, 2: 1, 3: 0}]
True
Raises
------
NetworkXPointlessConcept
If ``strategy`` is ``strategy_saturation_largest_first`` or
``strategy_independent_set`` and ``interchange`` is ``True``.
References
----------
.. [1] Adrian Kosowski, and Krzysztof Manuszewski,
Classical Coloring of Graphs, Graph Colorings, 2-19, 2004.
ISBN 0-8218-3458-4.
.. [2] David W. Matula, and Leland L. Beck, "Smallest-last
ordering and clustering and graph coloring algorithms." *J. ACM* 30,
3 (July 1983), 417–427. <http://dx.doi.org/10.1145/2402.322385>
.. [3] Maciej M. Sysło, Marsingh Deo, Janusz S. Kowalik,
Discrete Optimization Algorithms with Pascal Programs, 415-424, 1983.
ISBN 0-486-45353-7.
"""
if len(G) == 0:
return {}
# Determine the strategy provided by the caller.
strategy = STRATEGIES.get(strategy, strategy)
if not callable(strategy):
raise nx.NetworkXError('strategy must be callable or a valid string. '
'{0} not valid.'.format(strategy))
# Perform some validation on the arguments before executing any
# strategy functions.
if interchange:
if strategy is strategy_independent_set:
msg = 'interchange cannot be used with strategy_independent_set'
raise nx.NetworkXPointlessConcept(msg)
if strategy is strategy_saturation_largest_first:
msg = ('interchange cannot be used with'
' strategy_saturation_largest_first')
raise nx.NetworkXPointlessConcept(msg)
colors = {}
nodes = strategy(G, colors)
if interchange:
return _interchange.greedy_coloring_with_interchange(G, nodes)
for u in nodes:
# Set to keep track of colors of neighbours
neighbour_colors = {colors[v] for v in G[u] if v in colors}
# Find the first unused color.
for color in itertools.count():
if color not in neighbour_colors:
break
# Assign the new color to the current node.
colors[u] = color
return colors