Re: Graph labeling problem

Can you show a solution for 5 nodes? Or for 3 nodes? I fear it's nor possible to write a program to solve an unsolvable problem.

I understand "adjacent" as "having a common vertex".

#! /usr/bin/perl
use warnings;
use strict;
use feature qw{ say };

use Data::Dumper;
use Storable qw{ dclone };

my @LABELS = 'a' .. 'z';

sub add_edge {
    my ($edges) = @_;

    for my $v1 (sort keys %$edges) {
        for my $v2 (sort keys %$edges) {
            next if $v2 <= $v1
                 || exists $edges->{$v1}{$v2};

            my %labels = map { $_ => undef } @LABELS[0 .. keys(%$edges
+) - 2];
            delete @labels{ values %{ $edges->{$v1} },
                            values %{ $edges->{$v2} } };
            next unless keys %labels;

            for my $l (sort keys %labels) {
                my $e = dclone($edges);
                $e->{$v1}{$v2} = $e->{$v2}{$v1} = $l;

                unless (grep keys %{ $e->{$_} } != keys(%$e) - 1, keys
+ %$e) {
                    print Dumper $e;
                    exit
                }
                add_edge($e);
            }
        }
    }
}

my @vertices = (1 .. shift);
my %edges = (1 => {map {2 + $_ => $LABELS[$_]} 0 .. $#vertices - 1});
$edges{2 + $_} = {1 => $LABELS[$_]} for 0 .. $#vertices - 1;

add_edge(\%edges);
[download]

Update: Fixed a bug in the code. It's now still running searching for the solution for 5 nodes.

Update: The code now shows solutions for sizes 4, 6, and 8; and also shows there's no solution for sizes 3 and 5. Checking all the possibilities for larger sizes seems to be very slow.

map{substr$_->[0],$_->[1]||0,1}[\*||{},3],[[]],[ref qr-1,-,-1],[{}],[sub{}^*ARGV,3]

Comment on Re: Graph labeling problem Select or Download Code

Replies are listed 'Best First'.
Re^2: Graph labeling problem by LanX (Saint) on Feb 19, 2022 at 21:59 UTC
> I understand "adjacent" as "having a common vertex". Probably I'm having a fundamental misunderstanding of the problem ... ... but I think with just one more color it's trivial! Consider an incidence matrix (Node x Node) with the colors given in the cells (here RGBYCM...) Now a solution for N colors (instead of N-1) is straightforward, we just rotate the N colors left for each row. NB: The colors must be symmetric to the diagonal, because it's not a directed graph - i.e. `(a,b)=(b,a)` etc. That's guarantied by the rotation. The diagonal must be "emptied" at the end, because circular edges aren't allowed- i.e. `(a,a)=undef` Hence one color is missing in each row and column. `N=3 a b c a R G b R B c G B` [download] `N=4 a b c d a R G B b R B Y c G B R d B Y R` [download] `N=5 a b c d e a R G B Y b R B Y C c G B C R d B Y C G e Y C R G` [download] `N=6 a b c d e f a R G B Y C b R B Y C M c G B C M R d B Y C R G e Y C M R B f C M R G B` [download] Cheers Rolf _{(addicted to the Perl Programming Language :) Wikisyntax for the Monastery}	[reply] [d/l] [select]
Re^3: Graph labeling problem by choroba (Cardinal) on Feb 19, 2022 at 22:06 UTC
> Probably I'm having a fundamental misunderstanding of the problem ... Why? Do you understand "adjacent" in a different way? > but I think with one more color it's trivial Why "but"? I think so, too. `map{substr$_->[0],$_->[1]\|\|0,1}[\\|\|{},3],[[]],[ref qr-1,-,-1],[{}],[sub{}^ARGV,3]`	[reply] [d/l]
Re^4: Graph labeling problem by LanX (Saint) on Feb 19, 2022 at 22:13 UTC
> Why? Do you understand "adjacent" in a different way? No, in the first draft I thought I could easily improve the solution for the OP's N-1 problem based on this. But then I realized the limitations by symmetry. But I left the phrase in... just in case. Anyway - on a meta level - I realized that going for a (slightly) sub-optimal solution is almost ever the clever CS approach. Like here, why trying to solve a very hard mathematical problem just to spare one color? Cheers Rolf _{(addicted to the Perl Programming Language :) Wikisyntax for the Monastery}	[reply]
Re^2: Graph labeling problem by baxy77bax (Deacon) on Feb 19, 2022 at 20:40 UTC
when i was checking it manually i checked for 4 and 6 and just naively concluded there must be for others but u R right , 3 and 5 so far do not have the solution \|N\|-1! `e +-----------------------+ \| b \| +-----------------+ \| \| d \| \| +-----------+ \| \| \| a b \| e \| a \| 1-----2-----3-----4-----5 \| \| c \| \| +-----------+ \| d \| +-----------------+ \| c \| +-----------+` [download] PS this is definitely a solution but as u said for larger graphs it takes forever. Thnx!	[reply] [d/l]
Re^2: Graph labeling problem by etj (Priest) on Feb 20, 2022 at 15:47 UTC
You'd probably be better off using the Graph module rather than rolling your own?	[reply]
Re^3: Graph labeling problem by LanX (Saint) on Feb 20, 2022 at 15:53 UTC
Could you please elaborate how? There is no mention of colo(u)r in the whole POD of Graph Cheers Rolf _{(addicted to the Perl Programming Language :) Wikisyntax for the Monastery}	[reply]
Re^4: Graph labeling problem by etj (Priest) on Feb 24, 2022 at 19:16 UTC
Because then there is no need to write one's own `add_edges` etc. Graph does not have colouring methods for now, but pull-requests adding them (ideally with tests) are always welcome.	[reply] [d/l]
Re^5: Graph labeling problem by LanX (Saint) on Feb 25, 2022 at 10:53 UTC