Graph colouring: Difference between revisions
added Perl 6 programming solution
m (sp.) |
(added Perl 6 programming solution) |
||
Line 143:
+-----------------------------+
</pre>
=={{header|Perl 6}}==
<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<Nil>:exists { # skip islanders for now
%NodePool{$_}:delete for @(%OneMany<Nil>);
%NodePool<Nil>:delete;
}
while %NodePool.keys.Bool {
my $color = @ColorPool.grab;
my %TempPool = %NodePool;
while (my \n = %TempPool.keys.pick) {
%NodeColor{n} = $color;
%TempPool{n}:delete;
%TempPool{$_}:delete for @(%OneMany{n}) ; # skip neighbors as well
%NodePool{n}:delete;
}
}
if %OneMany<Nil>:exists { # islanders use an existing color
%NodeColor{$_} = %NodeColor.values.pick for @(%OneMany<Nil>);
}
return %NodeColor
}
my \DATA = [
[<0 1>,<1 2>,<2 0>,<3 Nil>,<Nil 4>,<5 Nil>],
[<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 %output = GraphNodeColor $_;
say "Nodes : ", %output.keys.elems;
say "Edges : ", $_.elems;
say "Colors : ", %output.values.Set.elems;
}</lang>
{{out}}
<pre>DATA : [(0 1) (1 2) (2 0) (3 Nil) (Nil 4) (5 Nil)]
Result : {0 => 0, 1 => 5, 2 => 2, 3 => 0, 4 => 0, 5 => 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 => 4, 2 => 4, 3 => 4, 4 => 4, 5 => 5, 6 => 5, 7 => 5, 8 => 5}
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 => 2, 2 => 3, 3 => 2, 4 => 3, 5 => 2, 6 => 3, 7 => 2, 8 => 3}
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 : {1 => 6, 2 => 6, 3 => 6, 4 => 6, 5 => 4, 6 => 4, 7 => 4, 8 => 4}
Nodes : 8
Edges : 12
Colors : 2</pre>
=={{Header|Python}}==
| |||