Beefy Boxes and Bandwidth Generously Provided by pair Networks
Welcome to the Monastery

Re: Algorithm For Uninstalling Dependencies

by JadeNB (Chaplain)
on Nov 20, 2009 at 23:01 UTC ( #808545=note: print w/replies, xml ) Need Help??

in reply to Algorithm For Uninstalling Dependencies

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; }
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 --^ : (); } }

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://808545]
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others about the Monastery: (5)
As of 2021-05-14 07:10 GMT
Find Nodes?
    Voting Booth?
    Perl 7 will be out ...

    Results (149 votes). Check out past polls.