text: # -*- 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 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
          for v in nodes:
              yield v
  
  
  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_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
  
  
  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)
         * ``'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. <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. '
                                 '{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
  