7. gw_scc.exe の使用法

• アルゴリズムの名称：Strongly Connected Components
• 内容：有向グラフにおいて、閉路ができている部分の要素をグループ別に出力する

【概要】

scc は、"Strongly Connected Components" のことです。

このアプリは、有向グラフにおいて、閉路 (閉じたループ) ができている部分の要素をグループ別に出力します。

1. gw_scc.exe を起動すると、操作ガイドが現れるので [OK] を押す。
   
   以下の手順で、10個のノードを持つグラフを作成する。
   
   1. 左端の画面上で、クリックすると１つのノード「N1」が生成される。
   2. さらに、右方向に順に６個のノード N2, N3, N4, N5, N6, N7 を追加する
   3. 最後に、右端から３個のノード N8, N9, N10 を追加する
   
   
   
   
2. 以下の手順で、12個のエッジ (E1 ～ E12) を作成する
   
   E1: N1 --> N2
   E2: N2 --> N3
   E3: N3 --> N4
   E4: N4 --> N5
   E5: N8 --> N9
   E6: N9 --> N10
   E7: N10 --> N7
   E8: N7 --> N6
   E9: N6 --> N5
   E10: N3 --> N6
   E11: N1 --> N7
   E12: N9 --> N6
   
   ・このグラフには閉路 (閉じたループ) が無いので、個々のノードが要素１つを持つグループを構成する。ノードのラベルが、各グループ番号となります。
   
   
   
3. 新しいエッジ「N6 --> N8」を作成すると、「N6 --> N8 --> N9 --> N6」が閉路を構成するので、１つのグループを形成し、グループ番号が "２" となる。
   
   さらに、「N9 --> N10 --> N7 --> N6」が閉路となり、グループ番号 "２" に組入れられる。
   
   　
   
   
4. 新たに「16 nodes, 16 edges」のグラフを作成する
   
   メニューの "Graph-> Create-> random planar" を選ぶ
   
   　　 ダイアログが現れるので、以下の設定をする
   
   　　　　　　　 nodes = 16
   　　　　　　　 edges = 16
   　　　　　　　 layout= circle
   
   
   
   
5. ノード [2] から ノード [6] へエッジを作成する
   
   
   
6. １つの閉路が出来て、グループ "４" が形成される
   
   右下のノード [2] から 上方のノード [4] へエッジを作成する
   
   
   
7. １つの閉路が出来て、グループ "３" が形成される