algorithm.py

# -*- coding: utf-8 -*-
"""
/***************************************************************************
 FiveColorMap
                                 A QGIS plugin
 This plugin colors each shape differently than its neighbors using five colors
 Generated by Plugin Builder: http://g-sherman.github.io/Qgis-Plugin-Builder/
                              -------------------
        begin                : 2018-05-20
        git sha              : $Format:%H$
        copyright            : (C) 2018 by Erik Shelley
        email                : erik@erikshelley.com
 ***************************************************************************/
"""
from collections import deque


class Node(object):

    def __init__(self, i, neighbors, component=[]):
        self.i          = i
        self.component  = component
        self.neighbors  = neighbors
        self.color      = None

    def colorize(self, c):
        self.color = c
        for node in self.component:
            node.colorize(c)

    def __len__(self):
        return len(self.neighbors)


class Graph(object):

    def __init__(self, inputGraph):
        self._nodes = {i: Node(i, neighbors) for i, neighbors in enumerate(inputGraph)}
        self._len = len(self._nodes)

    def remove(self, i):
        node = self._nodes[i]
        del self._nodes[i]
        for j in node.neighbors:
            self._nodes[j].neighbors.remove(i)
        return node

    def insert(self, node):
        i = node.i
        self._nodes[i] = node
        for j in node.neighbors:
            self._nodes[j].neighbors.add(i)

    def join(self, u, v):
        data = self._nodes
        i0 = self._len
        node = Node(i0, data[u].neighbors | data[v].neighbors, [data[u], data[v]])
        self.remove(u)
        self.remove(v)
        for i in node.neighbors:
            data[i].neighbors.add(i0)
        self._nodes[i0] = node
        self._len += 1
        return i0

    def split(self, i):
        for node in self._nodes[i].component:
            self.insert(node)
        self.remove(i)

    def node(self, i):
        return self._nodes[i]

    def nodes(self):
        return self._nodes

    def __len__(self):
        return len(self._nodes)


class FiveColor(object):

    def __init__(self, inputGraph):
        super(FiveColor, self).__init__()
        self.inputGraph = inputGraph

    def run(self):
        # Init
        graph = Graph(self.inputGraph)
        collapse = deque()

        # Reduce graph
        while len(graph) > 4:
            #done = float(len(graph)) / float(len(self.inputGraph))
            #self.notify_progress((1 - done) * 50)
            #progress_callback.emit((1 - done) * 50)
            #self.show_progress((1 - done) * 50)
            for i, node in graph.nodes().items():
                if len(node) <= 5:
                    break
            if len(node) > 5:
                raise RuntimeError("No node of degree at most 5.")
                #raise RuntimeError(tr("No node of degree at most 5."))
            graph.remove(i)
            joined = None
            if len(node) == 5:
                for i in node.neighbors:
                    for j in node.neighbors:
                        if i != j and i not in graph.node(j).neighbors:
                            joined = graph.join(i, j)
                            break
                    if joined is not None:
                        break
                if joined is None:
                    raise RuntimeError("Can't find two non adjacent node.")
                    #raise RuntimeError(tr("Can't find two non adjacent node."))
            collapse.append((node, joined))

        # Trivial color
        for c, node in enumerate(graph.nodes().values()):
            node.colorize(c)

        # Recontruct graph
        while len(collapse) > 0:
            #done = float(len(graph)) / float(len(self.inputGraph))
            #self.notify_progress(50 + (1 - done) * 50)
            #progress_callback.emit((1 - done) * 50)
            #self.show_progress((1 - done) * 50)
            node, joined = collapse.pop()
            if joined is not None:
                graph.split(joined)
            used = set([graph.node(i).color for i in node.neighbors])
            for c in range(5):
                if c not in used:
                    node.colorize(c)
                    break
            graph.insert(node)

        # Final result
        colorindex = [graph.node(i).color for i in range(len(graph))]
        return colorindex