Graph colouring: Difference between revisions

← Older edit

Graph colouring (view source)

Revision as of 08:28, 10 February 2024

67,316 bytes added , 3 months ago

Add C# implementation

Aspen138

338

edits

Revision as of 23:25, 12 March 2020 (view source) Petelomax (talk \| contribs) (→‎{{Header\|Phix}}) ← Older edit		Latest revision as of 08:28, 10 February 2024 (view source) Aspen138 (talk \| contribs) (Add C# implementation)
(33 intermediate revisions by 15 users not shown)
Line 1: {{~~draft~~ task}} 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. <~~lang~~syntaxhighlight lang="go">package main import ( Line 326 ⟶ 774: } } }</~~lang~~syntaxhighlight> {{out}} Line 455 ⟶ 903: </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. <~~lang~~syntaxhighlight lang="julia">using Random """Useful constants for the colors to be selected for nodes of the graph""" Line 562 ⟶ 1,467: prettyprintcolors(exgraph) end </~~lang~~syntaxhighlight>{{out}} <pre> Colors for the graph named Ex1: Line 621 ⟶ 1,526: </pre> =={{header\|~~Perl~~Mathematica}} 6/ {{header\|Wolfram Language}}== <syntaxhighlight lang="mathematica">ClearAll[ColorGroups] ~~<lang perl6>#!/usr/bin/env perl6~~ 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 ~~sub GraphNodeColor(@RAW) {~~ Edge 1 to 7 has colors 1 and 2 ~~my %OneMany = my %NodeColor;~~ Edge 1 to 8 has colors 1 and 2 ~~for @RAW { %OneMany{$_[0]}.push: $_[1] ; %OneMany{$_[1]}.push: $_[0] }~~ Edge 2 to 5 has colors 1 and 2 ~~my @ColorPool = "0", "1" … ^+%OneMany.elems; # as string~~ Edge 2 to 7 has colors 1 and 2 ~~my %NodePool = %OneMany.keys.SetHash;~~ Edge 2 to 8 has colors 1 and 2 ~~if %OneMany<NaN>:exists { # skip islanders for now~~ Edge 3 to 5 has colors 1 and 2 ~~%NodePool{$_}:delete for @(%OneMany<NaN>);~~ Edge 3 to 6 has colors 1 and 2 ~~%NodePool<NaN>:delete;~~ Edge 3 to 8 has colors 1 and 2 } Edge 4 to 5 has colors 1 and 2 ~~while %NodePool.Bool {~~ Edge 4 to 6 has colors 1 and 2 ~~my $color = @ColorPool.grab;~~ Edge 4 to 7 has colors 1 and 2 ~~my %TempPool = %NodePool;~~ Vertices: 8 ~~while (my \n = %TempPool.pick.key) {~~ Edges: 12 ~~%NodeColor{n} = $color;~~ Colors used: 2 ~~%TempPool{n}:delete;~~ ~~%TempPool{$_}:delete for @(%OneMany{n}) ; # skip neighbors as well~~ Edge 1 to 4 has colors 1 and 2 ~~%NodePool{n}:delete;~~ 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 ~~if %OneMany<NaN>:exists { # islanders use an existing color~~ Edge 3 to 6 has colors 1 and 2 ~~%NodeColor{$_} = %NodeColor.pick.value for @(%OneMany<NaN>)~~ Edge 3 to 8 has colors 1 and 2 } Edge 5 to 2 has colors 1 and 2 ~~return %NodeColor~~ 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 = [( [<0 [1>,<1 2>],<[2 0>,<3 ~~NaN>~~],<[3,1],[4 ~~NaN>~~,<undef],[5,undef],[6,undef] ~~NaN>~~], [<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>] ], [<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>] ], [<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>], ] ]); for my $d (@DATA) { ~~say~~ ~~"DATA~~my %result = ~~: ",~~GraphNodeColor @$_d; ~~say "Result : ";~~ my($graph,$colors); ~~my %out = GraphNodeColor $_;~~ ~~say~~ "$~~_[0]-$_[1]:\t~~graph ~~Color~~ ~~%out{$_[0]}~~.= "'(' . join(' ', @$_~~[1]~~) .~~isNaN??~~ '), '~~!!%out{$_[1]}~~ for @$_d; $colors .= ' ' . $result{$$_[0]} . '-' . ($result{$$_[1]} // '') . ' ' for @$d; ~~say "Nodes : ", %out.keys.elems;~~ ~~say "Edges : ", $_.elems;~~ say ~~"Colors~~'Graph : ",' ~~%out~~.~~values.Set.elems~~ $graph =~ s/,\s*$//r; say 'Colors : ' . $colors; ~~}</lang>~~ say 'Nodes : ' . keys %result; say 'Edges : ' . @$d; say 'Unique : ' . uniq values %result; say ''; }</syntaxhighlight> {{out}} <pre>~~DATA~~ Graph : ~~[(0 1)~~ (1 2), (2 03), (3 ~~NaN~~1), (4 ~~NaN~~), (5 ~~NaN~~)], (6 ) Colors : 0-1 1-2 2-0 0- 0- 0- ~~Result :~~ ~~0-1: Color 2 4~~ ~~1-2: Color 4 3~~ ~~2-0: Color 3 2~~ ~~3-NaN: Color 4~~ ~~4-NaN: Color 3~~ ~~5-NaN: Color 2~~ Nodes : 6 Edges : 6 ~~Colors~~Unique : 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)]~~ 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) ~~Result :~~ 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 ~~1-6: Color 5 6~~ ~~1-7: Color 5 6~~ ~~1-8: Color 5 6~~ ~~2-5: Color 5 6~~ ~~2-7: Color 5 6~~ ~~2-8: Color 5 6~~ ~~3-5: Color 5 6~~ ~~3-6: Color 5 6~~ ~~3-8: Color 5 6~~ ~~4-5: Color 5 6~~ ~~4-6: Color 5 6~~ ~~4-7: Color 5 6~~ Nodes : 8 Edges : 12 ~~Colors~~Unique : 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)]~~ 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) ~~Result :~~ 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 ~~1-4: Color 3 6~~ ~~1-6: Color 3 6~~ ~~1-8: Color 3 6~~ ~~3-2: Color 3 6~~ ~~3-6: Color 3 6~~ ~~3-8: Color 3 6~~ ~~5-2: Color 3 6~~ ~~5-4: Color 3 6~~ ~~5-8: Color 3 6~~ ~~7-2: Color 3 6~~ ~~7-4: Color 3 6~~ ~~7-6: Color 3 6~~ Nodes : 8 Edges : 12 ~~Colors~~Unique : 24 ~~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)]~~ 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) ~~Result :~~ 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 ~~1-6: Color 1 5~~ ~~7-1: Color 5 1~~ ~~8-1: Color 5 1~~ ~~5-2: Color 5 1~~ ~~2-7: Color 1 5~~ ~~2-8: Color 1 5~~ ~~3-5: Color 1 5~~ ~~6-3: Color 5 1~~ ~~3-8: Color 1 5~~ ~~4-5: Color 1 5~~ ~~4-6: Color 1 5~~ ~~4-7: Color 1 5~~ Nodes : 8 Edges : 12 ~~Colors~~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... ~~<lang Phix>-- demo\rosetta\Graph_colouring.exw~~ <!--<syntaxhighlight lang="phix">(phixonline)--> ~~constant tests = split("""~~ <span style="color: #000080;font-style:italic;">-- demo\rosetta\Graph_colouring.exw</span> ~~0-1 1-2 2-0 3~~ <span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> ~~1-6 1-7 1-8 2-5 2-7 2-8 3-5 3-6 3-8 4-5 4-6 4-7~~ <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-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 1-2 2-0 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""","\n")~~ 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 ~~function colour(sequence nodes, links, colours, soln, integer best, next, used=0)~~ 1-6 7-1 8-1 5-2 2-7 2-8 3-5 6-3 3-8 4-5 4-6 4-7 ~~-- fill/try each colours[next], recursing as rqd and saving any improvements.~~ """</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> ~~-- 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)).~~ <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> ~~-- On really big graphs I might consider making nodes..best static, esp colours.~~ <span style="color: #000080;font-style:italic;">-- fill/try each colours[next], recursing as rqd and saving any improvements. ~~integer c = 1~~ -- nodes/links are read-only here, colours is the main workspace, soln/best are ~~while c<best do~~ -- the results, next is 1..length(nodes), and used is length(unique(colours)). ~~bool avail = true~~ -- On really big graphs I might consider making nodes..best static, esp colours, ~~for i=1 to length(links[next]) do~~ -- in which case you will probably also want a if "colours~~[links~~[next]~~[i]]~~ ==c ~~then~~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> ~~avail = false~~ <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> ~~exit~~ <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> ~~end if~~ <span style="color: #004080;">bool</span> <span style="color: #000000;">avail</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span> ~~end for~~ <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> ~~if avail then~~ <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> ~~colours[next] = c~~ <span style="color: #000000;">avail</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span> ~~integer newused = used + (find(c,colours)==next)~~ if ~~next~~ <~~length(nodes)~~span ~~then~~style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> ~~{best,soln} = colour(nodes,links,colours,soln,best,next+1,newused)~~ <span style="color: #008080;">end</span> <span style="color: #008080;">for</span> ~~elsif newused<best then~~ <span style="color: #008080;">if</span> <span style="color: #000000;">avail</span> <span style="color: #008080;">then</span> ~~{best,soln} = {newused,colours}~~ <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> ~~end if~~ <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> ~~end if~~ <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> ~~c += 1~~ <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 while~~ <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> ~~return {best,soln}~~ <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> ~~end function~~ <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> ~~function add_node(sequence nodes, links, string n)~~ <span style="color: #000000;">c</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> ~~integer rdx = find(n,nodes)~~ <span style="color: #008080;">end</span> <span style="color: #008080;">while</span> ~~if rdx=0 then~~ <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> ~~nodes = append(nodes,n)~~ <span style="color: #008080;">end</span> <span style="color: #008080;">function</span> ~~links = append(links,{})~~ ~~rdx = length(nodes)~~ <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> ~~end if~~ <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> ~~return {nodes, links, rdx}~~ <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> ~~end function~~ <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> ~~for t=1 to length(tests) do~~ <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> ~~string tt = tests[t]~~ <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> ~~sequence lt = split(tt," "),~~ <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> ~~nodes = {},~~ <span style="color: #008080;">end</span> <span style="color: #008080;">function</span> ~~links = {}~~ ~~integer linkcount = 0, left, right~~ <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> ~~for l=1 to length(lt) do~~ <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> ~~sequence ll = split(lt[l],"-")~~ <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> ~~{nodes, links, left} = add_node(nodes,links,ll[1])~~ <span style="color: #000000;">nodes</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{},</span> ~~if length(ll)=2 then~~ <span style="color: #000000;">links</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span> ~~{nodes, links, right} = add_node(nodes,links,ll[2])~~ <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> ~~links[left] &= right~~ <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> ~~links[right] &= left~~ <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> ~~linkcount += 1~~ <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> ~~end if~~ <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> ~~end for~~ <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> ~~integer ln = length(nodes)~~ <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> ~~printf(1,"test%d: %d nodes, %d edges, ",{t,ln,linkcount})~~ <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> ~~sequence colours = repeat(0,ln),~~ <span style="color: #000000;">linkcount</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> ~~soln = tagset(ln) -- fallback solution~~ <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> ~~integer next = 1, best = ln~~ <span style="color: #008080;">end</span> <span style="color: #008080;">for</span> ~~printf(1,"%d colours:%v\n",colour(nodes,links,colours,soln,best,next))~~ <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> ~~end for</lang>~~ <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> Line 808 ⟶ 1,969: </pre> =={{~~Header~~header\|Python}}== <~~lang~~syntaxhighlight lang="python">import re from collections import defaultdict from itertools import count Line 881 ⟶ 2,042: ]: g = Graph(name, connections) g.greedy_colour()</~~lang~~syntaxhighlight> {{out}} Line 947 ⟶ 2,108: 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>