Rosetta Code

Graph colouring: Difference between revisions

Page Discussion

Graph colouring (view source)

Revision as of 08:28, 10 February 2024

16,555 bytes added ,  4 months ago
Add C# implementation
(Add C# implementation)
(7 intermediate revisions by 4 users not shown)
Line 152:
{{trans|Python}}
 
<langsyntaxhighlight lang="11l">F first_avail_int(data)
‘return lowest int 0... not in data’
V d = Set(data)
Line 197:
(‘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)</langsyntaxhighlight>
 
{{out}}
Line 261:
#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>
 
Line 269 ⟶ 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 440 ⟶ 774:
}
}
}</langsyntaxhighlight>
 
{{out}}
Line 571 ⟶ 905:
=={{header|Haskell}}==
 
<langsyntaxhighlight lang="haskell">import Data.Maybe
import Data.List
import Control.Monad.State
Line 639 ⟶ 973:
mark c (n:ns) = do
modify ((n, c) :)
mark c (filter (`notElem` adjacentNodes g n) ns)</langsyntaxhighlight>
 
Simple usage examples:
Line 655 ⟶ 989:
 
The task:
<langsyntaxhighlight 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"
Line 672 ⟶ 1,006:
putStrLn "node\tcolor\tadjacent colors"
mapM_ mkLine ns
putStrLn ""</langsyntaxhighlight>
 
Runing greedy algorithm:
Line 777 ⟶ 1,111:
=={{header|J}}==
Greedy coloring satisfies the task requirements.
<langsyntaxhighlight Jlang="j">parse=: {{
ref=: 2$L:1(;:each cut y) -.L:1 ;:'-'
labels=: /:~~.;ref
Line 791 ⟶ 1,125:
end.
;colors
}}</langsyntaxhighlight>
 
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">
<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'
Line 828 ⟶ 1,162:
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>
</lang>
 
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:
 
<langsyntaxhighlight Jlang="j">anneal=: {{
best=. i.#y [ cost=. #~.greedy y
for.i.#y do.
Line 869 ⟶ 1,203:
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>
</lang>
 
=={{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 977 ⟶ 1,467:
prettyprintcolors(exgraph)
end
</langsyntaxhighlight>{{out}}
<pre>
Colors for the graph named Ex1:
Line 1,037 ⟶ 1,527:
 
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<langsyntaxhighlight Mathematicalang="mathematica">ClearAll[ColorGroups]
ColorGroups[g_Graph] := Module[{h, cols, indset, diffcols},
h = g;
Line 1,071 ⟶ 1,561:
3 \[UndirectedEdge] 5, 6 \[UndirectedEdge] 3,
3 \[UndirectedEdge] 8, 4 \[UndirectedEdge] 5,
4 \[UndirectedEdge] 6, 4 \[UndirectedEdge] 7}]]</langsyntaxhighlight>
{{out}}
<pre>Edge 0 to 1 has colors 1 and 3
Line 1,133 ⟶ 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 1,259 ⟶ 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 1,304 ⟶ 1,794:
=={{header|Perl}}==
{{trans|Raku}}
<langsyntaxhighlight lang="perl">use strict;
use warnings;
no warnings 'uninitialized';
Line 1,367 ⟶ 1,857:
say 'Unique : ' . uniq values %result;
say '';
}</langsyntaxhighlight>
{{out}}
<pre>Graph : (1 2), (2 3), (3 1), (4 ), (5 ), (6 )
Line 1,397 ⟶ 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...
<!--<langsyntaxhighlight Phixlang="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>
Line 1,470 ⟶ 1,960:
<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>
<!--</langsyntaxhighlight>-->
{{out}}
<pre>
Line 1,480 ⟶ 1,970:
 
=={{header|Python}}==
<langsyntaxhighlight lang="python">import re
from collections import defaultdict
from itertools import count
Line 1,552 ⟶ 2,042:
]:
g = Graph(name, connections)
g.greedy_colour()</langsyntaxhighlight>
 
{{out}}
Line 1,618 ⟶ 2,108:
 
Ex4 changes the order of nodes enough to affect the number of colours used.
 
=={{header|Racket}}==
{{incorrect|Racket|There appears to be a severe lack of code here.}}
 
<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,667 ⟶ 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,737 ⟶ 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,886 ⟶ 2,367:
}
j = j + 1
}</langsyntaxhighlight>
 
{{out}}
Line 2,018 ⟶ 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 2,036 ⟶ 2,517:
});
return(graph,colors,numEdges)
}</langsyntaxhighlight>
<langsyntaxhighlight lang="zkl">fcn printColoredGraph(graphStr){
graph,colors,numEdges := colorGraph(graphStr);
nodes:=graph.keys.sort();
Line 2,054 ⟶ 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 2,061 ⟶ 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/299012...354110"