title: How can I implement a makefile-style algorithm in python
body: <p>I am implementing an acoustic feature extraction system in python, and I need to implement a <a href="http://www.gnu.org/software/make/" rel="nofollow">makefile</a>-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.</p>
  
  <p>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.</p>
  
  <p>An example of such a system might be the following:</p>
  
  <pre><code>            ,-&gt; [B] -&gt; [D] ----+
  input --&gt; [A]           ^      v
              `-&gt; [C] ----+---&gt; [E] --&gt; output
  </code></pre>
  
  <p>and the function calls (assuming each block <code>X</code> is a function of the form <code>output = X(inputs)</code> might be something like:</p>
  
  <pre><code>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
  </code></pre>
  
  <p>I already have the function graph loaded in the form of a dictionary with each dictionary entry of the form <code>(inputs, function)</code> like so:</p>
  
  <pre><code>blocks = {'A' : (('input'), A),
            'B' : (('A'), B),
            'C' : (('A'), C),
            'D' : (('B','C'), D),
            'output' : (('D','C'), E)}
  </code></pre>
  
  <p>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.</p>