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

comment on

( #3333=superdoc: 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?

blokhead


In reply to Re^3: Algorithm For Uninstalling Dependencies by blokhead
in thread Algorithm For Uninstalling Dependencies by Limbic~Region

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Are you posting in the right place? Check out Where do I post X? to know for sure.
  • Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
    <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
  • Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
  • Want more info? How to link or or How to display code and escape characters are good places to start.
Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others taking refuge in the Monastery: (3)
As of 2021-10-26 05:32 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    My first memorable Perl project was:







    Results (90 votes). Check out past polls.

    Notices?