How can I implement a makefile-style algorithm in python

I am implementing an acoustic feature extraction system in python, and I need to implement a makefile-style algorithm to ensure that all blocks in the feature extraction system are run in the correct order, and without repeating any feature extractions stages.

The input to this feature extraction system will be a graph detailing the links between the feature extraction blocks, and I'd like to work out which functions to run when based upon the graph.

An example of such a system might be the following:

            ,-> [B] -> [D] ----+
input --> [A]           ^      v
            `-> [C] ----+---> [E] --> output

and the function calls (assuming each block X is a function of the form output = X(inputs) might be something like:

a = A(input)
b = B(a)
c = C(a)
d = D(b,c)  # can't call D until both b and c are ready
output = E(d,c)   # can't call E until both c and d are ready

I a开发者_开发技巧lready have the function graph loaded in the form of a dictionary with each dictionary entry of the form (inputs, function) like so:

blocks = {'A' : (('input'), A),
          'B' : (('A'), B),
          'C' : (('A'), C),
          'D' : (('B','C'), D),
          'output' : (('D','C'), E)}

I'm just currently drawing a blank on what the makefile algorithm does exactly, and how to go about implementing it. My google-fu appears to be not-very-helpful here too. If someone at least can give me a pointer to a good discussion of the makefile algorithm that would probably be a good start.

Topological sorting

blocks is basically an adjacency list representation of the (acyclic) dependency graph. Hence, to get the correct order to process the blocks, you can perform a topological sort.

As the other helpful answerers have already pointed out, what I'm after is a topological sort, but I think my particular case is a little simpler because the function graph must always start at input and end at output.

So, here is what I ended up doing (I've edited it slightly to remove some context-dependent stuff, so it may not be completely correct):

def extract(func_graph):
    def _getsignal(block,signals):
        if block in signals:
            return signals[block]
        else:
            inblocks, fn = func_graph[block]
            inputs = [_getsignal(i,signals) for i in inblocks]
            signals[block] = fn(inputs)
            return signals[block]

    def extract_func (input):
        signals = dict(input=input)
        return _getsignal('output',signals)

    return extract_func

So now given I can set up the function with

fn = extract(blocks)

And use it as many times as I like:

list_of_outputs = [fn(i) for i in list_of_inputs]

I should probably also put in some checks for loops, but that is a problem for another day.

For code in many languages, including Python try these Rosetta code links: Topological sort, and Topological sort/Extracted top item.