Need help in finding an efficient algorithm

Discussion in 'Perl Misc' started by robertday5@gmail.com, Jan 6, 2005.

  1. Guest

    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
     
    , Jan 6, 2005
    #1
    1. Advertising

  2. Anno Siegel Guest

    <> wrote in comp.lang.perl.misc:
    > 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
     
    Anno Siegel, Jan 6, 2005
    #2
    1. Advertising

  3. Sherm Pendley, Jan 6, 2005
    #3
  4. Anno Siegel Guest

    Sherm Pendley <> wrote in comp.lang.perl.misc:
    > Anno Siegel wrote:
    >
    > > I think there is a CPAN module for that,

    >
    > 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
     
    Anno Siegel, Jan 6, 2005
    #4
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    6
    Views:
    1,147
  2. Timasmith
    Replies:
    36
    Views:
    890
  3. Replies:
    16
    Views:
    556
    sap.liu
    Aug 27, 2005
  4. KK
    Replies:
    1
    Views:
    316
  5. Sam Kong
    Replies:
    15
    Views:
    232
    Sam Kong
    Jan 24, 2007
Loading...

Share This Page