0

http://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm

http://en.algoritmy.net/article/44220/Tarjans-algorithm

強く接続されたコンポーネントに対する Tarjan のアルゴリズムの私の Ruby バージョンでは、このバグを理解できません。Kosaraju-Sharir アルゴリズムが動作するようになり、Ruby の Tarjan アルゴリズムがいくつかのグラフで動作します。しかし、接続されるべき2つのコンポーネントが接続されていません---「10」と「11、12、9」

入力ファイルはこの有向グラフです: http://algs4.cs.princeton.edu/42directed/tinyDG.txt

expected: [["1"], ["0", "2", "3", "4", "5"], ["10", "11", "12", "9"], ["6", "8"], ["7"]]
got: [["1"], ["0", "2", "3", "4", "5"], ["10"], ["11", "12", "9"], ["6", "8"], ["7"]]

単一のコンポーネントを作成しようとするこの最後のループでは、「10」(スタックの最後のアイテム) から始まりますが、現在の頂点 (「親」) も「10」です! これにより、ループが別のコンポーネントとして「10」を切り捨てられます。スタックの最新のアイテムが親ノードと同じなのはなぜですか? ["12"、"11"、"9"、そして "10"] を収集した後、コンポーネントの END にのみ "10" が表示されることを期待します。「10」が最後ではなく最初に表示されるため、この問題が発生します。どうすれば修正できますか？

  begin
    last_stack_item = stack.pop
    component << last_stack_item.name
  end while last_stack_item != parent # we're back at the root

私のRubyコード:

    # Tarjan's algorithm to find all strongly connected components (SCCs)
    def scc_tarjan
      index = 0 # numbers nodes consecutively in the order discovered
      stack, scc, vertices = [], [], []

      # create new Struct, if not already defined
      if Struct::const_defined?("TarjanVertex")
        Struct.const_get("TarjanVertex")
      else
        Struct.new("TarjanVertex", :name, :index, :lowlink)
      end

      adj_lists.each do |v|
        # -1 means vertex is unvisited
        vertex = Struct::TarjanVertex.new(v.name, -1, -1)
        vertices << vertex  # array of all TarjanVertex objects in graph
      end
      vertices.each do |vertex|
        tarjan_dfs(vertex, scc, stack, index, vertices) if vertex.index == -1
      end
      # return nested array of all SCCs in graph
      scc
    end

  def tarjan_dfs(parent, scc, stack, index, vertices)
    # Set depth index for vertex to smallest unused index
    parent.index = index
    # lowlink is roughly the smallest index of any node known to be reachable from the vertex
    parent.lowlink = index
    index += 1
    stack << parent
    # loop through all vertices connected to parent
    adj_vertices(parent.name, adj_lists).each do |adj_vertex|
      # since adj_vertices returns array of strings,
      # must convert to TarjanVertex objects
      child = vertices.select {|v| v.name == adj_vertex}.first

      if child.index == -1  # if child vertex not yet visited
        tarjan_dfs(child, scc, stack, index, vertices) # recurse on child

        # change parent's lowlink to smaller lowlink of parent and child)
        parent.lowlink = [parent.lowlink, child.lowlink].min

      # vertex points to earlier (already visited) one in stack,
      # with lower index. thus it's the current SCC
      elsif stack.include?(child)
        parent.lowlink = [parent.lowlink, child.index].min
      end
    end

    # if a vertex's lowlink = its index here, this # cannot go any lower.
    # vertex MUST be root of the SCC.
    if parent.lowlink == parent.index
      component = []  # a single SCC

      # pop off entire SCC, one vertex at a time
      begin
        last_stack_item = stack.pop
        component << last_stack_item.name
      end while last_stack_item != parent # we're back at the root
      scc << component.sort # done with a single SCC
    end
  end
4

2 に答える 2

-1

indexは深さ優先検索のタイムスタンプです。これは、dfs() が未訪問の頂点に到達するたびに、その値が 1 増加する必要があることを意味します。結果として、すべてのノードの値indexは異なる必要があり、アルゴリズムが終了すると、index値は、グラフ内の頂点の数と等しくなければなりません。

しかしindex、関数にパラメーターとして渡しましたtarjan_dfs。値渡しなので、dfs()index += 1で のコピーを変更しただけですindex。その結果、indexが dfs-tree の深さ (深さ優先検索のスパンによって形成されるツリー) になります。バグの元です。

したがって$index、ローカル変数の代わりにグローバル変数を使用indexすると、バグが修正されます。実際、質問の冒頭にリストされているすべてのコードはindex、グローバル変数として使用されています。

グローバル変数を使用したくないが、それでも同じ効果を達成したい場合は、変更可能なオブジェクトを使用してラップできます。例えば：

  • に変更index = 0、index = {value: 0}
  • に変更parent.index = index、parent.index = index[:value]
  • に変更parent.lowlink = index、parent.lowlink = index[:value]
  • に変更index += 1しindex[:value] += 1ます。

これは、ランダム グラフ ジェネレーターを備えた実行可能な Ruby 実装で、2 つのプロシージャの出力を比較します。役に立つことを願っています。

# My version:
def tarjan_scc(adj)
  n = adj.size
  dfn = Array.new(n, -1) # dfn[u] is the timestamp when dfs reached node u
  low = Array.new(n, -1) # low[u] is the lowest index that u or u's children can reach in at most one step
  index = {value: 0}
  stk, sccs = [], []
  (0...n).each do |u|
    tarjan_scc_dfs(adj, u, index, dfn, low, stk, sccs) if dfn[u] == -1
  end
  sccs.sort!
end

def tarjan_scc_dfs(adj, u, index, dfn, low, stk, sccs)
  dfn[u] = low[u] = index[:value]
  index[:value] += 1
  stk.push(u)
  adj[u].each do |v|
    if dfn[v] == -1
      tarjan_scc_dfs(adj, v, index, dfn, low, stk, sccs)
      low[u] = [low[u], low[v]].min
    elsif stk.include?(v)
      low[u] = [low[u], dfn[v]].min
    end
  end
  if dfn[u] == low[u]
    scc = []
    scc << stk.pop while stk[-1] != u
    sccs << scc.push(stk.pop).sort
  end
end


# Test version, with these two changes:
# 1) change Hash `index` to Fixnum `index`
# 2) change `low[u] = [low[u], dfn[v]].min` to `low[u] = [low[u], low[v]].min`
def tarjan_scc_dfs_test(adj, u, index, dfn, low, stk, sccs)
  dfn[u] = low[u] = index
  index += 1
  stk.push(u)
  adj[u].each do |v|
    if dfn[v] == -1
      tarjan_scc_dfs_test(adj, v, index, dfn, low, stk, sccs)
      low[u] = [low[u], low[v]].min
    elsif stk.include?(v)
      low[u] = [low[u], low[v]].min
    end
  end
  if dfn[u] == low[u]
    scc = []
    scc << stk.pop while stk[-1] != u
    sccs << scc.push(stk.pop).sort
  end
end

def tarjan_scc_test(adj)
  n = adj.size
  dfn = Array.new(n, -1)
  low = Array.new(n, -1)
  index = 0
  stk, sccs = [], []
  (0...n).each do |u|
    tarjan_scc_dfs_test(adj, u, index, dfn, low, stk, sccs) if dfn[u] == -1
  end
  sccs.sort!
end


# Randomly generate a simple direct graph with at most max_n nodes
# Nodes are number 0 to max_n - 1. Edges stored adjacent list
def generate_graph(max_n)
  @rng ||= Random.new(Time.hash)
  n = @rng.rand(1..max_n)
  ed = []
  n.times do |i|
    n.times do |j|
      ed << [i, j] if i != j
    end
  end

  ed.size.times do |i|
    j = @rng.rand(i...ed.size)
    ed[i], ed[j] = ed[j], ed[i]
  end

  adj = Array.new(n) { Array.new }
  @rng.rand(0..ed.size).times do |i|
    u, v = ed[i]
    adj[u] << v
  end
  adj
end

# Main loop: generating random graphs and test two functions until answers differ from each other.
while true
  adj = generate_graph(8)
  sccs = tarjan_scc(adj)
  sccs_test = tarjan_scc_test(adj)
  if sccs != sccs_test
    puts "Graph: "
    adj.size.times do |u|
      puts "#{u}: #{adj[u]}"
    end
    puts "Correct components output:"
    p sccs
    puts "Wrong components output by text program:"
    p sccs_test
    break
  end
end

アップデート：

これは、このテスト ケースでの変更されたアルゴリズムの手順です (アルゴリズムを正しく理解している限り)。

0->1, 1->2, 2->1, 1->0, 0->3, 3->2.

init: [[index=0, lowlink=0], [index=-1, lowlink=-1], [index=-1, lowlink=-1], [index=-1, lowlink=-1]]
0->1: [[index=0, lowlink=0], [index=1, lowlink=1], [index=-1, lowlink=-1], [index=-1, lowlink=-1]]
1->2: [[index=0, lowlink=0], [index=1, lowlink=1], [index=2, lowlink=2], [index=-1, lowlink=-1]]
2->1: [[index=0, lowlink=0], [index=1, lowlink=1], [index=2, lowlink=1], [index=-1, lowlink=-1]]
(ノード 2 から戻り、現在の親はノード 1 です)
1->0: [[index=0, lowlink=0], [index=1, lowlink=0], [index=2, lowlink=1], [index=-1, lowlink=-1]]
(注意: この順序で各エッジにアクセスすると、ノード 2 のローリンクは 0 ではなく 1 になります)
(ノード 1 から戻り、現在の親はノード 0 です)
0->3: [[index=0, lowlink=0], [index=1, lowlink=0], [index=2, lowlink=1], [index=1, lowlink=1]]
3->2: [[index=0, lowlink=0], [index=1, lowlink=0], [index=2, lowlink=1], [index=1, lowlink=1]]
(ノード 2 のローリンクは 1 であるため、ノード 3 のローリンクは 0 ではなく、ノード 3 は単一の SCC としてマークされます)
(ノード 3 から戻り、現在の親はノード 0 です)
([0, 1, 2] を SCC としてマーク)

ご覧のとおり、エッジにアクセスする順序によって異なる答えが得られます。しかし、tarjans-algorithm では問題になりません。

于 2014-04-18T15:53:50.210 に答える