Rosetta Code

Graph colouring: Difference between revisions

Page Discussion

Graph colouring (view source)

Revision as of 08:28, 10 February 2024

46,736 bytes added ,  4 months ago
Add C# implementation
(Added Wren)
(Add C# implementation)
(17 intermediate revisions by 9 users not shown)
Line 148:
* [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}}==
Line 155 ⟶ 603:
 
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.
<langsyntaxhighlight lang="go">package main
 
import (
Line 326 ⟶ 774:
}
}
}</langsyntaxhighlight>
 
{{out}}
Line 453 ⟶ 901:
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.
<langsyntaxhighlight lang="julia">using Random
 
"""Useful constants for the colors to be selected for nodes of the graph"""
Line 561 ⟶ 1,467:
prettyprintcolors(exgraph)
end
</langsyntaxhighlight>{{out}}
<pre>
Colors for the graph named Ex1:
Line 619 ⟶ 1,525:
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}}==
Line 625 ⟶ 1,623:
For the four examples, it gives the minimal number of colors.
 
<langsyntaxhighlight Nimlang="nim">import algorithm, sequtils, strscans, strutils, tables
 
const NoColor = 0
Line 751 ⟶ 1,749:
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")</langsyntaxhighlight>
 
{{out}}
Line 796 ⟶ 1,794:
=={{header|Perl}}==
{{trans|Raku}}
<langsyntaxhighlight lang="perl">use strict;
use warnings;
no warnings 'uninitialized';
Line 859 ⟶ 1,857:
say 'Unique : ' . uniq values %result;
say '';
}</langsyntaxhighlight>
{{out}}
<pre>Graph : (1 2), (2 3), (3 1), (4 ), (5 ), (6 )
Line 889 ⟶ 1,887:
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)-->
<lang Phix>-- demo\rosetta\Graph_colouring.exw
<span style="color: #000080;font-style:italic;">-- demo\rosetta\Graph_colouring.exw</span>
constant tests = split("""
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
0-1 1-2 2-0 3
<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;">"""
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 0-4 1-6 1-82 3-2 3-60 3-8 5-2 5-4 5-8 7-2 7-4 7-6
1-6 7-1 8-17 51-8 2-5 2-7 2-8 3-5 6-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
""","\n",true)
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>
function colour(sequence nodes, links, colours, soln, integer best, next, used=0)
-- fill/try each colours[next], recursing as rqd and saving any improvements.
<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>
-- nodes/links are read-only here, colours is the main workspace, soln/best are
<span style="color: #000080;font-style:italic;">-- fill/try each colours[next], recursing as rqd and saving any improvements.
-- the results, next is 1..length(nodes), and used is length(unique(colours)).
-- nodes/links are read-only here, colours is the main workspace, soln/best are
-- On really big graphs I might consider making nodes..best static, esp colours,
-- the results, next is 1..length(nodes), and used is length(unique(colours)).
-- in which case you will probably also want a "colours[next] = 0" reset below.
-- On really big graphs I might consider making nodes..best static, esp colours,
integer c = 1
-- in which case you will probably also want a "colours[next] = 0" reset below.</span>
while c<best do
<span style="color: #004080;">integer</span> <span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
bool avail = true
<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>
for i=1 to length(links[next]) do
<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>
if colours[links[next][i]]==c then
<span style="color: #004080;">bool</span> <span style="color: #000000;">avail</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span>
avail = false
<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>
exit
<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>
end if
<span style="color: #000000;">avail</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span>
end for
<span style="color: #008080;">exit</span>
if avail then
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
colours[next] = c
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
integer newused = used + (find(c,colours)==next)
<span style="color: #008080;">if</span> <span style="color: #000000;">avail</span> <span style="color: #008080;">then</span>
if next<length(nodes) then
<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>
{best,soln} = colour(nodes,links,colours,soln,best,next+1,newused)
<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>
elsif newused<best then
<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>
{best,soln} = {newused,colours}
<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>
end if
<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>
end if
<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>
c += 1
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end while
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
return {best,soln}
<span style="color: #000000;">c</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
end function
<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>
function add_node(sequence nodes, links, string n)
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
integer rdx = find(n,nodes)
if rdx=0 then
<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>
nodes = append(nodes,n)
<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>
links = append(links,{})
<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>
rdx = length(nodes)
<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>
end if
<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>
return {nodes, links, rdx}
<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>
end function
<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>
for t=1 to length(tests) do
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
string tt = tests[t]
sequence lt = split(tt," "),
<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>
nodes = {},
<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>
links = {}
<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>
integer linkcount = 0, left, right
<span style="color: #000000;">nodes</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{},</span>
for l=1 to length(lt) do
<span style="color: #000000;">links</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
sequence ll = split(lt[l],"-")
<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>
{nodes, links, left} = add_node(nodes,links,ll[1])
<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>
if length(ll)=2 then
<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>
{nodes, links, right} = add_node(nodes,links,ll[2])
<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>
links[left] &= right
<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>
links[right] &= left
<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>
linkcount += 1
<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>
end if
<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>
end for
<span style="color: #000000;">linkcount</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
integer ln = length(nodes)
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
printf(1,"test%d: %d nodes, %d edges, ",{t,ln,linkcount})
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
sequence colours = repeat(0,ln),
<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>
soln = tagset(ln) -- fallback solution
<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>
integer next = 1, best = ln
<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>
printf(1,"%d colours:%v\n",colour(nodes,links,colours,soln,best,next))
<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>
end for</lang>
<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>
Line 968 ⟶ 1,970:
 
=={{header|Python}}==
<langsyntaxhighlight lang="python">import re
from collections import defaultdict
from itertools import count
Line 1,040 ⟶ 2,042:
]:
g = Graph(name, connections)
g.greedy_colour()</langsyntaxhighlight>
 
{{out}}
Line 1,106 ⟶ 2,108:
 
Ex4 changes the order of nodes enough to affect the number of colours used.
 
=={{header|Racket}}==
 
<lang racket></lang>
 
{{out}}
 
<pre></pre>
 
=={{header|Raku}}==
(formerly Perl 6)
<syntaxhighlight lang="raku" perl6line>sub GraphNodeColor(@RAW) {
my %OneMany = my %NodeColor;
for @RAW { %OneMany{$_[0]}.push: $_[1] ; %OneMany{$_[1]}.push: $_[0] }
Line 1,154 ⟶ 2,148:
say "Edges : ", $_.elems;
say "Colors : ", %out.values.Set.elems;
}</langsyntaxhighlight>
{{out}}
<pre>DATA : [(0 1) (1 2) (2 0) (3 NaN) (4 NaN) (5 NaN)]
Line 1,224 ⟶ 2,218:
{{libheader|Wren-sort}}
{{libheader|Wren-fmt}}
<langsyntaxhighlight ecmascriptlang="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
Line 1,373 ⟶ 2,367:
}
j = j + 1
}</langsyntaxhighlight>
 
{{out}}
Line 1,505 ⟶ 2,499:
 
=={{header|zkl}}==
<langsyntaxhighlight 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
Line 1,523 ⟶ 2,517:
});
return(graph,colors,numEdges)
}</langsyntaxhighlight>
<langsyntaxhighlight lang="zkl">fcn printColoredGraph(graphStr){
graph,colors,numEdges := colorGraph(graphStr);
nodes:=graph.keys.sort();
Line 1,541 ⟶ 2,535:
colors.values.pump(Dictionary().add.fp1(Void)).len()); // create set, count
println();
}</langsyntaxhighlight>
<langsyntaxhighlight 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",
Line 1,548 ⟶ 2,542:
"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);</langsyntaxhighlight>
{{out}}
<pre style="height:45ex">
Aspen138
338

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/299002...354110"