JPH01124060A - ネツトワーク図作成装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は、ネットワーク図作成装置に係り、特に、見易
さを確保しながら作業効率を大幅に高めたネットワーク
図自動しイアウト作成装置に関するものである。

〔従来の技術〕

ネットワーク図作成作業においては、従来、次の３つの
方式が用いられてきた。

第１の方式は、レイアラ１へに必要なすべての情報をオ
ペレータ（作業員）に間合せ、入力されたレイアウトの
情報に基づきレイアウトを実行するＣＡＤシステムのよ
うな手法である。

第２の方式は、線以外の部分をオペレータに間合せ、入
力されたレイアウト情報に基づき、それらのレイアウト
を実行し、レイアラ１〜が終了した時点で線により結合
する手法である。第２図と第３図とを参照して、第２の
方式を説明する。第２図において、Ａ−Ｊはレイアウト
すべきノード、ａ〜０はノード間を結合する線である。

四角で囲んだ数字はノード間の結び付きの強さを表す。

この数字が大きいほど結び伺きが強い。具体的な操作手
順を第３図に示す。Ａ段階で、まず、レイアラ１へを行
うシステムを起動し、レイアウトするスペースを表示す
る。Ｂ段階で、表示したスペース上に、ノードＡ〜１等
を設定していく。この時、システムは各ノードとそれを
表示すべき位置とを併せて記憶する。Ｃ段階で、システ
ムは各ノード間に必要な線を自動的に生成する。

第３の方式は、レイアウト上のすべての組合せを調べ、
例えば面積が最小となるレイアウトを実行するＬＳＩ−
ＣＡＤのような手法である。

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

上記第１および第２の方式においては、ネットワークの
ノード間の関係の外に、ノードのレイアウト上の位置情
報についても記憶する必要がある。

このため、ノードの追加、削除が発生した場合、レイア
ウトと位置情報の記憶とを再度やり直す必要がある。ま
た、レイアウトするスペースが変更になる場合や、表示
面積または表示手段が異なる機器に同一の情報を出力す
るためそれぞれに対して最適なレイアウトを実行する必
要が発生した場合は、それぞれレイアウトをやり直すだ
けでなく、それらレイアウトを機器の数だけすべて記憶
しておかなければならない。

一方、第３の方式では、レイアウト上で多数回の試行錯
誤がなされ、最終レイアウトを決定するまでに、多くの
時間を要する。したがって、端末画面において、対話形
式でデータを変更しレイアウト操作を実行しようとして
も、応答が遅く使用に耐えない。また、各ノードのつな
がりの強さ等を考慮しないで、機械的にレイアウトする
ことがら、本来は意味的にまとめてレイアウトしたいノ
ードが離れてレイアウトされることもあり、図の見易さ
が損なわれてしまう欠点があった。

本発明の目的は、ネットワークの意味的な情報のみを用
いて、試行錯誤を実質上伴わず、意味的なつながりを持
つノードを近くにレイアラ１〜可能なネットワーク図作
成装置を提供することである。

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

上記目的は、ネットワーク状に定義されたノードの関係
を木構造の関係として一旦とらえ、ノード全体をレイア
ウトし、それらノードを線で結合することにより達成さ
れる。

すなわち、本発明は、上記目的を達成するために、ネッ
トワーク状の関連を持つデータを入力する装置と、それ
らデータの関連をネットワーク図としてレイアウトする
レイアラ１−装置と、レイアウドされたネットワーク図
を出力する出力装置とで構成されたネジ１〜ワー９図作
成装置において、レイアウト装置が、データのネッＩ・
ワーク状の関連を有向グラフに変換する手段と、有向グ
ラフに閉ループが存在するときにその閉ループの逆向き
有向グラフを削除する手段と、閉ループが除かれた有向
グラフの最長パスを調べる手段と、最長パスの下位ノー
ドから関連を持っノードをその最長パスに順次付は加え
有向グラフを木構造に変換する手段と、木構造の各ノー
ドをレイアラ１〜し各ノード間を線で結合する手段とを
備えたネジ１〜ワー９図作成装置を提案するものである
。

有向グラフに変換する手段には、各有効グラフの意味の
つながりの強さを記憶する手段を備え、有向グラフの最
長パスを調べる手段には、分岐ノードで前記意味のつな
がりの強い有向グラフを優先的に採用する手段を備える
ことが望ましい。

〔作用〕

ネットワークから木構造に変換するときに、ネットワー
ク状の仕様を閉ループに含まない有向グラフとしてとら
え、次に、有向グラフの最長パスを木の幹とする。この
針上に在るノードの最下位ノードと関係のあるノードか
ら順次この幹にノードを付与していく。本方式により、
ネットワークの線の矢印の方向が一定方向となる。矢印
が一定方向化すると、オペレータがネットワーク図を見
るときの見方とレイアウトの流れの方向とを一致させる
ことができる。・また、木構造の最長パス決定時に、近
くにレイアウトする必要があるノードについては、ノー
ド間の線に優先度を設定し、優先度の高いノードを優先
的に幹に採用する。

このように、ネットワークのレイアウトを木構造のレイ
アウトに帰着させたため、見易さを確保したまま、高速
レイアウトが可能となる。すなわち、従来の方法では、
ノード数が増加するにつれて、レイアウトするための計
算量が指数関数的に激増するが、本発明では、ノード数
に比例した計算量で済むことになる。

また、最長パスに基づき木構造化するので、ノード間の
線を自然な形にできる。

第２図の例について、第４図から第６図を参照し、本発
明における有向グラフから木構造への変換の概要を説明
する。

ここでは、各ノード間の意味的なつながり情報とともに
ノードが入力され、有向グラフとして仮の矢印付けが終
了し、第２図が得られているものとする。

まず、第２図で閉ループとなっているｌ）　−＋　ｇ→
Ｅ→ｈ−）Ｄの線りをカットし、閉ループの無い有向グ
ラフとする。カット後の有向グラフを第４図に示す。

次に、第４図の有向グラフにおいて、最長パスを調べる
。最長パスは、Ａ→Ｂ→［）　−＞　Ｅ　−＞　Ｑであ
る。ただし、Ｄで優先度（ｆが１でｇが０）を評価した
場合、Ａ→Ｂ−＋Ｄ→Ｇとなる。これを木構造の幹とす
る。木構造の幹を第５図に示す。

そこで、木構造の葉からルートの順に、幹に付けるノー
ドを調べる。第５図で、Ａ　−）　Ｂ　−＋　Ｄ→Ｅ→
Ｇを幹にした場合は、Ｃ，Ｆ、Ｊ、Ｈがそれぞれ該当ノ
ードとなる。それを第６図（ａ）に示す。

また、Ａ→Ｂ−＋Ｄ−＋Ｇとした場合は、Ｃ，Ｅ、Ｊ。

Ｈがそれぞれ該当ノードとなる。それを第６図（ｂ）に
示す。

さらに、ノードがすべて幹とつながるまで、幹に付ける
ノードを調べ続ける。

〔実施例〕

次に、本発明によるネットワーク図作成装置の一実施例
の構成を第１図により説明する。

本装置は、入力装置１０とレイアウト装置１２と出力装
置２８とからなる。レイアウト装置１２は、入力装置ド
ライバ１４と演、算部１６と出力装置ドライバ１８とワ
ーキングメモリ２６とを備えている。演算部１６は仕様
入力部２０とレイアウト部２２とを含み、ワーキングメ
モリ２６は仕様記憶テーブル２４を含んでいる。

入力装置ドライバ１４は、入力装置１０からのデータを
演算部１６が理解可能なデータ形式に変換する。一方、
出力装置ドライバ１８は、出力装置（ＣＲＴ表示装置や
ＸＹプロッタ等）２８の動作に好適な信号形式で、レイ
アウト図等を出力する。

なお、入力装置１０側の機器と出力装置２８側の機器と
は、一つのＣＲＴ表示装置やキーボード等を共用しても
良く、入力データと出力図形とをマルチウィンド形式で
表示することも自由である。

入力装置１０から入力されたレイアウトすべき対象に関
するデータは、入力装置ドライバ１４と仕様入力部２０
とを介して、仕様記憶テーブル２４に格納される。レイ
アウト部２２はそのデータを用いて、レイアウト図を演
算し、出力装置ドライバ１８を介して、結果を出力装置
２８に出力する。

仕様記憶テーブル２４の一例を第７図に示す。

この仕様記憶テーブル２４は、いわゆる画像メモリでは
なく、表形式である。仕様記憶テーブル２４は、作成す
べきネットワークのノードを縦軸と横軸のそれぞれに記
憶し、これらノード間にレイアウト線が在ることを表の
交点にフラグ１を立てて表す。すなわち、縦軸の始点ノ
ード３０１（例えば５点）から終点ノード（例えばＥ点
）の方向に線が存在することを交点３０３に１を立てて
表し、無い場合は「−」を記憶する。また、線が存在す
る場合は、線の優先度３０４を整数１゜Ｏ等で記憶する
。この数が大きいほど優先度が高い。例えば、Ｄ→Ｇが
１で、Ｄ→ＥがＯであるから、Ｄ−＋Ｇの優先度が高い
。

レイアウト部２２は、第７図の仕様記憶テーブル２４に
基づき、第８図のレイアウトテーブルを用い、第９図の
アルゴリズムにより動作する。

第８図は、第２図や第４図等のレイアウトを表形式で表
現したレイアウトテーブルである。レイアウトテーブル
は、ネットワークを構成するノードを縦軸及び横軸に持
つ。縦軸と横軸の交点には、各線の先にいくつのノード
が存在するかを記憶するノード数エリア４０１と、木構
造の幹として用いた線を区別する区分フラグ４０２とが
記憶される。例えば、ノードＡからノードＢ方向を見る
と、Ｂ、Ｄ、Ｅ、Ｆの４個のノードが在るから、始点ノ
ードＡと終点ノードＢとの交点にノード数エリアに記憶
する数は４となる。同様にＡからＪ方向では、Ｊ、Ｅ、
Ｆの３となる。ただし、ＥからＤの逆向き有向グラフで
削除された部分には、０を記憶する。区分フラグ４０２
を、１の始点ノードＡから、２のＢ、３のり、４のＥと
たどっていけば、幹となったノードが分かる。

次に、第９図のアルゴリズムを説明する。入力装置から
ネットワークを構成するノードの相互関連を示す情報を
入力した第７図の状態（関連するノードの交点にフラグ
１を立て、優先度の数値も入力した状態）を前提とする
。

ステップ１００では、ネットワークを検索し。

閉ループとなっている線に対するレイアウトテーブルの
ノード数エリアの値をＯとする。これは。

有向グラフに閉ループが存在するときに、その閉ループ
の逆向き有向グラフを削除する段階である。

ステップ１１０では、第７図に示した仕様記憶テーブル
において線が出ていない始点ノードを見つけ、そのノー
ドを終点ノードとしている線をすべて記憶する。線が出
ていない始点ノードは、Ｃ９Ｆ、Ｇ、Ｉである。したが
って、これらのノードを終点とする線が記憶される。

ステップ１２０では、第８図のレイアウトテーブルにお
いて、ステップ１１０で記憶した線と対応する部分のノ
ード数エリアの値を１とする。例えば、１３−）Ｃの交
点に１が記憶される。

ステップ１３０では、第８図レイアウトテーブルのノー
ド数エリア４０１の値がすべて決定されたかどうかを判
断する。

まだの場合は、ステップ１４０に行き、レイアウトテー
ブルにおいて、線のノード数エリアの値がすべて決定さ
れた始点ノードを記憶する。

ステップ１５０では、ステップ１４０で記憶した各始点
ノードから出る線の内のノード数エリアの最大値を記憶
する。

ステップ１６０では、ステップ１４０で記憶した始点ノ
ードを終点とする線のノード数エリアの値をステップ１
５０で記憶した値＋１とする。すなわち、より上位のノ
ードであることを記憶する。

このような手順を順次続けると、ステップ１３０でレイ
アウトテーブルのノード数エリアの値がすべて決定され
た状態に至る。

ステップ］１０からステップ１６０までが、入力データ
のネットワーク状の関連を有向グラフに変換する段階で
ある。

ステップ１７０では、線を持たない終点ノードのノード
名を記憶する。この場合は、Ａである。

ステップ１８０では、ステップ１７０のノードを始点ノ
ードとする線の内で優先度が高くノード数エリアの値が
最大のものの区分フラグを１とする。Ａ→Ｂが該当する
。

ステップ１９０では、ステップ１８０で設定したノード
名を記憶し、ノード数エリアの値がすべて定義されてい
ないノードまでステップ１８０を繰り返し行う（区分フ
ラグはカウントアツプしていく）。

ステップ１７０からステップ１９０までは、木構造の幹
を作成する段階である。ここでは、Ａ→Ｂ−＋Ｄ→Ｅが
幹として作成されている。

ステップ２００では、終点ノードの内で一つも区分フラ
グが設定されていないものを探す。すなわち、最下位ノ
ードの方から木構造化する。

ステップ２１０では、ステップ２００で見つけた終点ノ
ードの線に対応する始点ノートをすべて調べる。始点ノ
ードの区分フラグが定義されているものが一つの場合は
、その始点ノードを記憶する。始点ノードの区分フラグ
が定義されているものが二つ以上の場合は、区分フラグ
の数値が小さいものの始点ノードを記憶する。木構造で
は、一つのノードから複数の線は出ていけるが、複数の
線は入れないからである。

ステップ２２０では、ステップ２１０で記憶した始点ノ
ードに対応する線のステップ２００で探した終点ノード
の区分フラグの値をステップ２］０の区分フラグの値＋
１に設定する。すなわち、階層が下がるにつれて区分フ
ラグの値を増やしていき、有向グラフを木構造に変換す
る。

ステップ２００からステップ２２０までは、最長パスに
下位ノードから関連を持つノードを最長パスに順次付は
加え有向グラフを木構造に変換する段階である。

ステップ２３０では、レイアウトテーブルに基づきノー
ドをレイアウトする。

ステップ２４０では、レイアウトテーブルに基づき線を
引く。

こうして、レイアウト図が完成する。

レイアウト図のデータは、出力装置に送られ、表示され
る。

〔発明の効果〕

本発明によれば、見易さを確保したままネットワーク図
を自動レイアウトすることが可能となるので、例えばソ
フトウェア仕様のように意味的な関係しか定義されてい
ないものでも、ネットワーク図として出力でき、従来の
画像情報として入力し管理し修正する方式と比較して、
作業効率が大幅に改善される。

【図面の簡単な説明】

第１図は本発明によるネットワーク図作成装置の一実施
例の構成を示すブロック図、第２図はレイアウトすべき
情報の一例を有向グラフ形式で示す図、第３図は従来の
レイアウト手順の一例を示す図、第４図は有向グラフの
一例を示す図、第５図は木構造の幹を示す図、第６図は
葉から幹に付けるノードを調べる状態を示す図、第７図
は仕様記憶テーブルの一例を示す図、第８図はレイアウ
トテーブルを示す図、第９図は本発明レイアラ１−装置
のアルゴリズムを示す図である。 １０・・・入力装置、１２・・・レイアウト装置、１６
・・演算部、２０・・・仕様入力部、２２・・・レイア
ウト部、２４・・・仕様記憶テーブル、２６・・・ワー
キング、メモリ、２８・・・出力装置、３０１・・・始
点ノード、３０２・・・終点ノード、３０３・・・交点
、３０４・・優先度、４０１・・・ノード数エリア、４
０２・・・区分フラグ。

Claims (1)

1. 【特許請求の範囲】 １、ネットワーク状の関連を持つデータを入力する装置
   と、前記データの関連をネットワーク図としてレイアウ
   トするレイアウト装置と、レイアウトされたネットワー
   ク図を出力する出力装置とからなるネットワーク図作成
   装置において、前記レイアウト装置が、 前記データのネットワーク状の関連を有向グラフに変換
   する手段と、 前記有向グラフに閉ループが存在するときに当該閉ルー
   プの逆向き有向グラフを削除する手段と、 閉ループが除かれた有向グラフの最長パスを調べる手段
   と、 前記最長パスの下位ノードから関連を持つノードを前記
   最長パスに順次付け加え前記有向グラフを木構造に変換
   する手段と、 前記木構造の各ノードをレイアウトし各ノード間を線で
   結合する手段と を備えたことを特徴とするネットワーク図作成装置。 ２、特許請求の範囲第１項において、 前記有向グラフに変換する手段が、各有効グラフの意味
   のつながりの強さを記憶する手段を含み、 前記有向グラフの最長パスを調べる手段が、分岐ノード
   で前記意味のつながりの強い有向グラフを優先的に採用
   する手段を含むことを特徴とするネットワーク図作成装
   置。