JPH061484B2 - 状態遷移図表示処理方式 - Google Patents

Description

【発明の詳細な説明】 〔概要〕 状態遷移図表示処理方式に関し、 状態遷移を示す矢印の交わりを少なくして状態遷移を見
易くすることを目的とし、 状態の各々についての遷移数を求める遷移数決定部と、
前記状態の数に応じて円周上の表示位置を決定する表示
位置決定部と、前記状態を前記表示位置に対応させてそ
の配置位置を決定する状態配置決定部とを備え、前記状
態配置決定部が前記遷移数に基づいて配置位置を決定す
るように構成する。

〔産業上の利用分野〕

本発明は状態遷移図表示処理方式に関する。

状態遷移図は、状態遷移関数をグラフ化して各状態間の
関係をわかり易く表示したものであり、プログラムや順
序回路の設計、解析等に広く用いられる。

〔従来の技術〕

第９図に図示の如き状態遷移関数（状態遷移表）につい
てグラフ化して状態遷移図とする場合、従来は次のよう
にされていた。

第１０図は従来技術説明図であり、従来の状態遷移図の
一例を示している。

従来は、表示すべき各状態ａないしｄは、ランダムにあ
るいは表れる順に、直線上（第１０図(A)）又は円周上
（第１０図(B)）に配置される。この後、状態遷移表に
従って、各状態の間に状態遷移を示すものとして有向の
矢印及び入力が表示される。例えば、状態ａに入力
“０”があると状態ｂに遷移する時は、「ａ の如く表示される。

〔発明が解決しようとする課題〕

前述の従来技術によれば、表示すべき各状態がランダム
に又は表れる順に配置されるため、第１０図(A)，(B)に
図示の如く、矢印が交わってしまう。そして、状態の数
が増し、状態遷移が複雑になる程、矢印の交わりは多く
なる可能性がある。

矢印の交わりが多くなると、状態遷移表から状態遷移図
を作成しても、状態遷移が見づらく、理解できにくくな
るという問題を生じる。

本発明は、状態遷移を示す矢印の交わりを少なくして状
態遷移を見易くした状態遷移図表示処理方式を提供する
ことを目的とする。

〔課題を解決するための手段〕

第１図は本発明の原理構成図であり、本発明によるデー
タ処理装置を示している。

第１図において、１は中央処理装置（ＣＰＵ）及びメモ
リを含む処理装置、２は遷移数決定部、３は状態配置決
定部、４は表示位置決定部、５は状態数カウント部、６
ないし８はメモリ部、９は表示情報部、１０は矢印付加
部、１１は表示制御部、１２はグラフィックライブラ
リ、１３は表示画面を有する表示装置である。

グラフ化して表示すべき対象である状態遷移表例えば第
９図の如きものが、メモリ部６に保持される。

遷移数決定部２は、メモリ部６の状態遷移表に基づいて
各状態間の遷移数を求め、第２図図示の如き遷移数の表
を作成し、これをメモリ部７に格納する。ここで、遷移
数とは、状態遷移図を作成した時に、付加される矢印の
本数をいう。例えば、今は第９図の状態遷移表によって
いるから、状態 の２本（遷移数２）である。従って、状態ａについての
遷移数の計Ｓｉは４とされ、また、状態ａと状態ａ、
ｂ、ｃ及びｄとの間の遷移数は、夫々、０，２，２及び
０とされる なお、遷移数の計Ｓｉは、実際は、状態配置決定部３が
状態配置の決定を行う際にその前処理として求められ
る。

状態数カウント部５は、メモリ部６の状態遷移表からそ
れに含まれる（表示すべき）状態の数を求める。

表示位置決定部４は、表示画面上において状態を表示す
べき複数（状態数の分だけ）の位置（表示位置）を、そ
の座標を指定して定める。表示位置は、状態数カウント
部５からの状態数と、表示情報部９からの表示画面の大
きさ等とに基づいて決定される。表示位置についての情
報は配置表としてメモリ部８に格納される。

状態配置決定部３は、メモリ部８の表示位置の各々に１
つの表示すべき状態を対応させることによって、各状態
の配置位置を決定する。これは、メモリ部７を参照し
て、遷移数（の大きさ）を利用して行われる。結果とし
て、メモリ部８に、表示位置の座標と状態とを対応させ
た配置表が得られる。

矢印付加部１０は、メモリ部８の配置表及びメモリ部６
の状態遷移表を参照して、各状態間に状態遷移を示す矢
印及び入力を、配置表に付加した情報を作成する。

表示制御部１１は、画面作成ツールであるグラフィック
ライブラリ１２を参照して、矢印付加部１０からの情報
に基づいて画面情報を作成し、表示装置１３に送信す
る。なお、グラフィックライブラリ１２は各表示装置１
３に対応して設けられる。

〔作用〕

第３図は本発明の作用説明図である。

第９図図示の状態遷移表がメモリ部６に格納される。こ
れに基づいて、遷移数決定部２は第２図図示の遷移数の
表を作成し、メモリ部７に格納する。一方、状態数カウ
ント部５は状態数「４」であることを知る。

次に、表示位置決定部４は、第３図(A)図示の如く、表
示画面130上における状態の表示位置131を決定する。即
ち、まず、表示情報部９から表示画面130の大きさ等に
ついての情報が与えられる。これに基づいて、半径Ｒ，
中心Ｏの円が定められ、この１つの円の円周上に４つの
表示領域131が位置するようにされる。次に、状態数で
円周を等分（この場合は４等分）し、各表示領域131間
の距離を等しくする。（状態数ｎの時、半径Ｒの円に内
接するｎ角形の各頂点が表示位置とされる。）表示位置
についての情報（座標）はメモリ部８に格納される。

次に、状態配置決定部３は、第３図(B)ないし(D)に示す
如き配置処理を行う。

まず、状態配置決定部３はメモリ部７の遷移数の表を参
照し、各状態について遷移数の計Ｓｉを求め、これが最
大の状態を１つ選ぶ。なお、この場合は全て「４」であ
るが、状態ａを選んだものとする。そして、状態ａを４
つの表示位置131の任意（又は所定）の１つに対応づけ
るようにメモリ部８に格納する。これを画面として示せ
ば、第３図(B)の如くなる。

次に、再び前記遷移数の表を参照して、残った状態ｂ，
ｃ及びｄの中から、状態ａとの間で遷移数が最大の状態
及び次に大きい状態を各々１つ選ぶ。なお、この場合は
状態ａとｂとの間の遷移数及び状態ａとｃとの間の遷移
数が共に「２」であるが、状態ｂを最大の状態、状態ｃ
を次に大きい状態として選んだものとする。そして、状
態ｂ及びｃを状態ａの時計回り方向及び反時計回り方向
（逆でもよい）の隣接する表示位置131に対応づける。
前述と同様に、この対応関係は、メモリ部８に格納さ
れ、画面としては第３図(C)の如くなる。

次に、残った状態ｄと表示位置131とが第３図(D)に示す
如く対応づけられ、状態配置が終了する。

なお、状態数が多い場合は、次のように処理が続行され
る。即ち、まず、状態ｂとの間の遷移数が最大の状態
（状態ｂ′とする）が１つ選ばれ、これが状態ｂの隣接
の表示位置に対応させられる。この選択において、すで
に１度選ばれた状態ａ及びｃは対象から除かれる（以下
同じ）。次に、同様にして、状態ｃの隣接の表示位置に
状態ｃ′が対応させられる。この後、状態ｂ′側、状態
ｃ′側の順で同様の配置処理を行い、状態が無くなるま
でくり返す。

この後、矢印付加部１０がメモリ部６の状態遷移表を参
照して矢印及び入力を付加する。そして、これを画面に
表示すると第３図(E)の如くなる。

以上の処理によれば、各状態間で遷移数の大きい（矢印
が多い）ものが隣接するようにされる。これにより、第
３図(E)と第１０図との比較から理解されるように、状
態遷移を示す矢印の交わりを少なくして状態遷移を見易
くできる。特に、状態数が少ない場合は、矢印の交わり
ほ無くすことができる。また、これらのための状態の配
置の決定を自動的に行うことができ、利用者の負担が無
い。

なお、第３図中の点線、半径Ｒを示す矢印、文字Ｒ及び
Ｏは表示画面130上には表示されない。

〔実施例〕

本発明の実施例として第１図図示のデータ処理装置につ
いて詳細に説明する。

まず、遷移数の決定について、第４図及び第５図を用い
て説明する。

第４図は実施例説明図であり、メモリ部６、遷移数決定
部２及びメモリ部７の構成を示している。第４図におい
て、１４及び１６はアドレス制御部、１５及び１７は読
出し制御部、１８は書込み制御部、１９は加算器、２０
ないし２８はレジスタである。

第５図はメモリ部説明図であり、特に、第５図(A)はメ
モリ部６に格納された状態遷移表の一例を示し、第５図
(B)はメモリ部７に格納された遷移数の表の一例を示し
ている。なお、状態遷移表は、第５図(A)図示の如く、
１ないしｎ（ｎ個）の状態数とa₁ないしa_k（ｋ個）の入
力（入力アルファベット）とからなるものとする。遷移
数決定部２は、メモリ部６の状態遷移表から状態数ｎ、
入力数ｋを知り、これをレジスタ２０及び２１に格納す
る。

アドレス制御部１４は、メモリ部７に遷移数の表とし
て、状態数ｎに基づいて、状態１ないしｎをＸ及びＹア
ドレスとし各アドレスに遷移数（の初期値）として
「０」を書込んだものを作成する。また、アドレス制御
部１４は、メモリ部６から状態遷移表の内容を読出すた
めの２次元（Ｘ及びＹ）アドレスを発生する。このアド
レス発生はＸ及びＹ方向に順にインクリメントされ、状
態遷移表の全内容を読出すようにされる。

今、アドレス制御部１４がＸアドレスとして入力アルフ
ァベットa_i，Ｙアドレスとして状態ｊ（以下このような
アドレスを（Ｘ，Ｙ）＝（a_i，ｊ）と記述する）を発生
したとする。アドレスa_i及びｊはレジスタ２２及び２３
に格納される。読出し制御部１５は、レジスタ２２及び
２３の内容に従ってメモリ部６の状態遷移表をアクセス
して、アドレス（a_i，ｊ）の内容を読出す。この内容
は、状態ｊに入力アルファベットa_iかせ入力された時に
次に遷移すべき状態を示すものであり、この場合は状態
ｍとされている。読出された内容（状態ｍ）はレジスタ
２４に格納される。

次に、アドレス制御部１６は、レジスタ２３及び２４の
内容を用いてメモリ部７をアクセスする。

メモリ部６の状態遷移表のアクセスに用いた状態(j)と
読出された状態(m)とが、メモリ部７の２次元アドレス
発生のために用いられる。アドレス制御部１６は、２つ
の状態から（Ｘ，Ｙ）＝（ｍ，ｊ）及び（ｍ，ｊ）の２
つのアドレスを順次発生し、レジスタ２５及び２６に格
納する。

即ち、まず、レジスタ２５及び２６に、Ｘアドレスとし
ての状態ｍ及びＹアドレスとしての状態ｊが格納され
る。読出し制御部１７は、これに基づいてメモリ部７の
遷移数の表をアクセスして、アドレス（ｍ，ｊ）の内容
Ｓ_ｏを読出す。この内容Ｓ_ｏは、状態ｍとｊとの間にお
ける遷移数を示すものであり、この場合は初期値「０」
とされている。読出された内容Ｓ_ｏはレジスタ２７に格
納される。これを受けて。加算器１９はレジスタ２７の
内容（Ｓ_ｏ）にレジスタ２８の内容「１」を加える。こ
の加算結果（Ｓ_ｏ＋１）を受けた書込み制御部１８は、
レジスタ２５及び２６の内容である元のアドレス（ｍ，
ｊ）に加算結果を書込む。

次に、レジスタ２５及び２６に、Ｘアドレスとしての状
態ｊ及びＹアドレスとしての状態ｍが格納される。この
後、前述と同様にしてアドレス（ｊ，ｍ）の内容Ｓ
_１（この場合は初期値「０」）が読出され、Ｓ_１＋１と
されて同一アドレスに再書込みされる。

以上をくり返すことにより、遷移数の表が作成される。

次に、表示位置の決定について、第６図及び第７図を用
いて説明する。

第６図は表示位置決定フローを示す。

第７図は表示位置説明図であり、特に、第７図(A)は画
面上の表示位置について示し、第７図(B)はメモリ部８
に格納された配置表の一例を示している。

主として表示画面130の大きさに基づいて、画面上の
円の中心Ｏの座標(C_x,C_y)及び半径Ｒが決定される。こ
の時、Ｘ，Ｙ座標は、例えば、第７図(A)図示の如く定
められる。

次に、状態数ｎに応じて円周上に等間隔に状態を表示
するために、Ｒａｄ＝２π／ｎを求め、ｉ＝０とする。

Ｒａｄ及びｉを用いて、所定の式に従い、Ｓ及びＣを
求める。

円の中心座標(C_x,C_y)、半径Ｒ、前記Ｓ及びＣを用い
て、所定の式に従い、前記円の円周上にある１点の座標
(X_i+1,Y_i+1)を求める。

例えば、ｉ＝０の時、ｓ＝０，ｃ＝１であるから(X₁,
Y₁)＝(C_x,C_y-R)とされる。

次に、ｉ＝ｉ＋１とした後、ｉがｎより小さい間上記
処理及びをくり返し行い、ｉがｎ以上となった時に
処理を終了する。これにより、前記円の円周上に等間隔
で配置されたｎ個の点の座標(X₁,Y₁)ないし(X_n,Y_n)が求
まる。

表示位置決定部４は、上記処理を行うと共に、処理で
求めた座標を、順次、メモリ部８に格納する。そして、
各座標に対応する状態を格納するための領域を設け、第
７図(B)図示の配置表を作成する。

この実施例において、第７図(A)図示の如く、ｎ個の座
標(X₁,Y₁)ないし(X_n,Y_n)は、その各々を中心とした小円
を描くために用いられる。この小円は、第３図図示の状
態を画面上に示すための領域131とされる。この小円の
大きさは、例えば、表示情報部９により決定される。

次に、状態配置の決定について、第８図を用いて説明す
る。

第８図は状態配置決定フローを示す 状態配置決定部３は、ｎ個の状態の各々に応じてｎ個
のフラグ領域を確保し、全フラグを「０」（クリア）と
する。フラグが「０」の時、そのフラグに対応する状態
について未だ配置が決定されていないこと、即ち、メモ
リ部８の配置表に座標と対応されて入力されていないこ
とを示す。

状態配置決定部３は、メモリ部７の遷移数の表を用い
て、各状態についての遷移数の計Ｓｉを求め、適当な記
憶領域に（例えば第２図図示の如くしてメモリ部７内
に）保持する。

この後、状態配置決定部３は、フラグ及び遷移数の計Ｓ
ｉ等を用いてメモリ部７の遷移数の表（第５図(B)）を
アクセスし、以下の処理を行う。

対応するフラグが「０」の状態（初期であるから全て
の状態）の中から、遷移数の計Ｓｉが最大の状態（例え
ば状態ａとする）を選択する。

状態ａを初期位置(X₁,Y₁)に割り当てる。即ち、第７
図(B)の配置表に、座標(X₁,Y₁)と関連づけられて状態ａ
が入力される。これに応じて、状態ａに対応するフラグ
ａが「１」とされる。フラグ「１」の時、対応する状態
の配置が終了したことを示す。

対応するフラグが「０」の状態の中から、状態ａとの
間の遷移数が最大及び二番目に大きい状態を選択する。
このために、メモリ部７の遷移数の表を、アドレス
（Ｘ，Ｙ）＝(Y_j,a)（但し、ｊ＝１〜ｎ）としてアクセ
スする。即ち、Ｙアドレスを状態ａに固定し、Ｘアドレ
スを状態１から状態ｎまで順に変化させてアクセスし、
その内容（即ち状態ａと各状態との間の遷移数）を読出
す。そして、最大及び二番目に大きい遷移数に対応する
状態（例えば状態ｂ及び状態ｃとする）を各々選択す
る。

状態ｂ及びｃを、各々、状態ａの時計回り隣の位置(X
₂,Y₂)及び反時計回り隣の位置(X_n,Y_n)に割り当てる。こ
れに応じて、フラグｂ及びフラグｃが「１」とされる。

全フラグが「１」か否かが判断される。全フラグが
「１」の時、全ての状態の割り当てが終了したとして処
理が終了する。

対応するフラグが「０」の状態の中から、状態ｂとの
間の遷移数が最大の状態を選択する。このために、前述
と同様に、メモリ部７の遷移数の表を、アドレス（Ｘ，
Ｙ）＝(X_j,b)（但し、ｊ＝１〜ｎ）としてアクセスし、
その内容を読出す。そして、最大の遷移数に対応する状
態（例えば状態ｂ′とする）を選択する。

状態ｂが状態ａ以外の状態との間に遷移関係を持たな
い場合、遷移数が０である複数の状態の中から任意の１
つが（状態ｂ′として）選ばれることになる。このよう
な場合、状態ｂ′を状態ｂの隣接位置に割り当てること
は禁止される。メモリ部７の遷移数の表を、アドレス
（Ｘ，Ｙ）＝（ｂ′，ｂ）としてアクセスし、その内容
（即ち状態ｂとｂ′との間の遷移数）を読出す。読出し
た内容が０の時、上記の理由により以下の処理 を省略して状態ｂ′の割り当てを禁止し、処理 も少なくとも１つの状態(b′)が未割り当てで残るから
省略される。

読出した内容が０でない時、状態ｂ′を状態ｂの時計回
り隣の位置(X₃,Y₃)に割り当てる。フラグｂ′が「１」
とされる。

処理と同様の処理が行われる。

状態ｃについて処理と同様の処理を行い、状態ｃとの
間で最大の遷移数を持つ状態（例えば状態ｃ′とする）
を選択する。

状態ｃとｃ′との関係について処理と同様の処理を同
様の理由で行い、状態ｃとｃ′との間の遷移数の値を知
る。

この値が０の時、以下の処理が省略される。

前記値が０でない時、状態ｃ′を状態ｃの反時計回り隣
の位置(X_n-1,Y_n-1)に割り当てる。フラグｃ′が「１」
とされる。

状態ｂ′及びｃ′について処理ないしをくり返し行
うため、処理対象をｂ′及びｃ′とする。

納しておいて再度参照する）。

処理及び により読出した遷移数のいずれかが０でない時、状態
ｂ′又はｃ′のいずれかが割り当てられているから、当
該状態について処理ないし又はないしが行われ
る。

処理及び により読出した遷移数が共に０である時、状態ｂ及びｃ
とは遷移関係のない状態について処理以下がくり返し
行われる。

処理と同様の処理を行う。

フラグ「０」の状態が残っていると、その状態について
処理以下がくり返される。状態ｂ′及びｃ′も対象と
して残される。

以上により、状態配置の決定が終了する。

なお、処理から理解されるように、未配置の状態と最
新に配置された２つの状態との間において、何ら遷移関
係が存在しない場合、未配置の状態の中から遷移数の計
Ｓｉが最大のものが選択される。そして、この状態は、
残った配置位置の両端又は中央に配置される。この後、
処理以下が行われる。

矢印付加部１０は、各状態間に矢印を付加し、これに入
力を付加して、状態遷移図を完成する。

なお、ある状態がある入力により自己に戻る矢印を有す
る場合、この矢印による遷移数を遷移数の計Ｓｉから求
める時に算入しないようにしてもよい。当該矢印は半径
Ｒの円の外側に表示される。

〔発明の効果〕

以上説明したように、本発明によれば、状態遷移表（又
は関数）に基づいて各状態間の関係をグラフ化して示す
状態遷移図表示処理方式において、遷移数を求めてこれ
を利用することによって、遷移数の大きい関係にある状
態を隣接させ小さい関係にある状態を隣接させないよう
にして、状態遷移を示す矢印の交わりを少なくして見易
くした状態遷移図を得ることができ、プログラムや順序
回路の設計、解析の効率を向上することができる。

【図面の簡単な説明】

第１図は本発明の原理構成図、 第２図は遷移数の表を示す図、 第３図は本発明の作用説明図、 第４図は実施例説明図、 第５図はメモリ部説明図、 第６図は表示位置決定フローを示す図、 第７図は表示位置説明図、 第８図は配置位置決定フローを示す図、 第９図は状態遷移表を示す図、 第１０図は従来技術説明図、 １は中央処理装置及びメモリを含む処理装置、２は遷移
数決定部、３は状態配置決定部、４は表示位置決定部、
５は状態数カウント部、６ないし８はメモリ部、９は表
示情報部、１０は矢印付加部、１１は表示制御部、１２
はグラフィックライブラリ、１３は表示装置。

Claims (1)

【特許請求の範囲】
1. 【請求項１】複数の状態の各々について当該状態と他の
   状態との間の相互の遷移数を求めてメモリに格納する遷
   移数決定処理部（２）と、 前記状態の数に応じて円周上の表示位置を決定する表示
   位置決定処理部（４）と、 前記状態を前記表示位置に対応させてその配置位置を決
   定する状態配置決定処理部（３）とを備え、 前記状態配置決定処理部（３）はメモリ上に各状態に対
   応して当該状態の配置位置の決定の有無を示すフラグ領
   域を確保し、メモリに格納された各領域の前記遷移数の
   中で最大の遷移数を有する状態を第１番目に選択して初
   期表示位置に割り当てるとともに当該選択された状態の
   フラグを決定済状態に変更し、しかる後、フラグが配置
   未決定を示している非選択の残りの状態の中で前記決定
   済状態と遷移関係を有し、かつ最大およびその次の大き
   さの遷移数を有する２つの状態を選択し、先に選択され
   た状態の表示位置の両側の隣接する表示位置に当該２つ
   の状態をそれぞれ割り当てるとともに当該２つの選択さ
   れた状態のフラグを決定済状態に変更し、以降は残りの
   表示位置未決定の状態の中で直前に決定された状態と遷
   移関係を有し、かつ遷移数の最も大きい状態を選択して
   順次、状態表示未決定の表示位置方向に表示位置を決定
   するよう処理する ことを特徴とする状態遷移図表示処理方式。