強連結成分分解をScalaで書いてみた


Haskellのコンパイルはメインのファイルを指定するだけでソースコードの依存関係を自動的に解析してコンパイルしてくれます。だからMakefileをわざわざ書く必要がありません。とても便利です。
このような依存関係を持つようなグラフを並べ替える必要がある時に役立つのがトポロジカルソートです。

ところでOCamlやSML、F#などのMLでは、相互再帰する関数同士をandで繋げて書きます。

```a.ml
type ta = A | AB of tb
and tb = B | Ba of ta

let rec a x = if x <= 0 then x else b (x - 1)
and b x = if x <= 0 then x else a (x + 1)
```

この例では型taから型tbを参照していて、型tbからも型taを参照しています。
また関数aから関数bを参照していて、関数bから関数aも参照しています。
このような場合は単純に順番を付ける事は出来ません。

このandで結ばれているデータ定義や関数の固まりをグラフの用語で強連結成分といいます。

強連結成分に分解しながら依存解析順に並べるアルゴリズムがあるので、強連結成分に分解すれば、トポロジカルソートも出来るわけです。

以下にScalaで書いた、強連結成分分解を示します。

```scala:scc.scala
package scc

object main extends App {

  def scc(g:Map[Int,Set[Int]]) {

    def rg(g:Map[Int,Set[Int]]):Map[Int,Set[Int]] = {

      g.toList.foldLeft(Map[Int,Set[Int]]()) {
        case (map,(k,set)) =>
          val map2 = if (map.contains(k)) map else map+(k->Set[Int]())
          set.foldLeft(map2) {
            case (map,v) => map + (v-> (if (map.contains(v)) map(v)+k else Set(k)) )
          }
      }
    }
    val rG = rg(g)

    def dfs(g:Map[Int,Set[Int]],ls:Iterable[Int],r:List[Int]):(Map[Int,Set[Int]],List[Int]) = {
      ls.foldLeft(g,r) {
        case ((g,r),x) =>
          if(!g.contains(x)) {
            (g,r)
          } else {
            val (g3,r3) = dfs(g - x, (g(x) - x), r)
            (g3,x::r3)
          }
      }
    }

    val (map,vs) = dfs(g,g.map{case(v,_)=>v},List())

    println("vs="+vs)

    def rdfs(g:Map[Int,Set[Int]], v:Int,ls:List[Int]):(Map[Int,Set[Int]],List[Int]) = {
      if(!g.contains(v)) (g, ls)
      else g(v).foldLeft(g - v, v :: ls){
        case ((rg,ls), v) => rdfs(rg , v, ls)
      }
    }

    val (u2,ls) = vs.foldLeft(rG,List[List[Int]]()) {
      case ((rg,ls),v) =>
          val (rg2,l) = rdfs(rg, v, List[Int]())
          (rg2, if(l==List()) ls else l::ls)
    }

    println(ls)
  }

  scc(
    Map(
      0->Set(1),
      1->Set(2),
      2->Set(3),
      3->Set(6),
      4->Set(5),
      5->Set(4),
      6->Set(1,8,7,3),
      7->Set(6),
      8->Set(),
      9->Set(10)
    )
  )
}
```

以上の内容を `scc.scala` として保存して、

```bash
$ scalac scc.scala
$ scala scc.main
```

とすると、

```
vs=List(9, 5, 4, 0, 1, 2, 3, 6, 7, 8)
List(List(8), List(2, 3, 7, 6, 1), List(0), List(4, 5), List(9))
```

のように表示されます。vsは途中経過です。

```
    Map(
      0->Set(1),
      1->Set(2),
      2->Set(3),
      3->Set(6),
      4->Set(5),
      5->Set(4),
      6->Set(1,8,7,3),
      7->Set(6),
      8->Set(),
      9->Set(10)
    )
```

このMapが依存データを表していて、0->Set(1)は1が0に依存している事を表しています。結果は

```
List(List(8), List(2, 3, 7, 6, 1), List(0), List(4, 5), List(9))
```

と表示されているので、8が親玉です。2,3,7,6,1は強連結成分です。OCamlのコードではandで繋ぐ物ですね。そして、0が続き、4,5が更に子どもで、9が一番最後です。9が参照しているという10は表示されていない所に注意ですね。依存関係の順番はOCaml等の順番と逆順になっているのが残念なので、逆順に並べてくれるアルゴリズムを使うとよいです。
実はここに至るまでの道のりは長いのですが、長過ぎて眠くなるとせっかくの授業も勿体ないですよね。簡単なソースがあって、動かしてみれると嬉しいのではないかと思う訳です。そして、これは、適当に書いてみた物なので間違えているかもしれないので、正しく動作するプログラムが欲しければ十分なテストが必要です。

なぜScalaなのかというと、そこにあったからなのですが、理由をこじつければ、より多くの人が読みやすいのではないかと思うからです。Scalaの標準のMapやSetは便利です。

依存解析を自動でやってくれるHaskellは最高！なのかというと、必ずしもそうではありません。MLのプログラムはいわば強連結成分で分析したソートした結果でファイルを管理するので、依存関係が明白になり、コンパイルも依存解析をする必要がないのでより高速に動きます。一長一短なのです。MLの優れている点はまさにここにあって、文法もまた解析が楽です。操作的意味論の議論もしやすくなります。(とはいえ、機能が豊富なOCamlのパーサもまた巨大です。)一方、Haskellの解析は(MLに比べると依存関係を分析する分)難しくなり使用するメモリ量等も増える事になります。でも便利です。そう、Scalaもコンパイル遅いっていう話がありますよねぇ。でも便利だ。でもOCamlのコンパイル速いですよー。キュルキュル動きますよー。でも前方参照がぁ。そうだ！適当に書いたら１回だけ自動的にソートしてくれる拡張を書けば良いんだ！って言ってもなぁ。簡単じゃないだろう。うーん悩ましい。

強連結成分分解はHaskellの実装を調べているときに教えて貰ったのかあるいは、ツイッターのまとめを見たのか忘れましたが、(すいません)とにかく、Haskellerの方に感謝です。

## 参考URL

1. tomiflu's blog - 強連結成分分解 2012
	http://tomiflu.hatenablog.com/entry/20121219/1355906640

2. 東北大学工学部授業資料 - アルゴリズムとデータ構造 第１２回 グラフの深さ優先探索 塩浦昭義 2012
	http://www.dais.is.tohoku.ac.jp/~shioura/teaching/ad11/ad11-12.pdf

3. tsort.scala - ThiporKong
	https://gist.github.com/ThiporKong/4399695 

4. そろそろホンキ出す - トポロジカルソート mingw 2009
	http://ameblo.jp/mingw/entry-10389158344.html
5. kanetaiの二次記憶装置 - 強連結成分分解(Decomposition of Strongly Connected Components)
	http://d.hatena.ne.jp/kanetai/20140209/1391915669

6. 基礎数理 - グラフの強連結成分分解
	http://www.misojiro.t.u-tokyo.ac.jp/~murota/lect-kisosuri/strongdec141015.pdf

7. External Memory - 強連結成分分解アルゴリズムの雰囲気
	http://spinda2.blog48.fc2.com/blog-entry-492.html

8. 各種アルゴリズムの C++ による実装 -  強連結成分分解
	http://www.prefield.com/algorithm/graph/strongly_connected_components.html

9. stackoverflow - How to implement a DFS with immutable data types
	http://stackoverflow.com/questions/5471234/how-to-implement-a-dfs-with-immutable-data-types

10. togatter let rec の型推論と多相型
	http://togetter.com/li/82350