Graph colouring: Difference between revisions
Add C# implementation
(→{{Header|Python}}: Ex2 fix) |
(Add C# implementation) |
||
| (53 intermediate revisions by 16 users not shown) | |||
Line 1:
{{
Line 9:
by the two node numbers connected by the edge separated by a dash.
Edges define the nodes being connected. Only unconnected nodes ''need'' a separate
description.
For example,
Line 43:
* Integers may be used to denote different colours.
* Algorithm should do better than just assigning each vertex a separate colour. The idea is to minimise the number of colours used, although no algorithm short of exhaustive search for the minimum is known at present, (and exhaustive search is '''not''' a requirement).
* Show for each edge, the colours assigned on each vertex.
* Show the total number of nodes, edges, and colours used for each graph.
Line 118:
+-------------------+
</pre>
;Ex4:
This is the same graph, node naming, and edge order as Ex2 except some of the edges x-y are flipped to y-x.
This might alter the node order used in the greedy algorithm leading to differing numbers of colours.
1-6 7-1 8-1 5-2 2-7 2-8 3-5 6-3 3-8 4-5 4-6 4-7
<pre>
+-------------------------------------------------+
| |
| |
+-------------------+---------+ |
| | | |
+---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+
| 4 | --- | 5 | --- | 2 | --- | 7 | --- | 1 | --- | 6 | --- | 3 | --- | 8 |
+---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+
| | | | | |
+---------+-----------------------------+---------+ | |
| | | |
| | | |
+-----------------------------+-------------------+ |
| |
| |
+-----------------------------+
</pre>
;References:
* [[wp:Greedy coloring|Greedy coloring]] Wikipedia.
* [https://www.slideshare.net/PriyankJain26/graph-coloring-48222920 Graph Coloring : Greedy Algorithm & Welsh Powell Algorithm] by Priyank Jain.
=={{header|11l}}==
{{trans|Python}}
<syntaxhighlight lang="11l">F first_avail_int(data)
‘return lowest int 0... not in data’
V d = Set(data)
L(i) 0..
I i !C d
R i
F greedy_colour(name, connections)
DefaultDict[Int, [Int]] graph
L(connection) connections.split(‘ ’)
I ‘-’ C connection
V (n1, n2) = connection.split(‘-’).map(Int)
graph[n1].append(n2)
graph[n2].append(n1)
E
graph[Int(connection)] = [Int]()
// Greedy colourisation algo
V order = sorted(graph.keys())
[Int = Int] colour
V neighbours = graph
L(node) order
V used_neighbour_colours = neighbours[node].filter(nbr -> nbr C @colour).map(nbr -> @colour[nbr])
colour[node] = first_avail_int(used_neighbour_colours)
print("\n"name)
V canonical_edges = Set[(Int, Int)]()
L(n1, neighbours) sorted(graph.items())
I !neighbours.empty
L(n2) neighbours
V edge = tuple_sorted((n1, n2))
I edge !C canonical_edges
print(‘ #.-#.: Colour: #., #.’.format(n1, n2, colour[n1], colour[n2]))
canonical_edges.add(edge)
E
print(‘ #.: Colour: #.’.format(n1, colour[n1]))
V lc = Set(colour.values()).len
print(" #Nodes: #.\n #Edges: #.\n #Colours: #.".format(colour.len, canonical_edges.len, lc))
L(name, connections) [
(‘Ex1’, ‘0-1 1-2 2-0 3’),
(‘Ex2’, ‘1-6 1-7 1-8 2-5 2-7 2-8 3-5 3-6 3-8 4-5 4-6 4-7’),
(‘Ex3’, ‘1-4 1-6 1-8 3-2 3-6 3-8 5-2 5-4 5-8 7-2 7-4 7-6’),
(‘Ex4’, ‘1-6 7-1 8-1 5-2 2-7 2-8 3-5 6-3 3-8 4-5 4-6 4-7’)]
greedy_colour(name, connections)</syntaxhighlight>
{{out}}
<pre>
Ex1
0-1: Colour: 0, 1
0-2: Colour: 0, 2
1-2: Colour: 1, 2
3: Colour: 0
#Nodes: 4
#Edges: 3
#Colours: 3
Ex2
1-6: Colour: 0, 1
1-7: Colour: 0, 1
1-8: Colour: 0, 1
2-5: Colour: 0, 1
2-7: Colour: 0, 1
2-8: Colour: 0, 1
3-5: Colour: 0, 1
3-6: Colour: 0, 1
3-8: Colour: 0, 1
4-5: Colour: 0, 1
4-6: Colour: 0, 1
4-7: Colour: 0, 1
#Nodes: 8
#Edges: 12
#Colours: 2
Ex3
1-4: Colour: 0, 1
1-6: Colour: 0, 2
1-8: Colour: 0, 3
2-3: Colour: 0, 1
2-5: Colour: 0, 2
2-7: Colour: 0, 3
3-6: Colour: 1, 2
3-8: Colour: 1, 3
4-5: Colour: 1, 2
4-7: Colour: 1, 3
5-8: Colour: 2, 3
6-7: Colour: 2, 3
#Nodes: 8
#Edges: 12
#Colours: 4
Ex4
1-6: Colour: 0, 1
1-7: Colour: 0, 1
1-8: Colour: 0, 1
2-5: Colour: 0, 1
2-7: Colour: 0, 1
2-8: Colour: 0, 1
3-5: Colour: 0, 1
3-6: Colour: 0, 1
3-8: Colour: 0, 1
4-5: Colour: 0, 1
4-6: Colour: 0, 1
4-7: Colour: 0, 1
#Nodes: 8
#Edges: 12
#Colours: 2
</pre>
=={{header|C#}}==
{{trans|Java}}
<syntaxhighlight lang="C#">
using System;
using System.Collections.Generic;
using System.Linq;
public static class GraphColoring
{
public static void Main(string[] args)
{
Colorize("0-1 1-2 2-0 3");
Colorize("1-6 1-7 1-8 2-5 2-7 2-8 3-5 3-6 3-8 4-5 4-6 4-7");
Colorize("1-4 1-6 1-8 3-2 3-6 3-8 5-2 5-4 5-8 7-2 7-4 7-6");
Colorize("1-6 7-1 8-1 5-2 2-7 2-8 3-5 6-3 3-8 4-5 4-6 4-7");
}
private static void Colorize(string graphRepresentation)
{
List<Node> graph = InitializeGraph(graphRepresentation);
List<Node> nodes = new List<Node>(graph);
while (nodes.Any())
{
Node maxNode = nodes.OrderByDescending(n => n.Saturation).First();
maxNode.Color = MinColor(maxNode);
UpdateSaturation(maxNode, nodes);
nodes.Remove(maxNode);
}
Console.WriteLine("Graph: " + graphRepresentation);
Display(graph);
}
private static Color MinColor(Node node)
{
HashSet<Color> colorsUsed = ColorsUsed(node);
foreach (Color color in Enum.GetValues(typeof(Color)))
{
if (!colorsUsed.Contains(color))
{
return color;
}
}
return Color.NoColor;
}
private static HashSet<Color> ColorsUsed(Node node)
{
return new HashSet<Color>(node.Neighbours.Select(n => n.Color));
}
private static void UpdateSaturation(Node node, List<Node> nodes)
{
foreach (Node neighbour in node.Neighbours)
{
if (neighbour.Color == Color.NoColor)
{
neighbour.Saturation = ColorsUsed(neighbour).Count;
}
}
}
private static void Display(List<Node> nodes)
{
HashSet<Color> graphColors = new HashSet<Color>(nodes.Select(n => n.Color));
foreach (Node node in nodes)
{
Console.Write($"Node {node.Index}: color = {node.Color}");
if (node.Neighbours.Any())
{
var indexes = node.Neighbours.Select(n => n.Index).ToList();
Console.Write(new string(' ', 8 - node.Color.ToString().Length) + "neighbours = " + string.Join(", ", indexes));
}
Console.WriteLine();
}
Console.WriteLine("Number of colours used: " + graphColors.Count);
Console.WriteLine();
}
private static List<Node> InitializeGraph(string graphRepresentation)
{
SortedDictionary<int, Node> map = new SortedDictionary<int, Node>();
foreach (string element in graphRepresentation.Split(' '))
{
if (element.Contains("-"))
{
string[] parts = element.Split('-');
int index1 = int.Parse(parts[0]);
int index2 = int.Parse(parts[1]);
Node node1 = map.GetOrAdd(index1, () => new Node(index1));
Node node2 = map.GetOrAdd(index2, () => new Node(index2));
node1.Neighbours.Add(node2);
node2.Neighbours.Add(node1);
}
else
{
int index = int.Parse(element);
map.GetOrAdd(index, () => new Node(index));
}
}
return new List<Node>(map.Values);
}
public enum Color { Blue, Green, Red, Yellow, Cyan, Orange, NoColor }
public class Node
{
public Node(int index)
{
Index = index;
Color = Color.NoColor;
Neighbours = new HashSet<Node>();
}
public int Index { get; }
public int Saturation { get; set; }
public Color Color { get; set; }
public HashSet<Node> Neighbours { get; }
}
private static TValue GetOrAdd<TKey, TValue>(this IDictionary<TKey, TValue> dictionary, TKey key, Func<TValue> valueFactory)
{
if (!dictionary.TryGetValue(key, out TValue value))
{
value = valueFactory();
dictionary[key] = value;
}
return value;
}
}
</syntaxhighlight>
{{out}}
<pre>
Graph: 0-1 1-2 2-0 3
Node 0: color = Blue neighbours = 1, 2
Node 1: color = Green neighbours = 0, 2
Node 2: color = Red neighbours = 1, 0
Node 3: color = Blue
Number of colours used: 3
Graph: 1-6 1-7 1-8 2-5 2-7 2-8 3-5 3-6 3-8 4-5 4-6 4-7
Node 1: color = Blue neighbours = 6, 7, 8
Node 2: color = Blue neighbours = 5, 7, 8
Node 3: color = Blue neighbours = 5, 6, 8
Node 4: color = Blue neighbours = 5, 6, 7
Node 5: color = Green neighbours = 2, 3, 4
Node 6: color = Green neighbours = 1, 3, 4
Node 7: color = Green neighbours = 1, 2, 4
Node 8: color = Green neighbours = 1, 2, 3
Number of colours used: 2
Graph: 1-4 1-6 1-8 3-2 3-6 3-8 5-2 5-4 5-8 7-2 7-4 7-6
Node 1: color = Blue neighbours = 4, 6, 8
Node 2: color = Green neighbours = 3, 5, 7
Node 3: color = Blue neighbours = 2, 6, 8
Node 4: color = Green neighbours = 1, 5, 7
Node 5: color = Blue neighbours = 2, 4, 8
Node 6: color = Green neighbours = 1, 3, 7
Node 7: color = Blue neighbours = 2, 4, 6
Node 8: color = Green neighbours = 1, 3, 5
Number of colours used: 2
Graph: 1-6 7-1 8-1 5-2 2-7 2-8 3-5 6-3 3-8 4-5 4-6 4-7
Node 1: color = Blue neighbours = 6, 7, 8
Node 2: color = Blue neighbours = 5, 7, 8
Node 3: color = Blue neighbours = 5, 6, 8
Node 4: color = Blue neighbours = 5, 6, 7
Node 5: color = Green neighbours = 2, 3, 4
Node 6: color = Green neighbours = 1, 3, 4
Node 7: color = Green neighbours = 1, 2, 4
Node 8: color = Green neighbours = 1, 2, 3
Number of colours used: 2
</pre>
=={{header|C++}}==
Using the DSatur algorithm from https://en.wikipedia.org/wiki/DSatur
<syntaxhighlight lang="c++">
#include <algorithm>
#include <cstdint>
#include <iostream>
#include <map>
#include <set>
#include <sstream>
#include <string>
#include <unordered_set>
#include <vector>
const std::vector<std::string> all_colours = { "PINK", "ORANGE", "CYAN", "YELLOW", "RED", "GREEN", "BLUE" };
class Node {
public:
Node(const int32_t& aID, const int32_t& aSaturation, const std::string& aColour)
: id(aID), saturation(aSaturation), colour(aColour) {}
Node() : id(0), saturation(0), colour("NO_COLOUR") {}
int32_t id, saturation;
std::string colour;
bool excluded_from_search = false;
};
int main() {
std::map<int32_t, Node, decltype([](const int32_t& a, const int32_t& b){ return a < b; })> graph;
std::map<int32_t, std::set<int32_t, decltype([](const int32_t& a, const int32_t& b) { return a < b; })>,
decltype([](const int32_t& a, const int32_t& b) { return a < b; })> neighbours;
const std::vector<std::string> graph_representations = { "0-1 1-2 2-0 3",
"1-6 1-7 1-8 2-5 2-7 2-8 3-5 3-6 3-8 4-5 4-6 4-7",
"1-4 1-6 1-8 3-2 3-6 3-8 5-2 5-4 5-8 7-2 7-4 7-6",
"1-6 7-1 8-1 5-2 2-7 2-8 3-5 6-3 3-8 4-5 4-6 4-7" };
for ( const std::string& graph_representation : graph_representations ) {
graph.clear();
neighbours.clear();
std::stringstream stream(graph_representation);
std::string element;
while ( stream >> element ) {
if ( element.find("-") != std::string::npos ) {
const int32_t id1 = element[0] - '0';
const int32_t id2 = element[element.length() - 1] - '0';
if ( ! graph.contains(id1) ) {
graph[id1] = Node(id1, 0, "NO_COLOUR");
}
Node node1 = graph[id1];
if ( ! graph.contains(id2) ) {
graph[id2] = Node(id2, 0, "NO_COLOUR");
}
Node node2 = graph[id2];
neighbours[id1].emplace(id2);
neighbours[id2].emplace(id1);
} else {
const int32_t id = element[0] - '0';
if ( ! graph.contains(id) ) {
graph[id] = Node(id, 0, "NO_COLOUR");
}
}
}
for ( uint64_t i = 0; i < graph.size(); ++i ) {
int32_t max_node_id = -1;
int32_t max_saturation = -1;
for ( const auto& [key, value] : graph ) {
if ( ! value.excluded_from_search && value.saturation > max_saturation ) {
max_saturation = value.saturation;
max_node_id = key;
}
}
std::unordered_set<std::string> colours_used;
for ( const int32_t& neighbour : neighbours[max_node_id] ) {
colours_used.emplace(graph[neighbour].colour);
}
std::string min_colour;
for ( const std::string& colour : all_colours ) {
if ( ! colours_used.contains(colour) ) {
min_colour = colour;
}
}
graph[max_node_id].excluded_from_search = true;
graph[max_node_id].colour = min_colour;
for ( int32_t neighbour : neighbours[max_node_id] ) {
if ( graph[neighbour].colour == "NO_COLOUR" ) {
graph[neighbour].saturation = colours_used.size();
}
}
}
std::unordered_set<std::string> graph_colours;
for ( const auto& [key, value] : graph ) {
graph_colours.emplace(value.colour);
std::cout << "Node " << key << ": colour = " + value.colour;
if ( ! neighbours[key].empty() ) {
std::cout << std::string(8 - value.colour.length(), ' ') << "neighbours = ";
for ( const int32_t& neighbour : neighbours[key] ) {
std::cout << neighbour << " ";
}
}
std::cout << std::endl;
}
std::cout << "Number of colours used: " << graph_colours.size() << std::endl << std::endl;
}
}
</syntaxhighlight>
{{ out }}
<pre>
Node 0: colour = BLUE neighbours = 1 2
Node 1: colour = GREEN neighbours = 0 2
Node 2: colour = RED neighbours = 0 1
Node 3: colour = BLUE
Number of colours used: 3
Node 1: colour = BLUE neighbours = 6 7 8
Node 2: colour = BLUE neighbours = 5 7 8
Node 3: colour = BLUE neighbours = 5 6 8
Node 4: colour = BLUE neighbours = 5 6 7
Node 5: colour = GREEN neighbours = 2 3 4
Node 6: colour = GREEN neighbours = 1 3 4
Node 7: colour = GREEN neighbours = 1 2 4
Node 8: colour = GREEN neighbours = 1 2 3
Number of colours used: 2
Node 1: colour = BLUE neighbours = 4 6 8
Node 2: colour = GREEN neighbours = 3 5 7
Node 3: colour = BLUE neighbours = 2 6 8
Node 4: colour = GREEN neighbours = 1 5 7
Node 5: colour = BLUE neighbours = 2 4 8
Node 6: colour = GREEN neighbours = 1 3 7
Node 7: colour = BLUE neighbours = 2 4 6
Node 8: colour = GREEN neighbours = 1 3 5
Number of colours used: 2
Node 1: colour = BLUE neighbours = 6 7 8
Node 2: colour = BLUE neighbours = 5 7 8
Node 3: colour = BLUE neighbours = 5 6 8
Node 4: colour = BLUE neighbours = 5 6 7
Node 5: colour = GREEN neighbours = 2 3 4
Node 6: colour = GREEN neighbours = 1 3 4
Node 7: colour = GREEN neighbours = 1 2 4
Node 8: colour = GREEN neighbours = 1 2 3
Number of colours used: 2
</pre>
=={{header|Go}}==
As mentioned in the task description, there is no known ''efficient'' algorithm which can guarantee that a minimum number of colors is used for a given graph. The following uses both the so-called 'greedy' algorithm (as described [https://www.geeksforgeeks.org/graph-coloring-set-2-greedy-algorithm/ here]) and the Welsh-Powell algorithm (as described [http://mrsleblancsmath.pbworks.com/w/file/fetch/46119304/vertex%20coloring%20algorithm.pdf here]), suitably adjusted to the needs of this task.
The results are exactly the same for both algorithms. Whilst one would normally expect Welsh-Powell to give better results overall, the last three examples are not well suited to it as each node has exactly the same number of neighbors i.e. the valences are equal.
The results agree with the Python entry for examples 1 and 2 but, for example 3, Python gives 2 colors compared to my 4 and, for example 4, Python gives 3 colors compared to my 2.
<syntaxhighlight lang="go">package main
import (
"fmt"
"sort"
)
type graph struct {
nn int // number of nodes
st int // node numbering starts from
nbr [][]int // neighbor list for each node
}
type nodeval struct {
n int // number of node
v int // valence of node i.e. number of neighbors
}
func contains(s []int, n int) bool {
for _, e := range s {
if e == n {
return true
}
}
return false
}
func newGraph(nn, st int) graph {
nbr := make([][]int, nn)
return graph{nn, st, nbr}
}
// Note that this creates a single 'virtual' edge for an isolated node.
func (g graph) addEdge(n1, n2 int) {
n1, n2 = n1-g.st, n2-g.st // adjust to starting node number
g.nbr[n1] = append(g.nbr[n1], n2)
if n1 != n2 {
g.nbr[n2] = append(g.nbr[n2], n1)
}
}
// Uses 'greedy' algorithm.
func (g graph) greedyColoring() []int {
// create a slice with a color for each node, starting with color 0
cols := make([]int, g.nn) // all zero by default including the first node
for i := 1; i < g.nn; i++ {
cols[i] = -1 // mark all nodes after the first as having no color assigned (-1)
}
// create a bool slice to keep track of which colors are available
available := make([]bool, g.nn) // all false by default
// assign colors to all nodes after the first
for i := 1; i < g.nn; i++ {
// iterate through neighbors and mark their colors as available
for _, j := range g.nbr[i] {
if cols[j] != -1 {
available[cols[j]] = true
}
}
// find the first available color
c := 0
for ; c < g.nn; c++ {
if !available[c] {
break
}
}
cols[i] = c // assign it to the current node
// reset the neighbors' colors to unavailable
// before the next iteration
for _, j := range g.nbr[i] {
if cols[j] != -1 {
available[cols[j]] = false
}
}
}
return cols
}
// Uses Welsh-Powell algorithm.
func (g graph) wpColoring() []int {
// create nodeval for each node
nvs := make([]nodeval, g.nn)
for i := 0; i < g.nn; i++ {
v := len(g.nbr[i])
if v == 1 && g.nbr[i][0] == i { // isolated node
v = 0
}
nvs[i] = nodeval{i, v}
}
// sort the nodevals in descending order by valence
sort.Slice(nvs, func(i, j int) bool {
return nvs[i].v > nvs[j].v
})
// create colors slice with entries for each node
cols := make([]int, g.nn)
for i := range cols {
cols[i] = -1 // set all nodes to no color (-1) initially
}
currCol := 0 // start with color 0
for f := 0; f < g.nn-1; f++ {
h := nvs[f].n
if cols[h] != -1 { // already assigned a color
continue
}
cols[h] = currCol
// assign same color to all subsequent uncolored nodes which are
// not connected to a previous colored one
outer:
for i := f + 1; i < g.nn; i++ {
j := nvs[i].n
if cols[j] != -1 { // already colored
continue
}
for k := f; k < i; k++ {
l := nvs[k].n
if cols[l] == -1 { // not yet colored
continue
}
if contains(g.nbr[j], l) {
continue outer // node j is connected to an earlier colored node
}
}
cols[j] = currCol
}
currCol++
}
return cols
}
func main() {
fns := [](func(graph) []int){graph.greedyColoring, graph.wpColoring}
titles := []string{"'Greedy'", "Welsh-Powell"}
nns := []int{4, 8, 8, 8}
starts := []int{0, 1, 1, 1}
edges1 := [][2]int{{0, 1}, {1, 2}, {2, 0}, {3, 3}}
edges2 := [][2]int{{1, 6}, {1, 7}, {1, 8}, {2, 5}, {2, 7}, {2, 8},
{3, 5}, {3, 6}, {3, 8}, {4, 5}, {4, 6}, {4, 7}}
edges3 := [][2]int{{1, 4}, {1, 6}, {1, 8}, {3, 2}, {3, 6}, {3, 8},
{5, 2}, {5, 4}, {5, 8}, {7, 2}, {7, 4}, {7, 6}}
edges4 := [][2]int{{1, 6}, {7, 1}, {8, 1}, {5, 2}, {2, 7}, {2, 8},
{3, 5}, {6, 3}, {3, 8}, {4, 5}, {4, 6}, {4, 7}}
for j, fn := range fns {
fmt.Println("Using the", titles[j], "algorithm:\n")
for i, edges := range [][][2]int{edges1, edges2, edges3, edges4} {
fmt.Println(" Example", i+1)
g := newGraph(nns[i], starts[i])
for _, e := range edges {
g.addEdge(e[0], e[1])
}
cols := fn(g)
ecount := 0 // counts edges
for _, e := range edges {
if e[0] != e[1] {
fmt.Printf(" Edge %d-%d -> Color %d, %d\n", e[0], e[1],
cols[e[0]-g.st], cols[e[1]-g.st])
ecount++
} else {
fmt.Printf(" Node %d -> Color %d\n", e[0], cols[e[0]-g.st])
}
}
maxCol := 0 // maximum color number used
for _, col := range cols {
if col > maxCol {
maxCol = col
}
}
fmt.Println(" Number of nodes :", nns[i])
fmt.Println(" Number of edges :", ecount)
fmt.Println(" Number of colors :", maxCol+1)
fmt.Println()
}
}
}</syntaxhighlight>
{{out}}
<pre>
Using the 'Greedy' algorithm:
Example 1
Edge 0-1 -> Color 0, 1
Edge 1-2 -> Color 1, 2
Edge 2-0 -> Color 2, 0
Node 3 -> Color 0
Number of nodes : 4
Number of edges : 3
Number of colors : 3
Example 2
Edge 1-6 -> Color 0, 1
Edge 1-7 -> Color 0, 1
Edge 1-8 -> Color 0, 1
Edge 2-5 -> Color 0, 1
Edge 2-7 -> Color 0, 1
Edge 2-8 -> Color 0, 1
Edge 3-5 -> Color 0, 1
Edge 3-6 -> Color 0, 1
Edge 3-8 -> Color 0, 1
Edge 4-5 -> Color 0, 1
Edge 4-6 -> Color 0, 1
Edge 4-7 -> Color 0, 1
Number of nodes : 8
Number of edges : 12
Number of colors : 2
Example 3
Edge 1-4 -> Color 0, 1
Edge 1-6 -> Color 0, 2
Edge 1-8 -> Color 0, 3
Edge 3-2 -> Color 1, 0
Edge 3-6 -> Color 1, 2
Edge 3-8 -> Color 1, 3
Edge 5-2 -> Color 2, 0
Edge 5-4 -> Color 2, 1
Edge 5-8 -> Color 2, 3
Edge 7-2 -> Color 3, 0
Edge 7-4 -> Color 3, 1
Edge 7-6 -> Color 3, 2
Number of nodes : 8
Number of edges : 12
Number of colors : 4
Example 4
Edge 1-6 -> Color 0, 1
Edge 7-1 -> Color 1, 0
Edge 8-1 -> Color 1, 0
Edge 5-2 -> Color 1, 0
Edge 2-7 -> Color 0, 1
Edge 2-8 -> Color 0, 1
Edge 3-5 -> Color 0, 1
Edge 6-3 -> Color 1, 0
Edge 3-8 -> Color 0, 1
Edge 4-5 -> Color 0, 1
Edge 4-6 -> Color 0, 1
Edge 4-7 -> Color 0, 1
Number of nodes : 8
Number of edges : 12
Number of colors : 2
Using the Welsh-Powell algorithm:
Example 1
Edge 0-1 -> Color 0, 1
Edge 1-2 -> Color 1, 2
Edge 2-0 -> Color 2, 0
Node 3 -> Color 0
Number of nodes : 4
Number of edges : 3
Number of colors : 3
Example 2
Edge 1-6 -> Color 0, 1
Edge 1-7 -> Color 0, 1
Edge 1-8 -> Color 0, 1
Edge 2-5 -> Color 0, 1
Edge 2-7 -> Color 0, 1
Edge 2-8 -> Color 0, 1
Edge 3-5 -> Color 0, 1
Edge 3-6 -> Color 0, 1
Edge 3-8 -> Color 0, 1
Edge 4-5 -> Color 0, 1
Edge 4-6 -> Color 0, 1
Edge 4-7 -> Color 0, 1
Number of nodes : 8
Number of edges : 12
Number of colors : 2
Example 3
Edge 1-4 -> Color 0, 1
Edge 1-6 -> Color 0, 2
Edge 1-8 -> Color 0, 3
Edge 3-2 -> Color 1, 0
Edge 3-6 -> Color 1, 2
Edge 3-8 -> Color 1, 3
Edge 5-2 -> Color 2, 0
Edge 5-4 -> Color 2, 1
Edge 5-8 -> Color 2, 3
Edge 7-2 -> Color 3, 0
Edge 7-4 -> Color 3, 1
Edge 7-6 -> Color 3, 2
Number of nodes : 8
Number of edges : 12
Number of colors : 4
Example 4
Edge 1-6 -> Color 0, 1
Edge 7-1 -> Color 1, 0
Edge 8-1 -> Color 1, 0
Edge 5-2 -> Color 1, 0
Edge 2-7 -> Color 0, 1
Edge 2-8 -> Color 0, 1
Edge 3-5 -> Color 0, 1
Edge 6-3 -> Color 1, 0
Edge 3-8 -> Color 0, 1
Edge 4-5 -> Color 0, 1
Edge 4-6 -> Color 0, 1
Edge 4-7 -> Color 0, 1
Number of nodes : 8
Number of edges : 12
Number of colors : 2
</pre>
=={{header|Haskell}}==
<syntaxhighlight lang="haskell">import Data.Maybe
import Data.List
import Control.Monad.State
import qualified Data.Map as M
import Text.Printf
------------------------------------------------------------
-- Primitive graph representation
type Node = Int
type Color = Int
type Graph = M.Map Node [Node]
nodes :: Graph -> [Node]
nodes = M.keys
adjacentNodes :: Graph -> Node -> [Node]
adjacentNodes g n = fromMaybe [] $ M.lookup n g
degree :: Graph -> Node -> Int
degree g = length . adjacentNodes g
fromList :: [(Node, [Node])] -> Graph
fromList = foldr add M.empty
where
add (a, bs) g = foldr (join [a]) (join bs a g) bs
join = flip (M.insertWith (++))
readGraph :: String -> Graph
readGraph = fromList . map interprete . words
where
interprete s = case span (/= '-') s of
(a, "") -> (read a, [])
(a, '-':b) -> (read a, [read b])
------------------------------------------------------------
-- Graph coloring functions
uncolored :: Node -> State [(Node, Color)] Bool
uncolored n = isNothing <$> colorOf n
colorOf :: Node -> State [(Node, Color)] (Maybe Color)
colorOf n = gets (lookup n)
greedyColoring :: Graph -> [(Node, Color)]
greedyColoring g = mapM_ go (nodes g) `execState` []
where
go n = do
c <- colorOf n
when (isNothing c) $ do
adjacentColors <- nub . catMaybes <$> mapM colorOf (adjacentNodes g n)
let newColor = head $ filter (`notElem` adjacentColors) [1..]
modify ((n, newColor) :)
filterM uncolored (adjacentNodes g n) >>= mapM_ go
wpColoring :: Graph -> [(Node, Color)]
wpColoring g = go [1..] nodesList `execState` []
where
nodesList = sortOn (negate . degree g) (nodes g)
go _ [] = pure ()
go (c:cs) ns = do
mark c ns
filterM uncolored ns >>= go cs
mark c [] = pure () :: State [(Node, Color)] ()
mark c (n:ns) = do
modify ((n, c) :)
mark c (filter (`notElem` adjacentNodes g n) ns)</syntaxhighlight>
Simple usage examples:
<pre>λ> let g = fromList [(1,[2,3]),(2,[3,4]),(4,[3,5])]
λ> g
fromList [(1,[2,3]),(2,[1,3,4]),(3,[1,2,4]),(4,[2,3,5]),(5,[4])]
λ> greedyColoring g
[(5,2),(4,1),(3,3),(2,2),(1,1)]
λ> wpColoring g
[(1,3),(4,3),(3,2),(5,1),(2,1)]</pre>
The task:
<syntaxhighlight lang="haskell">ex1 = "0-1 1-2 2-0 3"
ex2 = "1-6 1-7 1-8 2-5 2-7 2-8 3-5 3-6 3-8 4-5 4-6 4-7"
ex3 = "1-4 1-6 1-8 3-2 3-6 3-8 5-2 5-4 5-8 7-2 7-4 7-6"
ex4 = "1-6 7-1 8-1 5-2 2-7 2-8 3-5 6-3 3-8 4-5 4-6 4-7"
task method ex =
let g = readGraph ex
cs = sortOn fst $ method g
color n = fromJust $ lookup n cs
ns = nodes g
mkLine n = printf "%d\t%d\t%s\n" n (color n) (show (color <$> adjacentNodes g n))
in do
print ex
putStrLn $ "nodes:\t" ++ show ns
putStrLn $ "colors:\t" ++ show (nub (snd <$> cs))
putStrLn "node\tcolor\tadjacent colors"
mapM_ mkLine ns
putStrLn ""</syntaxhighlight>
Runing greedy algorithm:
<pre>λ> mapM_ (task greedyColoring) [ex1,ex2,ex3,ex4]
"0-1 1-2 2-0 3"
nodes: [0,1,2,3]
colors: [1,2,3]
node color adjacent colors
0 1 [2,3]
1 2 [1,3]
2 3 [2,1]
3 1 []
"1-6 1-7 1-8 2-5 2-7 2-8 3-5 3-6 3-8 4-5 4-6 4-7"
nodes: [1,2,3,4,5,6,7,8]
colors: [1,2]
node color adjacent colors
1 1 [2,2,2]
2 1 [2,2,2]
3 1 [2,2,2]
4 1 [2,2,2]
5 2 [1,1,1]
6 2 [1,1,1]
7 2 [1,1,1]
8 2 [1,1,1]
"1-4 1-6 1-8 3-2 3-6 3-8 5-2 5-4 5-8 7-2 7-4 7-6"
nodes: [1,2,3,4,5,6,7,8]
colors: [1,2]
node color adjacent colors
1 1 [2,2,2]
2 2 [1,1,1]
3 1 [2,2,2]
4 2 [1,1,1]
5 1 [2,2,2]
6 2 [1,1,1]
7 1 [2,2,2]
8 2 [1,1,1]
"1-6 7-1 8-1 5-2 2-7 2-8 3-5 6-3 3-8 4-5 4-6 4-7"
nodes: [1,2,3,4,5,6,7,8]
colors: [1,2]
node color adjacent colors
1 1 [2,2,2]
2 1 [2,2,2]
3 1 [2,2,2]
4 1 [2,2,2]
5 2 [1,1,1]
6 2 [1,1,1]
7 2 [1,1,1]
8 2 [1,1,1] </pre>
Runing Welsh-Powell algorithm:
<pre>λ> mapM_ (task wpColoring) [ex1,ex2,ex3,ex4]
"0-1 1-2 2-0 3"
nodes: [0,1,2,3]
colors: [1,2,3]
node color adjacent colors
0 1 [2,3]
1 2 [1,3]
2 3 [2,1]
3 1 []
"1-6 1-7 1-8 2-5 2-7 2-8 3-5 3-6 3-8 4-5 4-6 4-7"
nodes: [1,2,3,4,5,6,7,8]
colors: [1,2]
node color adjacent colors
1 1 [2,2,2]
2 1 [2,2,2]
3 1 [2,2,2]
4 1 [2,2,2]
5 2 [1,1,1]
6 2 [1,1,1]
7 2 [1,1,1]
8 2 [1,1,1]
"1-4 1-6 1-8 3-2 3-6 3-8 5-2 5-4 5-8 7-2 7-4 7-6"
nodes: [1,2,3,4,5,6,7,8]
colors: [1,2,3,4]
node color adjacent colors
1 1 [2,3,4]
2 1 [2,3,4]
3 2 [1,3,4]
4 2 [1,3,4]
5 3 [1,2,4]
6 3 [1,2,4]
7 4 [1,2,3]
8 4 [1,2,3]
"1-6 7-1 8-1 5-2 2-7 2-8 3-5 6-3 3-8 4-5 4-6 4-7"
nodes: [1,2,3,4,5,6,7,8]
colors: [1,2]
node color adjacent colors
1 1 [2,2,2]
2 1 [2,2,2]
3 1 [2,2,2]
4 1 [2,2,2]
5 2 [1,1,1]
6 2 [1,1,1]
7 2 [1,1,1]
8 2 [1,1,1]</pre>
=={{header|J}}==
Greedy coloring satisfies the task requirements.
<syntaxhighlight lang="j">parse=: {{
ref=: 2$L:1(;:each cut y) -.L:1 ;:'-'
labels=: /:~~.;ref
sparse=. (*:#labels) > 20*#ref
graph=: (+.|:) 1 (labels i.L:1 ref)} $.^:sparse 0$~2##labels
}}
greedy=: {{
colors=. (#y)#a:
for_node.y do.
color=. <{.(-.~ [:i.1+#) ~.;node#colors
colors=. color node_index} colors
end.
;colors
}}</syntaxhighlight>
To display colors for edges, we show the graph specification and beneath the representation of each edge A-B we show colorA:colorB.
<syntaxhighlight lang="j">
ex1=:'0-1 1-2 2-0 3'
ex2=:'1-6 1-7 1-8 2-5 2-7 2-8 3-5 3-6 3-8 4-5 4-6 4-7'
ex3=:'1-4 1-6 1-8 3-2 3-6 3-8 5-2 5-4 5-8 7-2 7-4 7-6'
ex4=:'1-6 7-1 8-1 5-2 2-7 2-8 3-5 6-3 3-8 4-5 4-6 4-7'
require'format/printf'
require'format/printf'
task=: {{
colors=. greedy parse y
echo'nodes: %d, edges: %d, colours: %d' sprintf #each graph;ref;~.colors
edgecolors=. <@(,&":':',&":])/"1(>labels i.L:1 ref){colors
,./>' ',.~each^:2(cut y),:each edgecolors
}}
task ex1
nodes: 4, edges: 4, colours: 3
0-1 1-2 2-0 3
0:1 1:2 2:0 0:0
task ex2
nodes: 8, edges: 12, colours: 2
1-6 1-7 1-8 2-5 2-7 2-8 3-5 3-6 3-8 4-5 4-6 4-7
0:1 0:1 0:1 0:1 0:1 0:1 0:1 0:1 0:1 0:1 0:1 0:1
task ex3
nodes: 8, edges: 12, colours: 4
1-4 1-6 1-8 3-2 3-6 3-8 5-2 5-4 5-8 7-2 7-4 7-6
0:1 0:2 0:3 1:0 1:2 1:3 2:0 2:1 2:3 3:0 3:1 3:2
task ex4
nodes: 8, edges: 12, colours: 2
1-6 7-1 8-1 5-2 2-7 2-8 3-5 6-3 3-8 4-5 4-6 4-7
0:1 1:0 1:0 1:0 0:1 0:1 0:1 1:0 0:1 0:1 0:1 0:1
</syntaxhighlight>
But, of course, we can do better than that. For example, we can try a few random ordered greedy color assignments, retaining a color assignment with the fewest colors:
<syntaxhighlight lang="j">anneal=: {{
best=. i.#y [ cost=. #~.greedy y
for.i.#y do.
o=. ?~#y
c=.#~.greedy o ([ { {"1) y
if. cost > c do.
best=. o [ cost=. c
end.
end.
(/:best) { greedy best ([ { {"1) y
}}
task=: {{
colors=. anneal parse y
echo'nodes: %d, edges: %d, colours: %d' sprintf #each graph;ref;~.colors
edgecolors=. <@(,&":':',&":])/"1(>labels i.L:1 ref){colors
,./>' ',.~each^:2(cut y),:each edgecolors
}}
task ex1
nodes: 4, edges: 4, colours: 3
0-1 1-2 2-0 3
0:1 1:2 2:0 0:0
task ex2
nodes: 8, edges: 12, colours: 2
1-6 1-7 1-8 2-5 2-7 2-8 3-5 3-6 3-8 4-5 4-6 4-7
0:1 0:1 0:1 0:1 0:1 0:1 0:1 0:1 0:1 0:1 0:1 0:1
task ex3
nodes: 8, edges: 12, colours: 2
1-4 1-6 1-8 3-2 3-6 3-8 5-2 5-4 5-8 7-2 7-4 7-6
0:1 0:1 0:1 0:1 0:1 0:1 0:1 0:1 0:1 0:1 0:1 0:1
task ex4
nodes: 8, edges: 12, colours: 2
1-6 7-1 8-1 5-2 2-7 2-8 3-5 6-3 3-8 4-5 4-6 4-7
0:1 1:0 1:0 1:0 0:1 0:1 0:1 1:0 0:1 0:1 0:1 0:1
</syntaxhighlight>
=={{header|Java}}==
Using the DSatur algorithm from https://en.wikipedia.org/wiki/DSatur
<syntaxhighlight lang="java">
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;
public final class GraphColoring {
public static void main(String[] aArgs) {
colourise("0-1 1-2 2-0 3");
colourise("1-6 1-7 1-8 2-5 2-7 2-8 3-5 3-6 3-8 4-5 4-6 4-7");
colourise("1-4 1-6 1-8 3-2 3-6 3-8 5-2 5-4 5-8 7-2 7-4 7-6");
colourise("1-6 7-1 8-1 5-2 2-7 2-8 3-5 6-3 3-8 4-5 4-6 4-7");
}
private static void colourise(String aGraphRepresentation) {
List<Node> graph = initialiseGraph(aGraphRepresentation);
List<Node> nodes = new ArrayList<Node>(graph);
while ( ! nodes.isEmpty() ) {
Node maxNode = nodes.stream().max( (one, two) -> Integer.compare(one.saturation, two.saturation) ).get();
maxNode.colour = minColour(maxNode);
updateSaturation(maxNode);
nodes.remove(maxNode);
}
System.out.println("Graph: " + aGraphRepresentation);
display(graph);
}
private static Colour minColour(Node aNode) {
Set<Colour> coloursUsed = coloursUsed(aNode);
for ( Colour colour : Colour.values() ) {
if ( ! coloursUsed.contains(colour) ) {
return colour;
}
}
return Colour.NO_COLOUR;
}
private static Set<Colour> coloursUsed(Node aNode) {
Set<Colour> coloursUsed = new HashSet<Colour>();
for ( Node neighbour : aNode.neighbours ) {
coloursUsed.add(neighbour.colour);
}
return coloursUsed;
}
private static void updateSaturation(Node aNode) {
for ( Node neighbour : aNode.neighbours ) {
if ( neighbour.colour == Colour.NO_COLOUR ) {
neighbour.saturation = coloursUsed(aNode).size();
}
}
}
private static void display(List<Node> aNodes) {
Set<Colour> graphColours = new HashSet<Colour>();
for ( Node node : aNodes ) {
graphColours.add(node.colour);
System.out.print("Node " + node.index + ": colour = " + node.colour);
if ( ! node.neighbours.isEmpty() ) {
List<Integer> indexes = node.neighbours.stream().map( n -> n.index ).toList();
System.out.print(" ".repeat(8 - String.valueOf(node.colour).length()) + "neighbours = " + indexes);
}
System.out.println();
}
System.out.println("Number of colours used: " + graphColours.size());
System.out.println();
}
private static List<Node> initialiseGraph(String aGraphRepresentation) {
Map<Integer, Node> map = new TreeMap<Integer, Node>();
for ( String element : aGraphRepresentation.split(" ") ) {
if ( element.contains("-") ) {
final int index1 = Integer.valueOf(element.substring(0, 1));
final int index2 = Integer.valueOf(element.substring(element.length() - 1));
Node node1 = map.computeIfAbsent(index1, k -> new Node(index1, 0, Colour.NO_COLOUR) );
Node node2 = map.computeIfAbsent(index2, k -> new Node(index2, 0, Colour.NO_COLOUR) );
node1.neighbours.add(node2);
node2.neighbours.add(node1);
} else {
final int index = Integer.valueOf(element);
map.computeIfAbsent(index, k -> new Node(index, 0, Colour.NO_COLOUR));
}
}
List<Node> graph = new ArrayList<Node>(map.values());
return graph;
}
private enum Colour { BLUE, GREEN, RED, YELLOW, CYAN, ORANGE, NO_COLOUR }
private static class Node {
public Node(int aIndex, int aSaturation, Colour aColour) {
index = aIndex; saturation = aSaturation; colour = aColour;
}
private int index, saturation;
private Colour colour;
private Set<Node> neighbours = new TreeSet<Node>( (one, two) -> Integer.compare(one.index, two.index) );
}
}
</syntaxhighlight>
{{ out }}
<pre>
Graph: 0-1 1-2 2-0 3
Node 0: colour = BLUE neighbours = [1, 2]
Node 1: colour = GREEN neighbours = [0, 2]
Node 2: colour = RED neighbours = [0, 1]
Node 3: colour = BLUE
Number of colours used: 3
Graph: 1-6 1-7 1-8 2-5 2-7 2-8 3-5 3-6 3-8 4-5 4-6 4-7
Node 1: colour = BLUE neighbours = [6, 7, 8]
Node 2: colour = BLUE neighbours = [5, 7, 8]
Node 3: colour = BLUE neighbours = [5, 6, 8]
Node 4: colour = BLUE neighbours = [5, 6, 7]
Node 5: colour = GREEN neighbours = [2, 3, 4]
Node 6: colour = GREEN neighbours = [1, 3, 4]
Node 7: colour = GREEN neighbours = [1, 2, 4]
Node 8: colour = GREEN neighbours = [1, 2, 3]
Number of colours used: 2
Graph: 1-4 1-6 1-8 3-2 3-6 3-8 5-2 5-4 5-8 7-2 7-4 7-6
Node 1: colour = BLUE neighbours = [4, 6, 8]
Node 2: colour = GREEN neighbours = [3, 5, 7]
Node 3: colour = BLUE neighbours = [2, 6, 8]
Node 4: colour = GREEN neighbours = [1, 5, 7]
Node 5: colour = BLUE neighbours = [2, 4, 8]
Node 6: colour = GREEN neighbours = [1, 3, 7]
Node 7: colour = BLUE neighbours = [2, 4, 6]
Node 8: colour = GREEN neighbours = [1, 3, 5]
Number of colours used: 2
Graph: 1-6 7-1 8-1 5-2 2-7 2-8 3-5 6-3 3-8 4-5 4-6 4-7
Node 1: colour = BLUE neighbours = [6, 7, 8]
Node 2: colour = BLUE neighbours = [5, 7, 8]
Node 3: colour = BLUE neighbours = [5, 6, 8]
Node 4: colour = BLUE neighbours = [5, 6, 7]
Node 5: colour = GREEN neighbours = [2, 3, 4]
Node 6: colour = GREEN neighbours = [1, 3, 4]
Node 7: colour = GREEN neighbours = [1, 2, 4]
Node 8: colour = GREEN neighbours = [1, 2, 3]
Number of colours used: 2
</pre>
=={{header|Julia}}==
Uses a repeated randomization of node color ordering to seek a minimum number of colors needed.
<syntaxhighlight lang="julia">using Random
"""Useful constants for the colors to be selected for nodes of the graph"""
const colors4 = ["blue", "red", "green", "yellow"]
const badcolor = "black"
@assert(!(badcolor in colors4))
"""
struct graph
undirected simple graph
constructed from its name and a string listing of point to point connections
"""
mutable struct Graph
name::String
g::Dict{Int, Vector{Int}}
nodecolor::Dict{Int, String}
function Graph(nam::String, s::String)
gdic = Dict{Int, Vector{Int}}()
for p in eachmatch(r"(\d+)-(\d+)|(\d+)(?!\s*-)" , s)
if p != nothing
if p[3] != nothing
n3 = parse(Int, p[3])
get!(gdic, n3, [])
else
n1, n2 = parse(Int, p[1]), parse(Int, p[2])
p1vec = get!(gdic, n1, [])
!(n2 in p1vec) && push!(p1vec, n2)
p2vec = get!(gdic, n2, [])
!(n1 in p2vec) && push!(p2vec, n1)
end
end
end
new(nam, gdic, Dict{Int, String}())
end
end
"""
tryNcolors!(gr::Graph, N, maxtrials)
Try up to maxtrials to get a coloring with <= N colors
"""
function tryNcolors!(gr::Graph, N, maxtrials)
t, mintrial, minord = N, N + 1, Dict()
for _ in 1:maxtrials
empty!(gr.nodecolor)
ordering = shuffle(collect(keys(gr.g)))
for node in ordering
usedneighborcolors = [gr.nodecolor[c] for c in gr.g[node] if haskey(gr.nodecolor, c)]
gr.nodecolor[node] = badcolor
for c in colors4[1:N]
if !(c in usedneighborcolors)
gr.nodecolor[node] = c
break
end
end
end
t = length(unique(values(gr.nodecolor)))
if t < mintrial
mintrial = t
minord = deepcopy(gr.nodecolor)
end
end
if length(minord) > 0
gr.nodecolor = minord
end
end
"""
prettyprintcolors(gr::graph)
print out the colored nodes in graph
"""
function prettyprintcolors(gr::Graph)
println("\nColors for the graph named ", gr.name, ":")
edgesdone = Vector{Vector{Int}}()
for (node, neighbors) in gr.g
if !isempty(neighbors)
for n in neighbors
edge = node < n ? [node, n] : [n, node]
if !(edge in edgesdone)
println(" ", edge[1], "-", edge[2], " Color: ",
gr.nodecolor[edge[1]], ", ", gr.nodecolor[edge[2]])
push!(edgesdone, edge)
end
end
else
println(" ", node, ": ", gr.nodecolor[node])
end
end
println("\n", length(unique(keys(gr.nodecolor))), " nodes, ",
length(edgesdone), " edges, ",
length(unique(values(gr.nodecolor))), " colors.")
end
for (name, txt) in [("Ex1", "0-1 1-2 2-0 3"),
("Ex2", "1-6 1-7 1-8 2-5 2-7 2-8 3-5 3-6 3-8 4-5 4-6 4-7"),
("Ex3", "1-4 1-6 1-8 3-2 3-6 3-8 5-2 5-4 5-8 7-2 7-4 7-6"),
("Ex4", "1-6 7-1 8-1 5-2 2-7 2-8 3-5 6-3 3-8 4-5 4-6 4-7")]
exgraph = Graph(name, txt)
tryNcolors!(exgraph, 4, 100)
prettyprintcolors(exgraph)
end
</syntaxhighlight>{{out}}
<pre>
Colors for the graph named Ex1:
0-1 Color: red, blue
0-2 Color: red, green
1-2 Color: blue, green
3: blue
4 nodes, 3 edges, 3 colors.
Colors for the graph named Ex2:
1-7 Color: blue, red
2-7 Color: blue, red
4-7 Color: blue, red
4-5 Color: blue, red
4-6 Color: blue, red
2-5 Color: blue, red
2-8 Color: blue, red
3-5 Color: blue, red
3-6 Color: blue, red
3-8 Color: blue, red
1-8 Color: blue, red
1-6 Color: blue, red
8 nodes, 12 edges, 2 colors.
Colors for the graph named Ex3:
2-7 Color: red, blue
4-7 Color: red, blue
6-7 Color: red, blue
1-4 Color: blue, red
4-5 Color: red, blue
2-3 Color: red, blue
2-5 Color: red, blue
3-6 Color: blue, red
3-8 Color: blue, red
1-8 Color: blue, red
5-8 Color: blue, red
1-6 Color: blue, red
8 nodes, 12 edges, 2 colors.
Colors for the graph named Ex4:
1-7 Color: blue, red
2-7 Color: blue, red
4-7 Color: blue, red
4-5 Color: blue, red
4-6 Color: blue, red
2-5 Color: blue, red
2-8 Color: blue, red
3-5 Color: blue, red
3-6 Color: blue, red
3-8 Color: blue, red
1-8 Color: blue, red
1-6 Color: blue, red
8 nodes, 12 edges, 2 colors.
</pre>
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">ClearAll[ColorGroups]
ColorGroups[g_Graph] := Module[{h, cols, indset, diffcols},
h = g;
cols = {};
While[! EmptyGraphQ[h], maxd = RandomChoice[VertexList[h]];
indset = Flatten[FindIndependentVertexSet[{h, maxd}]];
AppendTo[cols, indset];
h = VertexDelete[h, indset];
];
AppendTo[cols, VertexList[h]];
diffcols = Length[cols];
cols = Catenate[Map[Thread][Rule @@@ Transpose[{cols, Range[Length[cols]]}]]];
Print[Column[Row[{"Edge ", #1, " to ", #2, " has colors ", #1 /. cols, " and ", #2 /. cols }] & @@@ EdgeList[g]]];
Print[Grid[{{"Vertices: ", VertexCount[g]}, {"Edges: ", EdgeCount[g]}, {"Colors used: ", diffcols}}]]
]
ColorGroups[Graph[Range[0, 3], {0 \[UndirectedEdge] 1, 1 \[UndirectedEdge] 2,
2 \[UndirectedEdge] 0}]]
ColorGroups[Graph[Range[8], {1 \[UndirectedEdge] 6, 1 \[UndirectedEdge] 7,
1 \[UndirectedEdge] 8, 2 \[UndirectedEdge] 5,
2 \[UndirectedEdge] 7, 2 \[UndirectedEdge] 8,
3 \[UndirectedEdge] 5, 3 \[UndirectedEdge] 6,
3 \[UndirectedEdge] 8, 4 \[UndirectedEdge] 5,
4 \[UndirectedEdge] 6, 4 \[UndirectedEdge] 7}]]
ColorGroups[Graph[Range[8], {1 \[UndirectedEdge] 4, 1 \[UndirectedEdge] 6,
1 \[UndirectedEdge] 8, 3 \[UndirectedEdge] 2,
3 \[UndirectedEdge] 6, 3 \[UndirectedEdge] 8,
5 \[UndirectedEdge] 2, 5 \[UndirectedEdge] 4,
5 \[UndirectedEdge] 8, 7 \[UndirectedEdge] 2,
7 \[UndirectedEdge] 4, 7 \[UndirectedEdge] 6}]]
ColorGroups[Graph[Range[8], {1 \[UndirectedEdge] 6, 7 \[UndirectedEdge] 1,
8 \[UndirectedEdge] 1, 5 \[UndirectedEdge] 2,
2 \[UndirectedEdge] 7, 2 \[UndirectedEdge] 8,
3 \[UndirectedEdge] 5, 6 \[UndirectedEdge] 3,
3 \[UndirectedEdge] 8, 4 \[UndirectedEdge] 5,
4 \[UndirectedEdge] 6, 4 \[UndirectedEdge] 7}]]</syntaxhighlight>
{{out}}
<pre>Edge 0 to 1 has colors 1 and 3
Edge 1 to 2 has colors 3 and 2
Edge 2 to 0 has colors 2 and 1
Vertices: 4
Edges: 3
Colors used: 3
Edge 1 to 6 has colors 1 and 2
Edge 1 to 7 has colors 1 and 2
Edge 1 to 8 has colors 1 and 2
Edge 2 to 5 has colors 1 and 2
Edge 2 to 7 has colors 1 and 2
Edge 2 to 8 has colors 1 and 2
Edge 3 to 5 has colors 1 and 2
Edge 3 to 6 has colors 1 and 2
Edge 3 to 8 has colors 1 and 2
Edge 4 to 5 has colors 1 and 2
Edge 4 to 6 has colors 1 and 2
Edge 4 to 7 has colors 1 and 2
Vertices: 8
Edges: 12
Colors used: 2
Edge 1 to 4 has colors 1 and 2
Edge 1 to 6 has colors 1 and 2
Edge 1 to 8 has colors 1 and 2
Edge 3 to 2 has colors 1 and 2
Edge 3 to 6 has colors 1 and 2
Edge 3 to 8 has colors 1 and 2
Edge 5 to 2 has colors 1 and 2
Edge 5 to 4 has colors 1 and 2
Edge 5 to 8 has colors 1 and 2
Edge 7 to 2 has colors 1 and 2
Edge 7 to 4 has colors 1 and 2
Edge 7 to 6 has colors 1 and 2
Vertices: 8
Edges: 12
Colors used: 2
Edge 1 to 6 has colors 2 and 1
Edge 7 to 1 has colors 1 and 2
Edge 8 to 1 has colors 1 and 2
Edge 5 to 2 has colors 1 and 2
Edge 2 to 7 has colors 2 and 1
Edge 2 to 8 has colors 2 and 1
Edge 3 to 5 has colors 2 and 1
Edge 6 to 3 has colors 1 and 2
Edge 3 to 8 has colors 2 and 1
Edge 4 to 5 has colors 2 and 1
Edge 4 to 6 has colors 2 and 1
Edge 4 to 7 has colors 2 and 1
Vertices: 8
Edges: 12
Colors used: 2</pre>
=={{header|Nim}}==
We use the “DSatur” algorithm described here: https://en.wikipedia.org/wiki/DSatur.
For the four examples, it gives the minimal number of colors.
<syntaxhighlight lang="nim">import algorithm, sequtils, strscans, strutils, tables
const NoColor = 0
type
Color = range[0..63]
Node = ref object
num: Natural # Node number.
color: Color # Node color.
degree: Natural # Node degree.
dsat: Natural # Node Dsaturation.
neighbors: seq[Node] # List of neighbors.
Graph = seq[Node] # List of nodes ordered by number.
#---------------------------------------------------------------------------------------------------
proc initGraph(graphRepr: string): Graph =
## Initialize the graph from its string representation.
var mapping: Table[Natural, Node] # Temporary mapping.
for elem in graphRepr.splitWhitespace():
var num1, num2: int
if elem.scanf("$i-$i", num1, num2):
let node1 = mapping.mgetOrPut(num1, Node(num: num1))
let node2 = mapping.mgetOrPut(num2, Node(num: num2))
node1.neighbors.add node2
node2.neighbors.add node1
elif elem.scanf("$i", num1):
discard mapping.mgetOrPut(num1, Node(num: num1))
else:
raise newException(ValueError, "wrong description: " & elem)
for node in mapping.values:
node.degree = node.neighbors.len
result = sortedByIt(toSeq(mapping.values), it.num)
#---------------------------------------------------------------------------------------------------
proc numbers(nodes: seq[Node]): string =
## Return the numbers of a list of nodes.
for node in nodes:
result.addSep(" ")
result.add($node.num)
#---------------------------------------------------------------------------------------------------
proc `$`(graph: Graph): string =
## Return the description of the graph.
var maxColor = NoColor
for node in graph:
stdout.write "Node ", node.num, ": color = ", node.color
if node.color > maxColor: maxColor = node.color
if node.neighbors.len > 0:
echo " neighbors = ", sortedByIt(node.neighbors, it.num).numbers
else:
echo ""
echo "Number of colors: ", maxColor
#---------------------------------------------------------------------------------------------------
proc `<`(node1, node2: Node): bool =
## Comparison of nodes, by dsaturation first, then by degree.
if node1.dsat == node2.dsat: node1.degree < node2.degree
else: node1.dsat < node2.dsat
#---------------------------------------------------------------------------------------------------
proc getMaxDsatNode(nodes: var seq[Node]): Node =
## Return the node with the greatest dsaturation.
let idx = nodes.maxIndex()
result = nodes[idx]
nodes.delete(idx)
#---------------------------------------------------------------------------------------------------
proc minColor(node: Node): COLOR =
## Return the minimum available color for a node.
var colorUsed: set[Color]
for neighbor in node.neighbors:
colorUsed.incl neighbor.color
for color in 1..Color.high:
if color notin colorUsed: return color
#---------------------------------------------------------------------------------------------------
proc distinctColorsCount(node: Node): Natural =
## Return the number of distinct colors of the neighbors of a node.
var colorUsed: set[Color]
for neighbor in node.neighbors:
colorUsed.incl neighbor.color
result = colorUsed.card
#---------------------------------------------------------------------------------------------------
proc updateDsats(node: Node) =
## Update the dsaturations of the neighbors of a node.
for neighbor in node.neighbors:
if neighbor.color == NoColor:
neighbor.dsat = neighbor.distinctColorsCount()
#---------------------------------------------------------------------------------------------------
proc colorize(graphRepr: string) =
## Colorize a graph.
let graph = initGraph(graphRepr)
var nodes = sortedByIt(graph, -it.degree) # Copy or graph sorted by decreasing degrees.
while nodes.len > 0:
let node = nodes.getMaxDsatNode()
node.color = node.minColor()
node.updateDsats()
echo "Graph: ", graphRepr
echo graph
#---------------------------------------------------------------------------------------------------
when isMainModule:
colorize("0-1 1-2 2-0 3")
colorize("1-6 1-7 1-8 2-5 2-7 2-8 3-5 3-6 3-8 4-5 4-6 4-7")
colorize("1-4 1-6 1-8 3-2 3-6 3-8 5-2 5-4 5-8 7-2 7-4 7-6")
colorize("1-6 7-1 8-1 5-2 2-7 2-8 3-5 6-3 3-8 4-5 4-6 4-7")</syntaxhighlight>
{{out}}
<pre>Graph: 0-1 1-2 2-0 3
Node 0: color = 1 neighbors = 1 2
Node 1: color = 2 neighbors = 0 2
Node 2: color = 3 neighbors = 0 1
Node 3: color = 1
Number of colors: 3
Graph: 1-6 1-7 1-8 2-5 2-7 2-8 3-5 3-6 3-8 4-5 4-6 4-7
Node 1: color = 1 neighbors = 6 7 8
Node 2: color = 1 neighbors = 5 7 8
Node 3: color = 1 neighbors = 5 6 8
Node 4: color = 1 neighbors = 5 6 7
Node 5: color = 2 neighbors = 2 3 4
Node 6: color = 2 neighbors = 1 3 4
Node 7: color = 2 neighbors = 1 2 4
Node 8: color = 2 neighbors = 1 2 3
Number of colors: 2
Graph: 1-4 1-6 1-8 3-2 3-6 3-8 5-2 5-4 5-8 7-2 7-4 7-6
Node 1: color = 1 neighbors = 4 6 8
Node 2: color = 2 neighbors = 3 5 7
Node 3: color = 1 neighbors = 2 6 8
Node 4: color = 2 neighbors = 1 5 7
Node 5: color = 1 neighbors = 2 4 8
Node 6: color = 2 neighbors = 1 3 7
Node 7: color = 1 neighbors = 2 4 6
Node 8: color = 2 neighbors = 1 3 5
Number of colors: 2
Graph: 1-6 7-1 8-1 5-2 2-7 2-8 3-5 6-3 3-8 4-5 4-6 4-7
Node 1: color = 1 neighbors = 6 7 8
Node 2: color = 1 neighbors = 5 7 8
Node 3: color = 1 neighbors = 5 6 8
Node 4: color = 1 neighbors = 5 6 7
Node 5: color = 2 neighbors = 2 3 4
Node 6: color = 2 neighbors = 1 3 4
Node 7: color = 2 neighbors = 1 2 4
Node 8: color = 2 neighbors = 1 2 3
Number of colors: 2</pre>
=={{header|Perl}}==
{{trans|Raku}}
<syntaxhighlight lang="perl">use strict;
use warnings;
no warnings 'uninitialized';
use feature 'say';
use constant True => 1;
use List::Util qw(head uniq);
sub GraphNodeColor {
my(%OneMany, %NodeColor, %NodePool, @ColorPool);
my(@data) = @_;
for (@data) {
my($a,$b) = @$_;
push @{$OneMany{$a}}, $b;
push @{$OneMany{$b}}, $a;
}
@ColorPool = 0 .. -1 + scalar %OneMany;
$NodePool{$_} = True for keys %OneMany;
if ($OneMany{''}) { # skip islanders for now
delete $NodePool{$_} for @{$OneMany{''}};
delete $NodePool{''};
}
while (%NodePool) {
my $color = shift @ColorPool;
my %TempPool = %NodePool;
while (my $n = head 1, sort keys %TempPool) {
$NodeColor{$n} = $color;
delete $TempPool{$n};
delete $TempPool{$_} for @{$OneMany{$n}} ; # skip neighbors as well
delete $NodePool{$n};
}
if ($OneMany{''}) { # islanders use an existing color
$NodeColor{$_} = head 1, sort values %NodeColor for @{$OneMany{''}};
}
}
%NodeColor
}
my @DATA = (
[ [1,2],[2,3],[3,1],[4,undef],[5,undef],[6,undef] ],
[ [1,6],[1,7],[1,8],[2,5],[2,7],[2,8],[3,5],[3,6],[3,8],[4,5],[4,6],[4,7] ],
[ [1,4],[1,6],[1,8],[3,2],[3,6],[3,8],[5,2],[5,4],[5,8],[7,2],[7,4],[7,6] ],
[ [1,6],[7,1],[8,1],[5,2],[2,7],[2,8],[3,5],[6,3],[3,8],[4,5],[4,6],[4,7] ]
);
for my $d (@DATA) {
my %result = GraphNodeColor @$d;
my($graph,$colors);
$graph .= '(' . join(' ', @$_) . '), ' for @$d;
$colors .= ' ' . $result{$$_[0]} . '-' . ($result{$$_[1]} // '') . ' ' for @$d;
say 'Graph : ' . $graph =~ s/,\s*$//r;
say 'Colors : ' . $colors;
say 'Nodes : ' . keys %result;
say 'Edges : ' . @$d;
say 'Unique : ' . uniq values %result;
say '';
}</syntaxhighlight>
{{out}}
<pre>Graph : (1 2), (2 3), (3 1), (4 ), (5 ), (6 )
Colors : 0-1 1-2 2-0 0- 0- 0-
Nodes : 6
Edges : 6
Unique : 3
Graph : (1 6), (1 7), (1 8), (2 5), (2 7), (2 8), (3 5), (3 6), (3 8), (4 5), (4 6), (4 7)
Colors : 0-1 0-1 0-1 0-1 0-1 0-1 0-1 0-1 0-1 0-1 0-1 0-1
Nodes : 8
Edges : 12
Unique : 2
Graph : (1 4), (1 6), (1 8), (3 2), (3 6), (3 8), (5 2), (5 4), (5 8), (7 2), (7 4), (7 6)
Colors : 0-1 0-2 0-3 1-0 1-2 1-3 2-0 2-1 2-3 3-0 3-1 3-2
Nodes : 8
Edges : 12
Unique : 4
Graph : (1 6), (7 1), (8 1), (5 2), (2 7), (2 8), (3 5), (6 3), (3 8), (4 5), (4 6), (4 7)
Colors : 0-1 1-0 1-0 1-0 0-1 0-1 0-1 1-0 0-1 0-1 0-1 0-1
Nodes : 8
Edges : 12
Unique : 2</pre>
=={{header|Phix}}==
Exhaustive search, trims search space to < best so far, newused improves on unique().<br>
Many more examples/testing would be needed before I would trust this the tiniest bit.<br>
NB: As per talk page, when writing this I did not remotely imagine it might be used on over 400,000 nodes with over 3 million links...
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #000080;font-style:italic;">-- demo\rosetta\Graph_colouring.exw</span>
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">tests</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">split</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"""
0-1 1-2 2-0 3
1-6 1-7 1-8 2-5 2-7 2-8 3-5 3-6 3-8 4-5 4-6 4-7
1-4 1-6 1-8 3-2 3-6 3-8 5-2 5-4 5-8 7-2 7-4 7-6
1-6 7-1 8-1 5-2 2-7 2-8 3-5 6-3 3-8 4-5 4-6 4-7
"""</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">,</span><span style="color: #004600;">true</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">colour</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">nodes</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">links</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">colours</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">soln</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">best</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">next</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">used</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- fill/try each colours[next], recursing as rqd and saving any improvements.
-- nodes/links are read-only here, colours is the main workspace, soln/best are
-- the results, next is 1..length(nodes), and used is length(unique(colours)).
-- On really big graphs I might consider making nodes..best static, esp colours,
-- in which case you will probably also want a "colours[next] = 0" reset below.</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #000000;">colours</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">colours</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">c</span><span style="color: #0000FF;"><</span><span style="color: #000000;">best</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">bool</span> <span style="color: #000000;">avail</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">links</span><span style="color: #0000FF;">[</span><span style="color: #000000;">next</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">colours</span><span style="color: #0000FF;">[</span><span style="color: #000000;">links</span><span style="color: #0000FF;">[</span><span style="color: #000000;">next</span><span style="color: #0000FF;">][</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]]==</span><span style="color: #000000;">c</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">avail</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span>
<span style="color: #008080;">exit</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">avail</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">colours</span><span style="color: #0000FF;">[</span><span style="color: #000000;">next</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">c</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">newused</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">used</span> <span style="color: #0000FF;">+</span> <span style="color: #0000FF;">(</span><span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">c</span><span style="color: #0000FF;">,</span><span style="color: #000000;">colours</span><span style="color: #0000FF;">)==</span><span style="color: #000000;">next</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">next</span><span style="color: #0000FF;"><</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nodes</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">best</span><span style="color: #0000FF;">,</span><span style="color: #000000;">soln</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">colour</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nodes</span><span style="color: #0000FF;">,</span><span style="color: #000000;">links</span><span style="color: #0000FF;">,</span><span style="color: #000000;">colours</span><span style="color: #0000FF;">,</span><span style="color: #000000;">soln</span><span style="color: #0000FF;">,</span><span style="color: #000000;">best</span><span style="color: #0000FF;">,</span><span style="color: #000000;">next</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">newused</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">newused</span><span style="color: #0000FF;"><</span><span style="color: #000000;">best</span> <span style="color: #008080;">then</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">best</span><span style="color: #0000FF;">,</span><span style="color: #000000;">soln</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">newused</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">colours</span><span style="color: #0000FF;">)}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">c</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">best</span><span style="color: #0000FF;">,</span><span style="color: #000000;">soln</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">add_node</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">nodes</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">links</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">string</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">rdx</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">nodes</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">rdx</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">nodes</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nodes</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">links</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">links</span><span style="color: #0000FF;">,{})</span>
<span style="color: #000000;">rdx</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nodes</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">nodes</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">links</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">rdx</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">tt</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">t</span><span style="color: #0000FF;">]</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">lt</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">split</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tt</span><span style="color: #0000FF;">,</span><span style="color: #008000;">" "</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">nodes</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{},</span>
<span style="color: #000000;">links</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">linkcount</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">left</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">right</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">l</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lt</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">ll</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">split</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lt</span><span style="color: #0000FF;">[</span><span style="color: #000000;">l</span><span style="color: #0000FF;">],</span><span style="color: #008000;">"-"</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">nodes</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">links</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">left</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">add_node</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nodes</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">links</span><span style="color: #0000FF;">),</span><span style="color: #000000;">ll</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ll</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">2</span> <span style="color: #008080;">then</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">nodes</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">links</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">right</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">add_node</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nodes</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">links</span><span style="color: #0000FF;">),</span><span style="color: #000000;">ll</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">])</span>
<span style="color: #000000;">links</span><span style="color: #0000FF;">[</span><span style="color: #000000;">left</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">links</span><span style="color: #0000FF;">[</span><span style="color: #000000;">left</span><span style="color: #0000FF;">])&</span><span style="color: #000000;">right</span>
<span style="color: #000000;">links</span><span style="color: #0000FF;">[</span><span style="color: #000000;">right</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">links</span><span style="color: #0000FF;">[</span><span style="color: #000000;">right</span><span style="color: #0000FF;">])&</span><span style="color: #000000;">left</span>
<span style="color: #000000;">linkcount</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">ln</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nodes</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"test%d: %d nodes, %d edges, "</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ln</span><span style="color: #0000FF;">,</span><span style="color: #000000;">linkcount</span><span style="color: #0000FF;">})</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">colours</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ln</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">soln</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ln</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- fallback solution</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">next</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">best</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ln</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d colours:%v\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">colour</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nodes</span><span style="color: #0000FF;">,</span><span style="color: #000000;">links</span><span style="color: #0000FF;">,</span><span style="color: #000000;">colours</span><span style="color: #0000FF;">,</span><span style="color: #000000;">soln</span><span style="color: #0000FF;">,</span><span style="color: #000000;">best</span><span style="color: #0000FF;">,</span><span style="color: #000000;">next</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
test1: 4 nodes, 3 edges, 3 colours:{1,2,3,1}
test2: 8 nodes, 12 edges, 2 colours:{1,2,2,2,1,2,1,1}
test3: 8 nodes, 12 edges, 2 colours:{1,2,2,2,1,2,1,1}
test4: 8 nodes, 12 edges, 2 colours:{1,2,2,2,2,1,1,1}
</pre>
=={{header|Python}}==
<syntaxhighlight lang="python">import re
from collections import defaultdict
from itertools import count
Line 190 ⟶ 2,039:
('Ex2', "1-6 1-7 1-8 2-5 2-7 2-8 3-5 3-6 3-8 4-5 4-6 4-7"),
('Ex3', "1-4 1-6 1-8 3-2 3-6 3-8 5-2 5-4 5-8 7-2 7-4 7-6"),
('Ex4', "1-6 7-1 8-1 5-2 2-7 2-8 3-5 6-3 3-8 4-5 4-6 4-7"),
]:
g = Graph(name, connections)
g.greedy_colour()</
{{out}}
Line 236 ⟶ 2,086:
#Nodes: 8
#Edges: 12
#Colours: 2
Ex4
1-6: Colour: 0, 1
1-7: Colour: 0, 1
1-8: Colour: 0, 1
2-5: Colour: 2, 0
2-7: Colour: 2, 1
2-8: Colour: 2, 1
3-5: Colour: 2, 0
3-6: Colour: 2, 1
3-8: Colour: 2, 1
4-5: Colour: 2, 0
4-6: Colour: 2, 1
4-7: Colour: 2, 1
#Nodes: 8
#Edges: 12
#Colours: 3</pre>
Python dicts preserve insertion order and Ex2/Ex3 edges are traced in a similar way which could be the cause of exactly the same colours used for Ex2 and Ex3. The wp article must use an earlier version of Python/different ordering of edge definitions.
Ex4 changes the order of nodes enough to affect the number of colours used.
=={{header|Raku}}==
(formerly Perl 6)
<syntaxhighlight lang="raku" line>sub GraphNodeColor(@RAW) {
my %OneMany = my %NodeColor;
for @RAW { %OneMany{$_[0]}.push: $_[1] ; %OneMany{$_[1]}.push: $_[0] }
my @ColorPool = "0", "1" … ^+%OneMany.elems; # as string
my %NodePool = %OneMany.BagHash; # this DWIM is nice
if %OneMany<NaN>:exists { %NodePool{$_}:delete for %OneMany<NaN>, NaN } # pending
while %NodePool.Bool {
my $color = @ColorPool.shift;
my %TempPool = %NodePool;
while (my \n = %TempPool.keys.sort.first) {
%NodeColor{n} = $color;
%TempPool{n}:delete;
%TempPool{$_}:delete for @(%OneMany{n}) ; # skip neighbors as well
%NodePool{n}:delete;
}
}
if %OneMany<NaN>:exists { # islanders use an existing color
%NodeColor{$_} = %NodeColor.values.sort.first for @(%OneMany<NaN>)
}
return %NodeColor
}
my \DATA = [
[<0 1>,<1 2>,<2 0>,<3 NaN>,<4 NaN>,<5 NaN>],
[<1 6>,<1 7>,<1 8>,<2 5>,<2 7>,<2 8>,<3 5>,<3 6>,<3 8>,<4 5>,<4 6>,<4 7>],
[<1 4>,<1 6>,<1 8>,<3 2>,<3 6>,<3 8>,<5 2>,<5 4>,<5 8>,<7 2>,<7 4>,<7 6>],
[<1 6>,<7 1>,<8 1>,<5 2>,<2 7>,<2 8>,<3 5>,<6 3>,<3 8>,<4 5>,<4 6>,<4 7>],
];
for DATA {
say "DATA : ", $_;
say "Result : ";
my %out = GraphNodeColor $_;
say "$_[0]-$_[1]:\t Color %out{$_[0]} ",$_[1].isNaN??''!!%out{$_[1]} for @$_;
say "Nodes : ", %out.keys.elems;
say "Edges : ", $_.elems;
say "Colors : ", %out.values.Set.elems;
}</syntaxhighlight>
{{out}}
<pre>DATA : [(0 1) (1 2) (2 0) (3 NaN) (4 NaN) (5 NaN)]
Result :
0-1: Color 0 1
1-2: Color 1 2
2-0: Color 2 0
3-NaN: Color 0
4-NaN: Color 0
5-NaN: Color 0
Nodes : 6
Edges : 6
Colors : 3
DATA : [(1 6) (1 7) (1 8) (2 5) (2 7) (2 8) (3 5) (3 6) (3 8) (4 5) (4 6) (4 7)]
Result :
1-6: Color 0 1
1-7: Color 0 1
1-8: Color 0 1
2-5: Color 0 1
2-7: Color 0 1
2-8: Color 0 1
3-5: Color 0 1
3-6: Color 0 1
3-8: Color 0 1
4-5: Color 0 1
4-6: Color 0 1
4-7: Color 0 1
Nodes : 8
Edges : 12
Colors : 2
DATA : [(1 4) (1 6) (1 8) (3 2) (3 6) (3 8) (5 2) (5 4) (5 8) (7 2) (7 4) (7 6)]
Result :
1-4: Color 0 1
1-6: Color 0 2
1-8: Color 0 3
3-2: Color 1 0
3-6: Color 1 2
3-8: Color 1 3
5-2: Color 2 0
5-4: Color 2 1
5-8: Color 2 3
7-2: Color 3 0
7-4: Color 3 1
7-6: Color 3 2
Nodes : 8
Edges : 12
Colors : 4
DATA : [(1 6) (7 1) (8 1) (5 2) (2 7) (2 8) (3 5) (6 3) (3 8) (4 5) (4 6) (4 7)]
Result :
1-6: Color 0 1
7-1: Color 1 0
8-1: Color 1 0
5-2: Color 1 0
2-7: Color 0 1
2-8: Color 0 1
3-5: Color 0 1
6-3: Color 1 0
3-8: Color 0 1
4-5: Color 0 1
4-6: Color 0 1
4-7: Color 0 1
Nodes : 8
Edges : 12
Colors : 2</pre>
=={{header|Wren}}==
{{trans|Go}}
{{libheader|Wren-dynamic}}
{{libheader|Wren-sort}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="wren">import "./dynamic" for Struct
import "./sort" for Sort
import "./fmt" for Fmt
// (n)umber of node and its (v)alence i.e. number of neighbors
var NodeVal = Struct.create("NodeVal", ["n", "v"])
class Graph {
construct new(nn, st) {
_nn = nn // number of nodes
_st = st // node numbering starts from
_nbr = List.filled(nn, null) // neighbor list for each node
for (i in 0...nn) _nbr[i] = []
}
nn { _nn }
st { _st }
// Note that this creates a single 'virtual' edge for an isolated node.
addEdge(n1, n2) {
// adjust to starting node number
n1 = n1 - _st
n2 = n2 - _st
_nbr[n1].add(n2)
if (n1 != n2) _nbr[n2].add(n1)
}
// Uses 'greedy' algorithm.
greedyColoring {
// create a list with a color for each node
var cols = List.filled(_nn, -1) // -1 denotes no color assigned
cols[0] = 0 // first node assigned color 0
// create a bool list to keep track of which colors are available
var available = List.filled(_nn, false)
// assign colors to all nodes after the first
for (i in 1..._nn) {
// iterate through neighbors and mark their colors as available
for (j in _nbr[i]) {
if (cols[j] != -1) available[cols[j]] = true
}
// find the first available color
var c = available.indexOf(false)
cols[i] = c // assign it to the current node
// reset the neighbors' colors to unavailable
// before the next iteration
for (j in _nbr[i]) {
if (cols[j] != -1) available[cols[j]] = false
}
}
return cols
}
// Uses Welsh-Powell algorithm.
wpColoring {
// create NodeVal for each node
var nvs = List.filled(_nn, null)
for (i in 0..._nn) {
var v = _nbr[i].count
if (v == 1 && _nbr[i][0] == i) { // isolated node
v = 0
}
nvs[i] = NodeVal.new(i, v)
}
// sort the NodeVals in descending order by valence
var cmp = Fn.new { |nv1, nv2| (nv2.v - nv1.v).sign }
Sort.insertion(nvs, cmp) // stable sort
// create colors list with entries for each node
var cols = List.filled(_nn, -1) // set all nodes to no color (-1) initially
var currCol = 0 // start with color 0
for (f in 0..._nn-1) {
var h = nvs[f].n
if (cols[h] != -1) { // already assigned a color
continue
}
cols[h] = currCol
// assign same color to all subsequent uncolored nodes which are
// not connected to a previous colored one
var i = f + 1
while (i < _nn) {
var outer = false
var j = nvs[i].n
if (cols[j] != -1) { // already colored
i = i + 1
continue
}
var k = f
while (k < i) {
var l = nvs[k].n
if (cols[l] == -1) { // not yet colored
k = k + 1
continue
}
if (_nbr[j].contains(l)) {
outer = true
break // node j is connected to an earlier colored node
}
k = k + 1
}
if (!outer) cols[j] = currCol
i = i + 1
}
currCol = currCol + 1
}
return cols
}
}
var fns = [Fn.new { |g| g.greedyColoring }, Fn.new { |g| g.wpColoring }]
var titles = ["'Greedy'", "Welsh-Powell"]
var nns = [4, 8, 8, 8]
var starts = [0, 1, 1, 1]
var edges1 = [[0, 1], [1, 2], [2, 0], [3, 3]]
var edges2 = [[1, 6], [1, 7], [1, 8], [2, 5], [2, 7], [2, 8],
[3, 5], [3, 6], [3, 8], [4, 5], [4, 6], [4, 7]]
var edges3 = [[1, 4], [1, 6], [1, 8], [3, 2], [3, 6], [3, 8],
[5, 2], [5, 4], [5, 8], [7, 2], [7, 4], [7, 6]]
var edges4 = [[1, 6], [7, 1], [8, 1], [5, 2], [2, 7], [2, 8],
[3, 5], [6, 3], [3, 8], [4, 5], [4, 6], [4, 7]]
var j = 0
for (fn in fns) {
System.print("Using the %(titles[j]) algorithm:\n")
var i = 0
for (edges in [edges1, edges2, edges3, edges4]) {
System.print(" Example %(i+1)")
var g = Graph.new(nns[i], starts[i])
for (e in edges) g.addEdge(e[0], e[1])
var cols = fn.call(g)
var ecount = 0 // counts edges
for (e in edges) {
if (e[0] != e[1]) {
Fmt.print(" Edge $d-$d -> Color $d, $d", e[0], e[1],
cols[e[0]-g.st], cols[e[1]-g.st])
ecount = ecount + 1
} else {
Fmt.print(" Node $d -> Color $d\n", e[0], cols[e[0]-g.st])
}
}
var maxCol = 0 // maximum color number used
for (col in cols) {
if (col > maxCol) maxCol = col
}
System.print(" Number of nodes : %(nns[i])")
System.print(" Number of edges : %(ecount)")
System.print(" Number of colors : %(maxCol+1)")
System.print()
i = i + 1
}
j = j + 1
}</syntaxhighlight>
{{out}}
<pre>
Using the 'Greedy' algorithm:
Example 1
Edge 0-1 -> Color 0, 1
Edge 1-2 -> Color 1, 2
Edge 2-0 -> Color 2, 0
Node 3 -> Color 0
Number of nodes : 4
Number of edges : 3
Number of colors : 3
Example 2
Edge 1-6 -> Color 0, 1
Edge 1-7 -> Color 0, 1
Edge 1-8 -> Color 0, 1
Edge 2-5 -> Color 0, 1
Edge 2-7 -> Color 0, 1
Edge 2-8 -> Color 0, 1
Edge 3-5 -> Color 0, 1
Edge 3-6 -> Color 0, 1
Edge 3-8 -> Color 0, 1
Edge 4-5 -> Color 0, 1
Edge 4-6 -> Color 0, 1
Edge 4-7 -> Color 0, 1
Number of nodes : 8
Number of edges : 12
Number of colors : 2
Example 3
Edge 1-4 -> Color 0, 1
Edge 1-6 -> Color 0, 2
Edge 1-8 -> Color 0, 3
Edge 3-2 -> Color 1, 0
Edge 3-6 -> Color 1, 2
Edge 3-8 -> Color 1, 3
Edge 5-2 -> Color 2, 0
Edge 5-4 -> Color 2, 1
Edge 5-8 -> Color 2, 3
Edge 7-2 -> Color 3, 0
Edge 7-4 -> Color 3, 1
Edge 7-6 -> Color 3, 2
Number of nodes : 8
Number of edges : 12
Number of colors : 4
Example 4
Edge 1-6 -> Color 0, 1
Edge 7-1 -> Color 1, 0
Edge 8-1 -> Color 1, 0
Edge 5-2 -> Color 1, 0
Edge 2-7 -> Color 0, 1
Edge 2-8 -> Color 0, 1
Edge 3-5 -> Color 0, 1
Edge 6-3 -> Color 1, 0
Edge 3-8 -> Color 0, 1
Edge 4-5 -> Color 0, 1
Edge 4-6 -> Color 0, 1
Edge 4-7 -> Color 0, 1
Number of nodes : 8
Number of edges : 12
Number of colors : 2
Using the Welsh-Powell algorithm:
Example 1
Edge 0-1 -> Color 0, 1
Edge 1-2 -> Color 1, 2
Edge 2-0 -> Color 2, 0
Node 3 -> Color 0
Number of nodes : 4
Number of edges : 3
Number of colors : 3
Example 2
Edge 1-6 -> Color 0, 1
Edge 1-7 -> Color 0, 1
Edge 1-8 -> Color 0, 1
Edge 2-5 -> Color 0, 1
Edge 2-7 -> Color 0, 1
Edge 2-8 -> Color 0, 1
Edge 3-5 -> Color 0, 1
Edge 3-6 -> Color 0, 1
Edge 3-8 -> Color 0, 1
Edge 4-5 -> Color 0, 1
Edge 4-6 -> Color 0, 1
Edge 4-7 -> Color 0, 1
Number of nodes : 8
Number of edges : 12
Number of colors : 2
Example 3
Edge 1-4 -> Color 0, 1
Edge 1-6 -> Color 0, 2
Edge 1-8 -> Color 0, 3
Edge 3-2 -> Color 1, 0
Edge 3-6 -> Color 1, 2
Edge 3-8 -> Color 1, 3
Edge 5-2 -> Color 2, 0
Edge 5-4 -> Color 2, 1
Edge 5-8 -> Color 2, 3
Edge 7-2 -> Color 3, 0
Edge 7-4 -> Color 3, 1
Edge 7-6 -> Color 3, 2
Number of nodes : 8
Number of edges : 12
Number of colors : 4
Example 4
Edge 1-6 -> Color 0, 1
Edge 7-1 -> Color 1, 0
Edge 8-1 -> Color 1, 0
Edge 5-2 -> Color 1, 0
Edge 2-7 -> Color 0, 1
Edge 2-8 -> Color 0, 1
Edge 3-5 -> Color 0, 1
Edge 6-3 -> Color 1, 0
Edge 3-8 -> Color 0, 1
Edge 4-5 -> Color 0, 1
Edge 4-6 -> Color 0, 1
Edge 4-7 -> Color 0, 1
Number of nodes : 8
Number of edges : 12
Number of colors : 2
</pre>
=={{header|zkl}}==
<syntaxhighlight lang="zkl">fcn colorGraph(nodeStr){ // "0-1 1-2 2-0 3"
numEdges,graph := 0,Dictionary(); // ( 0:(1,2), 1:L(0,2), 2:(1,0), 3:() )
foreach n in (nodeStr.split(" ")){ // parse string to graph
n=n - " ";
if(n.holds("-")){
a,b := n.split("-"); // keep as string
graph.appendV(a,b); graph.appendV(b,a);
numEdges+=1;
}
else graph[n]=T; // island
}
colors,colorPool := Dictionary(), ["A".."Z"].walk();
graph.pump(Void,'wrap([(node,nbrs)]){ // ( "1",(0,2), "3",() )
clrs:=colorPool.copy(); // all colors are available, then remove neighbours
foreach i in (nbrs){ clrs.remove(colors.find(i)) } // if nbr has color, color not available
colors[node] = clrs[0]; // first available remaining color
});
return(graph,colors,numEdges)
}</syntaxhighlight>
<syntaxhighlight lang="zkl">fcn printColoredGraph(graphStr){
graph,colors,numEdges := colorGraph(graphStr);
nodes:=graph.keys.sort();
println("Graph: ",graphStr);
println("Node/color: ",
nodes.pump(List,'wrap(v){ String(v,"/",colors[v]) }).concat(", "));
println("Node : neighbours --> colors:");
foreach node in (nodes){
ns:=graph[node];
println(node," : ",ns.concat(" ")," --> ",
colors[node]," : ",ns.apply(colors.get).concat(" "));
}
println("Number nodes: ",nodes.len());
println("Number edges: ",numEdges);
println("Number colors: ",
colors.values.pump(Dictionary().add.fp1(Void)).len()); // create set, count
println();
}</syntaxhighlight>
<syntaxhighlight lang="zkl">graphs:=T(
"0-1 1-2 2-0 3",
"1-6 1-7 1-8 2-5 2-7 2-8 3-5 3-6 3-8 4-5 4-6 4-7",
"1-4 1-6 1-8 3-2 3-6 3-8 5-2 5-4 5-8 7-2 7-4 7-6",
"1-6 7-1 8-1 5-2 2-7 2-8 3-5 6-3 3-8 4-5 4-6 4-7"
);
graphs.apply2(printColoredGraph);</syntaxhighlight>
{{out}}
<pre style="height:45ex">
Graph: 0-1 1-2 2-0 3
Node/color: 0/A, 1/B, 2/C, 3/A
Node : neighbours --> colors:
0 : 1 2 --> A : B C
1 : 0 2 --> B : A C
2 : 1 0 --> C : B A
3 : --> A :
Number nodes: 4
Number edges: 3
Number colors: 3
Graph: 1-6 1-7 1-8 2-5 2-7 2-8 3-5 3-6 3-8 4-5 4-6 4-7
Node/color: 1/A, 2/A, 3/A, 4/A, 5/B, 6/B, 7/B, 8/B
Node : neighbours --> colors:
1 : 6 7 8 --> A : B B B
2 : 5 7 8 --> A : B B B
3 : 5 6 8 --> A : B B B
4 : 5 6 7 --> A : B B B
5 : 2 3 4 --> B : A A A
6 : 1 3 4 --> B : A A A
7 : 1 2 4 --> B : A A A
8 : 1 2 3 --> B : A A A
Number nodes: 8
Number edges: 12
Number colors: 2
Graph: 1-4 1-6 1-8 3-2 3-6 3-8 5-2 5-4 5-8 7-2 7-4 7-6
Node/color: 1/A, 2/A, 3/B, 4/B, 5/C, 6/C, 7/D, 8/D
Node : neighbours --> colors:
1 : 4 6 8 --> A : B C D
2 : 3 5 7 --> A : B C D
3 : 2 6 8 --> B : A C D
4 : 1 5 7 --> B : A C D
5 : 2 4 8 --> C : A B D
6 : 1 3 7 --> C : A B D
7 : 2 4 6 --> D : A B C
8 : 1 3 5 --> D : A B C
Number nodes: 8
Number edges: 12
Number colors: 4
Graph: 1-6 7-1 8-1 5-2 2-7 2-8 3-5 6-3 3-8 4-5 4-6 4-7
Node/color: 1/A, 2/A, 3/A, 4/A, 5/B, 6/B, 7/B, 8/B
Node : neighbours --> colors:
1 : 6 7 8 --> A : B B B
2 : 5 7 8 --> A : B B B
3 : 5 6 8 --> A : B B B
4 : 5 6 7 --> A : B B B
5 : 2 3 4 --> B : A A A
6 : 1 3 4 --> B : A A A
7 : 1 2 4 --> B : A A A
8 : 1 2 3 --> B : A A A
Number nodes: 8
Number edges: 12
Number colors: 2
</pre>
| |||