Beefy Boxes and Bandwidth Generously Provided by pair Networks
good chemistry is complicated,
and a little bit messy -LW

Task scheduling using perl

by a_ashokkumar (Initiate)
on Aug 18, 2005 at 13:27 UTC ( #484748=perlquestion: print w/replies, xml ) Need Help??

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:
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?

Replies are listed 'Best First'.
Re: Task scheduling using perl
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.

Re: Task scheduling using perl
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

Re: Task scheduling using perl
by davidrw (Prior) on Aug 18, 2005 at 13:42 UTC
    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; }
Re: Task scheduling using perl
by ikegami (Pope) on Aug 18, 2005 at 15:17 UTC
    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.
Re: Task scheduling using perl
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: 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.

    Larry Wall is Yoda: there is no try{} (ok, except in Perl6; way to ruin a joke, Larry! ;P)
    The Code that can be seen is not the true Code
    "In any sufficiently large group of people, most are idiots" - Kaa's Law
Re: Task scheduling using perl
by tlm (Prior) on Aug 19, 2005 at 00:19 UTC

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

    the lowliest monk

Log In?

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://484748]
Approved by Roger
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others imbibing at the Monastery: (5)
As of 2021-10-19 10:17 GMT
Find Nodes?
    Voting Booth?
    My first memorable Perl project was:

    Results (76 votes). Check out past polls.