algorithm - 使用 perl 按依赖项排序数组

Question

有一个哈希数组，

my @arr = get_from_somewhere();

@arr 的内容(例如)是:

@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" },
);

需要这样的东西:

my $texts = join("\n",  get_ordered_texts(@arr) );

soo 需要编写一个子程序，它从散列中返回 text 的数组，- 在依赖顺序中，所以从上面的例子需要得到:

"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

如你所见，在@arr中可以有一些重复的“行”，(上例中的“id2”)，任何id只需要输出一次。

还没有提供任何代码示例，因为还不知道如何开始。 ;(是否存在一些 CPAN 模块可以用于解决方案？

谁能指出我正确的方向？

Answer 1

使用 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);