Graph colouring: Difference between revisions

{{trans|Python}}

 

‘return lowest int 0... not in data’

V d = Set(data)

(‘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’)]

 

{{out}}

 

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.

 

import (

}

}

 

{{out}}

=={{header|Haskell}}==

 

import Data.List

import Control.Monad.State

mark c (n:ns) = do

modify ((n, c) :)

 

Simple usage examples:

 

The task:

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"

putStrLn "node\tcolor\tadjacent colors"

mapM_ mkLine ns

 

Runing greedy algorithm:

=={{header|J}}==

Greedy coloring satisfies the task requirements.

ref=: 2$L:1(;:each cut y) -.L:1 ;:'-'

labels=: /:~~.;ref

end.

;colors

 

To display colors for edges, we show the graph specification and beneath the representation of each edge A-B we show colorA:colorB.

 

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'

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

 

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:

 

best=. i.#y [ cost=. #~.greedy y

for.i.#y do.

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

 

=={{header|Julia}}==

Uses a repeated randomization of node color ordering to seek a minimum number of colors needed.

 

"""Useful constants for the colors to be selected for nodes of the graph"""

prettyprintcolors(exgraph)

end

<pre>

Colors for the graph named Ex1:

 

=={{header|Mathematica}} / {{header|Wolfram Language}}==

ColorGroups[g_Graph] := Module[{h, cols, indset, diffcols},

h = g;

3 \[UndirectedEdge] 5, 6 \[UndirectedEdge] 3,

3 \[UndirectedEdge] 8, 4 \[UndirectedEdge] 5,

{{out}}

<pre>Edge 0 to 1 has colors 1 and 3

For the four examples, it gives the minimal number of colors.

 

 

const NoColor = 0

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")

 

{{out}}

=={{header|Perl}}==

{{trans|Raku}}

use warnings;

no warnings 'uninitialized';

say 'Unique : ' . uniq values %result;

say '';

{{out}}

<pre>Graph : (1 2), (2 3), (3 1), (4 ), (5 ), (6 )

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...

<span style="color: #000080;font-style:italic;">-- demo\rosetta\Graph_colouring.exw</span>

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #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>

{{out}}

<pre>

 

=={{header|Python}}==

from collections import defaultdict

from itertools import count

]:

g = Graph(name, connections)

 

{{out}}

=={{header|Raku}}==

(formerly Perl 6)

my %OneMany = my %NodeColor;

for @RAW { %OneMany{$_[0]}.push: $_[1] ; %OneMany{$_[1]}.push: $_[0] }

say "Edges : ", $_.elems;

say "Colors : ", %out.values.Set.elems;

{{out}}

<pre>DATA : [(0 1) (1 2) (2 0) (3 NaN) (4 NaN) (5 NaN)]

{{libheader|Wren-sort}}

{{libheader|Wren-fmt}}

import "/sort" for Sort

import "/fmt" for Fmt

}

j = j + 1

 

{{out}}

 

=={{header|zkl}}==

numEdges,graph := 0,Dictionary(); // ( 0:(1,2), 1:L(0,2), 2:(1,0), 3:() )

foreach n in (nodeStr.split(" ")){ // parse string to graph

});

return(graph,colors,numEdges)

graph,colors,numEdges := colorGraph(graphStr);

nodes:=graph.keys.sort();

colors.values.pump(Dictionary().add.fp1(Void)).len()); // create set, count

println();

"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-6 7-1 8-1 5-2 2-7 2-8 3-5 6-3 3-8 4-5 4-6 4-7"

);

{{out}}

<pre style="height:45ex">