Re: Task scheduling using perl

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.

#!/usr/bin/perl -w
package main;
use strict;

my %dep;
while (<DATA>) {
    my @tasks = split '\s+', $_;
    my $key = shift @tasks;
    $dep{$key} = [@tasks];
}

## check for circular dependencies.
foreach my $k (keys %dep) {
    foreach my $item (@{$dep{$k}}) {
        ## is $k in the list for $dep{$item}?
        my $circ = 0;
        foreach (@{$dep{$item}}) { $circ++ if  $_ eq $k }
        die "Circular reference on $k => $item" if $circ;
    }
}

## sort tasks by least number of deps (exec 0-dep tasks first)
my @ord_tasks = sort { scalar(@{$dep{$a}}) <=> scalar(@{$dep{$b}}) } k
+eys %dep;

## "execute" each task, forking for dependencies.
my %exec_hist;
foreach my $task (@ord_tasks) {
    exec_task($task, \%exec_hist, \%dep)
}

sub exec_task {
    my $task = shift;
    my $history = shift;
    my $dep_hash = shift;
    my $level = shift;
    
    my %dep = %$dep_hash;
    defined $level or $level = 0;
    
    return if exists $history->{$task};
    $history->{$task} = undef;
    print "Analyze $task:\n";
    foreach ( @{$dep{$task}} ) {
        #~ print "\n";
        next if exists $history->{$_};
        print ">" for 0..$level;
        exec_task($_, $history, $dep_hash, $level+1);
    }
    print "." for 0..$level-1;
    print "EXEC($task)\n"
}

__DATA__
Task1 Task2 Task3
Task2 Task6 Task4
Task3 Task6 Task4
Task5 Task2 Task3
[download]

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)
[download]

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

<-radiant.matrix->
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

Comment on Re: Task scheduling using perl Select or Download Code


XP is just a number
	PerlMonks