diff env/lib/python3.9/site-packages/networkx/algorithms/coloring/greedy_coloring.py @ 0:4f3585e2f14b draft default tip

"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/env/lib/python3.9/site-packages/networkx/algorithms/coloring/greedy_coloring.py	Mon Mar 22 18:12:50 2021 +0000
@@ -0,0 +1,362 @@
+"""
+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():
+        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
+
+
+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
+    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")
+
+
+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
+    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_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]:
+                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,
+}
+
+
+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)
+       * ``'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 ``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
+    ----------
+    .. [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. <https://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. " 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