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.
| [reply] |
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
| [reply] [d/l] |
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;
}
| [reply] [d/l] [select] |
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.
| [reply] |
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.
<-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
| [reply] [d/l] [select] |
| [reply] |