Do you know where your variables are? PerlMonks

### Re^3: Algorithm For Uninstalling Dependencies

 on Nov 20, 2009 at 19:45 UTC ( #808515=note: print w/replies, xml ) Need Help??

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

Here is something that I think does what you want:

```use strict;

my %graph = (
FOO   => [qw/BAR BLAH ASDF/],
BAR   => [qw/LA/],
BLAH  => [qw/XYZ/],
ASDF  => [qw/OOOOO/],
LA    => [],
XYZ   => [qw/LA/],
OOOOO => []
);

my %reversegraph;
for my \$x (keys %graph) {
for my \$y (@{ \$graph{\$x} }) {
push @{\$reversegraph{\$y}}, \$x;
}
}

{
my %seen;
my %onstack;
my @list;

sub how_to_uninstall {
my \$target = shift;
(@list, %seen, %onstack) = ();

_traverse(\%reversegraph, \$target);
my @dependedontarget = @list;

(@list, %seen, %onstack) = ();
for my \$v (@dependedontarget) {
_traverse(\%graph, \$v) unless \$seen{\$v};
}

return @list;
}

sub _traverse {
my (\$G,\$x) = @_;
\$seen{\$x} = \$onstack{\$x} = 1;
for my \$y (@{\$G->{\$x}}) {
die "cyclic!" if \$onstack{\$y};    # back edge
_traverse(\$G,\$y) unless \$seen{\$y};
}
push @list, \$x;
\$onstack{\$x} = 0;
}
}
my @order = how_to_uninstall('BLAH');
print "@order\n";

__OUTPUT__
LA BAR XYZ BLAH OOOOO ASDF FOO
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?

Replies are listed 'Best First'.
Re^4: Algorithm For Uninstalling Dependencies
by Limbic~Region (Chancellor) on Nov 20, 2009 at 23:26 UTC
After an hour an a half, I convinced my co-worker he was full of contradictory statements and what he said he needed wasn't at all the correct definition of the problem. After figuring out what he really wanted to do, it turned out to be a simple matter of constructing a "depends on me" tree and then using the topological sort.

Cheers - L~R

Re^4: Algorithm For Uninstalling Dependencies
by Limbic~Region (Chancellor) on Nov 20, 2009 at 20:54 UTC
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.

Yes, it does seem odd. There is a 3rd unwritten rule that says

• You can't uninstall an item that has a non-existent dependency
In other words, if I get rid of BLAH without getting rid of FOO, I can never get rid of FOO. Also, there is no reason not to get rid of FOO because it will no longer work. I will confer with my co-worker to determine if there is an exception to this rule (a "must keep" list that says it is ok to leave a package in an inconsistent state). Alternatively, I will ask him if there is a technical restriction on removing a package before its dependencies since that would allow me to get rid of FOO but leave the other packages it depends on.

Cheers - L~R

Create A New User
Node Status?
node history
Node Type: note [id://808515]
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-05-26 02:41 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
World peace can best be achieved by:

Results (192 votes). Check out past polls.

Notices?