Wanted: Python solution for ordering dependencies

[Eduardo Schettino]

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)