Pathologically Eclectic Rubbish Lister PerlMonks

by a_ashokkumar (Initiate)
 on Aug 18, 2005 at 13:27 UTC 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:
.
.
.
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:

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

Create A New User
Node Status?
node history
Node Type: perlquestion [id://484748]
Approved by Roger
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others pondering the Monastery: (7)
As of 2018-03-24 18:22 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
When I think of a mole I think of:

Results (299 votes). Check out past polls.

Notices?