coloring

Documentation

Overview

Package coloring provides graph coloring functions.

Example (Sudoku)

package main

import (
	"fmt"
	"log"

	"gonum.org/v1/gonum/graph/coloring"
	"gonum.org/v1/gonum/graph/graphs/gen"
	"gonum.org/v1/gonum/graph/simple"
)

// A hard sudoku problem graded at a level of difficulty, "not fun".
// https://dingo.sbs.arizona.edu/~sandiway/sudoku/examples.html
var grid = [9][9]int{
	{0, 2, 0 /**/, 0, 0, 0 /**/, 0, 0, 0},
	{0, 0, 0 /**/, 6, 0, 0 /**/, 0, 0, 3},
	{0, 7, 4 /**/, 0, 8, 0 /**/, 0, 0, 0},

	{0, 0, 0 /**/, 0, 0, 3 /**/, 0, 0, 2},
	{0, 8, 0 /**/, 0, 4, 0 /**/, 0, 1, 0},
	{6, 0, 0 /**/, 5, 0, 0 /**/, 0, 0, 0},

	{0, 0, 0 /**/, 0, 1, 0 /**/, 7, 8, 0},
	{5, 0, 0 /**/, 0, 0, 9 /**/, 0, 0, 0},
	{0, 0, 0 /**/, 0, 0, 0 /**/, 0, 4, 0},
}

func main() {
	g := simple.NewUndirectedGraph()

	// Build the sudoku board constraints.
	for i := 0; i < 9; i++ {
		gen.Complete(g, row(i))
		gen.Complete(g, col(i))
	}
	for r := 0; r < 3; r++ {
		for c := 0; c < 3; c++ {
			gen.Complete(g, block{r, c})
		}
	}

	// Add constraints for the digits.
	gen.Complete(g, gen.IDRange{First: -9, Last: -1})

	// Mark constraints onto the graph.
	for r, row := range &grid {
		for c, val := range &row {
			if val == 0 {
				continue
			}
			for i := 1; i <= 9; i++ {
				if i != val {
					g.SetEdge(simple.Edge{F: simple.Node(-i), T: simple.Node(id(r, c))})
				}
			}
		}
	}

	k, colors, err := coloring.DsaturExact(nil, g)
	if err != nil {
		log.Fatal(err)
	}
	if k != 9 {
		log.Fatalln("could not solve problem", k)
	}
	sets := coloring.Sets(colors)
	for r := 0; r < 9; r++ {
		if r != 0 && r%3 == 0 {
			fmt.Println()
		}
		for c := 0; c < 9; c++ {
			if c != 0 {
				fmt.Print(" ")
				if c%3 == 0 {
					fmt.Print(" ")
				}
			}
			got := -int(sets[colors[id(r, c)]][0])
			if want := grid[r][c]; want != 0 && got != want {
				log.Fatalf("mismatch at row=%d col=%d: %d != %d", r, c, got, want)
			}
			fmt.Print(got)
		}
		fmt.Println()
	}

}

// row is a gen.IDer that enumerates the IDs of graph
// nodes representing a row of cells of a sudoku board.
type row int

func (r row) Len() int       { return 9 }
func (r row) ID(i int) int64 { return id(int(r), i) }

// col is a gen.IDer that enumerates the IDs of graph
// nodes representing a column of cells of a sudoku board.
type col int

func (c col) Len() int       { return 9 }
func (c col) ID(i int) int64 { return id(i, int(c)) }

// block is a gen.IDer that enumerates the IDs of graph
// nodes representing a 3×3 block of cells of a sudoku board.
type block struct {
	r, c int
}

func (b block) Len() int { return 9 }
func (b block) ID(i int) int64 {
	return id(b.r*3, b.c*3) + int64(i%3) + int64(i/3)*9
}

// id returns the graph node ID of a cell in a sudoku board.
func id(row, col int) int64 {
	return int64(row*9 + col)
}

Output:


1 2 6  4 3 7  9 5 8
8 9 5  6 2 1  4 7 3
3 7 4  9 8 5  1 2 6

4 5 7  1 9 3  8 6 2
9 8 3  2 4 6  5 1 7
6 1 2  5 7 8  3 9 4

2 6 9  3 1 4  7 8 5
5 4 8  7 6 9  2 3 1
7 3 1  8 5 2  6 4 9

Index

• Variables
• func Dsatur(g graph.Undirected, partial map[int64]int) (k int, colors map[int64]int, err error)
• func DsaturExact(term Terminator, g graph.Undirected) (k int, colors map[int64]int, err error)
• func Randomized(g graph.Undirected, partial map[int64]int, src rand.Source) (k int, colors map[int64]int, err error)
• func RecursiveLargestFirst(g graph.Undirected) (k int, colors map[int64]int)
• func SanSegundo(g graph.Undirected, partial map[int64]int) (k int, colors map[int64]int, err error)
• func Sets(colors map[int64]int) map[int][]int64
• func WelshPowell(g graph.Undirected, partial map[int64]int) (k int, colors map[int64]int, err error)
• type Terminator

Examples

• Package (Sudoku)

Variables

var ErrInvalidPartialColoring = errors.New("coloring: invalid partial coloring")

ErrInvalidPartialColoring is returned when a partial coloring is provided for a graph with inadmissible color assignments.

Functions

func Dsatur

func Dsatur(g graph.Undirected, partial map[int64]int) (k int, colors map[int64]int, err error)

Dsatur returns an approximate minimal chromatic number of g and a corresponding vertex coloring using the heuristic Dsatur coloring algorithm. If a partial coloring is provided the coloring will be consistent with that partial coloring if possible. Otherwise Dsatur will return ErrInvalidPartialColoring. See Brélaz doi:10.1145/359094.359101 for details of the algorithm.

func DsaturExact

func DsaturExact(term Terminator, g graph.Undirected) (k int, colors map[int64]int, err error)

DsaturExact returns the exact minimal chromatic number of g and a corresponding vertex coloring using the branch-and-bound Dsatur coloring algorithm of Brélaz. If the provided terminator is cancelled or times out before completion, the terminator's reason for termination will be returned along with a potentially sub-optimal chromatic number and coloring. If term is nil, DsaturExact will run to completion. See Brélaz doi:10.1145/359094.359101 for details of the algorithm.

func Randomized

func Randomized(g graph.Undirected, partial map[int64]int, src rand.Source) (k int, colors map[int64]int, err error)

Randomized returns an approximate minimal chromatic number of g and a corresponding vertex coloring using a greedy coloring algorithm with a random node ordering. If src is non-nil it will be used as the random source, otherwise the global random source will be used. If a partial coloring is provided the coloring will be consistent with that partial coloring if possible. Otherwise Randomized will return ErrInvalidPartialColoring.

func RecursiveLargestFirst

func RecursiveLargestFirst(g graph.Undirected) (k int, colors map[int64]int)

RecursiveLargestFirst returns an approximate minimal chromatic number of g and a corresponding vertex coloring using the Recursive Largest First coloring algorithm. See Leighton doi:10.6028/jres.084.024 for details of the algorithm.

func SanSegundo

func SanSegundo(g graph.Undirected, partial map[int64]int) (k int, colors map[int64]int, err error)

SanSegundo returns an approximate minimal chromatic number of g and a corresponding vertex coloring using the PASS rule with a single run of a greedy coloring algorithm. If a partial coloring is provided the coloring will be consistent with that partial coloring if possible. Otherwise SanSegundo will return ErrInvalidPartialColoring. See San Segundo doi:10.1016/j.cor.2011.10.008 for details of the algorithm.

func Sets

func Sets(colors map[int64]int) map[int][]int64

Sets returns the mapping from colors to sets of node IDs. Each set of node IDs is sorted by ascending value.

func WelshPowell

func WelshPowell(g graph.Undirected, partial map[int64]int) (k int, colors map[int64]int, err error)

WelshPowell returns an approximate minimal chromatic number of g and a corresponding vertex coloring using the Welsh and Powell coloring algorithm. If a partial coloring is provided the coloring will be consistent with that partial coloring if possible. Otherwise WelshPowell will return ErrInvalidPartialColoring. See Welsh and Powell doi:10.1093/comjnl/10.1.85 for details of the algorithm.

Types

type Terminator

type Terminator interface {
	// Done returns a channel that is closed when work
	// should be terminated. Done may return nil if this
	// work can never be canceled.
	// Successive calls to Done should return the same value.
	Done() <-chan struct{}

	// If Done is not yet closed, Err returns nil.
	// If Done is closed, Err returns a non-nil error
	// explaining why.
	// After Err returns a non-nil error, successive
	// calls to Err should return the same error.
	Err() error
}

Terminator is a cancellation-only context type. A context.Context may be used as a Terminator.