Eduardo Schettino wrote:
On Sun, Apr 25, 2010 at 11:44 PM, Jonathan Fine <jf...@pytex.org> wrote:
Eduardo Schettino wrote:
On Sun, Apr 25, 2010 at 4:53 AM, Jonathan Fine <jf...@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
--
http://mail.python.org/mailman/listinfo/python-list
