All pastes #204280 Raw Edit

Something

public text v1 · immutable
#204280 ·published 2006-10-15 20:35 UTC
rendered paste body
#!/usr/bin/perl
use strict;

use DBI;

my $dbh = DBI->connect( blah blah blah );

sub findpath {
    my ($from, $to) = @_;
    
    my $sth = $dbh->prepare( "select dest from tablename where src = ?" );
    
    my %closed;
    my @open;

    # we start with the source node, a zero-length path
    push @open, [ $from ];

    while ( @open ) {
        # sort by length, shortest at the top.
        # note: this is much better implemented as a heap.
        @open = sort { scalar(@$a) <=> scalar(@$b) } @open;
        
        # $expand is the one we expand, it's the shortest.
        # remove it from @open, and keep it.
        my $expand = shift @open;

        # query for what's connected to the last node in the list
        $sth->execute($expand->[-1]);

        # and add each of the result rows as a new path,
        # the original path in $expand plus the new node.
        while ( my $row = $sth->fetchrow_arrayref ) {
            # skip the ones that we've closed (there are shorter paths already)
            next if exists $closed{$row->[0]};
            
            # close that node
            $closed{$row->[0]} = 1;

            # return the path if it goes where we want it to go.
            return @$expand, $row->[0] if $row->[0] == $to;
            
            # and add the appended path.
            push @open, [ @$expand, $row->[0] ];
        } # fetchrow
    } # while @open

    return undef; # no path to go from -> to.
}