Wanted: Python solution for ordering dependencies

Jonathan Fine jfine at pytex.org
Sun Apr 25 12:37:44 EDT 2010


Eduardo Schettino wrote:
> On Sun, Apr 25, 2010 at 11:44 PM, Jonathan Fine <jfine at pytex.org> wrote:
>> Eduardo Schettino wrote:
>>> On Sun, Apr 25, 2010 at 4:53 AM, Jonathan Fine <jfine at pytex.org> wrote:
>>>> Hi
>>>>
>>>> I'm hoping to avoid reinventing a wheel (or other rolling device).  I've
>>>> got
>>>> a number of dependencies and, if possible, I want to order them so that
>>>> each
>>>> item has its dependencies met before it is processed.
>>>>
>>>> I think I could get what I want by writing and running a suitable
>>>> makefile,
>>>> but that seems to be such a kludge.
>>>>
>>>> Does anyone know of an easily available Python solution?
>>> http://pypi.python.org/pypi/doit
>>
>> Thank you for this, Eduardo. However, all I require is a means of ordering
>> the items that respects the dependencies.  This rest I can, and pretty much
>> have to, manage myself.
>>
>> So probably something more lightweight would suit me.
> 
> you just want a function?
> 
> def order_tasks(tasks):
>     ADDING, ADDED = 0, 1
>     status = {} # key task-name, value: ADDING, ADDED
>     task_order = []
>     def add_task(task_name):
>         if task_name in status:
>             # check task was alaready added
>             if status[task_name] == ADDED:
>                 return
>             # detect cyclic/recursive dependencies
>             if status[task_name] == ADDING:
>                 msg = "Cyclic/recursive dependencies for task %s"
>                 raise Exception(msg % task_name)
> 
>         status[task_name] = ADDING
>         # add dependencies first
>         for dependency in tasks[task_name]:
>             add_task(dependency)
> 
>         # add itself
>         task_order.append(task_name)
>         status[task_name] = ADDED
> 
>     for name in tasks.keys():
>         add_task(name)
>     return task_order
> 
> if __name__ == '__main__':
>     task_list = {'a':['b','c'],
>                  'b':['c'],
>                  'c':[]}
>     print order_tasks(task_list)
> 

Yes, this is good, and pretty much what I'd have written if I had to do 
it myself.  Thank you, Eduardo.

But the links posted by Chris Rebert suggest that this solution can be 
quadratic in its running time, and give a Python implementation of 
Tarjan's linear solution.  Here are the links:
     http://pypi.python.org/pypi/topsort/0.9
     http://www.bitformation.com/art/python_toposort.html

I don't know if the quadratic running time is an issue for my purpose.

-- 
Jonathan




More information about the Python-list mailing list