Task scheduling using perl

[a_ashokkumar]

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:
Task1 Task2 Task3
Task2 Task2 Task4
Task3 Task1 Task4
Task5 Task2 Task3
.
.
.
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

[Roger]

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.

[Fletch]

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.

[davidrw]

Is that sample data you real data? How do you plan to solve the dependency loops (Task1 requires Task3, but Task3 requires Task1)? Also, Task2 requires Task2?

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;
  my $task = shift @cols;

  $deps{$task}->{$_} = undef for @cols;
  # or another way:
  %{$deps{$task}} = map { $_ => undef } @cols;
}

[ikegami]

I sure hope that's not really your data. Task1 depends on Task3 and Task3 depends on Task1. your program should probably check for such loops.

[radiantmatrix]

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.

Read more... (source code) (2 kB)

This results in the following output:

Analyze Task4:
EXEC(Task4)
Analyze Task6:
EXEC(Task6)
Analyze Task5:
>Analyze Task2:
.EXEC(Task2)
>Analyze Task3:
.EXEC(Task3)
EXEC(Task5)
Analyze Task1:
EXEC(Task1)

The levels are tracked, so you can see that the dependency tree is navigated, only executing tasks once the dependencies have run.

[tlm]

I've never used it but you may want to take a look at Algorithm::Dependency and related modules.