graph.scc

有向グラフの強連結成分分解を行い、DAG を作る. 大まかにすることは、 元のグラフの頂点番号と、生成されたDAGの頂点番号を対応付けるベクトル cmp を見つけること. DAG は元のグラフの隣接関係と cmp を見て構成できる.

graph.scc.rs

Rust 実装. グラフを隣接リストとして表現し、有向グラフを与えると cmp と DAG の組みを返す.

/// convert a DiGraph to a DAG
/// scc: (neigh) -> (cmp, dag)
///   where
///     neigh is a neigh list of DiGraph
///     cmp is mapping vector; cmp[DiGraph-Vertex-Index] = DAG-Vertex-Index
///     dag is a neigh list of DAG
fn scc(neigh: &Vec<Vec<usize>>) -> (Vec<usize>, Vec<Vec<usize>>) {

    let n = neigh.len();

    // Post-order traversal
    let mut po = vec![];
    {
        let mut used = vec![false; n];
        for u in 0..n {
            let mut stack = vec![u];
            let mut pre = vec![];
            while let Some(v) = stack.pop() {
                if used[v] { continue }
                used[v] = true;
                pre.push(v);
                for &w in neigh[v].iter() { stack.push(w) }
            }
            pre.reverse(); po.extend(pre);
        }
    }

    let mut neigh_r = vec![vec![]; n];
    for u in 0..n {
        for &v in neigh[u].iter() {
            neigh_r[v].push(u);
        }
    }

    // Components
    let mut cmp = vec![0; n];
    let m;
    {
        let mut used = vec![false; n];
        let mut k = 0;
        po.reverse();
        for &u in po.iter() {
            let mut stack = vec![u];
            if used[u] { continue }
            while let Some(v) = stack.pop() {
                if used[v] { continue }
                used[v] = true;
                cmp[v] = k;
                for &w in neigh_r[v].iter() { stack.push(w) }
            }
            k += 1;
        }
        m = k;
    }

    // DAG
    let mut dag = vec![vec![]; m];
    for u in 0..n {
        let u2 = cmp[u];
        for &v in neigh[u].iter() {
            let v2 = cmp[v];
            if u2 != v2 { dag[u2].push(v2) }
        }
    }
    for u in 0..m {
        dag[u].sort();
        dag[u].dedup();
    }

    (cmp, dag)
}

graph.scc.cc

C++ 実装. class として定義してあり、コンストラクタで cmp のみ構成する. .dag() メソッドで DAG を返す. グラフは全て隣接リスト.

struct StronglyConnectedComponents {
  int N, K;

  vector<bool> used;
  vector<int> vs; // 帰り掛け順
  vector<vector<int>> arc;
  vector<vector<int>> arc_r;
  vector<int> cmp; // 連結成分

  void dfs(int v) {
    used[v] = true;
    for (int u: arc[v]) {
      if (!used[u]) dfs(u);
    }
    vs.push_back(v);
  }

  void rdfs(int v, int k) {
    used[v] = true;
    cmp[v] = k;
    for (int u: arc_r[v]) {
      if (!used[u]) rdfs(u, k);
    }
  }

  /* cmp の構成 */
  StronglyConnectedComponents(vector<vector<int>>&d) {
    N = d.size();

    cmp.resize(N);
    arc.resize(N);
    arc_r.resize(N);
    rep (u, N) {
      for (int v: d[u]) {
        arc[u].push_back(v);
        arc_r[v].push_back(u);
      }
    }

    vs.clear();
    used = vector<bool>(N, false);
    rep (i, N) if (!used[i]) dfs(i);

    int k = 0;
    used = vector<bool>(N, false);
    reverse(begin(vs), end(vs));
    for (int u: vs) if (!used[u]) rdfs(u, k++);

    K = k;
  }

  /* 隣接リスト dag */
  vector<vector<int>> dag()
  {
    vector<vector<int>> d(K, vector<int>(K, 0));
    rep (u, N) {
      int u2 = cmp[u];
      for (int v: arc[u]) {
        int v2 = cmp[v];
        if (u2 != v2) d[cmp[u]][cmp[v]] = 1;
      }
    }
    vector<vector<int>> neigh(K);
    rep (u, K) {
        rep (v, K) {
            if (u != v && d[u][v]) neigh[u].push_back(v);
        }
    }
    return neigh;
  }

};