\chapter{自動可視化への準備}
\section{可読性の定義}
\label{sec:可読性の定義}
作成するプログラムには，木表現で作成されたトポロジーを確実に図に再現することが求められるが，さらに，再現されたトポロジーは可読性が高いものである必要もある．本研究では，可読性の高さを定義する上でグラフ描画アルゴリズムにおける可視性の高さの基準\cite{力学モデルを用いた階層型グラフデータ画面配置手法の改良手法とウェブサイト視覚化への応用}を参考にプログラムに求められる可読性を定義した．
\begin{itemize}
\item 線が重ならない
\item 線の間が適切な距離を保つ
\item 線が滑らかである
\end{itemize}

\section{文法の定義}
\label{sec:文法の定義}
BNFによって文法定義を行う．
木文法{G=(S，N，F，R)}は以下のように定められる．Sは開始記号，Nは非終端記号の集合，Fは終端記号の集合，Rを生成規則とする．このとき，N= \{ S，A，$B_{+}$，$B_{-}$，$C_{+}$，$C_{-}$，${}C_{+}^{*}$，${}C_{-}^{*}$，\} ，F＝ \{ $a_{\phi}$()，$b_{\phi}(，\{\})$，$b_{\phi-}(，\{\})$，$a_{+}()$，$a_{-}()$，$a_{2}()$，$b_{++}\{，\}$，$b_{+-}\{，\}$，$b_{--}\{，\}$，$b_{-+}\{，\}$，$\beta_{+}\{\}$，$\beta_{-}\{\}$，$c_{+}(，)$，$c_{-}(，)$，l，n，cons(，)\}　とする．
\\ 
\\ 流れの生成規則\quad R
\\{\footnotesize
S\quad →\quad $a_{\phi}$($A^{*}$) ｜$b_{\phi+}$($B_{+}$，\{${}C_{-}^{*}$\})｜$b_{\phi-}$($B_{-}$，\{${}C_{+}^{*}$\})
\\A\quad →\quad$a_{+}$($B_{+}$) ｜$a_{-}$($B_{-}$)｜$a_{2}$(${}C_{+}^{*}$，${}C_{-}^{*}$)
\\$A^{*}$\quad  →\quad n｜ cons(A，$A^{*}$)
\\$B_{+}$\quad  →\quad l ｜$b_{++}$\{$B_{+}$，$B_{+}$\}｜$b_{+-}$($B_{+}$，$B_{-}$)｜$\beta_{+}$\{${}C_{+}^{*}$\}
\\$B_{-}$\quad  →\quad l ｜$b_{--}$\{$B_{-}$，$B_{-}$\}｜$b_{-+}$($B_{-}$，$B_{+}$)｜$\beta_{-}$\{${}C_{-}^{*}$\}
\\$C_{+}$\quad →\quad $c_{+}$($B_{+}$，${}C_{-}^{*}$)
\\$C_{-}$\quad →\quad $c_{-}$($B_{-}$，${}C_{+}^{*}$)
\\${}C_{+}^{*}$\quad →\quad n｜cons($C_{+}$，${}C_{+}^{*}$)
\\${}C_{-}^{*}$\quad →\quad n｜cons($C_{-}$，${}C_{-}^{*}$)
\\}

二次元多重領域上の流れは大域的に３つの基本パターン$a_{\phi}$，$b_{\phi+}$，$b_{\phi-}$からなる．
$a_{\phi}$は一様流を表す．$b_{\phi+}$，$b_{\phi-}$はともに円盤状の流れで最外境界部をもち，それぞれ＋が反時計回り，－が時計回りの流れを表す．

\begin{figure}[H]
\centering
\includegraphics[width=8cm]{Basis_ab.png}
\caption{３つの基本パターン　左から$a_{\phi}$，$b_{\phi+}$，$b_{\phi-}$}
\end{figure}
ここで，${}□_{T}^{L}$はホールである．Tにはどの非終端記号から生成される木であるかという情報と流れの向きを表す．一方，Lはホールが複数存在した場合,そのホールを区別するために利用するラベルである．
また，文脈からホールが明らかな場合ラベルを省略することがある．
そのほかにも，A系の流れ，B系の流れ，C系の流れの構造が存在する．基本パターンに，これらの構造を生成規則に則り，組み合わせることで流線図を表現する．


\begin{figure}[H]
\centering
\includegraphics[width=8cm]{akei.png}
\caption{$a$系の流れ　左から$a_{+}$，$a_{-}$，$a_{2}$}
\end{figure}

\begin{figure}[H]
\centering
\includegraphics[width=8cm]{bkei.png}
\caption{$b$系の流れ　左から$b_{++}$，$b_{--}$，$b_{+-}$，$b_{-+}$，$b_{+}$，$b_{-}$}
\end{figure}

\begin{figure}[H]
\centering
\includegraphics[width=4cm]{ckei.png}
\caption{$c$系の流れ　左から$c_{+}$，$c_{-}$}
\end{figure}

本研究では,木表現を確実に図に自動変換することが目的であるため\cite{円盤上の非圧縮流の反転の解析}で考えられた生成規則の円順列\{\}については考えないものとし,入力する文字列を容易にするため,ホール部分をそれぞれ置き換える．よって，実際に入力する文字列は例として以下のように入力する．
\\
$b_{\phi+}$($b_{++}$\{l，l\}，\{n\})\quad→\quad　b0+(b++（l，l），(n))
\\





\section{アプローチ}
\label{sec:アプローチ}
本研究の目的の達成には，\ref{sec:可読性の定義}の定義を満たすトポロジーな流れの図を二次元上の画面に表示することを必須としている．アプローチとしては，コンピュータのディスプレイ上に作成した図を可視化し，画像ファイルとして保存することを可能にするプログラミング言語を本研究で使用した．私達は様々な分野での実績があり多様な環境での信頼性が高い Python とベクタ形式での描画を支援するAsyptoteの２つプログラミング言語をアプローチ方法とした．


\section{構文解析}
\label{sec:構文解析}
本研究ではPythonでの実装を行うため，Python専用の構文解析ライブラリPLYを利用し構文解析を行った．PLYとは，Python Lex-Yaccの略であり，Python専用の構文解析ライブラリであり,lexモジュールとyaccモジュールからなる．lex.モジュールでは，入力されたテキストを正規表現により定義されたデータ構造に分解し，字句解析を行う．
プログラムコードの概要として，字句の部分をtokensで定義し,定義した字句の正規表現による具体的なルールを下の部分で定義していく．
\\
\\{\footnotesize
tokens=(
\\ \quad'定義する字句名'，
\\ \quad …
\\)
\\t\_定義した字句名=r'ルールの記述'
\\}
\\
本研究では,\ref{sec:文法の定義}によって定義された終端記号を字句として定義し,終端記号の具体的なルールとして入力文字を表す．また,改行は余白は無視する．例としてプログラムコードの一部を記述する．
\\
\\{\footnotesize
import ply.lex as lex
\\
tokens=(
\\ \quad 'CONS'，
\\ \quad'NIL'，
\\ \quad 'A0'，
\\ \quad 'LPAREN'，
\\ \quad 'RPAREN'，
\\ \quad 'COMMA'，
\\ \quad 'A\_PLUS'，
\\ \quad …
\\)
\\t\_ignore = '\textbackslash t\textbackslash n'
\\t\_NIL = r'n'
\\t\_A0 = r'a0'
\\t\_LPAREN =  r'\textbackslash( '
\\t\_RPAREN = r'\textbackslash) '
\\t\_COMMA =r','
\\t\_A\_PlUS = r'a\textbackslash+'
\\…
\\}
その他にも，t\_error()でエラー処理を行ったり，lex.lex()でオブジェクトの生成を行う．

一方，yacc.モジュールでは，lexモジュールによって定義された字句を読み込み，自由文法によって定義された構文を評価して抽象構文木を作成し構文解析を行う．プログラムコードの概要として，ｌexモジュールにより定義された字句を読み込み，読み込んだ字句からなる木構造を定義していく．
\\
\\{\footnotesize
import ply.yacc as yacc
\\ from ｌexモジュール　import tokens

\\ def \quad p_関数名(p)\quad :
\quad\quad'\quad : \quad 
\\ \quad …
\\)
\\t\_定義した字句名=r'ルールの記述'
\\}
\\

\subsection{デザインパターン}
\label{sec:デザインパターン}
ソフトウェア設計者の経験から同じような問題は，典型的に同じパターンの解決策になることが発見され，それらのパターンをカタログ化したものをデザインパターンという．オブジェクト指向において，様々なプログラムで利用でき，目的に応じて23種の中から選沢して扱うことができる．主にオブジェクト指向言語で再利用性が高いクラスやライブラリを作成する際に利用される．本研究では，デザインパターンの中のインタプリタパターンを取り扱う．インタプリタパターンについては，\cite{Java言語で学ぶデザインパターン入門}を参考にした．インタプリタパターンは，形式的に記述された記号列を解析した結果に則って処理したい場合に利用されるデザインパターンである．目的に応じた言語を作成することで，通訳の意味を果たすプログラムを用意することにより，素早く処理することが可能になる．再帰的な構造を持ち，全ての要素に共通な処理を持つ抽象クラスを定義することで構造の変更を容易にしたり，見た目をシンプルにすることが可能である．
本研究では，木文法より定義された生成規則によって，字句解析と構文解析を行い，構文木を作成する．そのため，構文木に則った処理を実現するのに最適なインタプリタパターンを利用した．また，作成するクラスが多いため，オーバーライドを利用することで機能の追加が容易になり，修正を減らすことができる．

\begin{figure}[H]
\centering
\includegraphics[width=100mm]{interpreter_pattern.png}
\caption{インタープリタパターン}
\end{figure}
\ref{実装するクラス図}で,\ref{デザインパターン}を利用する．


\subsection{Pythonでの描画に使用するライブラリ}
\label{sec:pythonでの描画に使用するライブラリ}
pythonでは流線図を描画するにあたり，python用のグラフ描画ライブラリであるmatplotlibを使用する．matplotlibはグラフ描画ライブラリであるが，棒グラフや折れ線グラフなどの一般的なグラフの描画だけでなく，平面上への関数・図形の描画や波のシミュレーションなど様々な描画を行うことができる．例えば，木表現$b_{++}\{ ，\}$をmatplotlibを用いて作図しようとする場合，プログラム\ref{b-plus-plus}のように記述することで図\ref{fig:b++-sample}が出力される(このプログラムでは，例を示すため明示的に円の中心と半径を示し描画を行った．また，プログラム簡略のため矢印と停留点を描画していない．)．このプログラムの7行目までは描画のための設定であり，描画領域として高さ・幅ともに100の正方形を用意している．また，draw\_circは円を描画する関数であり，描きたい円の中心の座標と半径を引数にとる．ここでは(x,y)座標をそれぞれ(50,30)，(50,70)とする２つの円を描画することで$b_{++}\{ ，\}$を表現した．描画した画像はsavefigで保存することができる．この例では，EPS形式で保存した．
\begin{lstlisting}[caption=$b_{++}\{，\}$,label=b-plus-plus]
import matplotlib.pyplot as plt

fig = plt.figure()
ax = fig.add_subplot(111,aspect='equal')
W,H = 100,100
ax.set_xlim([0,W])
ax.set_ylim([0,H])

def draw_circ(center,r):
    circ=plt.Circle(center,r,ec="black",fill=False)
    ax.add_patch(circ)

draw_circ((50,30),20)
draw_circ((50,70),20)

fig.savefig("b++.eps")
\end{lstlisting}

\begin{figure}[H]
\centering
\includegraphics[width=7cm]{b++.eps}
\caption{$b_{++}\{，\}$}
\label{fig:b++-sample}
\end{figure}