Lispの話(グラフの可視化)

こんにちは、たくさん寝太郎です。

気付いたら一ヶ月近くLand of Lispを放置していたので再び勉強再開しようと思います。

グラフ

ここで言うグラフとは、エッジ(辺)の集合とノード(節点)の集合で構成されるものです。

グラフ (データ構造) - Wikipedia

Graphvizというオープンソースのツールを使えば、上のようなグラフ構造を簡単に生成してくれます。

janken.dotというファイルを作って以下のように記述します。

digraph {
 goo -> choki
 choki -> paa
 paa -> goo
}

コマンドラインで次のように実行します。

neato -Tpng -O janken.dot

-Tpngは.pngファイルで出力
-Oは出力ファイルの名前を入力ファイルに基づいて自動的に生成するオプションです。
他にも様々なオプションがあります。

実際に実行するとjanken.dot.pngというファイルが出来てると思います。

dot言語の記法についてはこちらのサイトに詳しく載っています。
qiita.com

GraphvizとLispでグラフを描いてみる

グラフ理論には最短経路問題というものがあります。
今回は辺の重みが非負値の有向グラフを考えます。

作りたいやつ

ノードの数nを与えた時、始点を1・終点をnとします。
今回は簡単のためノードmとノードm+1,m+2を結ぶ場合のみを考え、各辺にランダムに0~9の重み付けをしたグラフを出力します。

例えばn=5の場合はこんな感じになります。

この場合だとノード1から5への最短経路は(1,3,5)で距離は9ですね。

ノードの数を定義する

(defun nodes-num ()
  (princ "Please type the number of nodes:")
  (defparameter *nodes-num* (read)))

dotファイルの形式になるよう出力する関数を作る

(defun graph->dot ()
  (princ "digraph{")
  (dotimes (i (1- *nodes-num*))
    (if (< i (- *nodes-num* 2))
      (dotimes (x 2)
	(progn (print (1+ i))
	       (princ "->")
	       (princ (+ i (+ x 2)))
	       (princ "[label=")
	       (princ (random 10))
	       (princ "];")))
      (progn (print (1+ i))
	     (princ "->")
	     (princ *nodes-num*)
	     (princ "[label=")
	     (princ (random 10))
	     (princ "];"))))
  (princ "}"))

ノードの数をnとした時、ノードm(m<n-2)とノードm+1,m+2を結び、ノードn-1とノードnを結びます。
上の関数ではifとdotimesを用いました。もっと楽な方法があるかもしれませんが...。

辺の重み付けは(random 10)で行なっています。

では上2つの関数を実行してみます。

(node-num)
(graph->dot)

Please type the number of nodes:6
digraph{
1 ->2[label=7];
1 ->3[label=8];
2 ->3[label=8];
2 ->4[label=3];
3 ->4[label=3];
3 ->5[label=2];
4 ->5[label=2];
4 ->6[label=3];
5 ->6[label=4];}

良い感じに出力されました。

ファイルへの出力

with-open-fileを使います。
例として「Hello world!」と書かれたファイルを生成してみましょう。

(with-open-file (my-stream
		  "helloworld.txt"
		  :direction :output
		  :if-exists :supersede)
  (princ "Hello world!" my-stream))

:directionで入力か出力かを指定し、:if-existsで既に同名のファイルが存在する場合に上書きするよう指定します。

ファイル入出力については以下のサイトが大変分かりやすいです。
www.geocities.jp

サンク

今すぐに実行したくない計算を包んでおくのに使われる無引数関数をサンク(thunk)と言います。

先ほどの定義ではgraph->dotを実行した場合結果は返り値ではなくコンソール出力で得られます。そこで、graph->dotをサンクとして渡すことで必要な時にgraph->dotを実行し出力をファイルに書き出すことができます。

(defun dot->png (fname thunk)
  (with-open-file (*standard-output*
		    fname
		    :direction :output
		    :if-exists :supersede)
    (funcall thunk))
  (ext:shell (concatenate 'string "neato -Tpng -O" fname)))

(defun graph->png (fname)
  (dot->png fname (lambda () (graph->dot))))

Land of Lispでは「コンソールの出力を横取りする」の中で*standard-output*を宣言している理由について述べていましたが正直よく分かりませんでした(かなしい)

とりあえずこれで求めていたプログラムが出来ました。
試しにn=10で実行してみます。

(nodes-num)
(graph->png "test.dot")

=>

Please type the number of nodes:10

それっぽい感じになりました。

これでLand of Lisp第7章まで終わりです。
年内までに読み終えられたら良いなぁ...