2017-02-13 15 views
0

入れ子になったforループのコードの周りに私の頭をラップするのに問題があります。私はWikiのKahnのアルゴリズムに従っています:Kahn's。 outgoingEdgeに各endArray要素(m)の入力エッジがあるかどうかをテストする方法を理解できません。ここでトポロジカルソート(Kahn's algorithm)のトラブル

は、私がこれまで持っているものである:ここでは

def topOrdering(self, graph): 

    retList = [] 
    candidates = set() 
    left = [] 
    right = [] 

    for key in graph: 
     left.append(key) 
     right.append(graph[key]) 

    flattenedRight = [val for sublist in right for val in sublist] 

    for element in left: 
     if element not in flattenedRight: 
      #set of all nodes with no incoming edges 
      candidates.add(element) 

    candidates = sorted(candidates) 

    while len(candidates) != 0: 
     a = candidates.pop(0) 
     retList.append(a) 
     endArray = graph[a] 

     for outGoingEdge in endArray: 

      if outGoingEdge not in flattenedRight: 
       candidates.append(outGoingEdge) 
       #flattenedRight.remove(outGoingEdge) 

      del outGoingEdge 


    if not graph: 
     return "the input graph is not a DAG" 
    else: 
     return retList 

は私のアルゴリズムを可視化した画像です。グラフは隣接リストの形式です。 enter image description here

答えて

2

空のセットから頂点を削除するたびに、indegree(入力エッジ数)を別々に保存し、カウントを減らすことができます。 countが0になると、後で処理される空集合に頂点を追加します。ここでは例です:

def top_sort(adj_list): 
    # Find number of incoming edges for each vertex 
    in_degree = {} 
    for x, neighbors in adj_list.items(): 
     in_degree.setdefault(x, 0) 
     for n in neighbors: 
      in_degree[n] = in_degree.get(n, 0) + 1 

    # Iterate over edges to find vertices with no incoming edges 
    empty = {v for v, count in in_degree.items() if count == 0} 

    result = [] 
    while empty: 
     # Take random vertex from empty set 
     v = empty.pop() 
     result.append(v) 

     # Remove edges originating from it, if vertex not present 
     # in adjacency list use empty list as neighbors 
     for neighbor in adj_list.get(v, []): 
      in_degree[neighbor] -= 1 

      # If neighbor has no more incoming edges add it to empty set 
      if in_degree[neighbor] == 0: 
       empty.add(neighbor) 

    if len(result) != len(in_degree): 
     return None # Not DAG 
    else: 
     return result 

ADJ_LIST = { 
    1: [2], 
    2: [3], 
    4: [2], 
    5: [3] 
} 

print(top_sort(ADJ_LIST)) 

出力:

[1, 4, 5, 2, 3] 
+0

ああ、私は言及を忘れてしまった、許可されていない空のキー。 –

+0

@JeffreyPhung空のキーが許されないということはどういう意味ですか?発信エッジがないので、 '3'は隣接リストにはないはずですか? – niemmi

+0

私の隣接リストには3つが含まれていません。あなたのロジックから、例外エラーが発生します。私はそれを自分のやり方でやろうとしました。あなたの方法から、私は再び隣人のための別の隣接リストを作成しなければならないと思いますか? –