jcpunk has asked for the wisdom of the Perl Monks concerning the following question:

I have searched google and thepen to no avail (my guess is that I am not searching for the right stuff) thus I appeal to you...
I am writting a function where I will be given a list of items that are selected. Each of these items (save one) has a dependency on another of those items. I need to sort them in order of dependency.

Example:
Object   => Dependency
1        => undef (no dependency)
2        => 4
3        => 5
4        => 3
5        => 1

[download]
I am given 1,2,3,4,5 and I need back 1,5,3,4,2

Here is my failed attempt at solving this... Could I ask that someone show me either what I have missed that makes it loop endlessly or a far simpler way of doing this..

%ArgHash is structued $ArgHash{$version}=csv,list,of,selected
and bubble sort stinks but I cannot think of a different way to do this...I am unenlightened
sub sortPatch
 {
  my %ArgHash=@_;

  my $version = join('',keys(%ArgHash));
  my @tbs = split(/\,/,$ArgHash{$version});

  my @LoopControl=@tbs;
  my @returning;

  foreach (@tbs,(1))  # this should make it go one more time... right?
   {
    my ($previous,$patchlist);
    foreach my $patch (@LoopControl)
     {
      undef($previous);
      undef($patchlist);
      $previous=$PatchInfo::patch{$version}{$patch}{'PREVIOUS'} if (de
+fined($PatchInfo::patch{$version}{$patch}{'PREVIOUS'}));
      $patchlist = join('|',@returning);

      if (defined($previous))
       {
        if (($previous ne '') and (not($previous =~ /$patchlist/)))
         {
          my $selected = join('|',@tbs);
          if (($previous =~ /$selected/) and ($selected ne ''))
           {
            push(@returning,$previous);
           }
         }
       }
      push(@returning,$patch);
     }
    @LoopControl=();
    @LoopControl=@returning;
   }

  return @returning;
 }

[download]

jcpunk
help?

Replies are listed 'Best First'.
Re: Sorting by association, a tail of dependency resolving gone nowhere
by Roy Johnson (Monsignor) on Dec 12, 2005 at 17:33 UTC
    Sounds like Re: Problems with sorting (recommending Sort::Topological) might be of help.

    If you'd rather roll your own, I thought this solution was rather elegant: 

    my %dmap = (
1        => undef,
2        => 4,
3        => 5,
4        => 3,
5        => 1,
);

my @sorted;
my %sorted_contents;
my %tried;

sub insert {
  my $candidate = $_[0];
  return if exists $sorted_contents{$candidate};
  die "Cycle!\n" if $tried{$candidate}++;
  my $dependency = $dmap{$candidate};
  insert($dependency) if (defined $dependency);
  $sorted_contents{$candidate} = push @sorted, $candidate;
}

insert $_ for keys %dmap;

print "@sorted\n";

    [download]
    Caution: Contents may have been coded under pressure.
[reply]
[d/l]
Re: Sorting by association, a tail of dependency resolving gone nowhere
by Celada (Monk) on Dec 12, 2005 at 18:17 UTC
    Check out the tsort utility, it already does this.
[reply]
Re: Sorting by association, a tail of dependency resolving gone nowhere
by ikegami (Patriarch) on Dec 12, 2005 at 17:33 UTC
    There doesn't seem to be any sorting involved in your example. 
    my %depends_on = (
   1 => undef,
   2 => 4,
   3 => 5,
   4 => 3,
   5 => 1,
);

my %dependant_of;
@dependant_of{values(%depends_on)} = keys(%depends_on);

my @sorted;

foreach (grep { !defined($depends_on{$_}) } keys(%depends_on)) {
   my $next = $_;

   while (defined $next) {
      push(@sorted, $next);
      $next = $dependant_of{$next};
   }
}

print(join(', ', @sorted), "\n");  # 1, 5, 3, 4, 2

    [download]

    Update: Rewrite. Original solution was wrong.

    Update: Fixed problem mentioned by Roy Johnson.

[reply]
[d/l]
      That solution depends on starting with the right $next. I don't think that's a reasonable precondition.
      Caution: Contents may have been coded under pressure.
[reply]
[d/l]
Re: Sorting by association, a tail of dependency resolving gone nowhere
by Not_a_Number (Prior) on Dec 12, 2005 at 21:36 UTC

    Dunno if this helps (a bit late) but my take would be something like:

    my %dmap = (
  1 => undef,
  2 => 4,
  3 => 5,
  4 => 3,
  5 => 1,
);

my $key = 0;
defined $dmap{$_} or $dmap{$_} = $key for keys %dmap;

my %pamd = reverse %dmap;
print $key = $pamd{$key} while $pamd{$key};

    [download]
[reply]
[d/l]
Re: Sorting by association, a tail of dependency resolving gone nowhere
by mikeraz (Friar) on Dec 12, 2005 at 18:01 UTC

    If your data is indeed stored in a hash you could do something like: 

    #!/usr/bin/perl -w
use strict;

my (%sortme, $k);

%sortme = (
        1 => undef,
        2 => 4,
        3 => 5,
        4 => 3,
        5 => 1,
        6 => 3
);

foreach $k ( sort {
                return -1 if !defined $sortme{$a};
                return 1 if !defined $sortme{$b};
                $sortme{$a} <=> $sortme{$b};
            } keys %sortme ) {
        print "$k -> $sortme{$k}\n";
}

    [download]
    substituding the print statement with whatever is needed for your larger application. Note that my example works if two keys have the same dependency. And you'll get a warning about uninitialzed value when it tries to print $sortme{1};

    Be Appropriate && Follow Your Curiosity
[reply]
[d/l]
      That doesn't produce a list in dependency order, it produces a list in numeric order of dependencies. 3, upon which 6 and 4 depend, ends up being printed last.
      Caution: Contents may have been coded under pressure.
[reply]

        <forehead slap />

        Be Appropriate && Follow Your Curiosity
[reply]
Re: Sorting by association, a tail of dependency resolving gone nowhere
by holli (Abbot) on Dec 12, 2005 at 17:38 UTC
    No need to implement your own sort. 
    my %dmap =  
(
  1 => 0
  2 => 4
  3 => 5
  4 => 3
  5 => 1
);

my @tosort = (1,2,3,4,5);
my @sorted = sort { $dmap{$a} <=> $dmap{$b} } @tosort;

    [download]
    Update: Corrected typos (thanks Roy Johnson and Ikegami)


    holli, /regexed monk/
[reply]
[d/l]
      Output of your program comes out: 1,5,4,2,3. It should be: 1,5,3,4,2
      --Artist
[reply]
[d/l]

Back to Seekers of Perl Wisdom