Need help in finding an efficient algorithm

R

robertday5

Need help in finding an efficient algorithm for the following problem.
There are tasks which have predecessor tasks which needs to be
completed before taking up the new task.
Our aim is to find the required order of the tasks, so that the
pre-requisite tasks are always completed before the task.
For example

TaskA needs taskJ and taskK
TaskB needs none
TaskC needs TaskA, taskK
taskD needs taskB
taskJ needs taskB
taskK needs none

There is no cyclical dependency and all the tasks take same amount of
time

A valid answer can be
taskB
taskK
taskJ
taskD
taskC
taskA
 
A

Anno Siegel

Need help in finding an efficient algorithm for the following problem.
There are tasks which have predecessor tasks which needs to be
completed before taking up the new task.
Our aim is to find the required order of the tasks, so that the
pre-requisite tasks are always completed before the task.
For example

TaskA needs taskJ and taskK
TaskB needs none
TaskC needs TaskA, taskK
taskD needs taskB
taskJ needs taskB
taskK needs none

There is no cyclical dependency and all the tasks take same amount of
time

A valid answer can be
taskB
taskK
taskJ
taskD
taskC
taskA

Google for "topological sort". I think there is a CPAN module for that,
but it must be named differently.

Anno
 
A

Anno Siegel

Sherm Pendley said:
Yep!

Sort::Topological

That's what I thought I searched for, but didn't find it. Now I do.
Well, "topological" is hard to type :)

Anno
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,479
Members
44,899
Latest member
RodneyMcAu

Latest Threads

Top