Graph colouring: Difference between revisions
m
→{{header|Perl 6}}: deterministic output and with BagHash storing Node/NaN => # of Neighbors which can come in handy for future experiments
m (→{{header|Perl 6}}: deterministic output and with BagHash storing Node/NaN => # of Neighbors which can come in handy for future experiments) |
|||
Line 628:
for @RAW { %OneMany{$_[0]}.push: $_[1] ; %OneMany{$_[1]}.push: $_[0] }
my @ColorPool = "0", "1" … ^+%OneMany.elems; # as string
my %NodePool = %OneMany.
if %OneMany<NaN>:exists {
while %NodePool.Bool {
my $color = @ColorPool.
my %TempPool = %NodePool;
while (my \n = %TempPool.
%NodeColor{n} = $color;
%TempPool{n}:delete;
Line 644 ⟶ 641:
}
if %OneMany<NaN>:exists { # islanders use an existing color
%NodeColor{$_} = %NodeColor.
}
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;
}
my \DATA = [
Line 668 ⟶ 683:
<pre>DATA : [(0 1) (1 2) (2 0) (3 NaN) (4 NaN) (5 NaN)]
Result :
0-1: Color
1-2: Color
2-0: Color
3-NaN: Color
4-NaN: Color
5-NaN: Color
Nodes : 6
Edges : 6
Line 679 ⟶ 694:
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
1-7: Color
1-8: Color
2-5: Color
2-7: Color
2-8: Color
3-5: Color
3-6: Color
3-8: Color
4-5: Color
4-6: Color
4-7: Color
Nodes : 8
Edges : 12
Line 696 ⟶ 711:
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
1-6: Color
1-8: Color
3-2: Color
3-6: Color
3-8: Color
5-2: Color
5-4: Color
5-8: Color
7-2: Color 3
7-4: Color 3
7-6: Color 3
Nodes : 8
Edges : 12
Colors :
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
7-1: Color
8-1: Color
5-2: Color
2-7: Color
2-8: Color
3-5: Color
6-3: Color
3-8: Color
4-5: Color
4-6: Color
4-7: Color
Nodes : 8
Edges : 12
| |||