Creating a Dependency Tree Using the Tree::DAG_Node Module and Postorder Transversal

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

Hi. I am attempting to build a dependency tree using the Tree::DAG_Node module and then perform a postorder transversal of the tree. During my search for a solution, I ran across tadman's (Golf) Dependency List Prioritization post. This code appears to solve my dependency problem (no pub intended).

my @list = f(
     a => [ 'b', 'c' ],
     b => [ 'c', 'd' ],
     c => [ 'd' ],
     e => [ 'b', 'a' ],
     f => undef,
);


sub f {
  $h{$_}||=[]for map@$_,%h=@_;
  sub x {
    my$x=1;
    $x+=x($_)for@{@h{@_}||[]};
    $x
  }
  sort{x($a)<=>x$b}keys%h
}
[download]

However, having read through, in advance, gmax's tutorial A crash course on trees, I am itching to use the Tree::DAG_Node module to solve this problem. The stumbling block I am encountering is that I do not know how to take a data structure, such as tadman's in the code snippet above, and then programmatically create a Directed Acyclic Graph. With the tree constructed, I can then use the "walk_down" method with the callbackback option for a postorder scan.

Any assistance will be greatly appreciated. Thanks.

Comment on Creating a Dependency Tree Using the Tree::DAG_Node Module and Postorder Transversal Download Code

Replies are listed 'Best First'.
Re: Creating a Dependency Tree Using the Tree::DAG_Node by gmax (Abbot) on Jan 25, 2003 at 13:42 UTC
The structure you are describing does not fit into a tree. As you can see, 'b', 'c', and 'd' have two parents each, thus clashing with the definition of a tree, where each node can only have one parent. `my %rules = ( a => [ 'b', 'c' ], b => [ 'c', 'd' ], c => [ 'd' ], e => [ 'b', 'a' ], f => undef, );` [download] dependency / \ f e \| \ \| a \| / \ b -- c \| \ +----- d You can simplify the structure, on the grounds that, since 'a' depends on 'b' and 'e' depends on 'a' as well, then you may assume that 'e' depends implicitly on 'b'. The same line of reasoning solves the problem for 'd' and 'c'. This structure is indeed representable by a Tree::Dag_Node object, even though it looks more like a linked list than a tree. `my %rules = ( a => [ 'b' ], b => [ 'c' ], c => [ 'd' ], e => [ 'a' ], f => undef, );` [download] dependency / \ f e \ a / b \ c \ d However, if you remove 'a' from e's list and put there only 'b', then you fall back onto forbidden ground, where a node has more than one parent. `my %rules = ( a => [ 'b' ], b => [ 'c' ], c => [ 'd' ], e => [ 'b' ], f => undef, );` [download] dependency / \ \ f e a \ / \ b c \ d While you can solve this dependency problem in a Makefile, you can't successfully describe it as a Directed Acyclic Graph Tree. See S.M. Burke's article on trees for more theoretical stuff. _ _ _ _ (_\|\| \| \|(_\|>< _\|	[reply] [d/l] [select]

Replies are listed 'Best First'.

Re: Creating a Dependency Tree Using the Tree::DAG_Node
by gmax (Abbot) on Jan 25, 2003 at 13:42 UTC

my %rules = (
     a => [ 'b', 'c' ],
     b => [ 'c', 'd' ],
     c => [ 'd' ],
     e => [ 'b', 'a' ],
     f => undef,
);
[download]

dependency
     /  \
   f     e
        | \
        |  a
        | / \
        b -- c
        |     \
        +----- d

my %rules = (
     a => [ 'b' ],
     b => [ 'c' ],
     c => [ 'd' ],
     e => [ 'a' ],
     f => undef,
);
[download]

my %rules = (
     a => [ 'b' ],
     b => [ 'c' ],
     c => [ 'd' ],
     e => [ 'b' ],
     f => undef,
);
[download]

    dependency
     /  \    \
   f     e    a
          \  / \ 
           b    c
                 \ 
                  d

S.M. Burke's article on trees

 _  _ _  _  
(_|| | |(_|><
 _|

[reply]
[d/l]
[select]