有向グラフを強連結成分に分解するアルゴリズム

CormenのIntroduction to Algorithmsには，グラフGと有向辺を逆にしたG_revに対してそれぞれDFSする方法が紹介されている．これは，わかりやすいアルゴリズムではあるのだけれど，逆グラフを求める必要があるのが玉にキズである．

一方，SedgewickのAlgorithms in C++には，逆グラフを求めないで1-passのDFSで求める手法が紹介されていた．こちらは連結成分を管理するためのスタックを別途使う必要があるが，逆グラフを求める必要がないのでうれしい．

そこで，OCamlで実装してみた．

module type DirectedGraphType =
  sig
    type t
    type node
    val all_nodes : t -> node list
    val adjacent_nodes : t -> node -> node list
  end

module type S =
  sig
    type t
    type node
    val decompose_scc : t -> node list list
  end

module Make(Graph: DirectedGraphType) =
  struct
    type t = Graph.t
    type node = Graph.node

    (*
     * decompose_scc: t -> node list list
     * 
     * -- decompose to strongly connected components(SCC)
     * -- from directed graph
     * 
     * ref. Algorithms in C++ by R. Sedgewick
     *)
    let decompose_scc g =
      let stack = Stack.create() in
      let all_nodes = Graph.all_nodes g in
      let node_num = List.length all_nodes in
      let values = Hashtbl.create node_num in
      let index = ref 0 in
      let results = ref  in
      let rec visit n =
        incr index;
        let min = ref !index in
          Hashtbl.add values n !index;
          Stack.push n stack;
          List.iter (
            fun t ->
              let m =
                if Hashtbl.mem values t then Hashtbl.find values t else visit t
              in
                if m < !min then min := m
          ) (Graph.adjacent_nodes g n);
          if !min == Hashtbl.find values n then
            (let rec loop ns =
              let m = Stack.pop stack in
                Hashtbl.replace values m (node_num + 1);
                if m != n then loop (m::ns) else (m::ns)
             in
               results := (loop )::!results);
          !min
      in
        List.iter
          (fun n -> if not (Hashtbl.mem values n) then ignore (visit n))
          all_nodes;
        !results
  end

基本的には参考書通りの実装だが，汎用的に使いたいのでファンクタとして定義している．