Graph colouring: Difference between revisions

Content added Content deleted
m (→‎{{header|Perl 6}}: deterministic output and with BagHash storing Node/NaN => # of Neighbors which can come in handy for future experiments)
Line 628: Line 628:
for @RAW { %OneMany{$_[0]}.push: $_[1] ; %OneMany{$_[1]}.push: $_[0] }
for @RAW { %OneMany{$_[0]}.push: $_[1] ; %OneMany{$_[1]}.push: $_[0] }
my @ColorPool = "0", "1" … ^+%OneMany.elems; # as string
my @ColorPool = "0", "1" … ^+%OneMany.elems; # as string
my %NodePool = %OneMany.keys.SetHash;
my %NodePool = %OneMany.BagHash; # this DWIM is nice
if %OneMany<NaN>:exists { # skip islanders for now
if %OneMany<NaN>:exists { %NodePool{$_}:delete for %OneMany<NaN>, NaN } # pending
%NodePool{$_}:delete for @(%OneMany<NaN>);
%NodePool<NaN>:delete;
}
while %NodePool.Bool {
while %NodePool.Bool {
my $color = @ColorPool.grab;
my $color = @ColorPool.shift;
my %TempPool = %NodePool;
my %TempPool = %NodePool;
while (my \n = %TempPool.pick.key) {
while (my \n = %TempPool.keys.sort.first) {
%NodeColor{n} = $color;
%NodeColor{n} = $color;
%TempPool{n}:delete;
%TempPool{n}:delete;
Line 644: Line 641:
}
}
if %OneMany<NaN>:exists { # islanders use an existing color
if %OneMany<NaN>:exists { # islanders use an existing color
%NodeColor{$_} = %NodeColor.pick.value for @(%OneMany<NaN>)
%NodeColor{$_} = %NodeColor.values.sort.first for @(%OneMany<NaN>)
}
}
return %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 = [
my \DATA = [
Line 668: Line 683:
<pre>DATA : [(0 1) (1 2) (2 0) (3 NaN) (4 NaN) (5 NaN)]
<pre>DATA : [(0 1) (1 2) (2 0) (3 NaN) (4 NaN) (5 NaN)]
Result :
Result :
0-1: Color 2 4
0-1: Color 0 1
1-2: Color 4 3
1-2: Color 1 2
2-0: Color 3 2
2-0: Color 2 0
3-NaN: Color 4
3-NaN: Color 0
4-NaN: Color 3
4-NaN: Color 0
5-NaN: Color 2
5-NaN: Color 0
Nodes : 6
Nodes : 6
Edges : 6
Edges : 6
Line 679: Line 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)]
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-6: Color 5 6
1-6: Color 0 1
1-7: Color 5 6
1-7: Color 0 1
1-8: Color 5 6
1-8: Color 0 1
2-5: Color 5 6
2-5: Color 0 1
2-7: Color 5 6
2-7: Color 0 1
2-8: Color 5 6
2-8: Color 0 1
3-5: Color 5 6
3-5: Color 0 1
3-6: Color 5 6
3-6: Color 0 1
3-8: Color 5 6
3-8: Color 0 1
4-5: Color 5 6
4-5: Color 0 1
4-6: Color 5 6
4-6: Color 0 1
4-7: Color 5 6
4-7: Color 0 1
Nodes : 8
Nodes : 8
Edges : 12
Edges : 12
Line 696: Line 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)]
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-4: Color 3 6
1-4: Color 0 1
1-6: Color 3 6
1-6: Color 0 2
1-8: Color 3 6
1-8: Color 0 3
3-2: Color 3 6
3-2: Color 1 0
3-6: Color 3 6
3-6: Color 1 2
3-8: Color 3 6
3-8: Color 1 3
5-2: Color 3 6
5-2: Color 2 0
5-4: Color 3 6
5-4: Color 2 1
5-8: Color 3 6
5-8: Color 2 3
7-2: Color 3 6
7-2: Color 3 0
7-4: Color 3 6
7-4: Color 3 1
7-6: Color 3 6
7-6: Color 3 2
Nodes : 8
Nodes : 8
Edges : 12
Edges : 12
Colors : 2
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)]
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: Color 1 5
1-6: Color 0 1
7-1: Color 5 1
7-1: Color 1 0
8-1: Color 5 1
8-1: Color 1 0
5-2: Color 5 1
5-2: Color 1 0
2-7: Color 1 5
2-7: Color 0 1
2-8: Color 1 5
2-8: Color 0 1
3-5: Color 1 5
3-5: Color 0 1
6-3: Color 5 1
6-3: Color 1 0
3-8: Color 1 5
3-8: Color 0 1
4-5: Color 1 5
4-5: Color 0 1
4-6: Color 1 5
4-6: Color 0 1
4-7: Color 1 5
4-7: Color 0 1
Nodes : 8
Nodes : 8
Edges : 12
Edges : 12
Retrieved from "https://rosettacode.org/wiki/Graph_colouring"