Rosetta Code

Graph colouring: Difference between revisions

Page Discussion

Graph colouring (view source)

Revision as of 11:54, 12 March 2020

519 bytes added ,  4 years ago
→‎{{header|Perl 6}}: Thanks Paddy3118 for the notification, update accordingly
m (→‎{{header|Go}}: Doh, typo reintroduced.)
(→‎{{header|Perl 6}}: Thanks Paddy3118 for the notification, update accordingly)
Line 456:
 
=={{header|Perl 6}}==
{{incomplete|Show for each edge, the colours assigned on each vertex.}}
<lang perl6>#!/usr/bin/env perl6
 
sub GraphNodeColor(@RAW) {
my %OneMany = my %NodeColor = ();
for @RAW { %OneMany{$_[0]}.push: $_[1] ; %OneMany{$_[1]}.push: $_[0] }
my @ColorPool = "0", "1" … ^+%OneMany.elems-2; # as string
my %NodePool = %OneMany.keys.SetHash;
if %OneMany<NilNaN>:exists { # skip islanders for now
%NodePool{$_}:delete for @(%OneMany<NilNaN>);
%NodePool<NilNaN>:delete;
}
while %NodePool.keys.Bool {
my $color = @ColorPool.grab;
my %TempPool = %NodePool;
while (my \n = %TempPool.keys.pick.key) {
%NodeColor{n} = $color;
%TempPool{n}:delete;
Line 478 ⟶ 477:
}
}
if %OneMany<NilNaN>:exists { # islanders use an existing color
%NodeColor{$_} = %NodeColor.values.pick.value for @(%OneMany<NilNaN>);
}
return %NodeColor
Line 485 ⟶ 484:
 
my \DATA = [
[<0 1>,<1 2>,<2 0>,<3 NilNaN>,<Nil 4 NaN>,<5 NilNaN>],
[<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>],
Line 493 ⟶ 492:
for DATA {
say "DATA : ", $_;
say "Result : ", my %output = GraphNodeColor $_;
my %out = GraphNodeColor $_;
say "Nodes : ", %output.keys.elems;▼
say "$_[0]-$_[1]:\t Color %out{$_[0]} ",$_[1].isNaN??''!!%out{$_[1]} for @$_;
▲ say "Nodes : ", %outputout.keys.elems;
say "Edges : ", $_.elems;
say "Colors : ", %outputout.values.Set.elems;
}</lang>
{{out}}
<pre>DATA   : [(0 1) (1 2) (2 0) (3 NilNaN) (Nil 4 NaN) (5 NilNaN)]
Result :
Result : {0 => 0, 1 => 5, 2 => 2, 3 => 0, 4 => 0, 5 => 0}
0-1: Color 2 4
Nodes  : 6▼
1-2: Color 4 3
Edges  : 6▼
2-0: Color 3 2
3-NaN: Color 4
4-NaN: Color 3
5-NaN: Color 2
▲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 :
Result : {1 => 4, 2 => 4, 3 => 4, 4 => 4, 5 => 5, 6 => 5, 7 => 5, 8 => 5}
1-6: Color 5 6
Nodes  : 8▼
1-7: Color 5 6
Edges  : 12▼
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 : 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 :
Result : {1 => 2, 2 => 3, 3 => 2, 4 => 3, 5 => 2, 6 => 3, 7 => 2, 8 => 3}
1-4: Color 3 6
Nodes  : 8▼
1-6: Color 3 6
Edges  : 12▼
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 : 2
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 :
Result : {1 => 6, 2 => 6, 3 => 6, 4 => 6, 5 => 4, 6 => 4, 7 => 4, 8 => 4}
1-6: Color 1 5
Nodes  : 8▼
7-1: Color 5 1
Edges  : 12▼
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 : 2</pre>
 
Hkdtam
351

edits

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