JPH11203332A

JPH11203332A - 経路圧縮方式

Info

Publication number: JPH11203332A
Application number: JP10021386A
Authority: JP
Inventors: Takumi Hasegawa; 拓己長谷川
Original assignee: NEC Corp
Current assignee: NEC Corp
Priority date: 1998-01-19
Filing date: 1998-01-19
Publication date: 1999-07-30
Also published as: US6275238B1

Abstract

(57)【要約】【課題】グラフ情報格納手段にどのようなグラフ情報
が格納されていても、グラフ情報の十分な経路圧縮を行
うことができるようにする。【解決手段】グラフ情報格納手段１は、グラフ情報を
格納する。直線型経路圧縮手段２はグラフ情報中の直線
型経路を圧縮し、流入型経路圧縮手段３はグラフ情報中
の流入型経路を圧縮し、分岐型経路圧縮手段４はグラフ
情報中の分岐型経路を圧縮し、多経路型経路圧縮手段５
はグラフ情報中の多経路型経路を圧縮し、クロス型経路
圧縮手段６はグラフ情報中のクロス型経路を圧縮する。
圧縮制御手段７は、グラフ情報格納手段１に格納されて
いるグラフ情報に、直線型経路圧縮手段２，流入型経路
圧縮手段３，分岐型経路圧縮手段４，多経路型経路圧縮
手段５およびクロス型経路圧縮手段６を総当たり的に適
用して経路を圧縮する。

Description

【発明の詳細な説明】

【０００１】本発明は経路圧縮方式に関し、特に論理回
路のようなグラフ構造を持ったデータ（以下、グラフ情
報という）に含まれる経路を圧縮する経路圧縮方式に関
する。

【０００２】

【従来の技術】従来の経路圧縮方式は、パス探索の際に
途中経路に探索の途中結果を保持する必要があり、これ
を計算機上で行った場合、メモリ容量を多く必要とする
ものであった。先行技術文献としては、「大規模回路向
けタイミング解析システムＨＥＡＲＴ（１）高速化の手
法」（情報処理学会第５回全国大会７Ｆ−６）（以下、
先行技術文献１という）がある。

【０００３】また、パス探索の際に途中経路に探索の途
中結果を保持しない経路圧縮方式も存在するが、この場
合、処理時間が多くなるものであった。先行技術文献と
しては、「遅延時間解析システム−ＮＥＬＴＡＳ２−」
（情報処理学会、設計自動化研究会資料、設計自動化１
４−３、１９８２）（以下、先行技術文献２という）が
ある。

【０００４】さらに、メモリ容量を削減する目的でデー
タの圧縮をする経路圧縮方式が存在するが、従来のこの
種の経路圧縮方式は、圧縮が十分ではないものであっ
た。先行技術文献としては、特開昭６２−２０２２６８
号公報（以下、先行技術文献３という）がある。

【０００５】

【発明が解決しようとする課題】上述した従来の経路圧
縮方式では、先行技術文献１に開示された技術の場合、
パス探索の際に途中経路に探索の途中結果を保持する必
要があり、これを計算機上で行った場合、メモリ容量を
多く必要とするという問題点があった。

【０００６】また、先行技術文献２に開示され技術の場
合、処理時間が多くなるという問題点があった。

【０００７】さらに、先行技術文献３に開示された技術
の場合、メモリ容量を削減する目的でデータを圧縮して
も、圧縮が十分ではないという問題点があった。

【０００８】本発明の目的は、グラフ情報格納手段にど
のようなグラフ情報が格納されていても、グラフ情報の
十分な経路圧縮を行うことができる経路圧縮方式を提供
することにある。

【０００９】

【課題を解決するための手段】本発明の経路圧縮方式
は、グラフ情報を格納するグラフ情報格納手段（図１の
１）と、グラフ情報中の直線型経路を圧縮する直線型経
路圧縮手段（図１の２）と、グラフ情報中の流入型経路
を圧縮する流入型経路圧縮手段（図１の３）と、グラフ
情報中の分岐型経路を圧縮する分岐型経路圧縮手段（図
１の４）と、グラフ情報中の多経路型経路を圧縮する多
経路型経路圧縮手段（図１の５）と、グラフ情報中のク
ロス型経路を圧縮するクロス型経路圧縮手段（図１の
６）と、前記グラフ情報格納手段に格納されているグラ
フ情報に、前記直線型経路圧縮手段，前記流入型経路圧
縮手段，前記分岐型経路圧縮手段，前記多経路型経路圧
縮手段および前記クロス型経路圧縮手段を総当たり的に
適用して経路を圧縮する圧縮制御手段（図１の７）とを
有することを特徴とする。

【００１０】また、本発明の経路圧縮方式は、グラフ情
報を格納するグラフ情報格納手段（図１の１）と、グラ
フ情報中の直線型経路を圧縮する直線型経路圧縮手段
（図１の２）と、グラフ情報中の流入型経路を圧縮する
流入型経路圧縮手段（図１の３）と、グラフ情報中の分
岐型経路を圧縮する分岐型経路圧縮手段（図１の４）
と、グラフ情報中の多経路型経路を圧縮する多経路型経
路圧縮手段（図１の５）と、グラフ情報中のクロス型経
路を圧縮するクロス型経路圧縮手段（図１の６）と、前
記グラフ情報格納手段に格納されているグラフ情報に基
づいて、直線型経路，流入型経路，分岐型経路，多経路
型経路およびクロス型経路を判別して、前記直線型経路
圧縮手段，前記流入型経路圧縮手段，前記分岐型経路圧
縮手段，前記多経路型経路圧縮手段および前記クロス型
経路圧縮手段を選択的に適用して経路を圧縮する圧縮制
御手段（図１の７）とを有することを特徴とする。

【００１１】一方、本発明の記録媒体は、コンピュータ
を、グラフ情報を格納するグラフ情報格納手段（図１の
１），グラフ情報中の直線型経路を圧縮する直線型経路
圧縮手段（図１の２），グラフ情報中の流入型経路を圧
縮する流入型経路圧縮手段（図１の３），グラフ情報中
の分岐型経路を圧縮する分岐型経路圧縮手段（図１の
４），グラフ情報中の多経路型経路を圧縮する多経路型
経路圧縮手段（図１の５），グラフ情報中のクロス型経
路を圧縮するクロス型経路圧縮手段（図１の６），なら
びに前記グラフ情報格納手段に格納されているグラフ情
報に、前記直線型経路圧縮手段，前記流入型経路圧縮手
段，前記分岐型経路圧縮手段，前記多経路型経路圧縮手
段および前記クロス型経路圧縮手段を総当たり的に適用
して経路を圧縮する圧縮制御手段（図１の７）として機
能させるためのプログラムを記録する。

【００１２】また、本発明の記録媒体は、コンピュータ
を、グラフ情報を格納するグラフ情報格納手段（図１の
１），グラフ情報中の直線型経路を圧縮する直線型経路
圧縮手段（図１の２），グラフ情報中の流入型経路を圧
縮する流入型経路圧縮手段（図１の３），グラフ情報中
の分岐型経路を圧縮する分岐型経路圧縮手段（図１の
４），グラフ情報中の多経路型経路を圧縮する多経路型
経路圧縮手段（図１の５），グラフ情報中のクロス型経
路を圧縮するクロス型経路圧縮手段（図１の６），なら
びに前記グラフ情報格納手段に格納されているグラフ情
報に基づいて、直線型経路，流入型経路，分岐型経路，
多経路型経路およびクロス型経路を判別して、前記直線
型経路圧縮手段，前記流入型経路圧縮手段，前記分岐型
経路圧縮手段，前記多経路型経路圧縮手段および前記ク
ロス型経路圧縮手段を選択的に適用して経路を圧縮する
圧縮制御手段（図１の７）として機能させるためのプロ
グラムを記録する。

【００１３】

【発明の実施の形態】以下、本発明の実施の形態につい
て図面を参照して詳細に説明する。

【００１４】図１は、本発明の第１の実施の形態に係る
経路圧縮方式の構成を示すブロック図である。本実施の
形態に係る経路圧縮方式は、ノードおよびアークからな
るグラフ情報を格納するグラフ情報格納手段１と、直線
型経路を圧縮する直線型経路圧縮手段２と、流入型経路
を圧縮する流入型経路圧縮手段３と、分岐型経路を圧縮
する分岐型経路圧縮手段４と、多経路型経路を圧縮する
多経路型経路圧縮手段５と、クロス型経路を圧縮するク
ロス型経路圧縮手段６と、直線型経路圧縮手段２，流入
型経路圧縮手段３，分岐型経路圧縮手段４，多経路型経
路圧縮手段５およびクロス型経路圧縮手段６の適用を制
御する圧縮制御手段７とから構成されている。

【００１５】グラフ情報格納手段１は、探索の対象とな
る有向グラフ情報を格納する。例えば、図１４に示すよ
うな論理回路の場合、図１５に示すようなノードおよび
アークからなるグラフが得られる。このようなグラフの
グラフ情報は、例えば、図１６に示すように、ノードテ
ーブルおよびアークテーブルに格納される。ノードテー
ブルの各エントリは、番号，入力方向アーク，出力方向
アーク，付加遅延時間およびピン名の各フィールドから
なる。また、アークテーブルの各エントリは、番号，入
力方向ノード，出力方向ノード，同じ入力ノードのアー
ク，同じ出力ノードのアーク，遅延時間，素子の遅延時
間，素子名および配線名の各フィールドからなる。ただ
し、図１６に例示したグラフ情報は、直線型経路圧縮手
段２，流入型経路圧縮手段３，分岐型経路圧縮手段４，
多経路型経路圧縮手段５およびクロス型経路圧縮手段６
の５つの経路圧縮手段の全てが適用されるものではな
い。

【００１６】図２および図３を参照すると、圧縮制御手
段７の処理は、全経路圧縮手段圧縮効果有無判定ステッ
プＳ１０１と、１つ目ノード着目ステップＳ１０２と、
全ノード処理完了判定ステップＳ１０３と、直線型経路
圧縮手段呼出しステップＳ１０４と、次ノード着目ステ
ップＳ１０５と、１つ目ノード着目ステップＳ１０６
と、全ノード処理完了判定ステップＳ１０７と、流入型
経路圧縮手段呼出しステップＳ１０８と、次ノード着目
ステップＳ１０９と、１つ目ノード着目ステップＳ１１
０と、全ノード処理完了判定ステップＳ１１１と、分岐
型経路圧縮手段呼出しステップＳ１１２と、次ノード着
目ステップＳ１１３と、１つ目ノード着目ステップＳ１
１４と、全ノード処理完了判定ステップＳ１１５と、多
経路型経路圧縮手段呼出しステップＳ１１６と、次ノー
ド着目ステップＳ１１７と、１つ目ノード着目ステップ
Ｓ１１８と、全ノード処理完了判定ステップＳ１１９
と、クロス型経路圧縮手段呼出しステップＳ１２０と、
次ノード着目ステップＳ１２１とからなる。

【００１７】図４を参照すると、直線型経路圧縮手段２
の処理は、入力方向アーク１本かつ出力方向アーク１本
判定ステップＳ２０１と、入力方向アーク遅延時間計算
ステップＳ２０２と、入力方向アーク素子遅延時間設定
ステップＳ２０３と、入力方向ノード接続変更ステップ
Ｓ２０４と、ノードおよびアーク削除ステップＳ２０５
とからなる。

【００１８】図５を参照すると、流入型経路圧縮手段３
の処理は、入力方向アーク２本以上かつ出力方向アーク
１本判定ステップＳ３０１と、各入力方向アーク遅延時
間計算ステップＳ３０２と、各入力方向アーク素子遅延
時間設定ステップＳ３０３と、各入力方向ノード接続変
更ステップＳ３０４と、ノードおよびアーク削除ステッ
プＳ３０５とからなる。

【００１９】図６を参照すると、分岐型経路圧縮手段４
の処理は、入力方向アーク１本かつ出力方向アーク２本
以上判定ステップＳ４０１と、各出力方向アーク遅延時
間計算ステップＳ４０２と、出力方向ノード接続変更ス
テップＳ４０３と、ノード削除ステップＳ４０４とから
なる。

【００２０】図７を参照すると、多経路型経路圧縮手段
５の処理は、入力側ノードと出力側ノードとの組合せ同
一存在判定ステップＳ５０１と、アーク削除ステップＳ
５０２とからなる。

【００２１】図８を参照すると、クロス型経路圧縮手段
６の処理は、入力方向アーク２本以上かつ出力方向アー
ク２本以上判定ステップＳ６０１と、入力方向および出
力方向アーク組合せ着目ステップＳ６０２と、全アーク
組合せ処理完了判定ステップＳ６０３と、ノード接続ア
ーク作成ステップＳ６０４と、新アーク遅延時間計算ス
テップＳ６０５と、新アーク素子遅延時間設定ステップ
Ｓ６０６と、別入力方向および出力方向アーク組合せ着
目ステップＳ６０７と、アークおよびノード削除ステッ
プＳ６０８とからなる。

【００２２】次に、このように構成された第１の実施の
形態に係る経路圧縮方式の動作について説明する。

【００２３】圧縮制御手段７は、グラフ情報格納手段１
に格納されているグラフ情報に基づいて次に適用すべき
経路圧縮手段を決定し、それを用いてグラフ情報の経路
を圧縮する。

【００２４】詳しくは、圧縮制御手段７は、グラフ情報
中の着目したノードについて、直線型経路圧縮手段２，
流入型経路圧縮手段３，分岐型経路圧縮手段４，多経路
型経路圧縮手段５およびクロス型経路圧縮手段６の５つ
の経路圧縮手段のどれを適用しても圧縮効果がないかど
うかを判定し（ステップＳ１０１）、圧縮効果があれ
ば、１つ目のノードに着目して（ステップＳ１０２）、
全てのノードを処理したかどうかを判定し（ステップＳ
１０３）、全てのノードを処理していなければ、直線型
経路圧縮手段２を呼び出す（ステップＳ１０４）。

【００２５】直線型経路圧縮手段２は、着目しているノ
ードの入力方向のアークが１本であり、かつ出力方向の
アークが１本であるかどうかを判定し（ステップＳ２０
１）、そうでなければ直線型経路ではないので、直ちに
処理を終了する。ステップＳ２０１でそうであれば、直
線型経路であるので、直線型経路圧縮手段２は、入力方
向のアークの遅延時間と、着目しているノードの付加遅
延時間と、出力方向のアークの遅延時間と、入力方向の
アークの素子の遅延時間とを加算して、入力方向のアー
クの遅延時間とする（ステップＳ２０２）。次に、直線
型経路圧縮手段２は、出力方向のアークの素子の遅延時
間を入力方向のアークの素子の遅延時間に設定し（ステ
ップＳ２０３）、入力方向のノードの出力側の接続を、
着目しているノードから出力方向のアークの出力側ノー
ドに変更し（ステップＳ２０４）、着目しているノード
と出力方向のアークとを削除して（ステップＳ２０
５）、処理を終了する。この結果、図９に示されるよう
な経路の圧縮が行われる。

【００２６】図９は、直線型経路圧縮手段２による経路
の圧縮を説明する図である。ノード２２は、削除され
る。ノード２１はノード２４に、ノード２３はノード２
５になる。ノード２１からノード２２へのアークの重み
とノード２２からノード２３へのアークの重みとは加算
されて、ノード２４からノード２６へのアークの重みと
なる。

【００２７】直線型経路圧縮手段２から制御が戻ると、
圧縮制御手段７は、次のノードに着目し（ステップＳ１
０５）、ステップＳ１０３に制御を戻してステップＳ１
０３〜Ｓ１０５を繰り返す。

【００２８】ステップＳ１０３で全てのノードを処理し
たと判定されると、圧縮制御手段７は、１つ目のノード
に着目して（ステップＳ１０６）、全てのノードを処理
したかどうかを判定し（ステップＳ１０７）、全てのノ
ードを処理していなければ、流入型経路圧縮手段３を呼
び出す（ステップＳ１０８）。

【００２９】流入型経路圧縮手段３は、着目しているノ
ードの入力方向のアークが２本以上であり、かつ出力方
向のアークが１本であるかどうかを判定し（ステップＳ
３０１）、そうでなければ流入型経路ではないので、直
ちに処理を終了する。ステップＳ３０１でそうであれ
ば、流入型経路であるので、流入型経路圧縮手段３は、
それぞれの入力方向のアークの遅延時間と、着目してい
るノードの付加遅延時間と、出力方向のアークの遅延時
間と、着目している入力方向のアークの素子の遅延時間
とを加算して、それぞれの入力方向のアークの遅延時間
とする（ステップＳ３０２）。次に、流入型経路圧縮手
段３は、出力方向のアークの素子の遅延時間をそれぞれ
の入力方向のアークの素子の遅延時間に設定し（ステッ
プＳ３０３）、それぞれの入力方向のノードの出力側の
接続を、着目しているノードから出力方向のアークの出
力側ノードに変更し（ステップＳ３０４）、着目してい
るノードと出力方向のアークとを削除して（ステップＳ
３０５）、処理を終了する。この結果、図１０に示され
るような経路の圧縮が行われる。

【００３０】図１０は、流入型経路圧縮手段３による経
路の圧縮を説明する図である。ノード３３は削除され
る。ノード３１はノード３５に、ノード３２はノード３
６に、ノード３４はノード３７になる。ノード３１から
ノード３３へのアークの重みとノード３３からノード３
４へのアークの重みとは加算されて、ノード３５からノ
ード３７へのアークの重みとなる。ノード３２からノー
ド３３へのアークの重みとノード３３からノード３４へ
のアークの重みとは加算されて、ノード３６からノード
３７へのアークの重みとなる。ノード３１とノード３２
との間にあるノードについても同様である。

【００３１】流入型経路圧縮手段３から制御が戻ると、
圧縮制御手段７は、次のノードに着目し（ステップＳ１
０９）、ステップＳ１０７に制御を戻してステップＳ１
０７〜Ｓ１０９を繰り返す。

【００３２】ステップＳ１０７で全てのノードを処理し
たと判定されると、圧縮制御手段７は、１つ目のノード
に着目して（ステップＳ１１０）、全てのノードを処理
したかどうかを判定し（ステップＳ１１１）、全てのノ
ードを処理していなければ、分岐型経路圧縮手段４を呼
び出す（ステップＳ１１２）。

【００３３】分岐型経路圧縮手段４は、着目しているノ
ードの入力方向のアークが１本であり、かつ出力方向の
アークが２本以上であるかどうかを判定し（ステップＳ
４０１）、そうでなければ分岐型経路ではないので、直
ちに処理を終了する。ステップＳ４０１でそうであれ
ば、分岐型経路であるので、分岐型経路圧縮手段４は、
それぞれの出力方向のアークの遅延時間と、着目してい
るノードの付加遅延時間と、入力方向のアークの遅延時
間と、入力方向のアークの素子の遅延時間とを加算し
て、それぞれの出力方向のアークの遅延時間とする（ス
テップＳ４０２）。次に、分岐型経路圧縮手段４は、出
力方向のノードの入力側の接続を、着目しているノード
から入力方向のアークの入力側ノードに変更し（ステッ
プＳ４０３）、着目しているノードと入力方向のノード
とを削除して（ステップＳ４０４）、処理を終了する。
この結果、図１１に示されるような経路の圧縮が行われ
る。

【００３４】図１１は、分岐型経路圧縮手段４による経
路の圧縮を説明する図である。ノード４２は削除され
る。ノード４１はノード４５に、ノード４３はノード４
６に、ノード４４はノード４７になる。ノード４１から
ノード４２へのアークの重みとノード４２からノード４
３へのアークの重みは加算されて、ノード４５からノー
ド４６へのアークの重みとなる。ノード４１からノード
４２へのアークの重みとノード４２からノード４４への
アークの重みは加算されて、ノード４５からノード４７
へのアークの重みとなる。ノー４３とノード４４との間
にあるノードについても同様である。

【００３５】分岐型経路圧縮手段４から制御が戻ると、
圧縮制御手段７は、次のノードに着目し（ステップＳ１
１３）、ステップＳ１１１に制御を戻してステップＳ１
１１〜Ｓ１１３を繰り返す。

【００３６】ステップＳ１１１で全てのノードを処理し
たと判定されると、圧縮制御手段７は、１つ目のノード
に着目して（ステップＳ１１４）、全てのノードを処理
したかどうかを判定し（ステップＳ１１５）、全てのノ
ードを処理していなければ、多経路型経路圧縮手段５を
呼び出す（ステップＳ１１６）。

【００３７】多経路型経路圧縮手段５は、着目している
ノードの入力方向の全てのアークについて、入力側ノー
ドと出力側ノードとの組合せが同一のものがあるかどう
かを判定し（ステップＳ５０１）、なければ多経路型経
路ではないので、直ちに処理を終了する。ステップＳ５
０１であれば、多経路型経路であるので、多経路型経路
圧縮手段５は、対象となるアークの中で、遅延時間と素
子の遅延時間との和が最大のアークを除いた他のアーク
を全て削除して（ステップＳ５０２）、処理を終了す
る。この結果、図１２に示されるような経路の圧縮が行
われる。

【００３８】図１２は、多経路型経路圧縮手段５による
経路の圧縮を説明する図である。ノード５１はノード５
３に、ノード５２はノード５４になる。ノード５１〜ノ
ード５２へのアークの全ての重みの中で最大の重みが、
ノード５３からノード５４へのアークの重みとなる。

【００３９】多経路型経路圧縮手段５から制御が戻る
と、圧縮制御手段７は、次のノードに着目し（ステップ
Ｓ１１７）、ステップＳ１１５に制御を戻してステップ
Ｓ１１５〜Ｓ１１７を繰り返す。

【００４０】ステップＳ１１５で全てのノードを処理し
たと判定されると、圧縮制御手段７は、１つ目のノード
に着目して（ステップＳ１１８）、全てのノードを処理
したかどうかを判定し（ステップＳ１１９）、全てのノ
ードを処理していなければ、クロス型経路圧縮手段６を
呼び出す（ステップＳ１２０）。

【００４１】クロス型経路圧縮手段６は、着目している
ノードの入力方向のアークが２本以上であり、かつ出力
方向のアークが２本以上であるかどうかを判定し（ステ
ップＳ６０１）、そうでなければクロス型経路ではない
ので、直ちに処理を終了する。ステップＳ６０１でそう
であれば、クロス型経路であるので、クロス型経路圧縮
手段６は、入力方向および出力方向のアークの組合せの
１つに着目し（ステップＳ６０２）、全てのアークの組
合せを処理したかどうかを判定する（ステップＳ６０
３）。全てのアークの組合せを処理していなければ、ク
ロス型経路圧縮手段６は、入力方向のアークの入力方向
のノードと出力方向のアークの出力方向のノードとを接
続するアークを作成し（ステップＳ６０４）、出力方向
のアークの遅延時間と、着目しているノードの付加遅延
時間と、入力方向のアークの遅延時間と、入力方向のア
ークの素子の遅延時間とを加算して、新たなアークの遅
延時間とする（ステップＳ６０５）。次に、クロス型経
路圧縮手段６は、出力方向のアークの素子の遅延時間を
新たなアークの素子の遅延時間に設定し（ステップＳ６
０６）、別の入力方向および出力方向のアークの組合せ
に着目し（ステップＳ６０７）、ステップＳ６０３に制
御を戻し、ステップＳ６０３〜Ｓ６０７を繰り返す。ス
テップＳ６０３で全てのアークの組合せを処理したと判
定されると、クロス型経路圧縮手段６は、処理済みのア
ークと着目しているノードとを削除して（ステップＳ６
０８）、処理を終了する。この結果、図１３に示される
ような経路の圧縮が行われる。

【００４２】図１３は、クロス型経路圧縮手段６による
経路の圧縮を説明する図である。ノード６４は削除され
る。ノード６１はノード６８に、ノード６２はノード６
９に、ノード６３はノード７０に、ノード６５はノード
７１に、ノード６６はノード７２に、ノード６７はノー
ド７３になる。ノード６１からノード６４へのアークの
重みとノード６４からノード６５へのアークの重みとは
加算されて、ノード６８からノード７１へのアークの重
みとなる。ノード６１からノード６４へのアークの重み
とノード６４からノード６６へのアークの重みとは加算
されて、ノード６８からノード７２へのアークの重みと
なる。以下同様になり、ノード６３からノード６４への
アークの重みとノード６４から６７へのアークの重みと
は加算されて、ノード７０からノード７３へのアークの
重みとなる。

【００４３】クロス型経路圧縮手段６から制御が戻る
と、圧縮制御手段７は、次のノードに着目し（ステップ
Ｓ１２１）、ステップＳ１１９に制御を戻してステップ
Ｓ１１９〜Ｓ１２１を繰り返す。

【００４４】ステップＳ１１９で全てのノードを処理し
たと判定されると、圧縮制御手段７は、ステップＳ１０
１に制御を戻し、ステップＳ１０１〜Ｓ１２１を繰り返
す。そして、ステップＳ１０１で直線型経路圧縮手段
２，流入型経路圧縮手段３，分岐型経路圧縮手段４，多
経路型経路圧縮手段５およびクロス型経路圧縮手段６の
５つの経路圧縮手段のどれを適用しても圧縮効果がない
と判定されると、圧縮制御手段７は、処理を終了する。

【００４５】このように、グラフ情報格納手段１にどの
ようなグラフ情報が格納されていようとも、圧縮制御手
段７の制御の元に、直線型経路圧縮手段２，流入型経路
圧縮手段３，分岐型経路圧縮手段４，多経路型経路圧縮
手段５およびクロス型経路圧縮手段６を総当たり的に適
用することにより、グラフ情報格納手段１に格納された
グラフ情報は、図９〜図１３の圧縮後の形のように、始
点および終点のみのノードとその間を結ぶアークのみか
ら構成されるグラフのグラフ情報になる。

【００４６】このことは、次のような背理法により証明
される。

【００４７】仮に、本発明の経路圧縮方式を適用した後
も、グラフ情報格納手段１に格納されるグラフ情報に、
始点および終点以外のノードやその間を結ぶアークが残
るとする。この場合、始点および終点以外のノードの１
つはいずれかの始点との間のアークを持つ。始点および
終点以外のノードで、始点とのアークを持つノードを
ｎ、ノードｎとのアークを持つノードの１つをａとす
る。この場合、下記のように分類される。

【００４８】（１）ノードａからノードｎへのアーク
が１本の場合

【００４９】（１−１）ノードｎから、ノードａと反
対方向に出るアークの数が１本、ノードａと同方向に出
るアークが１本の場合

【００５０】直線型経路圧縮手段２により圧縮されるは
ずであり、本発明の経路圧縮方式を適用した後のグラフ
情報ではない。

【００５１】（１−２）ノードｎから、ノードａと反
対方向に出るアークの数が２本以上、ノードａと同方向
に出るアークが１本の場合

【００５２】分岐型経路圧縮手段４により圧縮されるは
ずであり、本発明の経路圧縮方式を適用した後のグラフ
情報ではない。

【００５３】（１−３）ノードｎから、ノードａと反
対方向に出るアークの数が１本、ノードａと同方向に出
るアークが２本以上の場合

【００５４】流入型経路圧縮手段３により圧縮されるは
ずであり、本発明の経路圧縮方式を適用した後のグラフ
情報ではない。

【００５５】（１−４）ノードｎから、ノードａと反
対方向に出るアークの数が２本以上、ノードａと同方向
に出るアークが２本以上の場合

【００５６】クロス型経路圧縮手段６により圧縮される
はずであり、本発明の経路圧縮方式を適用した後のグラ
フ情報ではない。

【００５７】（２）ノードａからノードｎへのアーク
が２本以上の場合

【００５８】多経路型経略圧縮手段６により圧縮される
はずであり、本発明の経路圧縮方式を適用した後のグラ
フ情報ではない。

【００５９】なお、上記第１の実施の形態では、直線型
経路圧縮手段２，流入型経路圧縮手段３，分岐型経路圧
縮手段４，多経路型経路圧縮手段５およびクロス型経路
圧縮手段６内でそれぞれ直線型経路，流入型経路，分岐
型経路，多経路型経路およびクロス型経路であるかどう
かを判別するようにして、圧縮制御手段７は各経路圧縮
手段を総当たり的に適用するようにしたが、圧縮制御手
段７が、直線型経路，流入型経路，分岐型経路，多経路
型経路およびクロス型経路であるかどうかを判別するよ
うにして、直線型経路圧縮手段２，流入型経路圧縮手段
３，分岐型経路圧縮手段４，多経路型経路圧縮手段５お
よびクロス型経路圧縮手段６を選択的に適用するように
してもよい。

【００６０】次に、本発明の第２の実施の形態について
図面を参照して説明する。

【００６１】図１７を参照すると、本発明の第２の実施
の形態に係る経路圧縮方式は、データ処理装置１１と、
キーボード，マウス等でなる入力装置１２と、メモリ，
磁気ディスク装置等でなる記憶装置１３と、ディスプレ
イ等でなる出力装置１４と、経路圧縮プログラムを記録
した記録媒体１５とから、その主要部が構成されてい
る。記録媒体１５は、磁気ディスク，半導体メモリ，そ
の他の記録媒体であってもよい。

【００６２】経路圧縮プログラムは、記録媒体１５から
データ処理装置１１に読み込まれ、グラフ情報格納手段
１，直線型経路圧縮手段２，流入型経路圧縮手段３，分
岐型経路圧縮手段４，多経路型経路圧縮手段５，クロス
型経路圧縮手段６および圧縮制御手段７としてデータ処
理装置１１（記憶装置１３を含む）の動作を制御する。
経路圧縮プログラムの制御によるデータ処理装置１１
（記憶装置１３を含む）の動作は、図１ないし図１６に
示した第１の実施の形態に係る経路圧縮方式の場合と全
く同様になるので、その詳しい説明を割愛する。

【００６３】

【発明の効果】本発明の効果は、グラフ情報格納手段に
どのようなグラフ情報が格納されていようとも、グラフ
情報の十分な経路圧縮を行うことができることである。
その理由は、圧縮制御手段の制御の元に、直線型経路圧
縮手段，流入型経路圧縮手段，分岐型経路圧縮手段，多
経路型経路圧縮手段およびクロス型経路圧縮手段を総当
たり的に、あるいは選択的に適用することにより、グラ
フ情報格納手段に格納されたグラフ情報が始点および終
点のみのノードとその間を結ぶアークのみから構成され
るグラフ情報になるからである。

【図面の簡単な説明】

【図１】本発明の第１の実施の形態に係る経路圧縮方式
の構成を示すブロック図である。

【図２】図１中の圧縮制御手段の処理の前半部を示す流
れ図である。

【図３】図１中の圧縮制御手段の処理の後半部を示す流
れ図である。

【図４】図１中の直線型経路圧縮手段の処理を示す流れ
図である。

【図５】図１中の流入型経路圧縮手段の処理を示す流れ
図である。

【図６】図１中の分岐型経路圧縮手段の処理を示す流れ
図である。

【図７】図１中の多経路型経路圧縮手段の処理を示す流
れ図である。

【図８】図１中のクロス型経路圧縮手段の処理を示す流
れ図である。

【図９】図１中の直線型経路圧縮手段による経路の圧縮
を説明する図である。

【図１０】図１中の流入型経路圧縮手段による経路の圧
縮を説明する図である。

【図１１】図１中の分岐型経路圧縮手段による経路の圧
縮を説明する図である。

【図１２】図１中の多経路型経路圧縮手段による経路の
圧縮を説明する図である。

【図１３】図１中のクロス型経路圧縮手段による経路の
圧縮を説明する図である。

【図１４】図１中のグラフ情報格納手段に格納されるグ
ラフ情報の元となる論理回路の一例を示す図である。

【図１５】図１４の論理回路から生成されるグラフを例
示する図である。

【図１６】図１５のグラフのグラフ情報を格納するノー
ドテーブルおよびアークテーブルを例示する図である。

【図１７】本発明の第２の実施の形態に係る経路圧縮方
式の構成を示すブロック図である。

【符号の説明】

１グラフ情報格納手段２直線型経路圧縮手段３流入型経路圧縮手段４分岐型経路圧縮手段５多経路型経路圧縮手段６クロス型経路圧縮手段７圧縮制御手段１１データ処理装置１２入力装置１３記憶装置１４出力装置１５記録媒体Ｓ１０１全経路圧縮手段圧縮効果有無判定ステップＳ１０２１つ目ノード着目ステップＳ１０３全ノード処理完了判定ステップＳ１０４直線型経路圧縮手段呼出しステップＳ１０５次ノード着目ステップＳ１０６１つ目ノード着目ステップＳ１０７全ノード処理完了判定ステップＳ１０８流入型経路圧縮手段呼出しステップＳ１０９次ノード着目ステップＳ１１０１つ目ノード着目ステップＳ１１１全ノード処理完了判定ステップＳ１１２分岐型経路圧縮手段呼出しステップＳ１１３次ノード着目ステップＳ１１４１つ目ノード着目ステップＳ１１５全ノード処理完了判定ステップＳ１１６多経路型経路圧縮手段呼出しステップＳ１１７次ノード着目ステップＳ１１８１つ目ノード着目ステップＳ１１９全ノード処理完了判定ステップＳ１２０クロス型経路圧縮手段呼出しステップＳ１２１次ノード着目ステップＳ２０１入力方向アーク１本かつ出力方向アーク１本
判定ステップＳ２０２入力方向アーク遅延時間計算ステップＳ２０３入力方向アーク素子遅延時間設定ステップＳ２０４入力方向ノード接続変更ステップＳ２０５ノードおよびアーク削除ステップＳ３０１入力方向アーク２本以上かつ出力方向アーク
１本判定ステップＳ３０２各入力方向アーク遅延時間計算ステップＳ３０３各入力方向アーク素子遅延時間設定ステップＳ３０４各入力方向ノード接続変更ステップＳ３０５ノードおよびアーク削除ステップＳ４０１入力方向アーク１本かつ出力方向アーク２本
以上判定ステップＳ４０２各出力方向アーク遅延時間計算ステップＳ４０３出力方向ノード接続変更ステップＳ４０４ノード削除ステップＳ５０１入力側ノードと出力側ノードとの組合せ同一
存在判定ステップＳ５０２アーク削除ステップＳ６０１入力方向アーク２本以上かつ出力方向アーク
２本以上判定ステップＳ６０２入力方向および出力方向アーク組合せ着目ス
テップＳ６０３全アーク組合せ処理完了判定ステップＳ６０４ノード接続アーク作成ステップＳ６０５新アーク遅延時間計算ステップＳ６０６新アーク素子遅延時間設定ステップＳ６０７別入力方向および出力方向アーク組合せ着目
ステップＳ６０８アークおよびノード削除ステップ

Claims

【特許請求の範囲】

【請求項１】グラフ情報を格納するグラフ情報格納手
段と、グラフ情報中の直線型経路を圧縮する直線型経路圧縮手
段と、グラフ情報中の流入型経路を圧縮する流入型経路圧縮手
段と、グラフ情報中の分岐型経路を圧縮する分岐型経路圧縮手
段と、グラフ情報中の多経路型経路を圧縮する多経路型経路圧
縮手段と、グラフ情報中のクロス型経路を圧縮するクロス型経路圧
縮手段と、前記グラフ情報格納手段に格納されているグラフ情報
に、前記直線型経路圧縮手段，前記流入型経路圧縮手
段，前記分岐型経路圧縮手段，前記多経路型経路圧縮手
段および前記クロス型経路圧縮手段を総当たり的に適用
して経路を圧縮する圧縮制御手段とを有することを特徴
とする経路圧縮方式。
【請求項２】グラフ情報を格納するグラフ情報格納手
段と、グラフ情報中の直線型経路を圧縮する直線型経路圧縮手
段と、グラフ情報中の流入型経路を圧縮する流入型経路圧縮手
段と、グラフ情報中の分岐型経路を圧縮する分岐型経路圧縮手
段と、グラフ情報中の多経路型経路を圧縮する多経路型経路圧
縮手段と、グラフ情報中のクロス型経路を圧縮するクロス型経路圧
縮手段と、前記グラフ情報格納手段に格納されているグラフ情報に
基づいて、直線型経路，流入型経路，分岐型経路，多経
路型経路およびクロス型経路を判別して、前記直線型経
路圧縮手段，前記流入型経路圧縮手段，前記分岐型経路
圧縮手段，前記多経路型経路圧縮手段および前記クロス
型経路圧縮手段を選択的に適用して経路を圧縮する圧縮
制御手段とを有することを特徴とする経路圧縮方式。
【請求項３】前記圧縮制御手段が、着目したノードに
ついて前記直線型経路圧縮手段，前記流入型経路圧縮手
段，前記分岐型経路圧縮手段，前記多経路型経路圧縮手
段および前記クロス型経路圧縮手段のどれを適用しても
圧縮効果がないかどうかを判定するステップと、圧縮効
果があれば１つ目のノードに着目するステップと、全て
のノードを処理したかどうかを判定するステップと、全
てのノードを処理していなければ前記直線型経路圧縮手
段を呼び出すステップと、前記直線型経路圧縮手段から
制御が戻ると次のノードに着目するステップと、全ての
ノードを処理していれば１つ目のノードに着目するステ
ップと、全てのノードを処理したかどうかを判定するス
テップと、全てのノードを処理していなければ前記流入
型経路圧縮手段を呼び出すステップと、前記流入型経路
圧縮手段から制御が戻ると次のノードに着目するステッ
プと、全てのノードを処理していれば１つ目のノードに
着目するステップと、全てのノードを処理したかどうか
を判定するステップと、全てのノードを処理していなけ
れば前記分岐型経路圧縮手段を呼び出すステップと、前
記分岐型経路圧縮手段から制御が戻ると次のノードに着
目するステップと、全てのノードを処理していれば１つ
目のノードに着目するステップと、全てのノードを処理
したかどうかを判定するステップと、全てのノードを処
理していなければ前記多経路型経路圧縮手段を呼び出す
ステップと、前記多経路型経路圧縮手段から制御が戻る
と次のノードに着目するステップと、全てのノードを処
理していれば１つ目のノードに着目するステップと、全
てのノードを処理したかどうかを判定するステップと、
全てのノードを処理していなければ前記クロス型経路圧
縮手段を呼び出すステップと、前記クロス型経路圧縮手
段から制御が戻ると次のノードに着目するステップとを
含む圧縮制御処理を繰り返し行う請求項１記載の経路圧
縮方式。
【請求項４】前記直線型経路圧縮手段が、着目してい
るノードの入力方向のアークが１本であり、かつ出力方
向のアークが１本であるかどうかを判定するステップ
と、入力方向のアークの遅延時間と、着目しているノー
ドの付加遅延時間と、出力方向のアークの遅延時間と、
入力方向のアークの素子の遅延時間とを加算して、入力
方向のアークの遅延時間とするステップと、出力方向の
アークの素子の遅延時間を入力方向のアークの素子の遅
延時間とするステップと、入力方向のノードの出力側の
接続を、着目しているノードから出力方向のアークの出
力側ノードに変更するステップと、着目しているノード
と出力方向のアークとを削除するステップとを含む直線
型経路圧縮処理を行う請求項１または２記載の経路圧縮
方式。
【請求項５】前記流入型経路圧縮手段が、着目してい
るノードの入力方向のアークが２本以上であり、かつ出
力方向のアークが１本であるかどうかを判定するステッ
プと、それぞれの入力方向のアークの遅延時間と、着目
しているノードの付加遅延時間と、出力方向のアークの
遅延時間と、着目している入力方向のアークの素子の遅
延時間とを加算して、それぞれの入力方向のアークの遅
延時間とするステップと、出力方向のアークの素子の遅
延時間をそれぞれの入力方向のアークの素子の遅延時間
とするステップと、それぞれの入力方向のノードの出力
側の接続を、着目しているノードから出力方向のアーク
の出力側ノードに変更するステップと、着目しているノ
ードと出力方向のアークとを削除するステップとを含む
流入型経路圧縮処理を行う請求項１または２記載の経路
圧縮方式。
【請求項６】前記分岐型経路圧縮手段が、着目してい
るノードの入力方向のアークが１本であり、かつ出力方
向のアークが２本以上であるかどうかを判定するステッ
プと、それぞれの出力方向のアークの遅延時間と、着目
しているノードの付加遅延時間と、入力方向のアークの
遅延時間と、入力方向のアークの素子の遅延時間とを加
算して、それぞれの出力方向のアークの遅延時間とする
ステップと、出力方向のノードの入力側の接続を、着目
しているノードから入力方向のアークの入力側ノードに
変更するステップと、着目しているノードと入力方向の
ノードとを削除するステップとを含む分岐型経路圧縮処
理を行う請求項１または２記載の経路圧縮方式。
【請求項７】前記多経路型経路圧縮手段が、着目して
いるノードの入力方向の全てのアークについて、入力側
ノードと出力側ノードとの組合せが同一のものがあるか
どうかを判定するステップと、対象となるアークの中
で、遅延時間と素子の遅延時間との和が最大のアークを
除いた他のアークを全て削除するステップとを含む多経
路型経路圧縮処理を行う請求項１または２記載の経路圧
縮方式。
【請求項８】前記クロス型経路圧縮手段が、着目して
いるノードの入力方向のアークが２本以上であり、かつ
出力方向のアークが２本であるかどうかを判定するステ
ップと、入力方向および出力方向のアークの組合せの１
つに着目するステップと、全てのアークの組合せを処理
したかどうかを判定するステップと、全てのアークの組
合せを処理していなければ入力方向のアークの入力方向
のノードと出力方向のアークの出力方向のノードとを接
続するアークを作成するステップと、出力方向のアーク
の遅延時間と、着目しているノードの付加遅延時間と、
入力方向のアークの遅延時間と、入力方向のアークの素
子の遅延時間とを加算して、新たなアークの遅延時間と
するステップと、出力方向のアークの素子の遅延時間を
新たなアークの素子の遅延時間とするステップと、別の
入力方向および出力方向のアークの組合せに着目するス
テップと、処理済みのアークと着目しているノードとを
削除するステップとを含むクロス型経路圧縮処理を行う
請求項１または２記載の経路圧縮方式。
【請求項９】コンピュータを、グラフ情報を格納する
グラフ情報格納手段，グラフ情報中の直線型経路を圧縮
する直線型経路圧縮手段，グラフ情報中の流入型経路を
圧縮する流入型経路圧縮手段，グラフ情報中の分岐型経
路を圧縮する分岐型経路圧縮手段，グラフ情報中の多経
路型経路を圧縮する多経路型経路圧縮手段，グラフ情報
中のクロス型経路を圧縮するクロス型経路圧縮手段，な
らびに前記グラフ情報格納手段に格納されているグラフ
情報に、前記直線型経路圧縮手段，前記流入型経路圧縮
手段，前記分岐型経路圧縮手段，前記多経路型経路圧縮
手段および前記クロス型経路圧縮手段を総当たり的に適
用して経路を圧縮する圧縮制御手段として機能させるた
めのプログラムを記録した記録媒体。
【請求項１０】コンピュータを、グラフ情報を格納す
るグラフ情報格納手段，グラフ情報中の直線型経路を圧
縮する直線型経路圧縮手段，グラフ情報中の流入型経路
を圧縮する流入型経路圧縮手段，グラフ情報中の分岐型
経路を圧縮する分岐型経路圧縮手段，グラフ情報中の多
経路型経路を圧縮する多経路型経路圧縮手段，グラフ情
報中のクロス型経路を圧縮するクロス型経路圧縮手段，
ならびに前記グラフ情報格納手段に格納されているグラ
フ情報に基づいて、直線型経路，流入型経路，分岐型経
路，多経路型経路およびクロス型経路を判別して、前記
直線型経路圧縮手段，前記流入型経路圧縮手段，前記分
岐型経路圧縮手段，前記多経路型経路圧縮手段および前
記クロス型経路圧縮手段を選択的に適用して経路を圧縮
する圧縮制御手段として機能させるためのプログラムを
記録した記録媒体。