algorithm - BFSとトポロジカルソートの関係

Question

トポロジカルソートは、DFS (エッジが逆になっている) と queue の両方を使用して実行できます。BFS は queue を使用して実行することもできます。BFS のキューを使用しているときに要素を格納および取得する方法と、トポロジカルソートにキューを使用したときの方法との間に関係はありますか。明確化が役立ちます。ありがとう。

score 2 · Accepted Answer

いいえ、必ずしも関係はありません。ウィキペディアが指摘しているwikipedia/Topological_sorting＃AlgorithmsのKahnによるアルゴリズムを参照していると思います。

結果のソートの非一意性を反映して、構造体Sは単純にセット、キュー、またはスタックになり得ることに注意してください。

したがって、トポロジカルソートの「キュー」は実際には「任意のコレクション」構造であり、このコレクションの順序は重要ではありません。何でもかまいません。一方、BFSに使用されるキューは、すべて順序に関するものです。FIFO（先入れ先出し）タスクを実行できるようにします。この順序を変更すると、BFSアルゴリズムが台無しになります。

構造がキューであることが重要であるトポロジカルソートのための他の「キュー」ベースのアルゴリズムがあるかもしれません。特定のそのようなアルゴリズムについて質問している場合は、明確にしてください。

編集：関心のあるアルゴリズムは、カーンのものと同じ、改善されたアルゴリズムセクションであることが明確にされています。

編集：リンクしたページの改善されたアルゴリズムのセクションに従ってトポロジカルソートを実装するコードをいくつか作成しました。sort関数の引数として任意に使用するコレクションのタイプを作成しました。次に、スタック、キュー、ランダムポップコレクション、Pythonセット（ハッシュセットであるため、注文の保証はありません）など、いくつかのタイプのコレクションを作成します。

次に、グラフを作成し、各コレクションでそのグラフの並べ替えアルゴリズムをテストします。次に、トポロジカルソートのウィキペディアにリストされている定義を使用して、各結果をテストします。

..トポロジカルソート（topsortまたはtoposortと省略されることもあります）または有向グラフのトポロジカル順序付けは、頂点の線形順序付けであり、すべてのエッジuvについて、順序付けでuがvの前に来るようにします。

―ウィキペディア

コードはPythonで記述されており、次のようになります。結果はhttp://ideone.comからここにあります。テスト用にランダムなDAGを生成する簡単な方法がわからないため、テストグラフが不十分です。優れたDAGジェネレーターについてコメント/編集してください。

編集：今、私はより少ないラメジェネレーターを持っていますが、それはnetworkxを使用しています。関数nx_generate_random_dagはコード内にありますが、関数にnetworkxをインポートします。mainでマークされたセクションのコメントを解除して、グラフを生成できます。生成されたグラフをコードにハードコーディングしたので、より興味深い結果が得られます。

これはすべて、「コレクション」データ構造（アルゴリズムのキュー）の順序が任意の順序であることを示しています。

from collections import deque
import random


def is_topsorted(V,E,sequence):
  sequence = list(sequence)
  #from wikipedia definition of top-sort
  #for every edge uv, u comes before v in the ordering
  for u,v in E:
    ui = sequence.index(u)
    vi = sequence.index(v)
    if not (ui < vi):
      return False
  return True 

#the collection_type should behave like a set:
# it must have add(), pop() and __len__() as members.
def topsort(V,E,collection_type):
  #out edges
  INS = {}

  #in edges
  OUTS = {}
  for v in V:
    INS[v] = set()
    OUTS[v] = set()

  #for each edge u,v,
  for u,v in E:
    #record the out-edge from u
    OUTS[u].add(v)
    #record the in-edge to v
    INS[v].add(u)

  #1. Store all vertices with indegree 0 in a queue
  #We will start
  topvertices = collection_type()

  for v,in_vertices in INS.iteritems():
    if len(in_vertices) == 0:
      topvertices.add(v)

  result = []

  #4. Perform steps 2 and 3 while the queue is not empty.
  while len(topvertices) != 0:  
    #2. get a vertex U and place it in the sorted sequence (array or another queue).
    u = topvertices.pop()
    result.append(u)

    #3. For all edges (U,V) update the indegree of V,
    # and put V in the queue if the updated indegree is 0.

    for v in OUTS[u]:
      INS[v].remove(u)
      if len(INS[v]) == 0:
        topvertices.add(v)

  return result

class stack_collection:
  def __init__(self):
    self.data = list()
  def add(self,v):
    self.data.append(v)
  def pop(self):
    return self.data.pop()
  def __len__(self):
    return len(self.data)

class queue_collection:
  def __init__(self):
    self.data = deque()
  def add(self,v):
    self.data.append(v)
  def pop(self):
    return self.data.popleft()
  def __len__(self):
    return len(self.data)

class random_orderd_collection:
  def __init__(self):
    self.data = []
  def add(self,v):
    self.data.append(v)
  def pop(self):    
    result = random.choice(self.data)
    self.data.remove(result)
    return result
  def __len__(self):
    return len(self.data)

"""
Poor man's graph generator.
Requires networkx.

Don't make the edge_count too high compared with the vertex count,
 otherwise it will run for a long time or forever.
"""
def nx_generate_random_dag(vertex_count,edge_count):
  import networkx as nx

  V = range(1,vertex_count+1)
  random.shuffle(V)

  G = nx.DiGraph()
  G.add_nodes_from(V)

  while nx.number_of_edges(G) < edge_count:

    u = random.choice(V)
    v = random.choice(V)
    if u == v:
      continue

    for tries in range(2):
      G.add_edge(u,v)
      if not nx.is_directed_acyclic_graph(G):
        G.remove_edge(u,v)
        u,v = v,u
  V = G.nodes()
  E = G.edges()

  assert len(E) == edge_count
  assert len(V) == vertex_count
  return V,E




def main():

  graphs = []

  V = [1,2,3,4,5]
  E = [(1,2),(1,5),(1,4),(2,4),(2,5),(3,4),(3,5)]

  graphs.append((V,E))

  """
  Uncomment this section if you have networkx.
  This will generate 3 random graphs.
  """
  """
  for i in range(3):
    G = nx_generate_random_dag(30,120)
    V,E = G
    print 'random E:',E
    graphs.append(G)
  """


  #This graph was generated using nx_generate_random_dag() from above
  V = range(1,31)
  E = [(1, 10), (1, 11), (1, 14), (1, 17), (1, 18), (1, 21), (1, 23),
       (1, 30), (2, 4), (2, 12), (2, 15), (2, 17), (2, 18), (2, 19),
       (2, 25), (3, 22), (4, 5), (4, 8), (4, 22), (4, 23), (4, 26),
       (5, 27), (5, 23), (6, 24), (6, 28), (6, 27), (6, 20), (6, 29),
       (7, 3), (7, 19), (7, 13), (8, 24), (8, 10), (8, 3), (8, 12),
       (9, 4), (9, 8), (9, 10), (9, 14), (9, 19), (9, 27), (9, 28),
       (9, 29), (10, 18), (10, 5), (10, 23), (11, 27), (11, 5),
       (12, 10), (13, 9), (13, 26), (13, 3), (13, 12), (13, 6), (14, 24),
       (14, 28), (14, 18), (14, 20), (15, 3), (15, 12), (15, 17), (15, 19),
       (15, 25), (15, 27), (16, 4), (16, 5), (16, 8), (16, 18), (16, 20), (16, 23),
       (16, 26), (16, 28), (17, 4), (17, 5), (17, 8), (17, 12), (17, 22), (17, 28),
       (18, 11), (18, 3), (19, 10), (19, 18), (19, 5), (19, 22), (20, 5), (20, 29),
       (21, 25), (21, 12), (21, 30), (21, 17), (22, 11), (24, 3), (24, 10),
       (24, 11), (24, 28), (25, 10), (25, 17), (25, 23), (25, 27), (26, 3),
       (26, 18), (26, 19), (28, 26), (28, 11), (28, 23), (29, 2), (29, 4),
       (29, 11), (29, 15), (29, 17), (29, 22), (29, 23), (30, 3), (30, 7),
       (30, 17), (30, 20), (30, 25), (30, 26), (30, 28), (30, 29)]

  graphs.append((V,E))

  #add other graphs here for testing


  for G in graphs:
    V,E = G

    #sets in python are unordered but in practice their hashes usually order integers.
    top_set = topsort(V,E,set)

    top_stack = topsort(V,E,stack_collection)

    top_queue = topsort(V,E,queue_collection)

    random_results = []
    for i in range(0,10):
      random_results.append(topsort(V,E,random_orderd_collection))

    print
    print 'V: ', V
    print 'E: ', E
    print 'top_set ({0}): {1}'.format(is_topsorted(V,E,top_set),top_set)
    print 'top_stack ({0}): {1}'.format(is_topsorted(V,E,top_stack),top_stack)
    print 'top_queue ({0}): {1}'.format(is_topsorted(V,E,top_queue),top_queue)

    for random_result in random_results:
      print 'random_result ({0}): {1}'.format(is_topsorted(V,E,random_result),random_result)
      assert is_topsorted(V,E,random_result)

    assert is_topsorted(V,E,top_set)
    assert is_topsorted(V,E,top_stack)
    assert is_topsorted(V,E,top_queue)



main()

algorithm - BFSとトポロジカルソートの関係

2 に答える 2

Related

Reference