[php]トポロジカルソート

カテゴリ: php / author: uechoco / 2007年12月10日 15:06:41
この記事を読む時間：20分21秒くらい

トポロジカルソートって知っていますか？

最近では平成19年のソフトウェア開発技術者の午後問題で取り上げられました。
Googleで探しても他のソートよりは明らかに数が少ないですね。
おそらく、トポロジカルソートという名前のほかにも呼び方が複数あるのと、
そもそもソートの分類の中では異質なのかもしれません。

本題に入る前にグラフの種類について説明します。
ここでいうグラフというのは、Excelなどのウィザードで作成するグラフではなく、
グラフ理論で取り扱われる点集合と辺集合の組み合わせのことです。
下図(図1)のように図示されるのが一般的です。

図1. グラフの例

グラフにはいくつかの種類があります。
わかりやすいのが無向グラフ(undirected graph)と有向グラフ(directed graph)です。
その名のとおり、無向グラフは各辺に方向がついていないグラフ、有向グラフは各辺に方向がついているグラフです。
先ほどの図にはそれぞれの例が描かれています。
トポロジカルソートで扱うのはDAG(Directed Acyclic Graph : 有向非循環グラフ)です。
DAGは有向グラフの一種で、閉路を持たない（循環する部分を持たない）ものを指しています。
次の図2は循環のあるグラフの例で、今回のトポロジカルソートには用いることができないものです。

図2. 循環のあるグラフの例

さてさて本題。トポロジカルソートというのは、グラフの頂点に連番をつけていくのですが、
矢印の向きと大小関係が一致するようにするというものです。
頂点につけた番号は位相的順序とかトポロジカルソート値と呼びます。
図3、図4はトポロジカルソート値を割り当てたグラフの例です。

図3. トポロジカルソート値の例1

図4. トポロジカルソート値の例2

どのようにしてこのトポロジカルソート値を求めるかと言うと、一言で言えば再帰的に求めます。
深さ優先探索とかそういう用語も関係してきますが、解説が面倒なので今回は省略します。
というかもう解説がだいぶ面倒なのでソースコード出しちゃいます。

PLAIN TEXT
PHP:
  1. define('NMAX'   , 128);
  2. define('NEVER'  ,   0); // the node have never visited
  3. define('JUST'   ,   1); // the node is just been visiting
  4. define('ONCE'   ,   2); // the node have already visited
  5. define('NO_NODE',  -1); //
  6. /**
  7.  * topologically sort graph
  8.  *
  9.  * @author      uechoco <uechoco @gmail.com>
  10.  * @version     1.0.0
  11.  * @since       PHP 5.2.1
  12.  */
  13. class TopologicalSort
  14. {
  15.     /**
  16.      * label-list of nodes
  17.      *
  18.      * @var    array
  19.      * @access private
  20.      */
  21.     var $nodeLabels;
  22.  
  23.     /**
  24.      * adjacent matrix of nodes
  25.      *
  26.      * @var    array
  27.      * @access private
  28.      */
  29.     var $adjacent;
  30.  
  31.     /**
  32.      * index of topological values
  33.      *
  34.      * @var    array
  35.      * @access private
  36.      */
  37.     var $result;
  38.  
  39.     /**
  40.      * number of results
  41.      *
  42.      * @var    integer
  43.      * @access private
  44.      */
  45.     var $k;
  46.  
  47.     /**
  48.      * execute "topological sort"
  49.      *
  50.      * @param  string
  51.      * @access public
  52.      * @return boolean
  53.      */
  54.     function execute($fileName)
  55.     {
  56.         $this->initialize();
  57.  
  58.         $num = $this->readDAG($fileName);
  59.  
  60.         if ($num == 0)
  61.         {
  62.             echo "{$fileName} is invalid data.";
  63.             return false;
  64.         }
  65.  
  66.         for ($i = 0; $i <$num; $i++)
  67.         {
  68.             if ($this->isNeverVisited($i))
  69.             {
  70.                 if (!$this->visit($i, $num))
  71.                 {
  72.                     echo 'A cyclic link is found.';
  73.                     return false;
  74.                 }
  75.             }
  76.         }
  77.         return true;
  78.     }
  79.  
  80.     /**
  81.      * initialize class fields
  82.      *
  83.      * @access   private
  84.      * @return   void
  85.      */
  86.     function initialize()
  87.     {
  88.         for ($i = 0; $i <NMAX; $i++)
  89.         {
  90.             $this->nodeLabels[$i] = '';
  91.             $this->result[$i]     = NO_NODE;
  92.             $this->visited[$i]    = NEVER;
  93.             for ($j = 0; $j <NMAX; $j++)
  94.             {
  95.                 $this->adjacent[$i][$j] = false;
  96.             }
  97.         }
  98.  
  99.         $this->k = 0;
  100.     }
  101.  
  102.     /**
  103.      * return true if the index have never visited, otherwise false
  104.      *
  105.      * @param    integer
  106.      * @access   private
  107.      * @return   void
  108.      */
  109.     function isNeverVisited($i)
  110.     {
  111.         return ($this->visited[$i] == NEVER);
  112.     }
  113.  
  114.     /**
  115.      * get number of nodes
  116.      *
  117.      * @access   private
  118.      * @return   integer
  119.      */
  120.     function getNodeCount()
  121.     {
  122.         $n = 0;
  123.  
  124.         // search the valid nodes in the label-list of nodes, and count these
  125.         while ($n <NMAX && $this->nodeLabels[$n] != '')
  126.         {
  127.             $n++;
  128.         }
  129.         return $n;
  130.     }
  131.  
  132.     /**
  133.      * register label of node
  134.      *
  135.      * @param    string  label of node
  136.      * @access   private
  137.      * @return   integer
  138.      */
  139.     function registerNodeLabel($nodeLabel)
  140.     {
  141.         if (
  142.         $nodeLabel == '')
  143.         {
  144.             return 0;
  145.         }
  146.  
  147.         // search the label in the label-list of nodes
  148.         $i = 0;
  149.         while ($i <NMAX && $this->nodeLabels[$i] != '')
  150.         {
  151.             // return the index if the label already exists
  152.             if ($this->nodeLabels[$i] == $nodeLabel)
  153.             {
  154.                 return $i;
  155.             }
  156.             $i++;
  157.         }
  158.         if (
  159.         $i>= NMAX)
  160.         {
  161.             return 0;
  162.         }
  163.  
  164.         // a new node label
  165.         $this->nodeLabels[$i] = $nodeLabel;
  166.         return $i;
  167.     }
  168.  
  169.     /**
  170.      * read DAG data
  171.      *
  172.      * @param    string
  173.      * @access   private
  174.      * @return   integer
  175.      */
  176.     function readDAG($fileName)
  177.     {
  178.         // open and read the file
  179.         $lines = file($fileName);
  180.         if ($lines === false)
  181.         {
  182.             return 0;
  183.         }
  184.  
  185.         // parse each line
  186.         foreach($lines as $line)
  187.         {
  188.             $matches = array();
  189.             $nodeLabelFrom = '';
  190.             $nodeLabelTo   = '';
  191.             if (
  192.             preg_match('/(w.*?)s.*?(w.*?)/', $line, $matches))
  193.             {
  194.                 $nodeLabelFrom = $matches[1];
  195.                 $nodeLabelTo   = $matches[2];
  196.             }
  197.             else
  198.             {
  199.                 return 0;
  200.             }
  201.             if (
  202.             $nodeLabelFrom == '' || $nodeLabelTo == '')
  203.             {
  204.                 return 0;
  205.             }
  206.  
  207.             // register nodes
  208.             $i = $this->registerNodeLabel($nodeLabelFrom);
  209.             $j = $this->registerNodeLabel($nodeLabelTo);
  210.             if (
  211.             $i <0 || $i>= NMAX || $j <0 || $j>= NMAX)
  212.             {
  213.                 return 0;
  214.             }
  215.  
  216.             $this->adjacent[$i][$j] = true;
  217.         }
  218.         return $this->getNodeCount();
  219.     }
  220.  
  221.     /**
  222.      * check visited
  223.      *
  224.      * @param    integer
  225.      * @param    integer
  226.      * @access   private
  227.      * @return   boolean
  228.      */
  229.     function visit($i, $n)
  230.     {
  231.         if ($n <0 || $n>= NMAX || $i <0 || $i>= $n)
  232.         {
  233.             return false;
  234.         }
  235.  
  236.         $this->visited[$i] = JUST;
  237.         for (
  238.         $j = 0; $j <$n; $j++)
  239.         {
  240.             if ($this->adjacent[$j][$i])
  241.             {
  242.                 $v = $this->visited[$j];
  243.                 if (($v == JUST) || (($v == NEVER) && !$this->visit($j, $n)))
  244.                 {
  245.                     return false;
  246.                 }
  247.             }
  248.         }
  249.  
  250.         $this->visited[$i] = ONCE;
  251.         $this->result[$this->k] = $i;
  252.         $this->k++;
  253.         return true;
  254.     }
  255.  
  256.     /**
  257.      * toArray
  258.      *
  259.      * @access   public
  260.      * @return   string
  261.      */
  262.     function toArray()
  263.     {
  264.         if ($this->k <= 0)
  265.         {
  266.             return;
  267.         }
  268.  
  269.         $data = array();
  270.         for ($i = 0; $i <$this->k; $i++)
  271.         {
  272.             $data[] = $this->nodeLabels[$this->result[$i]];
  273.         }
  274.         return $data;
  275.     }
  276.  
  277.     /**
  278.      * toString
  279.      *
  280.      * @param    string
  281.      * @access   public
  282.      * @return   string
  283.      */
  284.     function toString($glue = ', ')
  285.     {
  286.         return implode($glue, $this->toArray());
  287.     }
  288. }
  289.  
  290.  
  291. $ts = new TopologicalSort();
  292. if ($ts->execute('./data/ts01.dat'))
  293. {
  294.     echo $ts->toString();
  295. }

というわけで、こんな感じです。なんとなく英語でコメント書いたんですが、
正直、英語で書き始めなければと後悔しています。

各フィールドをざっくり説明します。

nodeLabels
頂点のラベルを保持しておくための配列です。データ内の出現順に追加されます。
adjacent
どの頂点からどの頂点への接続があるのかを保持しておくための隣接行列です。
行列自体はn次の正方行列です。2次元配列を用いることで、行列を再現しています。
visited
走査中の頂点の状態を保持しておくための配列です。頂点の個数だけ使用します。
頂点の状態は、次の3つがあります。

NEVER
まだ走査で訪れていない頂点です。
JUST
現在の走査で訪れている頂点です。
ONCE
既に走査で訪れたことのある頂点です。
result
トポロジカルソート値が確定した頂点のインデックス（添字）を保持しておくための配列です。
頂点の個数だけ使用します。トポロジカルソート値が確定した頂点から順に追加されます。
初期状態では、NO_NODEという定数で初期化されています。
k
トポロジカルソート値が確定している頂点の個数です。

このプログラムのアルゴリズムの中心は、visit()メソッドです。
自分への接続がある場合は再帰的にトポロジカルソート値を求め、
循環接続がある場合はfalseを返してメソッドを抜けようとします。

■参考Web文献

Spaghetti Source - トポロジカルソート
http://www.prefield.com/algorithm/graph/topological_sort.html

情報処理推進機構：情報処理技術者試験センター：問題冊子・配点割合・解答例・採点講評（2007、平成19年）
http://www.jitec.jp/1_04hanni_sukiru/mondai_kaitou_2007h19.html#19aki


コメントはまだありません »

コメントはまだありません。

この投稿へのコメントの RSS フィード。 TrackBack URI

コメントする

Copyright © 2012 うえちょこ＠ぼろぐ. WP Theme created by Web Top.