#!/usr/bin/perl
use strict;
use warnings;

my %all_pkg;
my %want_rm;
my %must_keep = map {$_ => 1} grep {! $want_rm{$_}} keys %all_pkg;

my %tree;

for my $pkg (keys %all_pkg) {
    push @{$tree{$_}}, $pkg for dependencies($pkg);
}

PACKAGE:
for my $pkg (keys %want_rm) {
    my @rm_order = how_to_uninstall($pkg);
    for (@rm_order) {
        if ($must_keep{$_}) {
            print "Can't remove $pkg - depends on $_ which is a must keep\n";
            next PACKAGE;
        }
    }
    print "Safe to remove $pkg\n";
    for (@rm_order) {
        print "\tRemoving $_\n";
        remove_pkg($_);
    }
}

sub dependencies {
    my ($pkg) = @_;
    # Functionality to return list of dependencies
}

sub remove_pkg {
    my ($pkg) = @_;
    # Functionality to remove a package
}

{
    my %seen;
    my %onstack;
    my @list;
    sub how_to_uninstall {
        my $target = shift;
        (@list, %seen, %onstack) = ();
        _traverse($target);
        return @list;
    }
    sub _traverse {
        my $x = shift;
        $seen{$x} = $onstack{$x} = 1;
        for my $y (@{$tree{$x}}) {
            die "cyclic!" if $onstack{$y};
            _traverse($y) unless $seen{$y};
        }
        push @list, $x;
        $onstack{$x} = 0;
    }
}