### view env/lib/python3.9/site-packages/networkx/algorithms/coloring/greedy_coloring.py @ 0:4f3585e2f14bdraftdefaulttip

author shellac Mon, 22 Mar 2021 18:12:50 +0000
line wrap: on
line source
```
"""
Greedy graph coloring using various strategies.
"""
from collections import defaultdict, deque
import itertools

import networkx as nx
from networkx.utils import arbitrary_element
from networkx.utils import py_random_state
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",
]

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)

@py_random_state(2)
def strategy_random_sequential(G, colors, seed=None):
"""Returns a random permutation of the nodes of ``G`` as a list.

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

seed : integer, random_state, or None (default)
Indicator of random number generation state.
See :ref:`Randomness<randomness>`.
"""
nodes = list(G)
seed.shuffle(nodes)
return nodes

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 \$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()
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():
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]

# 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)
remaining -= set(G[v]) | {v}
return result

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
yield from nodes

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

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")

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")

def strategy_connected_sequential(G, colors, traversal="bfs"):
"""Returns an iterable over nodes in ``G`` in the order given by a

``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_components(G):
source = arbitrary_element(component)
# Yield the source node, then all the nodes in the specified
# traversal order.
yield source
for (_, end) in traverse(G.subgraph(component), source):
yield end

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]:
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]:

#: 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,
}

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 _, and smallest-last is based on
_.

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)
* ``'saturation_largest_first'``
* ``'DSATUR'`` (alias for the previous strategy)

interchange: bool
Will use the color interchange algorithm described by _ if set
to ``True``.

Note that ``saturation_largest_first`` and ``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 ``saturation_largest_first`` or
``independent_set`` and ``interchange`` is ``True``.

References
----------
..  Adrian Kosowski, and Krzysztof Manuszewski,
Classical Coloring of Graphs, Graph Colorings, 2-19, 2004.
ISBN 0-8218-3458-4.
..  David W. Matula, and Leland L. Beck, "Smallest-last
ordering and clustering and graph coloring algorithms." *J. ACM* 30,
3 (July 1983), 417–427. <https://doi.org/10.1145/2402.322385>
..  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. " f"{strategy} not valid."
)
# 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 independent_set"
raise nx.NetworkXPointlessConcept(msg)
if strategy is strategy_saturation_largest_first:
msg = "interchange cannot be used with" " 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
```