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

Hi, I have the following problem at hand:
There are a set of tasks some of which are dependent on others. I have the input file that looks like:
.
.
.
Basically, the first element on any line is the task that is dependent on the remaining tasks mentioned in the line. For eg., Task1 is dependent on Task2 & Task3 & so on.
I am supposed to read the file contents & resolve the dependencies between the tasks & come up with a list that has the least dependent task first & the most dependent task at the end of the list.
Is there a simple PERL way of sequencing the tasks?
Thanks,
Ashok

Replies are listed 'Best First'.
by Roger (Parson) on Aug 18, 2005 at 13:40 UTC
One possible solution: You could use a Simple tree structure, such as CPAN module Tree::Simple, and insert your tasks into the tree based on parent/children relationship. To find out which job has the least dependency, just begin from the leaf of the tree and traverse back up the tree.

by Fletch (Chancellor) on Aug 18, 2005 at 13:41 UTC

Look at Graph and it's topological_sort method. Also if you have a copy of Mastering Algorithms with Perl it discusses topological sorting in one of the chapters covering graphs.

--
We're looking for people in ATL

by davidrw (Prior) on Aug 18, 2005 at 13:42 UTC

Anyways, my first thought is build a hash structure of the form \$deps{\$task}{\$requiredTask} .. so with the above you would have something like:
```%deps = (
1 => { 2 => undef, 3 => undef },
2 => { 2 => undef, 4 => undef },
3 => { 1 => undef, 4 => undef },
5 => { 2 => undef, 3 => undef },
);
So now, to see if X requires Y, you can just do exists \$deps{\$X}->{\$Y}, or to list the deps (1 level) do keys %{\$deps{\$X}} . From there you can loop through listing dependencies or make a recursive rountine to find all levels (but be very careful of the cyclic deps).

To build the above data structure, it could just be something like:
```my %deps;
while(<STDIN>){
my @cols = split;

# or another way:
%{\$deps{\$task}} = map { \$_ => undef } @cols;
}
by ikegami (Pope) on Aug 18, 2005 at 15:17 UTC
by radiantmatrix (Parson) on Aug 18, 2005 at 16:39 UTC

Your problem is stated sort of oddly, and your test data has circular dependencies, which I decided to treat as an error. I put new test data in my __DATA__ block after verifying that circular dependencies are found correctly by this code.

I also took the liberty of creating a task entry for tasks that are not in the left column, but are a dependency (e.g. Task4 and Task6 in the sample data).

This is a little messy, but should illustrate the type of approach you have to use.

This results in the following output:

```Analyze Task4: