How timely, since just yesterday I discovered the tsort unix utility. Give it a list of edges, one on each line, in the form "A B", meaning that A must come before B. It will output a topological sorting.

blokhead,
The proof of concept you offered on your scratch of a TS is producing the same result as Algorithm::Dependency::Ordered (the wrong thing). I am not saying a TS isn't what I need, just that I am not seeing how to convince it to give me the list I want.

In my example above, your code gave me LA -> XYZ -> BLAH which only satisfies rule 1 above. To satisfy rule 2, FOO and 3 other items must also be removed. In other words, it only appears to go down (DFS) not back up. I am honestly not trying to be dense here. The code I am using is below:

Read more... (1039 Bytes)

Cheers - L~R

Oh, I think I see what you mean now..

Here is something that I think does what you want:

Read more... (1367 Bytes)
You do a DFS from the target, following edges backwards. The resulting list will tell you all of the items that depend on the target. These are all the items that we know must be removed if the target is to be removed (according to your rules). The fact that we used DFS here doesn't really matter, we just need a list of all vertices that can reach the target.

Now we have a list of items that must be removed. Before removing any item, we must first remove all of its dependents. This where the topological sort happens. Doing a DFS (following edges forward) from some item X results in a topological sorting of the items that must be removed if you want to remove X. So we can just do a DFS from each of vertices in that list. We re-use the %seen array so that these multiple DFS calls don't repeat (similar to how you would do topological sort on an entire graph, by starting new DFSes until everything has been seen).

On a side note, it seems slightly odd that you would remove all of FOO and all of its dependencies as a result of removing BLAH. What if BAR or XYZ are required elsewhere? Are there more conditions than are captured in this small example?

blokhead

Beeing lazy in programming, I'd try creative use of 'make': After transferring the dependencies into a Makefile, 'make -t' creates the dependeny tree in an empty directory as 0 byte files. After 'touch'ing the file to be removed, 'make -n' provides a suitable action plan that just needs reversing.

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 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]

I'm not that smart, so I just played with L~R's code and I got it to produce one of the outcomes you said was expected.

Code:

Test Run:

can you come up with an algorithm that solves the problem?

sub uninstall {
    my ($pkg) = @_;
    return if !installed($pkg);
    uninstall($_) for get_dependencies($pkg);
    ... uninstall $pkg here ...
}
[download]

Update: Ah, nevermind. That deletes dependencies that are still in use. Why would you want to do delete a dependency that's still in use? By that logic, uninstalling CGI::Simple should uninstall perl (strict's distribution).

Unless the ... uninstall $pkg here ... is more complicated than it seems, I think that this doesn't do what Limbic~Region wants: it will uninstall 'down', but not 'up'.

Yeah, realized and updated while you were posting.