Beefy Boxes and Bandwidth Generously Provided by pair Networks
XP is just a number
 
PerlMonks  

Algorithm For Uninstalling Dependencies

by Limbic~Region (Chancellor)
on Nov 20, 2009 at 14:57 UTC ( #808454=perlquestion: print w/replies, xml ) Need Help??
Limbic~Region has asked for the wisdom of the Perl Monks concerning the following question:

All,
A co-worker has posed a problem to me. I haven't had time to work on it myself, but I think it is interesting and thought I would share. Given a dependency tree and a selected item, generate the ordered list of items that must be removed in order to remove the selected item. The rules are easy:
  • All dependencies must be removed first
  • Any item that depends on a removed item, must be removed after that item is removed

Consider the data below. The left most token is the item and all tokens to the right of it are the dependencies.

FOO BAR BLAH ASDF BAR LA BLAH XYZ ASDF OOOOO LA XYZ LA OOOOO

Let's say we want to remove BLAH. The following is my own mental representation of the process.

Simple path down: BLAH -> XYZ -> LA But now we look back up: LA <- BAR <- FOO XYZ <- BLAH <- FOO BLAH <- FOO And now we look back down again FOO -> ASDF -> OOOOO And finally back up ASDF <- FOO

So to remove 'BLAH', the following items must be removed:

BLAH XYZ LA BAR FOO ASDF OOOOO
In what order? I believe any of the following are viable.
LA -> XYZ -> BLAH -> BAR -> OOOOO -> ASDF -> FOO LA -> XYZ -> BLAH -> OOOOO -> ASDF -> BAR -> FOO LA -> XYZ -> BLAH -> OOOOO -> BAR -> ASDF -> FOO

I have looked at Algorithm::Dependency::Ordered but it doesn't do the right thing. Now assuming you have a valid tree (doesn't have an item that must be removed both before and after another item), can you come up with an algorithm that solves the problem?

UPDATE: It turns out these are the wrong requirements (though it is an interesting problem). For the actual (more boring) - see Re^4: Algorithm For Uninstalling Dependencies.

Cheers - L~R

Replies are listed 'Best First'.
Re: Algorithm For Uninstalling Dependencies
by blokhead (Monsignor) on Nov 20, 2009 at 15:35 UTC
    That's a topological sorting of a DAG! Graph.pm has a topological sort routine, and I'm sure you could find many other Perl implementations or even quickly roll your own (it's easy: if you can implement depth-first search, then you are about 2 lines of code away from a topological sort algorithm).

    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

      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:

      Cheers - L~R

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

        Here is something that I think does what you want:

        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

Re: Algorithm For Uninstalling Dependencies
by NiJo (Friar) on Nov 20, 2009 at 21:03 UTC
    The problem benind the question sounds like Limbic~Region's coworker is trying to write yet another package manager, e. g. for Linux distributions. The source code of e. g. apt (Debian, in C++) or portage (Gentoo, in Python) might provide further insight.

    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.

Re: Algorithm For Uninstalling Dependencies
by JadeNB (Chaplain) on Nov 20, 2009 at 23:01 UTC

    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 --^ : (); } }
Re: Algorithm For Uninstalling Dependencies
by VinsWorldcom (Parson) on Nov 20, 2009 at 19:17 UTC

    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.

    There are lots of extra "prints" in there so I can see what's happening with the recursion ...

    Code:

    Test Run:

Re: Algorithm For Uninstalling Dependencies
by ikegami (Pope) on Nov 20, 2009 at 20:08 UTC

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

    Don't you simply need a postfix visitor?

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

    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.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://808454]
Approved by marto
Front-paged by biohisham
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others making s'mores by the fire in the courtyard of the Monastery: (4)
As of 2018-06-20 01:05 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    Should cpanminus be part of the standard Perl release?



    Results (116 votes). Check out past polls.

    Notices?