How to resolve the algorithm Graph colouring step by step in the Raku programming language

Published on 12 May 2024 09:40 PM
#Raku

How to resolve the algorithm Graph colouring step by step in the Raku programming language

Table of Contents

Problem Statement

A Graph is a collection of nodes (or vertices), connected by edges (or not). Nodes directly connected by edges are called neighbours. In our representation of graphs, nodes are numbered and edges are represented by the two node numbers connected by the edge separated by a dash. Edges define the nodes being connected. Only unconnected nodes need a separate description. For example, Describes the following graph. Note that node 3 has no neighbours

A useful internal datastructure for a graph and for later graph algorithms is as a mapping between each node and the set/list of its neighbours. In the above example: Colour the vertices of a given graph so that no edge is between verticies of the same colour. The wp articles left-side graph The wp articles right-side graph which is the same graph as Ex2, but with different node orderings and namings. This is the same graph, node naming, and edge order as Ex2 except some of the edges x-y are flipped to y-x. This might alter the node order used in the greedy algorithm leading to differing numbers of colours.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Graph colouring step by step in the Raku programming language

Source code in the raku programming language

sub GraphNodeColor(@RAW) {
   my %OneMany = my %NodeColor;
   for @RAW { %OneMany{$_[0]}.push: $_[1] ; %OneMany{$_[1]}.push: $_[0] }
   my @ColorPool = "0", "1" … ^+%OneMany.elems; # as string
   my %NodePool  = %OneMany.BagHash; # this DWIM is nice
   if %OneMany:exists { %NodePool{$_}:delete for %OneMany, NaN } # pending
   while %NodePool.Bool {
      my $color = @ColorPool.shift;
      my %TempPool = %NodePool;
      while (my \n = %TempPool.keys.sort.first) {
         %NodeColor{n} = $color;
         %TempPool{n}:delete;
         %TempPool{$_}:delete for @(%OneMany{n}) ; # skip neighbors as well
         %NodePool{n}:delete;
      }
   }
   if %OneMany:exists { # islanders use an existing color
      %NodeColor{$_} = %NodeColor.values.sort.first for @(%OneMany)
   }
   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;
}

You may also check:How to resolve the algorithm Draw a sphere step by step in the Wren programming language
You may also check:How to resolve the algorithm Apply a callback to an array step by step in the Kotlin programming language
You may also check:How to resolve the algorithm Hofstadter Q sequence step by step in the FreeBASIC programming language
You may also check:How to resolve the algorithm IBAN step by step in the D programming language
You may also check:How to resolve the algorithm Menu step by step in the Sidef programming language