指向性非循環グラフの（特殊な場合の）トポロジカルソートのための最も効率的なアルゴリズムは何ですか？

Question

私は有向非循環グラフ（DAG）の特別なケースであるデータセットを持っています。私のDAGのノードには、0または1の円弧があります。すべての弧は等しく重み付けされています（つまり、弧に含まれる唯一の情報は、それが指し示すノードであり、「距離」または「コスト」または「重み」はありません）。

私のユーザーは、アークレスノードの順序が保持されていると想定して、ノードを半無作為の順番で入力しますが、すべてのアークはそれらを指すノードより前にソートされます。

class Node: 
    def __init__(self, name, arc=None): 
     self.name = str(name) 
     self.arc = str(arc) 

入力等を考慮すると、そこで

（self.arcノードに尖っなく、オブジェクト自体の文字列表現であることに注意）：ここ

は私のデータを表す単純化されたクラスでありますこの：

input = [Node('A'), 
     Node('B'), 
     Node('C'), 
     Node('Z', 'Y'), 
     Node('X', 'W'), 
     Node('Y', 'X'), 
     Node('W')] 

あなたは、好ましくは、最も少ないループと中間データ構造を使用して、このような出力を得るでしょう：

output = [Node('A'), 
      Node('B'), 
      Node('C'), 
      Node('W'), 
      Node('X', 'W'), 
      Node('Y', 'X'), 
      Node('Z', 'Y')] 

Answer 1

今のところ、これは私が思い付くことができました最高のアルゴリズムです：私はこれについては好きではグラフと1を構築するための唯一の2つのループ（1があるということです

def topo_sort(nodes): 
    objects = {}   # maps node names back to node objects 
    graph = OrderedDict() # maps node names to arc names 
    output = [] 
    for node in nodes: 
     objects[node.name] = node 
     graph[node.name] = node.arc 
    arcs = graph.values() 

    # optional 
    missing = set(arcs) - set(graph) - {None} 
    if missing: 
     print('Invalid arcs: {}'.format(', '.join(missing))) 

    def walk(arc): 
     """Recurse down the tree from root to leaf nodes.""" 
     obj = objects.get(arc) 
     if obj and obj not in output: 
      follow_the_arcs(graph.get(arc)) 
      output.append(obj) 

    # Find all root nodes 
    for node in graph: 
     if node not in arcs: 
      walk(node) 
    return ordered 

ルーツを見つけるために）、出力はlist.append()、遅いものはlist.insert()で独占的に作られています。誰にもこれの改善について考えてもらえますか？私が見落とした明らかな非効率性はありますか？

ありがとうございます！