Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

Source code for networkx.algorithms.coloring.greedy_coloring

# -*- coding: utf-8 -*-
"""
Greedy graph coloring using various strategies.
"""
#    Copyright (C) 2014 by
#    Christian Olsson <chro@itu.dk>
#    Jan Aagaard Meier <jmei@itu.dk>
#    Henrik Haugbølle <hhau@itu.dk>
#    All rights reserved.
#    BSD license.
import networkx as nx
import random
import itertools
from . import greedy_coloring_with_interchange as _interchange

__author__ = "\n".join(["Christian Olsson <chro@itu.dk>",
                        "Jan Aagaard Meier <jmei@itu.dk>",
                        "Henrik Haugbølle <hhau@itu.dk>"])
__all__ = [
    'greedy_color',
    'strategy_largest_first',
    'strategy_random_sequential',
    'strategy_smallest_last',
    'strategy_independent_set',
    'strategy_connected_sequential',
    'strategy_connected_sequential_dfs',
    'strategy_connected_sequential_bfs',
    'strategy_saturation_largest_first'
]


def min_degree_node(G):
    return min(G, key=G.degree)


def max_degree_node(G):
    return max(G, key=G.degree)


def strategy_largest_first(G, colors):
    """
    Largest first (lf) ordering. Ordering the nodes by largest degree
    first.
    """
    nodes = G.nodes()
    nodes.sort(key=lambda node: -G.degree(node))

    return nodes


def strategy_random_sequential(G, colors):
    """
    Random sequential (RS) ordering. Scrambles nodes into random ordering.
    """
    nodes = G.nodes()
    random.shuffle(nodes)

    return nodes


def strategy_smallest_last(G, colors):
    """
    Smallest last (sl). Picking the node with smallest degree first,
    subtracting it from the graph, and starting over with the new smallest
    degree node. When the graph is empty, the reverse ordering of the one
    built is returned.
    """
    len_g = len(G)
    available_g = G.copy()
    nodes = [None] * len_g

    for i in range(len_g):
        node = min_degree_node(available_g)

        available_g.remove_node(node)
        nodes[len_g - i - 1] = node

    return nodes


def strategy_independent_set(G, colors):
    """
    Greedy independent set ordering (GIS). Generates a maximal independent
    set of nodes, and assigns color C to all nodes in this set. This set
    of nodes is now removed from the graph, and the algorithm runs again.
    """
    len_g = len(G)
    no_colored = 0
    k = 0

    uncolored_g = G.copy()
    while no_colored < len_g:  # While there are uncolored nodes
        available_g = uncolored_g.copy()

        while len(available_g):  # While there are still nodes available
            node = min_degree_node(available_g)
            colors[node] = k  # assign color to values

            no_colored += 1
            uncolored_g.remove_node(node)
            # Remove node and its neighbors from available
            available_g.remove_nodes_from(available_g.neighbors(node) + [node])
        k += 1
    return None


def strategy_connected_sequential_bfs(G, colors):
    """
    Connected sequential ordering (CS). Yield nodes in such an order, that
    each node, except the first one, has at least one neighbour in the
    preceeding sequence. The sequence is generated using BFS)
    """
    return strategy_connected_sequential(G, colors, 'bfs')


def strategy_connected_sequential_dfs(G, colors):
    """
    Connected sequential ordering (CS). Yield nodes in such an order, that
    each node, except the first one, has at least one neighbour in the
    preceeding sequence. The sequence is generated using DFS)
    """
    return strategy_connected_sequential(G, colors, 'dfs')


def strategy_connected_sequential(G, colors, traversal='bfs'):
    """
    Connected sequential ordering (CS). Yield nodes in such an order, that
    each node, except the first one, has at least one neighbour in the
    preceeding sequence. The sequence can be generated using both BFS and
    DFS search (using the strategy_connected_sequential_bfs and
    strategy_connected_sequential_dfs method). The default is bfs.
    """
    for component_graph in nx.connected_component_subgraphs(G):
        source = component_graph.nodes()[0]

        yield source  # Pick the first node as source

        if traversal == 'bfs':
            tree = nx.bfs_edges(component_graph, source)
        elif traversal == 'dfs':
            tree = nx.dfs_edges(component_graph, source)
        else:
            raise nx.NetworkXError(
                'Please specify bfs or dfs for connected sequential ordering')

        for (_, end) in tree:
            # Then yield nodes in the order traversed by either BFS or DFS
            yield end


def strategy_saturation_largest_first(G, colors):
    """
    Saturation largest first (SLF). Also known as degree saturation (DSATUR).
    """
    len_g = len(G)
    no_colored = 0
    distinct_colors = {}

    for node in G.nodes_iter():
        distinct_colors[node] = set()

    while no_colored != len_g:
        if no_colored == 0:
             # When sat. for all nodes is 0, yield the node with highest degree
            no_colored += 1
            node = max_degree_node(G)
            yield node
            for neighbour in G.neighbors_iter(node):
                distinct_colors[neighbour].add(0)
        else:
            highest_saturation = -1
            highest_saturation_nodes = []

            for node, distinct in distinct_colors.items():
                if node not in colors:  # If the node is not already colored
                    saturation = len(distinct)
                    if saturation > highest_saturation:
                        highest_saturation = saturation
                        highest_saturation_nodes = [node]
                    elif saturation == highest_saturation:
                        highest_saturation_nodes.append(node)

            if len(highest_saturation_nodes) == 1:
                node = highest_saturation_nodes[0]
            else:
                # Return the node with highest degree
                max_degree = -1
                max_node = None

                for node in highest_saturation_nodes:
                    degree = G.degree(node)
                    if degree > max_degree:
                        max_node = node
                        max_degree = degree

                node = max_node

            no_colored += 1
            yield node
            color = colors[node]
            for neighbour in G.neighbors_iter(node):
                distinct_colors[neighbour].add(color)


[docs]def greedy_color(G, strategy=strategy_largest_first, interchange=False): """Color a graph using various strategies of greedy graph coloring. The strategies are described in [1]_. 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. Parameters ---------- G : NetworkX graph strategy : function(G, colors) 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 dict of the currently assigned colors, keyed by nodes. You can pass your own ordering function, or use one of the built in: * strategy_largest_first * strategy_random_sequential * strategy_smallest_last * strategy_independent_set * strategy_connected_sequential_bfs * strategy_connected_sequential_dfs * strategy_connected_sequential (alias of strategy_connected_sequential_bfs) * strategy_saturation_largest_first (also known as DSATUR) interchange: bool Will use the color interchange algorithm described by [2]_ 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=nx.coloring.strategy_largest_first) >>> d in [{0: 0, 1: 1, 2: 0, 3: 1}, {0: 1, 1: 0, 2: 1, 3: 0}] True References ---------- .. [1] Adrian Kosowski, and Krzysztof Manuszewski, Classical Coloring of Graphs, Graph Colorings, 2-19, 2004. ISBN 0-8218-3458-4. .. [2] Maciej M. Syslo, Marsingh Deo, Janusz S. Kowalik, Discrete Optimization Algorithms with Pascal Programs, 415-424, 1983. ISBN 0-486-45353-7. """ colors = {} # dictionary to keep track of the colors of the nodes if len(G): if interchange and ( strategy == strategy_independent_set or strategy == strategy_saturation_largest_first): raise nx.NetworkXPointlessConcept( 'Interchange is not applicable for GIS and SLF') nodes = strategy(G, colors) if nodes: if interchange: return (_interchange .greedy_coloring_with_interchange(G, nodes)) else: for node in nodes: # set to keep track of colors of neighbours neighbour_colors = set() for neighbour in G.neighbors_iter(node): if neighbour in colors: neighbour_colors.add(colors[neighbour]) for color in itertools.count(): if color not in neighbour_colors: break # assign the node the newly found color colors[node] = color return colors