#!/usr/bin/perl -w

my @links = map { [/^(\w+)\s+(\w+)/] } split /\n/, <<LINKS;
apple bug unid1 unid2
apple cat unid1 unid3
bug dog unid2 unid4
apple dog unid1 unid4
dog owl unid4 unid5
LINKS

# All links work both ways:
my %links;
for (@links) {
    my ($left,$right) = @$_;
    # We store all links in arrays
    $links{$left} ||= [];
    $links{$right} ||= [];

    # Links work both ways
    push @{$links{$left}}, $right;
    push @{$links{$right}}, $left;
}

sub find_joins {
    my ($start, $goal, $prefix, $visited) = @_;

    $visited ||= {}; # our breadcrumb trail so we dont
    $prefix ||= [];  # the path so far
    my $curr = $start;

    # warn "[@$prefix] $start => $goal";

    my @results; # All the paths that lead from $start to $end
    $visited->{$start} = 1;

    for my $link (grep { ! $visited->{$_} } @{$links{$start}}) {
        if ($link eq $goal) {
            push @results, [@$prefix,$start,$goal];
        } else {
            my %v = %$visited;
            push @results, find_joins($link,$goal,[@$prefix,$start],\%v);
        }
    }

    # Sort by length, then asciibetically
    @results = sort { scalar @$a <=> scalar @$b or $a->[0] cmp $b->[0] } @results;

    # print the whole thing with indices
    for $i ( 0 .. $#results ) {
        print "@{$results[$i]}\n";
    }

}
find_joins( 'apple' => 'owl' );

##</code><code>##

dbmathis@dbmathis-linux:~$ ./tmp.pl
apple bug dog owl

apple dog owl
Use of uninitialized value in string comparison (cmp) at ./tmp.pl line 46.
Use of uninitialized value in string comparison (cmp) at ./tmp.pl line 46.


dbmathis@dbmathis-linux:~$