Ordering array by dependencies with perl

algorithm, cpan, graph, perl, sorting

Solution

Using Graph:

use Graph qw( );

my @recs = (
   { id => "id2",    requires => 'someid', text => "another text2" },
   { id => "xid4",   requires => 'id2',    text => "text44" },
   { id => "someid", requires => undef,    text => "some text" },
   { id => "id2",    requires => 'someid', text => "another text2" },
   { id => "aid",    requires => undef,    text => "alone text" },
   { id => "id2",    requires => 'someid', text => "another text2" },
   { id => "xid3",   requires => 'id2',    text => "text33" },
);

sub get_ordered_recs {
   my %recs;
   my $graph = Graph->new();
   for my $rec (@_) {
      my ($id, $requires) = @{$rec}{qw( id requires )};

      $graph->add_vertex($id);
      $graph->add_edge($requires, $id) if $requires;

      $recs{$id} = $rec;
   }

   return map $recs{$_}, $graph->topological_sort();
}

my @texts = map $_->{text}, get_ordered_recs(@recs);

Problem

Have an array of hashes, ``` my @arr = get_from_somewhere(); ``` the @arr contents (for example) is: ``` @arr = ( { id => "id2", requires => 'someid', text => "another text2" }, { id => "xid4", requires => 'id2', text => "text44" }, { id => "someid", requires => undef, text => "some text" }, { id => "id2", requires => 'someid', text => "another text2" }, { id => "aid", requires => undef, text => "alone text" }, { id => "id2", requires => 'someid', text => "another text2" }, { id => "xid3", requires => 'id2', text => "text33" }, ); ``` need something like: ``` my $texts = join("\n", get_ordered_texts(@arr) ); ``` soo need write a sub what return the array of `text`s from the hashes, - in the dependent order, so from the above example need to get: ``` "some text", #someid the id2 depends on it - so need be before id2 "another text2", #id2 the xid3 and xid4 depends on it - and it is depends on someid "text44", #xid4 the xid4 and xid3 can be in any order, because nothing depend on them "text33", #xid3 but need be bellow id2 "alone text", #aid nothing depends on aid and hasn't any dependencies, so this line can be anywhere ``` as you can see, in the @arr can be some duplicated "lines", ("id2" in the above example), need output only once any id. Not providing any code example yet, because havent any idea how to start. ;( Exists some CPAN module what can be used to the solution? Can anybody points me to the right direction?

Original source