#!/usr/bin/perl

use strict;
use warnings;
use re 'eval';
   
my %graph;
my @path;

while (<DATA>) {
    chomp;
    my ($node, $edges) = split /\s*:\s*/;
    my @edges = split /\s*,\s*/ => $edges;
   
    foreach my $edge (@edges) {
        $graph {$node} {$edge} = 1
    }
}
my @nodes = keys %graph;
   
sub hamiltonian {
    my $regex = "";

    foreach my $c (0 .. $#nodes) {
        $regex .= '(?:';
        $regex .=  join "|\n   " =>
                    map {"(?{local \$q [$c] = \$nodes [$_]})"} 0 .. $#nodes;
        $regex .= ")\n";

        next unless $c;
       
        $regex .= "(?(?{";
        foreach my $d (0 .. $c - 1) {
            $regex .= "\$q [$c] eq \$q [$d] ||\n     ";
        }  
        $regex .= "!\$graph {\$q [" . ($c - 1) . "]} {\$q [" . $c . "]}";
        $regex .= "})x|)\n";
    }

    $regex .= "(?{ \@path = \@q })";

    $regex;
}
    
my $regex = hamiltonian;
   
if ("" =~ /$regex/x) {
    local $" = ", ";
    print "Found path [@path]\n";
}
else {
    print "No path found.\n";
}
    

__DATA__
v1: v2
v2: v1, v3, v4
v3: v2, v4
v4: v2, v3, v5
v5: v4, v6, v8
v6: v5, v7, v8
v7: v6, v8
v8: v5, v6, v7