Wanted: Python solution for ordering dependencies
in [Python]
|
Prev: Reminder: 6 days left for EuroPython 2010 talk submissions
Next: Reading a binary file and wrtiting the bytes verbatimin an utf-8 file
From: Jonathan Fine on 25 Apr 2010 12:37 Eduardo Schettino wrote: > On Sun, Apr 25, 2010 at 11:44 PM, Jonathan Fine <jfine(a)pytex.org> wrote: >> Eduardo Schettino wrote: >>> On Sun, Apr 25, 2010 at 4:53 AM, Jonathan Fine <jfine(a)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
From: Lie Ryan on 25 Apr 2010 13:00
On 04/26/10 02:37, Jonathan Fine wrote: > > I don't know if the quadratic running time is an issue for my purpose. It's not until you decide it's yes. |