Algoritmus Welsh-Powell je grafový algoritmus sloužící k hornímu odhadu chromatického čísla grafu. Jeho vstupem je graf G definovaný jako dvě množiny - uzly V a hrany E. Výstupem je horní odhad, takže přesná hodnota chromatického čísla je vždy menší nebo rovna vypočítané hodnotě.

Kroky algoritmu

  • Inicializuj pracovní seznam S = V a počítadlo i = 1.
  • Dokud není seznam S prázdný, opakuj:
    • Seřaď uzly v seznamu S do nerostoucí posloupnosti podle jejich stupně.
    • Obarvi první uzel v posloupnosti barvou číslo i a stejnou barvu postupně přiřaď i všem dalším uzlům, které s tímto uzlem nesousedí.
    • Ze seznamu S odeber všechny právě obarvené uzly.
    • Inkrementuj počítadlo i.

Příklad

Inicializace

Na začátku jsou všechny uzly neobarvené (v závorkách jsou uvedeny stupně uzlů). Seznam S je naplněn všemi uzly a seřazen do nerostoucí posloupnosti.

Seznam SC(5)E(4)F(3)B(2)G(2)A(1)D(1)
diagram

Krok 1

V první iteraci je vybrán první uzel (C) a spolu s dalšími uzly, které s ním nesousedí (G), je obarven barvou číslo 1 (modrá). Poté jsou obarvené uzly odebrány ze seznamu S.

Seznam SE(4)F(3)B(2)A(1)D(1)
diagram

Krok 2

Seznam S není prázdný, algoritmus pokračuje dál. Ve druhé iteraci je opět vybrán první uzel (E) a spolu s dalšími uzly, které s ním nesousedí (A, D), je obarven barvou číslo 2 (žlutá). Poté jsou obarvené uzly odebrány ze seznamu S.

Seznam SF(3)B(2)
diagram

Krok 3

Seznam S stále není prázdný, algoritmus pokračuje dál. Ve třetí iteraci je opět vybrán první uzel (F) a spolu s dalšími uzly, které s ním nesousedí (B), je obarven barvou číslo 3 (zelená). Poté jsou obarvené uzly odebrány ze seznamu S.

Seznam S(prázdný)
diagram

Krok 4

Seznam S je prázdný, algoritmus končí. Celkem byly použity tři barvy, chromatické číslo grafu je tedy menší nebo rovno třem.

Implementace

package graph.algorithm.color;

import graph.model.Graph;

import java.util.*;
import java.util.stream.Collectors;

/**
 * Implementation of Welsh-Powell`s algorithm.
 */
public final class WelshPowell {
    /**
     * Calculate the upper-bound approximate of graph color number.
     * @param graph given graph
     * @return map of node to its color index (starting from 0)
     */
    public static <N> Map<N, Integer> colorByWelshPowell(final Graph<N, ?> graph) {
        final Set<N> allNodes = graph.nodes();
        final int n = allNodes.size();
        final Map<N, Integer> colors = new HashMap<>(n);
        final List<N> sortedNodesToColor = new ArrayList<>(n);

        sortedNodesToColor.addAll(allNodes
                .stream()
                .sorted(Comparator.<N>comparingInt(node -> graph.adjacent(node).size()).reversed())
                .collect(Collectors.toList()));

        int color = 0;

        while (!sortedNodesToColor.isEmpty()) {
            final Set<N> thisStepColoredNodes = new LinkedHashSet<>();

            // take the first node

            final N first = sortedNodesToColor.get(0);
            thisStepColoredNodes.add(first);

            // find all nodes not connected with that node

            sortedNodesToColor
                    .stream()
                    .filter(node -> first != node)
                    .filter(node -> !graph.isAdjacent(first, node))
                    .forEach(thisStepColoredNodes::add);

            // color them by the next available color

            final int nextColor = color++;
            thisStepColoredNodes.forEach(node -> colors.put(node, nextColor));

            // remove them from queue

            sortedNodesToColor.removeAll(thisStepColoredNodes);
        }

        return colors;
    }
}

Zdrojový kód Pokrytí testy

Reference

  • Dr. Jeanne Stynes, Computer Science