pythonでメイクファイルスタイルのアルゴリズムを実装するには

Question

私はPythonで音響特徴抽出システムを実装していますが、スタイルアルゴリズムを実装して、特徴抽出システム内のすべてのブロックが正しい任意の特徴抽出段階を繰り返さずに、

このフィーチャ抽出システムへの入力は、フィーチャ抽出ブロック間のリンクを詳細に示すグラフになります。グラフに基づいて実行する関数を作成したいと思います。

次かもしれないようなシステムの例：

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

と関数呼び出し（各ブロックXと仮定すると、フォームoutput = X(inputs)の関数であるようなものであるかもしれない：

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 

私は既に、関数のグラフを辞書の形式で読み込んだ(inputs, function)という形式の各辞書エントリを次のようにしています：

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

私は現在、makefileアルゴリズムが正確に何をしているのか、それをどうやって実装しようとしているのかについては何も書いていません。私のgoogle-fuはあまり役に立ちません。誰かが少なくともmakefileアルゴリズムの良い議論へのポインタを私に与えることができれば、それはおそらく良いスタートになるだろう。

Answer 1

Topological sorting

Answer 2

blocks基本的に（非環式）、依存グラフの隣接リスト表現です。したがって、ブロックを処理する正しい順序を得るために、トポロジカルなソートを実行できます。他の有用な回答がすでに指摘したように

Answer 3

は、私が後だことtopological sortですが、私は、関数のグラフが常にinputで開始し、outputで終了しなければならないので、私の特定のケースは少し簡単になると思います。

だから、ここで私は（私は少しいくつかのコンテキスト依存のものを削除するには、それを編集したので、それは完全に正確でない場合があります）やってしまったものです：

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 

だから今、私は設定することができます与えられました

fn = extract(blocks) 

と機能アップと私が好きなように何回もそれを使用する：

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

私はプロのはずおそらくループのチェックを入れていますが、それは別の日の問題です。

Answer 4

Pythonを含む多くの言語でのコードについては、Topological sortおよびTopological sort/Extracted top itemのロゼッタコードリンクを試してみてください。