Need help in finding an efficient algorithm

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

  1. robertday5

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

  2. robertday5

    Anno Siegel Guest

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

  3. Yep!

    Sort::Topological

    sherm--
     
    Sherm Pendley, Jan 6, 2005
    #3
  4. robertday5

    Anno Siegel Guest

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

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 (here). After that, you can post your question and our members will help you out.