Maybe I've got my terminology mixed up, but I am a bit unhappy with the idea of installing the dependencies before their dependents. That means that, if the uninstall is interrupted, then the repository will be in an inconsistent state. Did you mean to remove dependents first? If so, then, as ikegami points out, why would you want to remove dependencies at all? It seems like this will allow you to knock out a large repository more or less inadvertently.

Anyway, below is my attempt at code that will accomplish this, with ‘dependency’ replaced by ‘down’ and ‘dependent’ replaced by ‘up’ (to fit with how I was thinking of the problem). mk_kv and reverse_hoa are just for parsing your dependency specification into a HoA. This particular algorithm found the uninstallation order LA -> XYZ -> BLAH -> BAR -> OOOOO -> ASDF -> FOO when I ran it; it's sort of non-deterministic, since it depends on the order of the entries returned from a call to keys.

sub mk_kv; sub reverse_hoa;

sub mk_kv {
    return $_[0] => [ @_[1 .. $#_] ];
}

sub reverse_hoa {
    my %hoa = @_;
    my %reversed;
    for my $key ( keys %hoa ) {
        for my $value ( @{$hoa{$key}} ) {
            push @{$reversed{$value}}, $key
        }
    }
    return %reversed;
}
[download]

sub remove; sub remove_down; sub remove_up;
my $down = { map { mk_kv split / /, $_ } split /\n/, $graph }; # $down
+->{$key} is an arrayref of the modules downstream from $key
my $up = { reverse_hoa %$down }; # $up->{$key} is an arrayref of the m
+odules upstream from $key

remove $down, $up, $remove; # This returns an array listing the module
+s to be uninstalled, with the earliest leftmost.

{
my ( $down, $up );
my ( %removed, %to_remove, @spare );

sub remove {
    my $remove;
    ( $down, $up, $remove ) = @_;
    undef %removed;
    undef %to_remove;
    return remove_down($remove), remove_up;
}

sub remove_down {
    my ( $remove ) = @_;
    if ( exists $removed{$remove} ) {
        return ()
    } else {
        undef $removed{$remove}; # $remove has been removed
        undef @to_remove{@spare} if @spare = @{$up->{$remove}}; # All 
+modules up stream from $remove should be removed in post-processing
            # undef @hash{()} fails
        delete @to_remove{keys %removed}; # Don't remove in post-proce
+ssing if already removed
        return map( { remove_down $_ } @{$down->{$remove}} ), $remove;
    }
}

sub remove_up {
    return ( @spare = keys %to_remove )  ?
        ( ( map { remove_down $_ } @spare ), remove_up )
            # FALSE --v
            #       The call to remove_down is almost certainly unnece
+ssary, except for the side effect of setting keys in %to_remove
            # FALSE --^
    :
        ();
}
}
[download]