(57)【特許請求の範囲】
【請求項１】
プリント配線板での配線経路の設計を支援する装置であって、
格子点をノードとし、隣接する格子点間を結ぶ線分を枝とする有向グラフを、前記配線経路を作成する対象領域面上に定義する有向グラフ定義部と、
前記対象領域面上において配線の配置が禁止される領域の位置を示す配線禁止領域情報についての入力を取得する配線禁止領域情報取得部と、
前記対象領域面上に定義されている前記格子点のうちで、複数の配線の各々によってそれぞれ結ばれる複数組の格子点の組の情報である結線情報についての入力を取得する結線情報取得部と、
前記有向グラフを構成している枝のうちで、前記配線禁止領域情報で示されている領域内に位置している格子点に繋がっている枝に対しフロー容量を「０」に設定すると共に、その他の枝に対しフロー容量を「１」に設定し、更に、前記複数組の格子点の各組に属している一対の格子点に、フロー容量が「１」である枝を介してフローの始点と終点とをそれぞれ接続することで、フローネットワークを作成するフローネットワーク作成部と、
前記フローネットワーク作成部が各枝について設定した前記フロー容量の下で前記始点から前記終点へのフロー量が最大となるフローの経路を、前記フローネットワークから探索するフロー経路探索部と、
前記フロー経路探索部による前記経路の探索結果に従って、前記結線情報で示されている複数組の格子点の各組に属している前記一対の格子点を各々結ぶ前記複数の配線の経路を決定する配線経路決定部と、
を備えることを特徴とする配線設計支援装置。
【請求項２】
前記格子点の間隔は、前記対象領域面上での前記配線における線幅及び配線間隔の定義に基づいて設定されることを特徴とする請求項１に記載の配線設計支援装置。
【請求項３】
前記結線情報取得部は、前記配線により接続を行う端子の前記対象領域面上での配置位置の情報の入力から、該端子と前記格子点との対応関係を示す対応関係情報を生成し、該対応関係情報と該配線により接続を行う端子を特定する論理接続情報の入力とに基づいて前記結線情報を生成することを特徴とする請求項１又は２に記載の配線設計支援装置。
【請求項４】
前記論理接続情報により特定されている前記配線により接続を行う端子が２端子部品の一方の端子である場合には、前記結線情報取得部は、該２端子部品における他方の端子と前記格子点とに対しての前記対応関係情報を更に生成し、
前記フローネットワーク作成部は、前記場合においては、前記２端子部品ついての中継ノードを新規に定義して、前記一方の端子に対応する格子点と前記始点若しくは前記終点とを接続する枝の途中に該中継ノードを挿入し、更に、前記対応関係情報において前記他方の端子との対応関係が示されている格子点と該中継ノードとをフロー容量が「１」である枝を介して接続し、
前記配線設計支援装置は、前記配線経路決定部が経路を決定した配線により接続される一方の接続先が前記２端子部品における前記他方の端子となった場合に、該配線により接続を行う端子の前記対象領域面上での配置位置についての前記入力された情報を変更して、該他方の端子についての該情報と該２端子部品における前記一方の端子についての該情報とを交換することによって、該配線により接続される端子を前記論理接続情報で特定される端子に一致させる２端子部品情報交換部を更に備える、
ことを特徴とする請求項３に記載の配線設計支援装置。
【請求項５】
前記２端子部品情報交換部は、更に、前記配線経路決定部が経路を決定した複数の配線に、接続を行う一方の接続先が同一形状の２端子部品である配線が少なくとも２つ存在することとなった場合に、該配線により接続を行う端子の前記対象領域面上での配置位置についての前記入力された情報を変更して、そのうちの１の配線に接続される２端子部品の端子についての該情報と、そのうちの別の１の配線に接続される、該２端子部品とは別の２端子部品の端子についての該情報とを交換することによって、該１の配線により接続される端子を前記論理接続情報で特定される端子に一致させることを特徴とする請求項４に記載の配線設計支援装置。
【請求項６】
前記配線経路決定部が経路を決定した複数の配線に、接続を行う一方の接続先が同一形状の多連集合部品である配線が少なくとも２つ存在することとなった場合に、該配線により接続を行う端子の前記対象領域面上での配置位置についての前記入力された情報を変更して、そのうちの１の配線に接続される多連集合部品の端子についての該情報と、そのうちの別の１の配線に接続される、当該多連集合部品の他の端子若しくは該多連集合部品とは別の多連集合部品の端子についての該情報とを交換することによって、該１の配線により接続される端子を前記論理接続情報で特定される端子に一致させる多連集合部品情報交換部を更に備えることを特徴とする請求項３から５のうちのいずれか一項に記載の配線設計支援装置。
【請求項７】
前記配線経路決定部が経路を決定した配線を、２線１組の平行配線である差動信号配線に置換する差動信号配線置換部を更に備えることを特徴とする請求項１から６のうちのいずれか一項に記載の配線設計支援装置。
【請求項８】
プリント配線板での配線経路の設計を支援する配線設計支援装置が行う方法であって、前記配線設計支援装置が、
格子点をノードとし、隣接する格子点間を結ぶ線分を枝とする有向グラフを、前記配線経路を作成する対象領域面上に定義し、
前記対象領域面上において配線の配置が禁止される領域の位置を示す配線禁止領域情報についての入力を取得し、
前記対象領域面上に定義されている前記格子点のうちで、複数の配線の各々によってそれぞれ結ばれる複数組の格子点の組の情報である結線情報についての入力を取得し、
前記有向グラフを構成している枝のうちで、前記配線禁止領域情報で示されている領域内に位置している格子点に繋がっている枝に対しフロー容量を「０」に設定すると共に、その他の枝に対しフロー容量を「１」に設定し、更に、前記複数組の格子点の各組に属している一対の格子点に、フロー容量が「１」である枝を介してフローの始点と終点とをそれぞれ接続することで、フローネットワークを作成し、
前記枝の各々について設定した前記フロー容量の下で前記始点から前記終点へのフロー量が最大となるフローの経路を、前記フローネットワークから探索し、
前記経路の探索結果に従って、前記結線情報で示されている複数組の格子点の各組に属している前記一対の格子点を各々結ぶ前記複数の配線の経路を決定する、
ことを特徴とする配線設計支援方法。
【請求項９】
プリント配線板での配線経路の設計の支援をコンピュータに行わせるためのプログラムであって、
格子点をノードとし、隣接する格子点間を結ぶ線分を枝とする有向グラフを、前記配線経路を作成する対象領域面上に定義し、
前記対象領域面上において配線の配置が禁止される領域の位置を示す配線禁止領域情報についての入力を取得し、
前記対象領域面上に定義されている前記格子点のうちで、複数の配線の各々によってそれぞれ結ばれる複数組の格子点の組の情報である結線情報についての入力を取得し、
前記有向グラフを構成している枝のうちで、前記配線禁止領域情報で示されている領域内に位置している格子点に繋がっている枝に対しフロー容量を「０」に設定すると共に、その他の枝に対しフロー容量を「１」に設定し、更に、前記複数組の格子点の各組に属している一対の格子点に、フロー容量が「１」である枝を介してフローの始点と終点とをそれぞれ接続することで、フローネットワークを作成し、
前記枝の各々について設定した前記フロー容量の下で前記始点から前記終点へのフロー量が最大となるフローの経路を、前記フローネットワークから探索し、
前記経路の探索結果に従って、前記結線情報で示されている複数組の格子点の各組に属している前記一対の格子点を各々結ぶ前記複数の配線の経路を決定する、
処理を前記コンピュータに実行させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本明細書で議論される実施態様は、プリント配線板での配線の設計を支援する技術に関するものである。
【背景技術】
【０００２】
半導体チップのボンディングパッドと半導体パッケージのピンとの間の配線経路の設計に関し、１つの面上に設けられた複数の端点同士を、当該面上の配線禁止領域以外を通る経路で接続する配線を設計するという技術が知られている。この技術は、当該端点および当該面上の配線禁止領域の任意の２つの間それぞれに仮想的な配線密度監視用の辺（監視辺）を作成し、この監視辺それぞれと交差する配線の幅に基づいて、端点同士を接続する配線経路を設計するというものである。
【０００３】
また、半導体チップなどのパッケージにおける多端子ネットの自動発生の技術に関し、結線可能で且つ冗長経路を含まない一筆書きの多端子ネットを自動的に発生するという技術が知られている。この技術では、Ｎ端子（Ｎは３以上の整数）のネットを自動発生するために、パッケージの所与の設計ルールを満たした（Ｎ−１）端子の結線データが初期データとして与えられる。すると、この技術では、まず、配線開始点の端子群と、ネット発生対象であるＮ端子目の端子群とを対象として、中間の端子群を無視して２端子ネット発生処理を実行する。そして、初期データと、２端子ネット発生処理の実行結果とを合成することにより暫定ネットを発生し、この暫定ネットをパッケージの設計ルールを満たすように修正する。
【０００４】
また、基板上における各パッド部からそれぞれの結線先である各ビア部への最適な配線の位置を、演算処理により自動的に決定するという技術が知られている。この技術では、まず、各パッド部と各ビア部とを結ぶ各仮配線のうちの２つが形成する交点と対応の各ビア部との間の各距離を判定し、この距離が長い仮配線を、距離が短い仮配線の対応のビア部の周りに迂回させて暫定配線とする。この処理は、各仮配線が形成する交点の全てについて順次実行される。次に、各暫定配線同士又は暫定配線と仮配線とが形成する交点と、暫定配線又は仮配線の対応のビア部との間の各距離を判定し、この距離が長い暫定配線又は仮配線を、距離が短い暫定配線又は仮配線の対応のビア部の周りに迂回させて最適な配線とする。この処理は、各暫定配線同士が形成する交点及び暫定配線と仮配線とが形成する交点の全てについて順次実行される。
【０００５】
また、多数のノード間を波長多重された光伝送路により接続する光通信網において、２つのノード間に設定される光パスを網内にできるだけ合理的に設定する技術に関し、光パス網において必要となる波長数を低減させるという技術が知られている。この技術では、予備パスの経路探索を全ての光伝送路の故障を想定して光伝送路の距離（経路収容数）を算出して最短経路の探索が行われ、多重波長数が最大となる光伝送路についてだけ波長低減が行われる。
【０００６】
また、集積回路パッケージにおける配線経路の作成を適切に支援する技術が知られている。この技術では、まず、集積回路パッケージの少なくとも各ピン、各水平ピン間、各垂直ピン間、及び各対角ピン間を配線のボトルネック箇所とし、各ボトルネック箇所に配線容量が付与される。次に、ボトルネック箇所毎に入り口ノード及び出口ノードの二つのノードが生成される。次に、それぞれのボトルネック箇所について、ボトルネック箇所内の入り口ノードから出口ノードへの有向枝が生成される。また、隣接するボトルネック箇所間において一方の出口ノードから他方の入り口ノードへの有向枝が相互に生成される。そして、対角ピン間のボトルネック箇所と当該対角ピン間の全ての斜め隣のボトルネック箇所との間において一方の出口ノードから他方の入り口ノードへの有向枝が相互に生成される。そして、生成された全ての有向枝に、ボトルネック箇所に割り当てられた配線容量の最小値が枝容量として付与される。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特許第３１８４７９６号公報
【特許文献２】特許第３５４８０７０号公報
【特許文献３】特許第４４４３４５０号公報
【特許文献４】特許第３２２４１１４号公報
【特許文献５】特開２０１０−２１１７５３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
近年、電子機器に使用されるプリント配線板は、電子回路の大規模化と高密度化との進展により、配線区間数が増加している。また、デジタル信号の高速化や省電力化に伴って波形の品質に対する要求が高くなったことにより、特に反射ノイズ対策としてダンピング抵抗や終端抵抗を挿入する機会が増加している。このような抵抗部品は、適切な位置に配置してできる限り短い線長で接続しなければ所望の効果が期待できないため、プリント配線板の設計者は、配線長が長くならないよう注意しながら抵抗部品の配置及び端子（ピン）間の配線の設計作業を行っている。
【０００９】
例えばＢＧＡ（Ball Grid Array）などといった非常に多くのピンを備えている部品（以下、「多ピン部品」と称する）を配置する場合には、その周囲に数十〜数百の抵抗部品を配置し、且つ、互いに線長が長くならないよう考慮して配線する必要がある。このような配線を単層で行うための一般的な手法では、まず、多ピン部品内の各ピンから当該多ピン部品の外側まで、なるべく迂回をしないようにして配線を伸ばす。そして、次に、配線順序に応じ、チップ抵抗や多連抵抗等の抵抗部品を配置し、若しくは抵抗部品の入れ替えを行って、前述した配線との接続を行う。しかしながら、配線数が多くなると、先に配線を済ませていた配線ラインが後の配線にとっての邪魔になるという場面がしばしば発生し、その都度、配線経路の修正を行うこととなる。このような修正が、プリント配線板での配線設計作業に多くの時間が必要とされる要因のひとつとなっている。
【００１０】
ここで、このような配線設計に前述した各種の技術を用いた場合には、配線設定に長い時間を要することが多いと思われ、中には配線経路が存在してもその経路を見つけ出せないこともあると考えられる。
【００１１】
上述した問題に鑑み、本明細書で後述する配線設計支援装置は、プリント配線板での配線経路の設計作業を適切に支援する新たな手法を提供する。
【課題を解決するための手段】
【００１２】
本明細書で後述する配線設計支援装置は、プリント配線板での配線経路の設計を支援する装置である。この装置のひとつに、有向グラフ定義部、配線禁止領域情報取得部、結線情報取得部、フローネットワーク作成部、フロー経路探索部、及び配線経路決定部を備えるというものがある。ここで、有向グラフ定義部は、格子点をノードとし、隣接する格子点間を結ぶ線分を枝とする有向グラフを、当該配線経路を作成する対象領域面上に定義する。配線禁止領域情報取得部は、当該対象領域面上において配線の配置が禁止される領域の位置を示す配線禁止領域情報についての入力を取得する。結線情報取得部は、当該対象領域面上に定義されている当該格子点のうちで、複数の配線の各々によってそれぞれ結ばれる複数組の格子点の組の情報である結線情報についての入力を取得する。フローネットワーク作成部は、まず、当該有向グラフを構成している枝のうちで当該配線禁止領域情報で示されている領域内に位置している格子点に繋がっている枝に対しフロー容量を「０」に設定すると共に、その他の枝に対しフロー容量を「１」に設定する。更に、フローネットワーク作成部は、当該複数組の格子点の各組に属している一対の格子点に、フロー容量が「１」である枝を介してフローの始点と終点とをそれぞれ接続することで、当該フローネットワークを作成する。フロー経路探索部は、フローネットワーク作成部が各枝について設定したフロー容量の下で当該始点から当該終点へのフロー量が最大となるフローの経路を、当該フローネットワークから探索する。配線経路決定部は、フロー経路探索部による当該経路の探索結果に従って、当該結線情報で示されている複数組の格子点の各組に属している当該一対の格子点を各々結ぶ複数の配線の経路を決定する。
【００１３】
また、本明細書で後述する配線設計支援方法のひとつは、プリント配線板での配線経路の設計を支援する配線設計支援装置が行う方法である。当該配線設計支援装置が行うこの方法は、まず、格子点をノードとし、隣接する格子点間を結ぶ線分を枝とする有向グラフを、当該配線経路を作成する対象領域面上に定義する。次に、当該対象領域面上において配線の配置が禁止される領域の位置を示す配線禁止領域情報についての入力を取得する。次に、当該対象領域面上に定義されている当該格子点のうちで、複数の配線の各々によってそれぞれ結ばれる複数組の格子点の組の情報である結線情報についての入力を取得する。次に、フローネットワークの作成を行う。この作成のために、まず、当該有向グラフを構成している枝のうちで当該配線禁止領域情報で示されている領域内に位置している格子点に繋がっている枝に対しフロー容量を「０」に設定すると共に、その他の枝に対しフロー容量を「１」に設定する。次に、当該複数組の格子点の各組に属している一対の格子点に、フロー容量が「１」である枝を介してフローの始点と終点とをそれぞれ接続することで、当該フローネットワークが作成される。次に、当該枝の各々について設定したフロー容量の下で当該始点から当該終点へのフロー量が最大となるフローの経路を、当該フローネットワークから探索する。そして、当該経路の探索結果に従って、当該結線情報で示されている複数組の格子点の各組に属している当該一対の格子点を各々結ぶ複数の配線の経路を決定する。
【００１４】
また、本明細書で後述するプログラムのひとつは、プリント配線板での配線経路の設計の支援をコンピュータに行わせるためのものである。このプログラムは、以下の処理をコンピュータに実行させる。この処理は、まず、格子点をノードとし、隣接する格子点間を結ぶ線分を枝とする有向グラフを、当該配線経路を作成する対象領域面上に定義する。次に、当該対象領域面上において配線の配置が禁止される領域の位置を示す配線禁止領域情報についての入力を取得する。次に、当該対象領域面上に定義されている当該格子点のうちで、複数の配線の各々によってそれぞれ結ばれる複数組の格子点の組の情報である結線情報についての入力を取得する。次に、フローネットワークの作成を行う。この作成のために、まず、当該有向グラフを構成している枝のうちで当該配線禁止領域情報で示されている領域内に位置している格子点に繋がっている枝に対しフロー容量を「０」に設定すると共に、その他の枝に対しフロー容量を「１」に設定する。次に、当該複数組の格子点の各組に属している一対の格子点に、フロー容量が「１」である枝を介してフローの始点と終点とをそれぞれ接続することで、当該フローネットワークが作成される。次に、当該枝の各々について設定したフロー容量の下で当該始点から当該終点へのフロー量が最大となるフローの経路を、当該フローネットワークから探索する。そして、当該経路の探索結果に従って、当該結線情報で示されている複数組の格子点の各組に属している当該一対の格子点を各々結ぶ複数の配線の経路を決定する。
【発明の効果】
【００１５】
本明細書で後述する配線設計支援装置は、プリント配線板での配線経路の設計作業の支援を適切に行えるという効果を奏する。
【図面の簡単な説明】
【００１６】
【図１】配線設計支援装置の一実施例の機能ブロック図である。
【図２】記憶装置での各種記憶データのデータ構造の説明図である。
【図３】コンピュータのハードウェア構成例である。
【図４】フローネットワークの一例である。
【図５Ａ】エドモンズ・カープのアルゴリズムの説明図（その１）である。
【図５Ｂ】エドモンズ・カープのアルゴリズムの説明図（その２）である。
【図５Ｃ】エドモンズ・カープのアルゴリズムの説明図（その３）である。
【図５Ｄ】エドモンズ・カープのアルゴリズムの説明図（その４）である。
【図５Ｅ】エドモンズ・カープのアルゴリズムの説明図（その５）である。
【図６】図４のフローネットワークについての最大フロー問題のエドモンズ・カープのアルゴリズムでの解である。
【図７】フローネットワークの作成例（その１）である。
【図８】フローネットワークの作成例（その２）である。
【図９Ａ】図１の配線設計支援装置による自動配線の手順の概要の説明図（その１）である。
【図９Ｂ】図１の配線設計支援装置による自動配線の手順の概要の説明図（その２）である。
【図９Ｃ】図１の配線設計支援装置による自動配線の手順の概要の説明図（その３）である。
【図９Ｄ】図１の配線設計支援装置による自動配線の手順の概要の説明図（その４）である。
【図１０Ａ】配線経路自動設計処理の手順の概要の説明図（その１）である。
【図１０Ｂ】配線経路自動設計処理の手順の概要の説明図（その２）である。
【図１１】配線経路自動設計処理の処理内容を図解したフローチャートである。
【図１２】有向グラフ定義処理の処理内容を図解したフローチャートである。
【図１３】図１２の有向グラフ定義処理におけるノード及び枝の定義の手法の説明図である。
【図１４Ａ】ノード情報テーブルのデータ構造の説明図である。
【図１４Ｂ】枝情報テーブルのデータ構造の説明図である。
【図１５】配線禁止領域情報取得処理の処理内容を図解したフローチャートである。
【図１６】使用禁止ノードテーブルのデータ構造の説明図である。
【図１７】結線情報取得処理の処理内容を図解したフローチャートである。
【図１８】端点要素引き当てテーブルのデータ構造の説明図である。
【図１９】フローネットワーク作成処理の処理内容を図解したフローチャートである。
【図２０Ａ】フローネットワーク作成処理の処理内容の説明図（その１）である。
【図２０Ｂ】フローネットワーク作成処理の処理内容の説明図（その２）である。
【図２１Ａ】フロー経路探索処理の処理内容を図解したフローチャート（その１）である。
【図２１Ｂ】フロー経路探索処理の処理内容を図解したフローチャート（その２）である。
【図２２】フロー経路探索処理で使用する各種データテーブルのデータ構造の説明図である。
【図２３Ａ】配線経路決定処理の処理内容を図解したフローチャート（その１）である。
【図２３Ｂ】配線経路決定処理の処理内容を図解したフローチャート（その２）である。
【図２４Ａ】２端子部品情報交換処理の処理内容を図解したフローチャート（その１）である。
【図２４Ｂ】２端子部品情報交換処理の処理内容を図解したフローチャート（その２）である。
【図２５Ａ】多連集合部品情報交換処理の処理内容を図解したフローチャート（その１）である。
【図２５Ｂ】多連集合部品情報交換処理の処理内容を図解したフローチャート（その２）である。
【図２５Ｃ】多連集合部品情報交換処理の処理内容を図解したフローチャート（その３）である。
【図２５Ｄ】多連集合部品情報交換処理の処理内容を図解したフローチャート（その４）である。
【図２６Ａ】差動信号の伝送に好適な配線経路の例である。
【図２６Ｂ】フローネットワークの作成例（その３）である。
【発明を実施するための形態】
【００１７】
まず図１について説明する。図１は、プリント配線板での配線経路の自動設計を行うことで当該配線経路の設計作業を支援する配線設計支援装置の一実施例の機能ブロック図である。
【００１８】
この配線設計支援装置１は、ＭＰＵ１０、記憶装置３０、表示装置４１、マウス装置４２、キーボード装置４３、ＲＡＭ４４、及びＲＯＭ４５を備えている。なお、これらの構成要素は、システムバス４６を介して接続されており、各種のデータをＭＰＵ１０の管理の下で相互に授受することができる。
【００１９】
ＭＰＵ（Micro Processing Unit）１０は、配線設計支援装置１全体の動作を制御する演算処理装置である。また、ＭＰＵ１０は、有向グラフ定義部１１、配線禁止領域情報取得部１２、結線情報取得部１３、フローネットワーク作成部１４、フロー経路探索部１５、及び配線経路決定部１６として機能する。なお、ＭＰＵ１０が、更に、２端子部品情報交換部１７、多連集合部品情報交換部１８、及び差動信号配線置換部１９として機能するようにしてもよい。これらの機能の詳細については後述する。なお、ＭＰＵ１０は、ＲＯＭ４５に予め格納されている所定の制御プログラムを読み出して実行することによって、これらの各機能ブロックが備えている機能を提供できるようになる。
【００２０】
記憶装置３０は、配線設計支援装置１に入力される情報である配線禁止領域情報３１、論理接続情報３２、及び部品情報３３と、配線設計支援装置１が出力する情報である配線経路情報３４とを記憶しておく装置である。これらの情報の具体的な内容については後述する。
【００２１】
表示装置４１は、ＭＰＵ１０から送付される表示データに応じて各種のテキストや画像を表示する。
マウス装置４２及びキーボード装置４３は、配線設計支援装置１の使用者からの各種の指示やデータの入力を受け付ける入力装置である。
【００２２】
ＲＡＭ（Random Access Memory）４４は、ＭＰＵ１０による制御プログラムの実行の際に、例えば作成した各種のテーブルを記憶しておくために使用する等、必要に応じて作業用記憶領域として使用する、随時書き込み読み出し可能な半導体メモリである。
【００２３】
ＲＯＭ（Read Only Memory）４５は、所定の制御プログラムが予め記録されている読み出し専用半導体メモリである。ＭＰＵ１０は、この制御プログラムを配線設計支援装置１の起動時に読み出して実行することにより、配線設計支援装置１全体の動作の制御や、前述の各機能ブロックが備えている機能を提供できるようになる。
【００２４】
次に、ＭＰＵ１０によって提供される、前述の各機能ブロックが備えている機能について説明する。
有向グラフ定義部１１は、格子点をノードとし、隣接する格子点間を結ぶ線分を枝とする有向グラフを、プリント配線板における、配線経路を作成する対象領域面上に定義する。なお、このときの格子点の間隔は、例えば、この対象領域面上でのプリント配線における線幅及び配線間隔の定義に基づいて設定される。
【００２５】
配線禁止領域情報取得部１２は、上述の対象領域面上において配線の配置が禁止される領域の位置を示す配線禁止領域情報３１についての入力を取得する。
結線情報取得部１３は、上述の対象領域面上に定義されている格子点のうちで、複数の配線の各々によってそれぞれ結ばれる複数組の格子点の組の情報である結線情報についての入力を取得する。
【００２６】
フローネットワーク作成部１４はフローネットワークの作成を行う。より具体的には、フローネットワーク作成部１４は、まず、有向グラフ定義部１１が定義した有向グラフを構成している枝のうちで、配線禁止領域情報３１で示されている領域内に位置している格子点に繋がっている枝に対しフロー容量を「０」に設定する。そして、その他の枝に対しては、フロー容量を「１」に設定する。次に、フローネットワーク作成部１４は、前述の複数組の格子点の各組に属している一対の格子点に、フロー容量が「１」である枝を介してフローの始点と終点とをそれぞれ接続する。フローネットワーク作成部１４は、フローネットワークの作成をこのようにして行う。
【００２７】
フロー経路探索部１５は、フローネットワーク作成部１４が各枝について設定したフロー容量の下で前述の始点から終点へのフロー量が最大となるフローの経路を、フローネットワーク作成部１４が作成したフローネットワークから探索する。
【００２８】
配線経路決定部１６は、フロー経路探索部１５による上述の経路の探索結果に従って、前述の結線情報で示されている複数組の格子点の各組に属している一対の格子点を各々結ぶ複数の配線の経路を決定する。配線経路決定部１６は、決定された配線の経路を特定する情報を、配線経路情報３４として、記憶装置３０に記憶する。
【００２９】
この構成では、プリント配線板による配線経路の自動設計を、フローネットワークにおける最大フロー問題に帰着させて実行する。また、フローネットワークにおける枝の容量を「０」として配線禁止領域を表現し、当該容量を「１」として配線可能領域を表現する。このようにすることで、配線経路が存在すれば確実に発見することができ、また、配線経路の自動設計に要する時間の短縮化が期待できる。
【００３０】
なお、結線情報取得部１３は、前述の結線情報を、例えば以下のようにして行う。すなわち、結線情報取得部１３は、まず、配線により接続を行う端子の対象領域面上での配置位置の情報の入力から、当該端子と格子点との対応関係を示す対応関係情報を生成する。なお、各端子の配置位置情報は、部品情報３３から取得される。結線情報取得部１３は、この対応関係情報と配線により接続を行う端子間の論理接続情報３２の入力とに基づいて、この結線情報を取得する。
【００３１】
また、論理接続情報３２により特定されている、配線により接続を行う端子が２端子部品の一方の端子である場合には、各機能ブロックが以下の機能を提供するようにしてもよい。
【００３２】
この場合においては、まず、結線情報取得部１３は、当該２端子部品における他方の端子と前述の格子点とに対しての対応関係情報を更に生成する。また、フローネットワーク作成部１４は、この場合においては、まず、当該２端子部品ついての中継ノードを新規に定義して、上述の一方の端子に対応する格子点と前述の始点若しくは終点とを接続する枝の途中に当該中継ノードを挿入する。更に、フローネットワーク作成部１４は、前述の対応関係情報において上述の他方の端子との対応関係が示されている格子点と当該中継ノードとをフロー容量が「１」である枝を介して接続する。
【００３３】
２端子部品交換部１７は、上記の場合に用いられるものである。２端子部品情報交換部１７は、配線経路決定部１６が経路を決定した配線により接続される一方の接続先がこの２端子部品における上述の他方の端子となった場合に、当該配線により接続を行う端子の対象領域面上での配置位置についての入力された情報を変更する。この変更は、当該他方の端子についてのこの情報と当該２端子部品における当該一方の端子についての当該情報とを交換して、当該配線により接続される端子を、論理接続情報３２で特定される端子に一致させるというものである。
【００３４】
詳細は後述するが、配線設計支援装置１は、この２端子部品情報交換部１７を備えることで、特定の場合において配線経路を短縮することができる。
また、２端子部品情報交換部１７は、配線経路決定部１６が経路を決定した複数の配線に、接続を行う一方の接続先が同一形状の２端子部品である配線が少なくとも２つ存在することとなった場合に、以下に述べる機能を提供してもよい。すなわち、２端子部品情報交換部１７は、この場合に、当該配線により接続を行う端子の対象領域面上での配置位置についての入力された情報を変更する。この変更は、上述の場合のうちの１の配線に接続される２端子部品の端子についての当該情報と、上述の場合のうちの別の１の配線に接続される、当該２端子部品とは別の２端子部品の端子についての当該情報とを交換するというものである。この変更によって、当該１の配線により接続される端子を論理接続情報３２で特定される端子に一致させることができる。
【００３５】
詳細は後述するが、２端子部品情報交換部１７が上記の機能を更に提供することで、論理接続情報３２による制約条件の一部を一旦除外して配線経路の決定を行ってから、配線経路と論理接続情報３２との不一致を解消することが可能になる。このようにすることで、遅い順序での配線経路の作成のために配置済みの配線の経路の修正が必要となるケースが減少し、設計作業に要する時間の短縮化に寄与する。
【００３６】
また、多連集合部品情報交換部１８は、配線経路決定部１６が経路を決定した複数の配線に、接続を行う一方の接続先が同一形状の多連集合部品である配線が少なくとも２つ存在することとなった場合に、以下に述べる機能を提供するものである。すなわち、多連集合部品情報交換部１８は、この場合に、当該配線により接続を行う端子の対象領域面上での配置位置についての入力された情報を変更する。この変更により、上述の場合のうちの１の配線に接続される多連集合部品の端子についての該情報を、上述の場合のうちの別の１の配線に接続される、当該多連集合部品の他の端子若しくは当該多連集合部品とは別の多連集合部品の端子についての該情報と交換する。この変更によって、当該１の配線により接続される端子を論理接続情報３２で特定される端子に一致させることができる。
【００３７】
なお、本願において、「多連集合部品」とは、ネットワーク抵抗器やチップ型コンデンサネットワークなどと称されている、素子値が同一である複数の２端子素子を１つのパッケージに封入した部品の総称をいうものとする。
【００３８】
詳細は後述するが、配線設計支援装置１は、この多連集合部品情報交換部１８を備えることで、論理接続情報３２による制約条件の一部を一旦除外して配線経路の決定を行ってから、配線経路と論理接続情報３２との不一致を解消することが可能になる。このようにすることで、遅い順序での配線経路の作成のために既に配置済みの配線の経路の修正が必要となるケースが減少し、設計作業に要する時間の短縮化に寄与する。
【００３９】
差動信号配線置換部１９は、配線経路決定部１６が経路を決定した配線を、２線１組の平行配線である差動信号配線に置換する。
配線設計支援装置１は、この差動信号配線置換部１９を備えることで、一対の配線を平行な経路で配線することが望まれる差動信号配線の設計支援を行うことができる。
【００４０】
次に、記憶装置３０により記憶される各種データのデータ構造について、図２を参照しながら説明する。
図２に示されているように、配線禁止領域情報３１、論理接続情報３２、部品情報３３、及び配線経路情報３４はいずれもテーブル構造のデータ構造を有している。
【００４１】
配線禁止領域情報３１は「形状」と「層」とを対応付けた情報である。ここで、「形状」の項目は、配線禁止領域のプリント配線板上での位置を特定する情報である。例えば、この１行目の「形状」のデータ例は、プリント配線板上に定義した二次元直交座標平面（Ｘ，Ｙ）上における座標（０，０）と（６００００，１０００）との２点を対角点とする矩形の領域を配線禁止領域とすることを表している。また、「層」の項目は、多層基板であるプリント配線板の各配線層においての配線禁止領域が設定される配線層を特定する情報である。例えば、この１行目の「層」のデータ例は、第１層から第１２層までの各配線層において、「形状」の情報で表されている領域を配線禁止領域とすることを表している。
【００４２】
論理接続情報３２は、「接続名」毎に「始点ピン名」と「終点ピン名」とを対応付けた情報である。ここで、「接続名」の項目は論理接続情報３２を個別に識別する情報であり、「始点ピン名」及び「終点ピン名」の各項目は、配線設計支援装置１によって自動設計される配線経路により接続を行う一対の端子を特定する情報である。例えば、この１行目の『ＳＩＧ−１』についてのデータ例は、部品名がＬＳＩ１である部品の１番ピンと部品名がＲ１である部品の１番ピンとを接続することを表している。
【００４３】
部品情報３３は、「部品名」毎に「部品位置」、「方向」、「ピン名」、及び「ピン位置」を対応付けた情報である。ここで、「部品名」の項目はプリント配線板上に配置される部品を個別に識別する情報である。また、「部品位置」の項目は、「部品名」で特定される部品の位置（当該部品の１番ピンの位置）を座標で表している。また、「方向」は、「部品名」で特定される部品の配置方向を、予め定めた基準方向に対する回転角度で表している。また、「ピン名」の項目は、「部品名」で特定される部品が備えている端子を個別に識別する情報である。更に、「ピン位置」の情報は、「部品名」及び「ピン名」で特定される部品の端子の位置（当該部品の１番ピンの位置を基準位置とするときの相対位置）を座標で表している。例えば、この１行目の『ＬＳＩ１』についてのデータ例は、部品名がＬＳＩ１である部品が、１番ピンが（４４５００，２７５００）の位置で、基準方向に沿って配置されることを表している。また、このデータ例では、この部品の２番ピンの相対位置は（１０００，０）であり、３番ピンの相対位置は（２０００，０）であること、なども表されている。
【００４４】
以上の配線禁止領域情報３１、論理接続情報３２、及び部品情報３３は、配線設計支援装置１の使用者によって用意されて記憶装置３０に予め記憶させておく情報である。
配線経路情報３４は、「接続名」で表されている論理接続情報３２について配線設計支援装置１によって自動設計された配線経路を表している。例えば、１行目の『ＳＩＧ−１』についてのデータ例は、第１２層における、座標（４５０００，２８０００）、（４５５００，２８０００）、（４５５００，３２０００）、（５２５００，３２０００）、…の各点をこの順序で接続した経路を表している。
【００４５】
記憶装置３０により記憶される各種情報は、以上のようなデータ構造を有している。
なお、図１に図解した配線設計支援装置１を、標準的な構成のコンピュータを用いて構成することもできる。
【００４６】
ここで図３について説明する。図３には、コンピュータのハードウェア構成例が図解されている。
このコンピュータ５０は、ＭＰＵ５１、ＲＯＭ５２、ＲＡＭ５３、ハードディスク装置５４、入力装置５５、表示装置５６、インタフェース装置５７、及び記録媒体駆動装置５８を備えている。なお、これらの構成要素はバスライン５９を介して接続されており、ＭＰＵ５１の管理の下で各種のデータを相互に授受することができる。
【００４７】
ＭＰＵ５１は、このコンピュータ５０全体の動作を制御する演算処理装置であり、図１におけるＭＰＵ１０として機能する。
ＲＯＭ５２は、所定の基本制御プログラムが予め記録されている読み出し専用半導体メモリであり、ＭＰＵ５１は、この基本制御プログラムをコンピュータ５０の起動時に読み出して実行することにより、このコンピュータ５０の各構成要素の動作制御が可能になる。このＲＯＭ５２は、図１におけるＲＯＭ４５の一部機能を提供する。
【００４８】
ＲＡＭ５３は、ＭＰＵ５１が各種の制御プログラムを実行する際に、必要に応じて作業用記憶領域として使用する、随時書き込み読み出し可能な半導体メモリであり、図１におけるＲＡＭ４４として機能する。
【００４９】
ハードディスク装置５４は、ＭＰＵ５１によって実行される各種の制御プログラムや各種のデータを記憶しておく記憶装置である。ＭＰＵ５１は、ハードディスク装置５４に記憶されている所定の制御プログラムを読み出して実行することにより、各種の制御処理を行えるようになる。ハードディスク装置５４は、図１における記憶装置３０の機能を提供すると共に、ＲＯＭ４５の一部機能の提供も行う。
【００５０】
入力装置５５は、コンピュータ５０の操作者により操作されると、その操作内容に対応付けられている管理者からの各種情報の入力を取得し、取得した入力情報をＭＰＵ５１に送付する。この入力装置５５は、図１におけるマウス装置４２及びキーボード装置４３に相当するものである。
【００５１】
表示装置５６はＭＰＵ５１から送付される表示データに応じて各種のテキストや画像を表示する例えば液晶ディスプレイであり、図１の表示装置４１に相当する。
インタフェース装置５７は、このコンピュータ５０に接続される各種機器との間での各種情報の授受の管理を行う。
【００５２】
記録媒体駆動装置５８は、可搬型記録媒体６０に記録されている各種の制御プログラムやデータの読み出しを行う装置である。ＭＰＵ５１は、可搬型記録媒体６０に記録されている所定の制御プログラムを、記録媒体駆動装置５８を介して読み出して実行することによって、後述する各種の制御処理を行うようにすることもできる。なお、可搬型記録媒体６０としては、例えばＣＤ−ＲＯＭ（Compact Disc Read Only Memory）やＤＶＤ−ＲＯＭ（Digital Versatile Disc Read Only Memory）、ＵＳＢ（Universal Serial Bus）規格のコネクタが備えられているフラッシュメモリなどがある。
【００５３】
このようなコンピュータ５０を用いて配線設計支援装置１を構成するには、例えば、後にフローチャートを示して説明する配線経路自動設計処理をＭＰＵ５１に行わせるための制御プログラムを作成する。作成された制御プログラムはハードディスク装置５４若しくは可搬型記録媒体６０に予め格納しておく。そして、ＭＰＵ５１に所定の指示を与えてこの制御プログラムを読み出させて実行させる。こうすることで、配線設計支援装置１の構成要素が各々有している機能のコンピュータ５０での提供が可能となる。
【００５４】
次に、図１の配線設計支援装置１により行われる配線経路の決定の手法について図面を参照しながら説明する。
配線設計支援装置１では、フローネットワークにおける最大フロー問題の解法のひとつとして広く知られている、エドモンズ・カープのアルゴリズム（Edmonds-Karp algorithm）を利用して、この配線経路の決定を行う。
【００５５】
図４は、フローネットワークの一例である。
このフローネットワークはＡからＧまでの計７個のノード（頂点）を備えている。ここでは、このうちのＡをフローの始点、すなわちフローが生成されるノードとし、Ｇをフローの終点、すなわちフローが消費されるノードとする。フローネットワークにおいては、始点と終点とを除く各ノードでは、流入するフロー量と流出するフロー量との合計はゼロであるという、フロー保存則が適用される。
【００５６】
また、図４の例では、各ノード間の枝（アーク）にはフローの向きが矢印のように定義されている。なお、各枝に“ｆ／ｃ”の形式で文字が付されている。ここで、“ｆ”は、その枝を流れるフローの量を表しており、“ｃ”は、その枝の容量、すなわち、その枝に流すことのできる最大のフロー量を表している。各枝では、この容量の範囲内であれば、矢印で示されている向きとは逆向きにフローが流れることが許容される。なお、図４の例は、初期状態を表しており、全ての枝のフローの量が「０」となっている。
【００５７】
最大フロー問題は、フローネットワークにおいて、始点から終点へのフロー量が最大となるフローを求めるというものである。エドモンズ・カープのアルゴリズムは、この最大フロー問題を以下のようにして解く。すなわち、始点から終点への経路の探索を幅優先探索により行う。ここで、経路上の各枝の容量に余裕があれば、その経路によるフローの形成を行う（バックトレース）。この手続きを新たな経路が発見できなくなるまで反復する（イタレーション）。
【００５８】
図４に例示したフローネットワークについての最大フロー問題を、エドモンズ・カープのアルゴリズムを用いて解く手順を図５Ａ、図５Ｂ、図５Ｃ、図５Ｄ、図５Ｅ、及び図６の各図を参照しながら説明する。
【００５９】
まず、「イタレーション１回目」について、図５Ａの各図を参照しながら説明する。
最初に「１波目」の図に注目する。「１波目」とは始点から枝を１本だけ経由するまでの経路である。
【００６０】
始点であるＡに隣接する（１本の枝で直接結ばれている）ノードのうち、Ａからのフローが流入可能であるノードは、フローの向きを考慮すると、Ｃ又はＤである。このとき、ＡからＣへの枝の容量を考慮すると、ＡからＣへ流し得るフロー量は「３」である。ここでは、このフロー量「３」のフローがＣに流入すると仮定する。また、同様に、ＡからＤへのフローによって、フロー量「３」のフローがＤに流入すると仮定する。
【００６１】
次に「２波目」の図に注目する。「２波目」とは始点から枝を２本経由するまでの経路である。
まずＣについて考える。Ｃに隣接するノードのうち、ＡからＣに流入したフローが流入可能であるノードはＢのみである。このとき、ＣからＢへの枝の容量を考慮すると、Ｃに流入したフローのうちＢへ流し得るフロー量は「３」である。ここでは、このフロー量「３」のフローがＢに流入すると仮定する。
【００６２】
前述したように、エドモンズ・カープのアルゴリズムでは、経路の探索を幅優先探索により行う。従って、次に行う経路の探索は、「２波目」で到達したＢからの経路の探索ではなく、「１波目」で到達したノードのうち、経路の探索を未だ行っていないＤからの経路の探索となる。
【００６３】
Ｄに隣接するノードのうち、ＡからＤに流入したフローが流入可能であるノードとしてはＥとＦとがある。
まずＥについて検討する。ＤからＥへの枝の容量を考慮すると、Ｄに流入したフローのうちＥへ流し得るフロー量は「２」である。ここでは、このフロー量「２」のフローがＥに流入すると仮定する。
【００６４】
次にＦについて検討する。Ｄに流入したフロー量を考慮すると、Ｄに流入したフローのうちＦへ流し得るフロー量は「３」である。ここでは、このフロー量「３」のフローがＦに流入すると仮定する。
【００６５】
次に「３波目」の図に注目する。「３波目」とは始点から枝を３本経由するまでの経路である。
まずＢについて考える。Ｂに隣接するノードのうち、ＡからＣを経由してＢに流入したフローが流入可能であるノードはＡ、Ｄ、及びＥである。ここでは、Ｂからフロー量「３」のフローがＡに流入すると仮定し、Ｂからフロー量「１」のフローがＤに流入すると仮定し、Ｂからフロー量「２」のフローがＥに流入すると仮定する。
【００６６】
次に、「２波目」で到達したノードのうち、経路の探索を未だ行っていないＥについて考える。Ｅに隣接するノードのうち、ＡからＤを経由してＥに流入したフローが流入可能であるノードはＣ又はＧである。このうち、Ｃについては、ＥからＣへの枝の容量を考慮して、フロー量「１」のフローがＣに流入すると仮定する。
【００６７】
次にＧについて考える。ここで注目すべきは、このＧが終点であることである。つまり、ここまでの経路探索によって、始点であるＡから流出したフローが終点であるＧに到達する。この結果、「イタレーション１回目」の経路探索は終了する。なお、このとき、ＡからＤ及びＥを経由してＧに流入し得るフロー量は、ＥからＧへの枝の容量を考慮すると、「１」である。この結果、ＡからＤ及びＥを経由してＧに流入する、フロー量「１」のフローが形成される。「バックトレース」の図は、この「イタレーション１回目」の経路探索によって発見された経路を太線の矢印で示したものである。なお、この図では、この経路を構成している各枝のフローの量が「１」と表示されている。
【００６８】
次に、「イタレーション２回目」について、図５Ｂの各図を参照しながら説明する。
最初に「１波目」の図に注目する。
始点であるＡに隣接するノードのうち、Ａからのフローが流入可能であるノードは、「イタレーション１回目」と同様、Ｃ又はＤである。このとき、ＡからＣへ流し得るフロー量は、「イタレーション１回目」と同様に「３」であるので、このフロー量「３」のフローがＣに流入すると仮定する。
【００６９】
その一方、ＡからＤへの経路は、「イタレーション１回目」の経路探索によって発見された経路と重複しており、既にフロー量「１」のフローを流すこととしている。このため、ＡからＤに残されている、流し得るフロー量（「残余容量」と称することとする。）は、元の容量「３」から「１」を減じた値「２」となっている。このフロー量「２」のフローがＤに流入すると仮定する。
【００７０】
次に「２波目」の図に注目する。
まずＣについて考える。Ｃに隣接するノードのうち、ＡからＣに流入したフローが流入可能であるノードはＢのみであり、Ｃに流入したフローのうちＢへ流し得るフロー量は「３」であるので、このフロー量「３」のフローがＢに流入すると仮定する。
【００７１】
次に、「１波目」で到達したノードのうち、経路の探索を未だ行っていないＤについて考える。Ｄに隣接するノードのうち、ＡからＤに流入したフローが流入可能であるノードとしてはＥとＦとがある。
【００７２】
まずＥについて検討する。ＤからＥへの経路は、「イタレーション１回目」の経路探索によって発見された経路と重複しており、既にフロー量「１」のフローを流すこととしている。このため、ＤからＥの残余容量は、元の容量「２」から「１」を減じた値「１」となっている。このフロー量「１」のフローがＤに流入すると仮定する。
【００７３】
次にＦについて検討する。「イタレーション２回目」においてＤに流入したフロー量を考慮すると、Ｄに流入したフローのうちＦへ流し得るフロー量は「２」である。ここでは、このフロー量「２」のフローがＦに流入すると仮定する。
【００７４】
次に「３波目」の図に注目する。
まずＢについて考える。Ｂに隣接するノードのうち、ＡからＣを経由してＢに流入したフローが流入可能であるノードはＡ、Ｄ、及びＥである。ここでは、Ｂからフロー量「３」のフローがＡに流入すると仮定し、Ｂからフロー量「１」のフローがＤに流入すると仮定し、Ｂからフロー量「２」のフローがＥに流入すると仮定する。
【００７５】
次に、「２波目」で到達したノードのうち、経路の探索を未だ行っていないＥについて考える。Ｅに隣接するノードのうち、ＡからＤを経由してＥに流入したフローが流入可能であるノードはＣ又はＧである。但し、ＥからＧへの経路は、「イタレーション１回目」の経路探索によって発見された経路と重複しており、既にフロー量「１」のフローを流すこととしている。このため、ＥからＧの残余容量は、元の容量「１」から「１」を減じた値「０」となっている。このため、「イタレーション２回目」では、ＥからＧへの経路にフローを増加させることはできない。一方、Ｃについては、ＥからＣへの枝の容量を考慮して、フロー量「１」のフローがＣに流入すると仮定する。
【００７６】
次に、「２波目」で到達したノードのうち、経路の探索を未だ行っていないＦについて考える。Ｆに隣接するノードのうち、ＡからＤを経由してＦに流入したフローが流入可能であるノードはＧである。つまり、ここまでの経路探索によって、始点であるＡから流出したフローが終点であるＧに到達する。この結果、「イタレーション２回目」の経路探索は終了する。なお、このとき、ＡからＤ及びＦを経由してＧに流入し得るフロー量は、「イタレーション２回目」においてＤに流入したフロー量を考慮すると、「２」である。この結果、ＡからＤ及びＦを経由してＧに流入する、フロー量「２」のフローが形成される。「バックトレース」の図は、「イタレーション１回目」及び「イタレーション２回目」の経路探索によって発見された経路を太線の矢印で示したものである。なお、この図では、「イタレーション１回目」と「イタレーション２回目」との経路探索によって発見された２つの経路で共用しているＡからＤへの枝についてのフローの量が、２つの経路の各々のフロー量の合計値である「３」と表示されている。一方、「イタレーション２回目」の経路探索によって発見された経路のうち、「イタレーション１回目」の経路探索によって発見された経路では使用されていない、ＤからＦへの枝及びＦからＧへの枝については、フローの量が「２」と表示されている。
【００７７】
次の「イタレーション３回目」については、「イタレーション２回目」と同様の手順であるので、詳細な説明を省略する。この「イタレーション３回目」によって、ＡからＣ、Ｂ、Ｄ、及びＦを経由してＧに流入する、フロー量「１」のフローが形成される。図５Ｃにおける「バックトレース」の図は、「イタレーション１回目」、「イタレーション２回目」、及び「イタレーション２回目」の経路探索によって発見された経路を太線の矢印で示したものである。
【００７８】
次に、「イタレーション４回目」について、図５Ｄの各図を参照しながら説明する。
最初に「１波目」の図に注目する。
始点であるＡに隣接するノードのうち、Ａからのフローが流入可能であるノードはＣ又はＤである。但し、これまでの経路探索によって、ＡからＤへの枝の残余容量は「０」となっているため、Ａからのフローが流入可能であるノードはＣのみである。ここでは、フロー量「２」のフローがＡからＣに流入すると仮定する。
【００７９】
次に「２波目」の図に注目する。
Ｃについて考える。Ｃに隣接するノードのうち、Ａからのフローが流入可能であるノードはＢのみである。このときのＣからＢへの枝の残余容量は「２」であり、ＡからＣに流入すると仮定したフロー量と同一であるので、ここでは、フロー量「２」のフローがＣからＢに流入すると仮定する。
【００８０】
次に「３波目」の図に注目する。
Ｂについて考える。Ｂに隣接するノードのうち、ＡからＣを経由したフローが流入可能であるノードはＡ、Ｄ、及びＥであった。但し、このときのＢからＤへの枝の残余容量は「０」である。従って、ここでは、フロー量「２」のフローがＢからＡに流入すると仮定し、また、フロー量「２」のフローがＢからＥに流入すると仮定する。
【００８１】
次に「４波目」の図に注目する。
まずＡについて考えるが、このＡは始点であり、始点から終点に至る経路の探索において当該始点自体を経由する経路は不適切であるので、この経路は無効とする。
【００８２】
次にＥについて考える。Ｅに隣接するノードのうち、ＡからＣ及びＢを経由したフローが流入可能であるノードは、一見するとＣ及びＧのみであるように見えるが、ここでＥからＤに向かう経路に注目する。
【００８３】
ＥからＤに向かう経路を構成している枝の容量は「２」であり、「イタレーション３回目」までの経路探索によって、逆流の向き（ＤからＥに向かう向き）であるフロー量「１」のフローが既に形成されている。このような場合には、ＥからＤに向かう方向には、この逆流を相殺する量のフロー、すなわちフロー量「１」のフローを流し得ると見ることができる。このように考えると、Ｅに隣接するノードのうち、ＡからＣ及びＢを経由したフローが流入可能であるノードは、Ｃ及びＧに加えて、Ｄも存在することが分かる。
【００８４】
なお、ＥからＧへの枝の残余容量は既に「０」となっているため、ＡからＣ及びＢを経由したフローをＥからＧへ流すことはできない。よって、ここでは、Ｅからフロー量「１」のフローがＣに流入すると仮定し、更に、Ｅからフロー量「１」のフローがＤに流入すると仮定する。
【００８５】
次に「５波目」の図に注目する。
まずＣについて考えるが、「イタレーション４回目」のここまでの経路は、Ａ→Ｃ→Ｂ→Ｅ→Ｃとなり、Ｃにおいて経路が環状になってしまう。このような環状経路は不適切であるので、この経路は無効とする。
【００８６】
次にＤについて考える。Ｄに隣接するノードのうち、ＡからＣ、Ｂ、及びＥを経由したフローが流入可能であるノードは、Ａ及びＦがあるが、ＤからＡへの枝の残余容量は既に「０」となっているため、ここでは、Ｄからフロー量「１」のフローがＦに流入すると仮定する。
【００８７】
次に「６波目」の図に注目する。
Ｆに隣接するノードのうち、ＡからＣ、Ｂ、Ｅ、及びＤを経由したフローが流入可能であるノードは、Ｇである。つまり、ここまでの経路探索によって、始点であるＡから流出したフローが終点であるＧに到達する。この結果、「イタレーション４回目」の経路探索は終了する。この結果、ＡからＣ、Ｂ、Ｅ、Ｄ、及びＦを経由してＧに流入する、フロー量「１」のフローが形成される。「バックトレース」の図は、「イタレーション１回目」から「イタレーション４回目」の経路探索によって発見された経路を太線の矢印で示したものである。
【００８８】
次に、「イタレーション５回目」について、図５Ｅの各図を参照しながら説明する。
この「イタレーション５回目」では、「１波目」から「３波目」までの手順により、Ａ→Ｃ→Ｂ→Ａ及びＡ→Ｃ→Ｂ→Ｅまでの経路の探索が行われるが、次の「４波目」の手順において、これに続く適切な経路が存在しない（飽和する）ことが判明する。この結果、「イタレーション５回目」が終了すると共に、経路の探索が全て終了する。
【００８９】
以上までの経路探索の反復により発見された経路を図６に示す。図６における「結果」の図は、最終的に発見されたフローを表しており、図４に例示したフローネットワークについての最大フロー問題の解である。
【００９０】
配線設計支援装置１では、フローネットワーク作成部１４が作成したフローネットワークに対し、フロー経路探索部１５が、以上までに説明したエドモンズ・カープのアルゴリズムを利用した最大フローの経路の探索を行う。
【００９１】
次に、この配線設計支援装置１が行う、配線経路の自動設計手順の概要を、図面を用いて説明する。
まず、フローネットワークの作成について、図７及び図８を参照しながら説明する。
【００９２】
最初に、有向グラフ定義部１１が、格子点をノードとし、隣接する格子点間を結ぶ線分を枝とする有向グラフを、プリント配線板における、配線経路を作成する対象領域面上に定義する。図７は、有向グラフ定義部１１が対象領域面上に有向グラフを定義した状態の例を表している。なお、図における丸印がノードであり、隣接する丸印を結ぶ線分が枝である。
【００９３】
なお、このとき、格子点の間隔は、この対象領域面上でのプリント配線における線幅及び配線間隔の定義に基づいて設定する。
次に、配線禁止領域情報取得部１２が、配線禁止領域情報３１を記憶装置３０から取得する。図７の例においては、配線禁止領域情報３１によって示されている配線禁止領域を、斜線が付されている矩形領域で表現している。
【００９４】
次に、結線情報取得部１３は、対象領域面上に定義されている格子点のうちで、複数の配線の各々によってそれぞれ結ばれる複数組の格子点の組の情報である結線情報を取得する。結線情報取得部１３は、この結線情報を、記憶装置３０に記憶されている論理接続情報３２と部品情報３３とから求める。
【００９５】
ここでは、結線情報取得部１３は、論理接続情報３２から、配線経路により接続を行う一対の端子を特定する情報として、第一組、第二組、第三組の計３組の情報を得たものとする。また、部品情報３３は、上記第一組の情報である一対の端子の対象領域面上の位置が、それぞれ図７の例における格子点Ａ及びＤの近傍であったものとする。また、同様に、上記第二組の情報である一対の端子が、それぞれ格子点Ｂ及びＥの近傍であり、上記第三組の情報である一対の端子が、それぞれ格子点Ｃ及びＦの近傍であったとものする。この場合、結線情報取得部１３は、結線情報として、ＡとＤとの組、ＢとＥとの組、ＣとＦとの組を獲得する。
【００９６】
次に、フローネットワーク作成部１４が、以下の手順に従ってフローネットワークの作成を行う。
まず、フローネットワーク作成部１４は、有向グラフ定義部１１が定義した有向グラフを構成している枝のうちで、配線禁止領域情報３１で示されている領域内に位置している格子点に繋がっている枝に対しフロー容量を「０」に設定する。そして、その他の枝に対しては、フロー容量を「１」に設定する。
【００９７】
フローネットワーク作成部１４は、前述の複数組の格子点の各組に属している一対の格子点に、フロー容量が「１」である枝を介してフローの始点と終点とをそれぞれ接続する。図７の例では、結線情報で示されている一対の端子のうちの一方である、格子点Ａ、Ｂ、及びＣに始点Ｓが接続され、当該一対の端子のうちの他方である、格子点Ｄ、Ｅ、及びＦに終点Ｔが接続されている。
【００９８】
なお、結線情報で示されている端子が２端子部品の端子である場合には、フローネットワーク作成部１４は、始点Ｓ及び終点Ｔを図８のように接続する。
図８の例は、結線情報取得部１３が獲得した結線情報に、格子点ＡとＧとの組が含まれており、このうちの格子点Ｇの近傍の端子が、２端子部品の一方の端子であり、その他方の端子が、格子点Ｄの近傍であった場合の例である。この場合、結線情報取得部１３は、格子点ＡとＧとの組の結線情報に、格子点Ｄを含める。
【００９９】
この図８の例の場合、フローネットワーク作成部１４は、この２端子部品についての中継ノードＪを新規に定義し、この中継ノードＪを格子点Ｇと終点Ｔとを接続する枝の途中に挿入する。なお、このときの格子点Ｇ及び終点Ｔの各々と中継ノードＪとを接続している枝のフロー容量も「１」とする。更に、フローネットワーク作成部１４は、中継ノードＪと格子点Ｄとをフロー容量が「１」である枝を介して接続する。
【０１００】
この場合には、配線設計支援装置１は格子点Ａと格子点Ｊとを結ぶ配線経路の自動設計を行う。この自動設計により得られる配線経路は、格子点Ｄ又は格子点Ｇを必ず経由する。このようにしておくと、論理接続情報３２が、格子点ＡとＧとに対応する端子を接続するというものであった場合でも、格子点Ｇを経由せずに格子点Ｄを経由して格子点Ｊに至る配線経路を見出す可能性が生じる。この配線経路は論理接続情報３２とは整合しないものになるが、このような場合には、２端子部品の配置方向を反転（１８０度回転）させるだけで、配線経路と結線情報との不整合は解消する。図８の例のような場合においては、格子点Ａから格子点Ｇに至る配線経路よりも、格子点Ａから格子点Ｄに至る配線経路の方が、経路長が短くなることは明白である。２端子部品情報交換部１７が行う端子の配置位置の情報の変更は、この２端子部品の配置方向の反転に相当するものである。
【０１０１】
なお、図８の例は、更に、格子点Ｅに対応する端子が２端子部品の一方の端子であって他方の端子が格子点Ｈに対応しており、格子点Ｅに対応する端子が２端子部品の一方の端子であって他方の端子が格子点Ｈに対応している場合を想定している。従って、フローネットワーク作成部１４は、格子点Ｅ及び格子点Ｈに接続される格子点Ｋと、格子点Ｆ及び格子点Ｉに接続される格子点Ｌとを更に設け、この格子点Ｋ及び格子点Ｌにそれぞれ終点Ｔを接続している。
【０１０２】
なお、以降は、フローネットワーク作成部１４によって図８のフローネットワークが作成されたものとして説明を続ける。
次に、フロー経路探索部１５が、フローネットワーク作成部１４が各枝について設定したフロー容量の下で始点Ｓから終点Ｔへのフロー量が最大となるフローの経路を、フローネットワーク作成部１４が作成した図８のフローネットワークから探索する。
【０１０３】
本実施例においては、フロー経路探索部１５は、この最大フローの経路の探索を、前述したエドモンズ・カープのアルゴリズムを利用して行う。図９Ａ、図９Ｂ、及び図９Ｃの各図は、エドモンズ・カープのアルゴリズムによる、図８に例示したフローネットワークにおける最大フローの経路の探索の途中の様子をそれぞれ図解したものであり、図９Ｄは、その最大フローの解である。なお、図９Ａ〜図９Ｄの各図においては、配線禁止領域、当該配線禁止領域内に位置している格子点、及び当該格子点に繋がっている枝の描画を省略した。
【０１０４】
図９Ａは、イタレーション１回目の経路探索によって発見された経路を太線の矢印で示したものであり、ここでは、始点Ｓから格子点Ａ及びＥ並びに中継ノードＫを経由して終点Ｔに至る経路が発見されたものとしている。
【０１０５】
図９Ｂは、イタレーション２回目の経路探索によって発見された経路を太線の矢印で示したものである。この図９Ｂでは、イタレーション１回目の経路探索によって発見された経路は破線の矢印で示されている。ここでは、始点Ｓから格子点Ｂ、Ａ、及びＤ並びに中継ノードＪを経由して終点Ｔに至る経路が発見されたものとしている。ここで「逆流」との文字が付されている枝は、イタレーション１回目の経路探索によって発見された経路に含まれており、その向きが１回目の向きとは逆向きであることを表している。この場合には、フロー経路探索部１５は、この逆流が発生した枝で２つの経路の流れを遮断すると共に、その枝の両端の格子点の各々で、２つの経路を接続する。この結果、始点Ｓから格子点Ａ及びＤ並びに中継ノードＪを経由して終点Ｔに至る経路と、始点Ｓから格子点Ｂ及びＥ並びに中継ノードＫを経由して終点Ｔに至る経路とが形成される。
【０１０６】
図９Ｃは、イタレーション２回目の経路探索によって発見された経路を太線の矢印で示したものである。この図９Ｃでは、イタレーション２回目までの経路探索によって発見された経路は破線の矢印で示されている。ここでは、始点Ｓから格子点Ｃ、Ｅ、及びＦ並びに中継ノードＬを経由して終点Ｔに至る経路が発見されたものとしている。但し、ここでは、図示されている２箇所の枝で逆流が発生したものとしている。フロー経路探索部１５は、この逆流が発生した枝で２つの経路の流れを遮断すると共に、その枝の両端の格子点の各々で、２つの経路を接続する。この結果、始点Ｓから格子点Ｂ及びＥ並びに中継ノードＫを経由して終点Ｔに至る経路と、始点Ｓから格子点Ｃ及びＦ並びに中継ノードＦを経由して終点Ｔに至る経路とが形成される。
【０１０７】
図９Ｄは、以上までのイタレーションによって経路の探索が全て終了して、始点Ｓから終点Ｔに至る３つの経路が発見されたこと表している。
配線経路決定部１６は、以上のようにして得られた３つの経路に従い、格子点ＡとＤとを結ぶ配線経路、格子点ＢとＥとを結ぶ配線経路、及び格子点ＣとＦとを結ぶ配線経路の３つの配線経路を、プリント配線板の対象領域面上に形成する。
【０１０８】
配線設計支援装置１は、以上のようにして配線経路の自動設計を行う。
次に、本実施例に係る配線設計支援装置１によって行われる、配線経路自動設計処理の手順の概要を、図１０Ａ及び図１０Ｂを参照しながら説明する。
【０１０９】
図１０Ａにおける（１）の図は、論理接続情報３２によって示されている、部品Ａ７１の各端子と、同一形状である複数の部品Ｂ７２の各々の端子との接続関係を破線により例示したものである。なお、部品Ａ７１は多ピン部品であり、部品Ｂは２端子部品である。ここで、部品Ａ７１と部品Ｂ７２の各々とは、プリント配線板上における部品情報３３により示されている位置に配置されている状態を表している。
【０１１０】
配線設計支援装置１の使用者が、配線経路の自動設計の開始を示している所定の指示を配線設計支援装置１に対して与えると、配線設計支援装置１は、まず、論理接続情報３２及び部品情報３３から配線対象の端子を有する部品の情報を抽出する。そして、配線によって接続される一方の端子を終点Ｔ側とし、他方の端子を始点Ｓ側とする。なお、ここで、配線設計支援装置１は、情報が抽出された部品Ｂ７２が２端子部品である場合には、２端子部品の２つの端子を終点Ｔ側とし、配線によってその部品Ｂ７２の端子に接続される相手側の部品の端子を始点Ｓ側とする。
【０１１１】
次に、配線設計支援装置１は、プリント配線板の前述の対象領域面上に前述の有向グラフを定義する。続いて、配線設計支援装置１は、配線禁止領域情報３１を取得して対象領域面上に配線禁止領域を設定し、更に、論理接続情報３２及び部品情報３３から、前述の結線情報を獲得する。図１０Ａにおける（２）の図には、この結線情報による結線対象である各格子点の位置がｘ印で表されている。
【０１１２】
次に、配線設計支援装置１は、前述のネットワークフローの作成を行い、更に、作成したネットワークフローにおいて始点Ｓから終点Ｔへのフロー量が最大となるフローの経路の探索を行う。そして、この探索結果によって得られた経路に従って配線経路をプリント配線板の対象領域面上に形成する。図１０Ａにおける（３）の図は、このようにして形成された配線経路が太線で表示されている。
【０１１３】
ここで、図１０Ａの（１）の図に破線で示されている、論理接続情報３２によって示されている接続関係と、図１０Ａの（３）の図に太線で示されている配線経路とは整合していない。但し、部品Ｂ７２はいずれも形状が同一であるので、自身の配置位置を、他の部品Ｂ７２の配置位置と交換することができる。そこで、配線設計支援装置１は、この場合に、この配線経路により接続を行う部品Ｂ７２の配置位置の情報を次々に入れ替えて、各配線で接続される端子の接続関係を、論理接続情報３２によって示されている接続関係に整合させる。２端子部品情報交換部１７が行う端子の配置位置の情報の変更は、この部品Ｂ７２の配置位置の交換に相当するものである。このようにして、論理接続情報３２によって示されている接続関係を一旦無視して配線経路を形成し、その後に論理接続情報３２との整合を取るようにすると、遅い順序での配線経路の作成のために既に配置済みの配線の経路の修正が必要となるケースが減少する。この結果、設計作業に要する時間の短縮化に寄与する。
【０１１４】
なお、配線対象の一方の経路が、前述の多連集合部品である場合には、配線経路自動設計処理は、以下のような手順で行われる。
図１０Ｂにおける（１）の図は、論理接続情報３２によって示されている、部品Ａ７１の各端子と、同一形状である複数の部品Ｃ７３の各々の端子との接続関係を破線により例示したものである。なお、部品Ａ７１は多ピン部品であり、部品Ｃ７３は多連集合部品である。ここで、部品Ａ７１と部品Ｃ７３の各々とは、プリント配線板上における部品情報３３により示されている位置に配置されている状態を表している。
【０１１５】
配線設計支援装置１の使用者が、配線経路の自動設計の開始を示している所定の指示を配線設計支援装置１に対して与えると、配線設計支援装置１は、まず、論理接続情報３２及び部品情報３３から配線対象の端子を有する部品の情報を抽出する。そして、配線によって接続される一方の端子を終点Ｔ側とし、他方の端子を始点Ｓ側とする。なお、ここで、配線設計支援装置１は、情報が抽出された部品が多連集合部品である場合には、多連集合部品の２つの端子を終点Ｔ側とし、配線によってその多連集合部品の端子に接続される相手側の部品の端子を始点Ｓ側とする。
【０１１６】
次に、配線設計支援装置１は、プリント配線板の前述の対象領域面上に前述の有向グラフを定義する。続いて、配線設計支援装置１は、配線禁止領域情報３１を取得して対象領域面上に配線禁止領域を設定し、更に、論理接続情報３２及び部品情報３３から、前述の結線情報を獲得する。図１０Ｂにおける（２）の図には、この結線情報による結線対象である各格子点の位置がｘ印で表されている。
【０１１７】
次に、配線設計支援装置１は、前述のネットワークフローの作成を行い、更に、作成したネットワークフローにおいて始点Ｓから終点Ｔへのフロー量が最大となるフローの経路の探索を行う。そして、この探索結果によって得られた経路に従って配線経路をプリント配線板の対象領域面上に形成する。図１０Ｂにおける（３）の図は、このようにして形成された配線経路が太線で表示されている。
【０１１８】
ここで、図１０Ｂの（１）の図に破線で示されている、論理接続情報３２によって示されている接続関係と、図１０Ｂの（３）の図に太線で示されている配線経路とは整合していない。但し、部品Ｃ７３はいずれも形状が同一であり、更に、多連集合部品である部品Ｃ７３を構成している複数の２端子素子の素子値も同一である。従って、配線による接続先の部品Ｃ７３の端子を、自身の他の２端子素子の端子、若しくは他の部品Ｃ７３の２端子素子の端子と交換することができる。多連集合部品情報交換部１８が行う端子の配置位置の情報の変更は、この部品Ｃ７３を構成する２端子素子の他の２端子素子への交換に相当するものである。このようにして、論理接続情報３２によって示されている接続関係を一旦無視して配線経路を形成し、その後に論理接続情報３２との整合を取るようにすると、遅い順序での配線経路の作成のために既に配置済みの配線の経路の修正が必要となるケースが減少する。この結果、設計作業に要する時間の短縮化に寄与する。
【０１１９】
以下、配線設計支援装置１によって行われる配線経路自動設計処理の具体的な処理内容について説明する。
まず図１１について説明する。図１１は、配線経路自動設計処理の処理内容を図解したフローチャートである。この処理は、配線設計支援装置１の使用者（以下、単に「使用者」と称することとする。）がマウス装置４２やキーボード装置４３を操作して行われる所定の実行開始指示をＭＰＵ１０が検出すると開始される。
【０１２０】
図１１において、まず、Ｓ１１では、使用者がマウス装置４２やキーボード装置４３を操作して入力される、自動配線を行わせるプリント配線板上の配線対象領域及び配線層を特定する指示を取得する処理が行われる。
【０１２１】
次に、Ｓ１００において、有向グラフ定義処理をＭＰＵ１０の有向グラフ定義部１１が行う。
次に、Ｓ２００において、配線禁止領域情報取得処理をＭＰＵ１０の配線禁止領域情報取得部１２が行う。
【０１２２】
次に、Ｓ３００において、結線情報取得処理をＭＰＵ１０の結線情報取得部１３が行う。
次に、Ｓ４００において、フローネットワーク作成処理をＭＰＵ１０のフローネットワーク作成部１４が行う。
【０１２３】
次に、Ｓ５００において、フロー経路探索処理をＭＰＵ１０のフロー経路探索部１５が行う。
次に、Ｓ６００において、配線経路決定処理をＭＰＵ１０の配線経路決定部１６が行う。
【０１２４】
次に、Ｓ７００において、２端子部品情報交換処理及び多連集合部品情報交換処理をＭＰＵ１０が行う。ここで、２端子部品情報交換処理は、配線対象の端子が２端子部品のもの若しくは多連集合部品のものである場合にＭＰＵ１０の２端子部品情報交換部１７により行われる処理である。また、多連集合部品情報交換処理は、配線対象の端子が多連集合部品のものである場合にＭＰＵ１０の多連集合部品情報交換部１８により行われる処理である。
【０１２５】
以上のＳ７００までの処理を終えると、図１１の配線経路自動設計処理が終了する。
次に、図１１におけるＳ１００からＳ７００までの各処理の詳細について説明する。
まず、図１１のＳ１００の処理である有向グラフ定義処理を説明する。図１２は、有向グラフ定義処理の処理内容を図解したフローチャートである。
【０１２６】
図１２のフローチャートを説明する前に、まず、この有向グラフ定義処理においてのノード及び枝の定義の手法について、図１３を用いて説明する。
この有向グラフ定義処理では、各格子点について、格子点にフローが流入する向きである入力専用のノード（入力ノード）、及び、格子点からフローが流出する向きである出力専用のノード（出力ノード）、並びに、入力ノードと出力ノードとを結ぶ枝を定義する。更に、この処理では、隣接する２つの格子点間を結ぶ枝として、その一方の格子点の出力ノードとその他方の格子点の入力ノードとを結ぶ枝、及び、当該他方の格子点の出力ノードと当該一方の格子点の入力ノードとを結ぶ枝とを定義する。図１３は、この定義を図解したものである。
【０１２７】
図１３において、左側の図は、有向グラフ定義処理により定義されるプリント配線板上の配線対象領域上に定義された有向グラフの例である。また、右側の図は、この左側の図において破線の矩形で囲まれている領域を拡大したものである。
【０１２８】
この右側の図において、破線の円が格子点を表している。また、この破線円内に配置されている、ｘ印及び丸印が付されている円が、有向グラフ定義処理により定義される入力ノード及び出力ノードをそれぞれ表している。なお、この右側の図における双方向の矢印は、有向グラフ定義処理により定義される枝を表している。
【０１２９】
図１２の説明を始める。まず、Ｓ１０１において、有向グラフ定義部１１は、プリント配線板上の配線対象領域上に格子を定義し、この格子における各格子点に、入力ノードと出力ノードとを設定する処理を行う。
【０１３０】
次に、Ｓ１０２において、有向グラフ定義部１１は、隣接する格子点間において、入力ノードと出力ノードとを結ぶ枝を設定する処理を行う。このとき、枝で結ばれたノード間の一方から、その他方のノードが特定できるようにしておく。
【０１３１】
次に、Ｓ１０３において、有向グラフ定義部１１は、Ｓ１０１の処理で格子点毎に設定した入力ノードと出力ノードとを結ぶ枝を設定する処理を行う。このとき、枝で結ばれたノード間の一方から、その他方のノードが特定できるようにしておく。
【０１３２】
以上の処理を終えると、有向グラフ定義処理が終了する。
ここで図１４Ａ及び図１４Ｂについて説明する。図１４Ａは、上述した有向グラフ定義処理により作成されるノード情報テーブル８１のデータ構造を表しており、図１４Ｂは、有向グラフ定義処理により作成される枝情報テーブル８２のデータ構造を表している。
【０１３３】
図１４Ａに表されているように、ノード情報テーブル８１は、「番号」、「座標」、「枝数」、「枝番号」の各項目のデータを対応付けたテーブルである。ここで、「番号」には、有向グラフ定義部１１が設定したノードを識別する番号が格納される。また、「座標」には、このノードが設定された格子点についての、プリント配線板上の配線対象領域上の位置を特定する座標データが格納される。「枝数」には、このノードから流出する向きの枝の本数のデータが格納される。また、「枝番号」には、このノードから流出する向きである各枝を特定するデータが格納される。
【０１３４】
なお、ノード情報テーブル８１において、「番号」が『Ｓ』『Ｃ』『Ｔ』である行のデータは、後述するフローネットワーク作成処理によってノード情報テーブル８１に追加される。
【０１３５】
図１４Ｂに表されているように、枝情報テーブル８２は、「番号」、「ノード情報」、及び「容量」の各項目のデータを対応付けたテーブルである。ここで、「番号」には、有向グラフ定義部１１が設定した枝を識別する番号データが格納される。なお、この番号データが、ノード情報テーブル８１における「枝番号」の項目に使用される。「ノード情報」には、この枝が向かう流入先のノードを特定するデータが格納される。この項目のデータには、ノード情報テーブル８１における「番号」データの番号が使用される。なお、「容量」には、この枝の容量データが格納されるが、その値は、後述するフローネットワーク作成処理によって設定される。
【０１３６】
図１２の有向グラフ定義処理では、まず、Ｓ１０１の処理によってノード情報テーブル８１の各レコードを生成して「番号」及び「座標」のデータを格納する処理が行われる。続くＳ１０２及びＳ１０３の処理では、枝情報テーブル８２の各レコードをまず生成して「番号」及び「ノード情報」のデータが格納され、次に、ノード情報テーブル８１の「枝番号」のデータが格納される。
【０１３７】
次に、図１１のＳ２００の処理である配線禁止領域情報取得処理を説明する。図１５は、配線禁止領域情報取得処理の処理内容を図解したフローチャートである。
図１５のＳ２０１では、配線禁止領域情報３１を取得して、配線禁止領域情報３１で示されている配線禁止領域内に位置している格子点に有向グラフ定義部１１が設定していたノードを特定する処理を配線禁止領域情報取得部１２が行う。この処理を終えると、配線禁止領域情報取得処理が終了する。
【０１３８】
ここで図１６について説明する。図１６は、上述した配線禁止領域情報取得処理により作成される使用禁止ノードテーブル８３のデータ構造を表している。
図１６に表されているように、使用禁止ノードテーブル８３は、「ノード番号」データを有している。この「ノード番号」データは、配線禁止領域情報３１で示されている配線禁止領域内に位置している格子点に有向グラフ定義部１１が設定していたノードを特定するデータである。なお、このデータは、当該ノードについてノード情報テーブル８１で設定されている「番号」データが格納される。
【０１３９】
図１５のＳ２０１では、配線禁止領域情報３１で示されている領域内に位置している格子点に有向グラフ定義部１１が設定していたノードについての「番号」データを、使用禁止ノードテーブル８３に格納する処理が配線禁止領域情報取得部１２により行われる。
【０１４０】
次に、図１１のＳ３００の処理である結線情報取得処理を説明する。図１７は、結線情報取得処理の処理内容を図解したフローチャートである。
図１７において、まず、Ｓ３０１では、論理接続情報３２及び部品情報３３を取得すると共に、これらの情報に基づいて、自動設計を行う配線による接続対象である各端子のプリント配線板上での位置を取得する処理を結線情報取得部１３が行う。
【０１４１】
次に、Ｓ３０２において、ノード情報テーブル８１を参照し、Ｓ３０１の処理で取得した各端子の位置に最も近い格子点の入力ノードを特定し、特定した入力ノードと端子との対応関係情報を生成する処理を結線情報取得部１３が行う。
【０１４２】
ここで図１８について説明する。図１８は、この結線情報取得処理により作成される端点要素引き当てテーブル８４のデータ構造を表している。端点要素引き当てテーブル８４は、上述した入力ノードと各端子との対応関係が表されてるテーブルである。
【０１４３】
図１８に表されているように、端点要素引き当てテーブル８４は、「ノード番号」、「部品ピン名」、「組番号」、「接続名」、及び「反転」の各項目のデータを対応付けたテーブルである。
【０１４４】
「部品ピン名」には、自動設計を行う配線による接続対象である端子を特定するデータが格納される。なお、このデータは、論理接続情報３２の「始点ピン名」及び「終点ピン名」の項目の情報である。
【０１４５】
「ノード番号」には、「部品ピン名」で特定される端子の位置に最も近い格子点に設定されている入力ノードを特定するデータが格納される。なお、このデータには、当該ノードについてノード情報テーブル８１で設定されている「番号」データが使用される。
【０１４６】
「組番号」には、「部品ピン名」で特定される端子を有している部品を、他の部品と区別するためのデータが格納される。図１８の例では、第１行から第５行までの各端子は、いずれも「組番号」データが『０』であるので、全て同一の部品（「ＬＳＩ１」）が有している端子であることを表している。
【０１４７】
「接続名」には、「部品ピン名」に示されている端子名について論理接続情報３２において対応付けられている「接続名」の項目の情報が格納される。なお、この「接続名」の情報の格納は、後述する配線経路決定処理によって行われ、情報が格納されるまでは空白（ヌルデータ）としておく。
【０１４８】
図１７の結線情報取得処理では、Ｓ３０２の処理によって特定された入力ノード毎に端点要素引き当てテーブル８４の各レコードが作成されて、「ノード番号」と「部品ピン名」とが対応付けられて対応関係情報が表される。また、「組番号」及び「接続名」の項目のデータについては、論理接続情報３２のデータに基づいて結線情報取得部１３が生成して格納する。
【０１４９】
なお、端点要素引き当てテーブル８４における「反転」の項目には、初期値として値「０」が格納されるが、これより説明する図１７のＳ３０３及びＳ３０４の処理により、値「１」が格納される。
【０１５０】
図１７の説明に戻る。Ｓ３０３の処理は、Ｓ３０１の処理で取得した端子が２端子部品の一方の端子であった場合に行われる処理である。この場合に、結線情報取得部１３は、まず、当該２端子部品の他方の端子のプリント配線板上での位置を取得する。そして次に、ノード情報テーブル８１を参照して、当該他方の端子の位置に最も近い格子点の入力ノードを特定し、特定した入力ノードと当該他方の端子との対応関係情報を生成する処理を行う。この処理により、端点要素引き当てテーブル８４にレコードが追加されて、「ノード番号」と「部品ピン名」とが対応付けられて対応関係情報が表される。また、「組番号」及び「接続名」の項目のデータについては、論理接続情報３２のデータに基づいて結線情報取得部１３が生成して格納する。更に、このＳ３０３の処理では、端点要素引き当てテーブル８４における当該他方の端子についてのレコードの「反転」の項目の値を「１」に設定する処理を結線情報取得部１３が行う。
【０１５１】
次に、Ｓ３０４の処理は、Ｓ３０１の処理で取得した端子が多連集合部品を構成している２端子素子の一方の端子であった場合に行われる処理である。この場合に、結線情報取得部１３は、まず、当該２端子素子の他方の端子のプリント配線板上での位置を取得する。そして次に、ノード情報テーブル８１を参照して、当該他方の端子の位置に最も近い格子点の入力ノードを特定し、特定した入力ノードと当該他方の端子との対応関係情報を生成する処理を行う。この処理により、端点要素引き当てテーブル８４にレコードが追加されて、「ノード番号」と「部品ピン名」とが対応付けられて対応関係情報が表される。また、「組番号」及び「接続名」の項目のデータについては、論理接続情報３２のデータに基づいて結線情報取得部１３が生成して格納する。更に、このＳ３０４の処理では、端点要素引き当てテーブル８４における当該他方の端子についてのレコードの「反転」の項目の値を「１」に設定する処理を結線情報取得部１３が行う。
【０１５２】
以上の処理を終えると、結線情報取得処理が終了する。
次に、図１１のＳ４００の処理であるフローネットワーク作成処理を説明する。図１９は、フローネットワーク作成処理の処理内容を図解したフローチャートである。
【０１５３】
図１９において、Ｓ４０１からＳ４０３にかけての処理は、有向グラフ定義部１１により定義された有向グラフの各枝に対してフロー容量を設定する処理である。なお、このフロー容量の設定は、枝情報テーブル８２の「容量」の項目に対して行われる。
まず、Ｓ４０１では、有向グラフの枝のうちの同一格子点内（すなわち、枝情報テーブル８２の「座標」データが一致）での入力ノードから出力ノードに向かう全ての枝に対して、フロー容量を「１」に設定する処理をフローネットワーク作成部１４が行う。なお、入力ノードは、ノード情報テーブル８１において「枝数」データが『１』であるノードであり、出力ノードは、「枝数」データが『１』ではないノードである。
【０１５４】
次に、Ｓ４０２では、有向グラフの枝のうちの隣接する格子点間での出力ノードから入力ノードに向かう全ての枝に対して、フロー容量を「１」に設定する処理をフローネットワーク作成部１４が行う。
【０１５５】
図２０Ａは、図１３の右側の図の有向グラフに対して、上述したＳ４０１及びＳ４０２の処理を行った結果を模式的に表した図である。以上までの処理によって、ノード間を結ぶ全ての枝に対して、この図に表されている矢印の向きにフロー容量「１」が設定される。
【０１５６】
次に、Ｓ４０３では、使用禁止ノードテーブル８３を参照し、使用禁止ノードテーブル８３に「ノード番号」が格納されているノードを結んでいる全ての枝のフロー容量を「０」に設定する処理をフローネットワーク作成部１４が行う。この処理により、配線禁止領域内を経由する経路が、自動設計される配線経路の候補から除外される。
【０１５７】
次に、Ｓ４０４では、有向グラフ定義部１１により定義された有向グラフに対し、フローの始点であるＳノードとフローの終点であるＴノードとの定義を追加する処理をフローネットワーク作成部１４が行う。この定義の追加は、ノード情報テーブル８１に対して、「番号」がそれぞれＳ及びＴである２つのレコードを追加することによって行われる。
【０１５８】
次に、Ｓ４０５では、Ｓノードから、格子点間の経路探索を行う一対の格子点の組のうちの一方に含まれる入力ノードに向かう枝を、当該組毎に作成する処理をフローネットワーク作成部１４が行う。フローネットワーク作成部１４は、このときに、論理接続情報３２における「始点ピン名」を、端点要素引き当てテーブル８４の「部品ピン名」から探索する処理を行う。そして、この探索処理により見つかった「部品ピン名」について端点要素引き当てテーブル８４において対応付けられている「ノード番号」で特定されるノードを、Ｓノードと結ぶ処理を行う。この処理は、Ｓノードからノードに向いている、フロー容量が「１」の枝のレコードを枝情報テーブル８２に追加すると共に、この枝を特定する番号を、ノード情報テーブル８１のＳノードのレコードにおける「枝番号」に追加する処理である。
【０１５９】
次に、Ｓ４０６では、格子点間の経路探索を行う一対の格子点の組のうちの一方に含まれる出力ノードからＴノードに向かう枝を、当該組毎に作成する処理をフローネットワーク作成部１４が行う。フローネットワーク作成部１４は、このときに、論理接続情報３２における「終点ピン名」を、端点要素引き当てテーブル８４の「部品ピン名」から探索する処理を行う。そして、この探索処理により見つかった「部品ピン名」について端点要素引き当てテーブル８４において対応付けられている「ノード番号」で特定されるノードを、Ｔノードと結ぶ処理を行う。この処理は、このノードからＴノードに向いている、フロー容量が「１」の枝のレコードを枝情報テーブル８２に追加すると共に、この枝を特定する番号を、ノード情報テーブル８１のＴノードのレコードにおける「枝番号」に追加する処理である。
【０１６０】
Ｓ４０７の処理は、論理接続情報３２における「終点ピン名」が、２端子部品の端子であった場合にフローネットワーク作成部１４が行う処理である。
この処理では、まず、２端子部品における２つの端子にそれぞれ対応するノードの「ノード番号」を端点要素引き当てテーブル８４から探し出す処理が行われる。次に、有向グラフ定義部１１により定義された有向グラフに対し、当該２端子部品についての中継ノードＣの定義を追加する処理が行われる。そして、当該２端子部品の２つの端子に対応する２つのノードからそれぞれＴノードへ向かう枝に、中継ノードＣを挿入する処理が行われる。この挿入の処理は、当該２端子部品の一方の端子及び他方の端子に対応する２つのノードからＴノードへ向かう枝の向きを中継ノードＣに変更すると共に、中継ノードＣからＴノードへ向かう、フロー容量が「１」の枝を追加する処理である。図２０Ｂは、この処理により中継ノードＣが挿入された有向グラフの例を図解したものである。
【０１６１】
このＳ４０７の処理では、フローネットワーク作成部１４は、具体的には、以下の処理を行う。まず、フローネットワーク作成部１４は、枝情報テーブル８２に対し中継ノードＣからノードかに向かう枝のレコードを追加すると共に、ノード情報テーブル８１に対し、「番号」がＣであり当該枝を「枝番号」に含むレコードを追加する処理を行う。次に、ノード情報テーブル８１において、２端子部品の２つの端子にそれぞれ対応している２つのノードの「ノード番号」に対応付けられている「枝番号」について、枝情報テーブル８２のレコードを参照する。そして、「ノード情報」が『Ｔ』であるものを見つけ出し、これを『Ｔ』から『Ｃ』に変更する。
【０１６２】
以上の処理を終えると、フローネットワーク作成処理が終了する。
次に、図１１のＳ５００の処理であるフロー経路探索処理を説明する。図２１Ａ及び図２１Ｂは、フロー経路探索処理の処理内容を図解したフローチャートである。また、図２２は、このフロー経路探索処理で使用する各種データテーブルのデータ構造を表している。
【０１６３】
図２１Ａにおいて、まず、Ｓ５０１では、枝情報テーブル８２のレコード数と同数のサイズの枝使用量テーブル８５を作成し、この枝使用量テーブル８５の全ての枝についての「使用量」を『０』に設定する処理をフロー経路探索部１５が行う。
【０１６４】
図２２に示されているように、枝使用量テーブル８５は、「番号」と「使用量」との両項目のデータを対応付けたテーブルである。ここで、「番号」には、枝情報テーブル８２において各枝の識別に用いられている「番号」が格納される。また、「使用量」には、「番号」で特定される枝に流すこととしている流量が格納される項目であり、このＳ５０１の処理により、初期値として『０』が設定される。
【０１６５】
次に、Ｓ５０２では、変数Ｐに初期値『０』を代入する処理をフロー経路探索部１５が行う。
Ｓ５０３は、図２１ＢのＳ５１７と対になって処理のループを表している。フロー経路探索部１５は、変数Ｐの値が自動設計を行う配線の数（すなわち、論理接続情報３２のレコード数）に達するまで、Ｓ５０４から図２１ＢのＳ５１６までの処理を繰り返す。このＳ５０４からＳ５１６までの処理が、エドモンズ・カープのアルゴリズムにおけるイタレーションの１回分に対応する。
【０１６６】
Ｓ５０４では、フロー経路探索部１５は以下の処理を行う。
まず、フロー経路探索部１５は、待ち行列が空である経路探索用キューテーブル８６を作成し、この経路探索用キューテーブル８６に、Ｓノードを表す『Ｓ』を入れる処理を行う。経路探索用キューテーブル８６は先入れ先出し（First In First Out）の待ち行列のテーブルである。図２２に示されているように、経路探索用キューテーブル８６には、「ノード番号」のデータとして、ノード情報テーブル８１において各ノードの識別に用いられている「番号」が格納される。
【０１６７】
次に、フロー経路探索部１５は、ノード情報テーブル８１のレコード数と同数のサイズの参照元ノード管理テーブル８７を作成する処理をフロー経路探索部１５が行う。
参照元ノード管理テーブル８７は、経路の探索において、あるノードに到達した経路がそのノードの直前に経由したノード（「参照元ノード」と称することとする。）を管理するテーブルである。図２２に示されているように、参照元ノード管理テーブル８７は、「番号」と「参照元ノード番号」との両項目のデータを対応付けたテーブルであり、そのどちらにも、ノード情報テーブル８１において各ノードの識別に用いられている「番号」が格納される。ここで、「参照元ノード番号」には、参照元ノード管理テーブル８７における同一レコードの「番号」データで特定されるノードについての参照元ノードを特定するデータが格納される。
【０１６８】
次に、フロー経路探索部１５は、参照元ノード管理テーブル８７の「参照元ノード番号」の項目に初期値を代入する処理を行う。具体的には、フロー経路探索部１５は、まず、参照元ノード管理テーブル８７におけるＳノードのレコード（「番号」が『Ｓ』であるレコード）における「参照元ノード番号」を『Ｓ』に設定する。Ｓノードはフローの始点であって参照元ノードが存在しないので、自分自身を参照元ノードと定義することにしたためである。次に、フロー経路探索部１５は、参照元ノード管理テーブル８７におけるＳノード以外のレコードを、初期値として、今回のイタレーションで探索中の経路では当該ノードを経由しないことを表す『０』に設定する。
【０１６９】
フロー経路探索部１５は、Ｓ５０４において以上の処理を行う。
次のＳ５０５は、図２１ＢのＳ５１３と対になって処理のループを表している。フロー経路探索部１５は、経路探索用キューテーブル８６が空になるまで、Ｓ５０６から図２１ＢのＳ５１２までの処理を繰り返す。
【０１７０】
まず、Ｓ５０６では、経路探索用キューテーブル８６から「ノード番号」を先出しして取得する処理をフロー経路探索部１５が行う。この処理により取得されたノード番号で特定されるノードを「ノードＮ」とする。
【０１７１】
次のＳ５０７は、図２１ＢのＳ５１２と対になって処理のループを表している。フロー経路探索部１５は、ノード情報テーブル８１におけるノードＮについてのレコードを参照して、ノードＮから流出する向きの各枝の「枝番号」のデータを取得し、この各枝について、Ｓ５０８からＳ５１１までの処理を行う。なお、Ｓ５０８からＳ５１１までの処理の説明では、処理の対象とする枝を「枝Ｅ」とする。
【０１７２】
Ｓ５０８では、フロー経路探索部１５は以下の処理を行う。
まず、フロー経路探索部１５は、枝情報テーブル８２における枝Ｅについてのレコードを参照し、枝Ｅが向かう流入先のノードの「ノード情報」のデータを取得する処理を行う。この「ノード情報」のデータで特定されるノードを「ノードＯ」とする。
【０１７３】
次に、フロー経路探索部１５は、参照元ノード管理テーブル８７におけるノードＯについてのレコードを参照し、このレコードにおける「参照元ノード番号」が、初期値である『０』のままであるか否かを判定する処理を行う。ここで、フロー経路探索部１５は、「参照元ノード番号」が『０』であると判定したとき（判定結果がＹｅｓのとき）にはＳ５０９に処理を進める。一方、フロー経路探索部１５は、「参照元ノード番号」が『０』ではなく、ノードＯについての参照元のノードの番号が既に示されていると判定したとき（判定結果がＮｏのとき）には、図２１ＢのＳ５１２に処理を進める。
【０１７４】
Ｓ５０９では、参照元ノード管理テーブル８７のノードＯのレコードにおける「参照元ノード番号」に、今回のイタレーションでの経路探索におけるノードＯについての参照元ノードである、ノードＮを特定する番号を設定する処理をフロー経路探索部１５が行う。
【０１７５】
次に、Ｓ５１０では、枝情報テーブル８２における枝Ｅについてのレコードの「容量」の値から、枝使用量テーブル８５における枝Ｅについてのレコードの「使用量」の値を減算した結果の値が正の値であるか否かを判定する処理をフロー経路探索部１５が行う。ここで、フロー経路探索部１５は、減算結果の値が正の値であり、今回のイタレーションでの探索によるフローを枝Ｅに流すことが可能であると判定したとき（判定結果がＹｅｓのとき）にはＳ５１１に処理を進める。一方、フロー経路探索部１５は、ここで、減算結果の値が正の値ではなく、今回のイタレーションで枝Ｅにフローをこれ以上流すことはできないと判定したとき（判定結果がＮｏのとき）には、図２１ＢのＳ５１２に処理を進める。
【０１７６】
次に、Ｓ５１１では、ノードＯを特定する番号を、経路探索用キューテーブル８６に入れる処理をフロー経路探索部１５が行う。この結果、ノードＯに続く経路の探索が、後に繰り返されるＳ５０６から図２１ＢのＳ５１２までの処理により行われるようになる。
【０１７７】
図２１Ｂに処理が進み、Ｓ５１２では、図２１ＡのＳ５０７と対になって表されている処理のループを終了するか否かを判定する処理をフロー経路探索部１５が行う。フロー経路探索部１５は、ここで、ノードＮから流出する向きの全ての枝について、このループ内の処理を済ませたと判定したときには、この処理のループを終了してＳ５１３に処理を進める。
【０１７８】
次に、Ｓ５１３では、図２１ＡのＳ５０５と対になって表されている処理のループを終了するか否かを判定する処理をフロー経路探索部１５が行う。フロー経路探索部１５は、ここで、経路探索用キューテーブル８６が空であると判定したときには、この処理のループを終了してＳ５１４に処理を進める。
【０１７９】
次に、Ｓ５１４では、参照元ノード管理テーブル８７を参照し、Ｔノードについての「参照元ノード番号」が、初期値である『０』のままであるか否かを判定する処理をフロー経路探索部１５が行う。フロー経路探索部１５は、ここで、Ｔノードについての「参照元ノード番号」が『０』であると判定したとき（判定結果がＹｅｓのとき）には、ＳノードからＴノードに至る配線経路が必要数発見できなかったとして、このフロー経路探索処理を直ちに終了する。一方、フロー経路探索部１５は、ここで、Ｔノードについての「参照元ノード番号」が『０』ではないと判定したとき（判定結果がＮｏのとき）には、今回のイタレーションで経路が発見できたとして、Ｓ５１５に処理を進める。
【０１８０】
次に、Ｓ５１５では、フロー経路探索部１５は以下の処理を行う。
まず、フロー経路探索部１５は、参照元ノード管理テーブル８７を参照してＴノードについての参照元ノードからＳノードに至るまでの経路を逆向きに辿り、その経路を構成する各枝を特定する番号を、枝情報テーブル８２から取得する処理を行う。次に、フロー経路探索部１５は、枝使用量テーブル８５を参照し、枝情報テーブル８２から取得した各枝についての「使用量」の値を変更する処理を行う。ここで、各枝のうち、入力ノードから出力ノードに向かう枝についての「使用量」は、その枝についての現在の「使用量」の値に『１』を加算した値とする。一方、出力ノードから入力ノードに向かう枝についての「使用量」は、その枝についての現在の「使用量」の値から『１』を減算した値とする。
【０１８１】
次に、Ｓ５１６では、変数Ｐの現在の値に『１』を加算した結果の値を改めて変数Ｐに代入する処理をフロー経路探索部１５が行う。
次に、Ｓ５１７では、図２１ＡのＳ５０３と対になって表されている処理のループを終了するか否かを判定する処理をフロー経路探索部１５が行う。フロー経路探索部１５は、ここで、変数Ｐの値が自動設計を行う配線数に達したと判定したときには、この処理のループを終了する。この処理のループが終了すると、フロー経路探索処理が終了する。
【０１８２】
次に、図１１のＳ６００の処理である配線経路決定処理を説明する。図２３Ａ及び図２３Ｂは、配線経路決定処理の処理内容を図解したフローチャートである。
図２３Ａにおいて、Ｓ６０１は、図２３ＢのＳ６１６と対になって処理のループを表している。配線経路決定部１６は、ノード情報テーブル８１におけるＳノードについてのレコードを参照して、Ｓノードから流出する向きの各枝の「枝番号」のデータを取得し、この各枝について、Ｓ６０２からＳ６１５までの処理を行う。なお、Ｓ６０２からＳ６１５までの処理の説明では、Ｓノードについての上記のレコードの「枝番号」のデータで特定される枝を「枝Ｅ」とする。
【０１８３】
Ｓ６０２では、枝使用量テーブル８５を参照し、枝Ｅについてのレコードの「使用量」の値が『１』よりも小さいか否かを判定する処理を配線経路決定部１６が行う。ここで、配線経路決定部１６は、この「使用量」の値が『１』よりも小さく、枝Ｅにその向きのフローをこれ以上流すことができないと判定したとき（判定結果がＹｅｓのとき）には、図２３ＢのＳ６１６に処理を進める。一方、配線経路決定部１６は、この「使用量」の値が『１』以上であり、枝Ｅにその向きのフローを流す余裕が残っていると判定したとき（判定結果がＮｏのとき）には、Ｓ６０３に処理を進める。
【０１８４】
次に、Ｓ６０３では、配線経路決定部１６は以下の処理を行う。
まず、配線経路決定部１６は、枝情報テーブル８２を参照して、枝Ｅが向かう流入先のノード（このノードを「ノードＮ」とする。）についての「ノード情報」を取得し、取得された「ノード情報」を、変数Ｐに初期値として代入する処理を行う。
【０１８５】
また、配線経路決定部１６は、変数ｐｎｔに初期値として座標（０，０）を代入すると共に、変数ｎｅｔに初期値として空白（ヌルデータ）を代入する処理を行う。
配線経路決定部１６は、Ｓ６０３において、以上の処理を行う。
【０１８６】
次のＳ６０４は、図２１ＢのＳ６１５と対になって処理のループを表している。配線経路決定部１６は、変数Ｐで特定されるノード（以下、このノードを「ノードＰ」と称することとする。）がＴノードとは異なるノードである限り、Ｓ６０５からＳ６１４までの処理を行う。
【０１８７】
次のＳ６０５は、図２１ＢのＳ６１４と対になって処理のループを表している。配線経路決定部１６は、ノード情報テーブル８１におけるノードＮについてのレコードを参照して、ノードＮから流出する向きの各枝の「枝番号」のデータを取得し、この各枝について、Ｓ６０６からＳ６１３までの処理を行う。なお、Ｓ６０６からＳ６１３までの処理の説明では、ノードＮについての上記のレコードの「枝番号」のデータで特定される枝を「枝Ｆ」とする。
【０１８８】
Ｓ６０６では、枝使用量テーブル８５を参照し、枝Ｆについてのレコードの「使用量」の値が『１』よりも小さいか否かを判定する処理を配線経路決定部１６が行う。ここで、配線経路決定部１６は、この「使用量」の値が『１』よりも小さく、枝Ｆにその向きのフローをこれ以上流すことができないと判定したとき（判定結果がＹｅｓのとき）には、図２３ＢのＳ６１１に処理を進める。一方、配線経路決定部１６は、この「使用量」の値が『１』以上であり、枝Ｆにその向きのフローを流す余裕が残っていると判定したとき（判定結果がＮｏのとき）には、Ｓ６０７に処理を進める。
【０１８９】
次に、Ｓ６０７では、変数ｎｅｔの現在の値が、初期値である空白のままであるか否かを判定する処理を配線経路決定部１６が行う。配線経路決定部１６は、ここで、変数ｎｅｔの値が空白であると判定したとき（判定結果がＹｅｓのとき）にはＳ６０８に処理を進め、変数ｎｅｔの値が空白ではないと判定したとき（判定結果がＮｏのとき）にはＳ６０９に処理を進める。なお、ここで、変数ｎｅｔの値が空白である場合とは、枝Ｆが、Ｓノードと枝Ｅを介して結ばれているノードから直接流入する枝である場合である。
【０１９０】
次に、Ｓ６０８では、配線経路決定部１６は以下の処理を行う。
まず、配線経路決定部１６は、端点要素引き当てテーブル８４におけるノードＮのレコードを参照して、「部品ピン名」データを取得する処理を行う。続いて、配線経路決定部１６は、論理接続情報３２を参照し、「部品ピン名」データで示されている端子についての「接続名」データを取得して変数ｎｅｔに代入する処理を行う。
【０１９１】
次に、配線経路決定部１６は、枝情報テーブル８２を参照して、枝Ｆが向かう流入先のノードについての「ノード情報」を取得する。この「ノード情報」により特定されるノードを「ノードＯ」とする。そして、配線経路決定部１６は、ノード情報テーブル８１のノードＯについてのレコードを参照し、このレコードにおける「座標」データを読み出して変数ｐｎｔに代入する処理を行う。
【０１９２】
配線経路決定部１６は、Ｓ６０８において以上の処理を行い、その後は、図２３ＢのＳ６１１に処理を進める。
一方、配線経路決定部１６は、Ｓ６０９では以下の処理を行う。
【０１９３】
まず、配線経路決定部１６は、Ｓ６０８の処理と同様に、枝情報テーブル８２を参照して、枝Ｆが向かう流入先のノードＯについての「ノード情報」を取得する。そして、配線経路決定部１６は、ノード情報テーブル８１のノードＯについてのレコードを参照し、このレコードにおける「座標」データを読み出して変数ｐｎｔ２に代入する処理を行う。
【０１９４】
次に、配線経路決定部１６は、配線経路情報３４における、変数ｎｅｔにこの時点で示されている「接続名」についてのレコードのデータを格納する処理を行う。この処理では、変数ｐｎｔの現在の座標値で示されている位置と、変数ｐｎｔ２の現在の座標値で示されている位置との間を所定幅の配線で結ぶ経路についての情報が、配線経路情報３４の「座標」の項目に格納される。なお、「層」の情報は、図１１のＳ１１の処理で取得された指示に含まれている配線層の情報が、そのまま格納される。
【０１９５】
配線経路決定部１６は、Ｓ６０９において以上の処理を行う。
次に、Ｓ６１０では、変数ｐｎｔ２の現在の座標値を変数ｐｎｔに代入する処理を配線経路決定部１６が行い、その後は図２３ＢのＳ６１１に処理を進める。
【０１９６】
図２３Ｂに進み、Ｓ６１１では、端点要素引き当てテーブル８４を参照し、ノードＯについてのレコードが端点要素引き当てテーブル８４に存在するか否かを判定する処理を配線経路決定部１６が行う。配線経路決定部１６は、ここで、ノードＯのレコードが端点要素引き当てテーブル８４に存在すると判定したとき（判定結果がＹｅｓのとき）にはＳ６１２に処理を進め、存在しないと判定したとき（判定結果がＮｏのとき）にはＳ６１３に処理を進める。
【０１９７】
次に、Ｓ６１２では、変数ｎｅｔに代入されている「接続名」のデータを、端点要素引き当てテーブル８４におけるノードＯについてのレコードの「接続名」のデータとして、格納する処理を配線経路決定部１６が行う。
【０１９８】
次に、Ｓ６１３では、ノードＯを特定する「ノード情報」のデータを、変数Ｐに代入する処理を配線経路決定部１６が行う。
次に、Ｓ６１４では、図２３ＡのＳ６０５と対になって表されている処理のループを終了するか否かを判定する処理を配線経路決定部１６が行う。配線経路決定部１６は、ここで、ノード情報テーブル８１のノードＮについてのレコードの「枝番号」で示されている全ての枝について、Ｓ６０６からＳ６１３までの処理を済ませたと判定したときには、この処理のループを終了してＳ６１５に処理を進める。
【０１９９】
次に、Ｓ６１５では、図２３ＡのＳ６０４と対になって表されている処理のループを終了するか否かを判定する処理を配線経路決定部１６が行う。配線経路決定部１６は、ここで、変数Ｐで表されているノードＰがＴノードに一致したと判定したときには、この処理のループを終了してＳ６１６に処理を進める。
【０２００】
次に、Ｓ６１６では、図２３ＡのＳ６０１と対になって表されている処理のループを終了するか否かを判定する処理を配線経路決定部１６が行う。配線経路決定部１６は、ここで、ノード情報テーブル８１のＳノードについてのレコードの「枝番号」で示されている全ての枝について、Ｓ６０２からＳ６１５までの処理を済ませたと判定したときには、この処理のループを終了する。この処理のループが終了すると、配線経路決定処理が終了する。
【０２０１】
次に、図１１のＳ７００の処理である、２端子部品情報交換処理及び多連集合部品情報交換処理について説明する。
まず、２端子部品情報交換処理について説明する。図２４Ａ及び図２４Ｂは、２端子部品情報交換処理の処理内容を図解したフローチャートである。
【０２０２】
図２４Ａにおいて、まず、Ｓ７０１では、各変数に初期値を代入する処理を２端子部品情報交換部１７が行う。具体的には、変数Ｐ、ｐｉｎ＿ｏｒｇ、ｐｉｎ＿ｎｅｗ、ｎｅｔ＿ｏｒｇ、ｎｅｔ＿ｎｅｗ、及びｒｏｔａｔｅの全てに、初期値として『０』を代入する処理を２端子部品情報交換部１７が行う。
【０２０３】
次のＳ７０２は、図２４ＢのＳ７２０と対になって処理のループを表している。２端子部品情報交換部１７は、変数Ｐの値が、端点要素引き当てテーブル８４のレコード数に達するまで（当該レコード数よりも小さい値ではなくなるまで）、Ｓ７０３から図２４ＢのＳ７１９までの処理を繰り返す。
【０２０４】
次に、Ｓ７０３では、端点要素引き当てテーブル８４のＰ番目のレコード（但し、最初のレコードを『０』番目とする）を参照し、当該レコードの「接続名」データが空白（ヌルデータ）であるか否かを判定する処理を２端子部品情報交換部１７が行う。２端子部品情報交換部１７は、ここで、「接続名」データが空白であると判定したとき（判定結果がＹｅｓのとき）には図２４ＢのＳ７１９に処理を進める。一方、２端子部品情報交換部１７は、「接続名」データが空白でないと判定したとき（判定結果がＮｏのとき）にはＳ７０４に処理を進める。ここで、「接続名」データが空白でない場合とは、当該「接続名」データを含むレコードの「ノード番号」で特定されるノードが、自動設計された配線経路上に含まれていることを表している。
【０２０５】
次に、Ｓ７０４では、各変数に値を代入する処理を２端子部品情報交換部１７が行う。具体的には、２端子部品情報交換部１７は、まず、端点要素引き当てテーブル８４のＰ番目のレコードを参照して、「部品ピン名」、「接続名」、及び「反転」の各データを取得する処理を行う。そして、取得された「部品ピン名」、「接続名」、及び「反転」の各データを、それぞれ、変数ｐｉｎ＿ｏｒｇ、ｎｅｔ＿ｎｅｗ、及びｒｏｔａｔｅに代入する処理を行う。
【０２０６】
次に、Ｓ７０５では、変数ｉに初期値として『０』を代入する処理を２端子部品情報交換部１７が行う。
次のＳ７０６は、Ｓ７１２と対になって処理のループを表している。２端子部品情報交換部１７は、変数ｉの値が、論理接続情報３２のテーブルのレコード数に達するまで（当該レコード数よりも小さい値ではなくなるまで）、Ｓ７０７からＳ７１１までの処理を繰り返す。
【０２０７】
次に、Ｓ７０７では、論理接続情報３２のテーブルのｉ番目のレコード（但し、最初のレコードを『０』番目とする）を参照し、当該レコードの「接続名」データが変数ｎｅｔ＿ｎｅｗの値に一致するか否かを判定する処理を２端子部品情報交換部１７が行う。２端子部品情報交換部１７は、ここで、「接続名」データが変数ｎｅｔ＿ｎｅｗの値に一致すると判定したとき（判定結果がＹｅｓのとき）にはＳ７０８に処理を進める。一方、２端子部品情報交換部１７は、ここで、「接続名」データが変数ｎｅｔ＿ｎｅｗの値とは異なると判定したとき（判定結果がＮｏのとき）にはＳ７０９に処理を進める。
【０２０８】
次に、Ｓ７０８において、２端子部品情報交換部１７は、論理接続情報３２のテーブルのｉ番目のレコードを参照して、当該レコードの「終点ピン名」のデータを、変数ｐｉｎ＿ｎｅｗに代入する処理を行う。
【０２０９】
次に、Ｓ７０９では、論理接続情報３２のテーブルのｉ番目のレコードを参照し、当該レコードの「終点ピン名」データが変数ｐｉｎ＿ｏｒｇの値に一致するか否かを判定する処理を２端子部品情報交換部１７が行う。２端子部品情報交換部１７は、ここで、「終点ピン名」データが変数ｐｉｎ＿ｏｒｇの値に一致すると判定したとき（判定結果がＹｅｓのとき）にはＳ７１０に処理を進める。一方、２端子部品情報交換部１７は、ここで、「接続名」データが変数ｐｉｎ＿ｏｒｇの値とは異なると判定したとき（判定結果がＮｏのとき）にはＳ７１１に処理を進める。
【０２１０】
次に、Ｓ７１０において、２端子部品情報交換部１７は、論理接続情報３２のテーブルのｉ番目のレコードを参照して、当該レコードの「接続名」のデータを、変数ｎｅｔ＿ｏｒｇに代入する処理を行う。
【０２１１】
次に、Ｓ７１１では、変数ｉの現在の値に『１』を加算した結果の値を改めて変数ｉに代入する処理を２端子部品情報交換部１７が行う。
次に、Ｓ７１２では、Ｓ７０６と対になって表されている処理のループを終了するか否かを判定する処理を２端子部品情報交換部１７が行う。２端子部品情報交換部１７は、ここで、変数ｉの値が、論理接続情報３２のテーブルのレコード数に達したと判定したときには、この処理のループを終了して、図２４ＢのＳ７１３に処理を進める。
【０２１２】
図２４Ｂに進み、Ｓ７１３では、端点要素引き当てテーブル８４から取得した変数ｎｅｔ＿ｎｅｗの「接続名」と論理接続情報３２のテーブルから取得した変数ｎｅｔ＿ｏｒｇの「接続名」とが一致したか否かを判定する処理を２端子部品情報交換部１７が行う。２端子部品情報交換部１７は、ここで、両者が同一の「接続名」で一致したと判定したとき（判定結果がＹｅｓのとき）には、部品の情報の交換は不要であるので、Ｓ７１９に処理を進める。一方、２端子部品情報交換部１７は、両者の「接続名」が一致しなかったと判定したとき（判定結果がＮｏのとき）には、Ｓ７１４に処理を進める。
【０２１３】
次に、Ｓ７１４では、部品情報３３のテーブルを参照して、変数ｐｉｎ＿ｏｒｇの「部品ピン名」で特定される端子を有している部品についての情報が格納されているレコードの情報を取得する処理を２端子部品情報交換部１７が行う。この処理により取得されたレコードの情報を「ｐａｒｔ＿ｏｒｇ」と称することとする。
【０２１４】
次に、Ｓ７１５では、部品情報３３のテーブルを参照して、変数ｐｉｎ＿ｎｅｗの「部品ピン名」で特定される端子を有している部品についての情報が格納されているレコードの情報を取得する処理を２端子部品情報交換部１７が行う。この処理により取得されたレコードの情報を「ｐａｒｔ＿ｎｅｗ」と称することとする。
【０２１５】
次に、Ｓ７１６では、ｐａｒｔ＿ｏｒｇとｐａｒｔ＿ｎｅｗとの間で「部品位置」データ及び「方向」データを入れ換えて、部品情報３３のテーブルに戻す処理を２端子部品情報交換部１７が行う。
【０２１６】
次に、Ｓ７１７では、変数ｒｏｔａｔｅの値が『１』であるか否かを判定する処理を２端子部品情報交換部１７が行う。２端子部品情報交換部１７は、ここで、変数ｒｏｔａｔｅの値が『１』であると判定したとき（判定結果がＹｅｓのとき）にはＳ７１８に処理を進める。一方、２端子部品情報交換部１７は、ここで、変数ｒｏｔａｔｅの値が『１』ではない（すなわち『０』である）と判定したとき（判定結果がＮｏのとき）にはＳ７１９に処理を進める。
【０２１７】
次に、Ｓ７１８では、「ｐａｒｔ＿ｎｅｗ」の情報における「部品位置」、「方向」、及び「ピン位置」の各データを変更する処理を２端子部品情報交換部１７が行う。この処理では、この２端子部品が有している２つの端子の位置を結ぶ線分の中点を回転軸の中心として当該２端子部品を１８０度回転したときの位置となるように各データの変更が行われる。
【０２１８】
次に、Ｓ７１９では、変数Ｐの現在の値に『１』を加算した結果の値を改めて変数Ｐに代入する処理を２端子部品情報交換部１７が行う。
次に、Ｓ７２０では、図２４ＡのＳ７０２と対になって表されている処理のループを終了するか否かを判定する処理を２端子部品情報交換部１７が行う。２端子部品情報交換部１７は、ここで、変数Ｐの値が、端点要素引き当てテーブル８４のテーブルのレコード数に達したと判定したときには、この処理のループを終了する。この処理のループが終了すると、２端子部品情報交換処理が終了する。
【０２１９】
次に、多連集合部品情報交換処理について説明する。図２５Ａ、図２５Ｂ、図２５Ｃ、及び図２５Ｄは、多連集合部品情報交換処理の処理内容を図解したフローチャートである。
【０２２０】
図２５Ａにおいて、まず、Ｓ７５１では、各変数に初期値を代入する処理を多連集合部品情報交換部１８が行う。具体的には、変数Ｐ、ｐｉｎ＿ｏｒｇ、ｐｉｎ＿ｎｅｗ、ｎｅｔ＿ｏｒｇ、ｎｅｔ＿ｎｅｗ、ｇｒｏｕｐ＿ｏｒｇ、及びｇｒｏｕｐ＿ｎｅｗの全てに、初期値として『０』を代入する処理を多連集合部品情報交換部１８が行う。
【０２２１】
次のＳ７５２は、図２５ＤのＳ７８５と対になって処理のループを表している。多連集合部品情報交換部１８は、変数Ｐの値が、端点要素引き当てテーブル８４のレコード数に達するまで（当該レコード数よりも小さい値ではなくなるまで）、Ｓ７５３から図２５ＤのＳ７８４までの処理を繰り返す。
【０２２２】
次に、Ｓ７５３では、端点要素引き当てテーブル８４のＰ番目のレコード（但し、最初のレコードを『０』番目とする）を参照し、当該レコードの「接続名」データが空白（ヌルデータ）であるか否かを判定する処理を多連集合部品情報交換部１８が行う。多連集合部品情報交換部１８は、ここで、「接続名」データが空白であると判定したとき（判定結果がＹｅｓのとき）には図２５ＤのＳ７８４に処理を進める。一方、多連集合部品情報交換部１８は、「接続名」データが空白でないと判定したとき（判定結果がＮｏのとき）にはＳ７５４に処理を進める。ここで、「接続名」データが空白でない場合とは、当該「接続名」データを含むレコードの「ノード番号」で特定されるノードが、自動設計された配線経路上に含まれていることを表している。
【０２２３】
次に、Ｓ７５４では、各変数に値を代入する処理を多連集合部品情報交換部１８が行う。具体的には、多連集合部品情報交換部１８は、まず、端点要素引き当てテーブル８４のＰ番目のレコードを参照して、「部品ピン名」、「接続名」、及び「組番号」の各データを取得する処理を行う。そして、取得された「部品ピン名」、「接続名」、及び「組番号」の各データを、それぞれ、変数ｐｉｎ＿ｏｒｇ、ｎｅｔ＿ｎｅｗ、及びｇｒｏｕｐ＿ｏｒｇに代入する処理を行う。
【０２２４】
次に、Ｓ７５５では、変数ｉに初期値として『０』を代入する処理を多連集合部品情報交換部１８が行う。
次のＳ７５６は、Ｓ７６２と対になって処理のループを表している。多連集合部品情報交換部１８は、変数ｉの値が、論理接続情報３２のテーブルのレコード数に達するまで（当該レコード数よりも小さい値ではなくなるまで）、Ｓ７５７からＳ７６１までの処理を繰り返す。
【０２２５】
次に、Ｓ７５７では、論理接続情報３２のテーブルのｉ番目のレコード（但し、最初のレコードを『０』番目とする）を参照し、当該レコードの「接続名」データが変数ｎｅｔ＿ｎｅｗの値に一致するか否かを判定する処理を多連集合部品情報交換部１８が行う。多連集合部品情報交換部１８は、ここで、「接続名」データが変数ｎｅｔ＿ｎｅｗの値に一致すると判定したとき（判定結果がＹｅｓのとき）にはＳ７５８に処理を進める。一方、多連集合部品情報交換部１８は、ここで、「接続名」データが変数ｎｅｔ＿ｎｅｗの値とは異なると判定したとき（判定結果がＮｏのとき）にはＳ７５９に処理を進める。
【０２２６】
次に、Ｓ７５８において、多連集合部品情報交換部１８は、論理接続情報３２のテーブルのｉ番目のレコードを参照して、当該レコードの「終点ピン名」のデータを、変数ｐｉｎ＿ｎｅｗに代入する処理を行う。
【０２２７】
次に、Ｓ７５９では、論理接続情報３２のテーブルのｉ番目のレコードを参照し、当該レコードの「終点ピン名」データが変数ｐｉｎ＿ｏｒｇの値に一致するか否かを判定する処理を多連集合部品情報交換部１８が行う。多連集合部品情報交換部１８は、ここで、「終点ピン名」データが変数ｐｉｎ＿ｏｒｇの値に一致すると判定したとき（判定結果がＹｅｓのとき）にはＳ７６０に処理を進める。一方、多連集合部品情報交換部１８は、ここで、「接続名」データが変数ｐｉｎ＿ｏｒｇの値とは異なると判定したとき（判定結果がＮｏのとき）にはＳ７６１に処理を進める。
【０２２８】
次に、Ｓ７６０において、多連集合部品情報交換部１８は、論理接続情報３２のテーブルのｉ番目のレコードを参照して、当該レコードの「接続名」のデータを、変数ｎｅｔ＿ｏｒｇに代入する処理を行う。
【０２２９】
次に、Ｓ７６１では、変数ｉの現在の値に『１』を加算した結果の値を改めて変数ｉに代入する処理を多連集合部品情報交換部１８が行う。
次に、Ｓ７６２では、Ｓ７５６と対になって表されている処理のループを終了するか否かを判定する処理を多連集合部品情報交換部１８が行う。多連集合部品情報交換部１８は、ここで、変数ｉの値が、論理接続情報３２のテーブルのレコード数に達したと判定したときには、この処理のループを終了して、図２５ＢのＳ７６３に処理を進める。
【０２３０】
図２５Ｂに進み、Ｓ７６３では、端点要素引き当てテーブル８４から取得した変数ｎｅｔ＿ｎｅｗの「接続名」と論理接続情報３２のテーブルから取得した変数ｎｅｔ＿ｏｒｇの「接続名」とが一致したか否かを判定する処理を多連集合部品情報交換部１８が行う。多連集合部品情報交換部１８は、ここで、両者が同一の「接続名」で一致したと判定したとき（判定結果がＹｅｓのとき）には、部品の情報の交換は不要であるので、Ｓ７１９に処理を進める。一方、多連集合部品情報交換部１８は、両者の「接続名」が一致しなかったと判定したとき（判定結果がＮｏのとき）には、Ｓ７６４に処理を進める。
【０２３１】
次に、Ｓ７６４では、変数ｊに初期値として『０』を代入する処理を多連集合部品情報交換部１８が行う。
次のＳ７６５は、Ｓ７６９と対になって処理のループを表している。多連集合部品情報交換部１８は、変数ｊの値が、端点要素引き当てテーブル８４のレコード数に達するまで（当該レコード数よりも小さい値ではなくなるまで）、Ｓ７６６からＳ７６８までの処理を繰り返す。
【０２３２】
次に、Ｓ７６６では、端点要素引き当てテーブル８４のｊ番目のレコード（但し、最初のレコードを『０』番目とする）を参照し、当該レコードの「部品ピン名」データが変数ｐｉｎ＿ｎｅｗの値に一致するか否かを判定する処理を多連集合部品情報交換部１８が行う。多連集合部品情報交換部１８は、ここで、「部品ピン名」データが変数ｐｉｎ＿ｎｅｗの値に一致すると判定したとき（判定結果がＹｅｓのとき）にはＳ７６７に処理を進める。一方、多連集合部品情報交換部１８は、ここで、「部品ピン名」データが変数ｐｉｎ＿ｎｅｗの値とは異なると判定したとき（判定結果がＮｏのとき）にはＳ７６８に処理を進める。
【０２３３】
次に、Ｓ７６７において、多連集合部品情報交換部１８は、端点要素引き当てテーブル８４のｊ番目のレコードを参照して、当該レコードの「組番号」のデータを、変数ｇｒｏｕｐ＿ｎｅｗに代入する処理を行う。
【０２３４】
次に、Ｓ７６８では、変数ｊの現在の値に『１』を加算した結果の値を改めて変数Ｐに代入する処理を多連集合部品情報交換部１８が行う。
次に、Ｓ７６９では、Ｓ７６５と対になって表されている処理のループを終了するか否かを判定する処理を多連集合部品情報交換部１８が行う。多連集合部品情報交換部１８は、ここで、変数ｊの値が、端点要素引き当てテーブル８４のテーブルのレコード数に達したと判定したときには、この処理のループを終了して、図２５ＣのＳ７７０に処理を進める。
【０２３５】
図２５Ｃに進み、Ｓ７７０では、各変数に初期値を代入する処理を多連集合部品情報交換部１８が行う。具体的には、変数ｋ、ｐｉｎ＿ｏｒｇ＿ｏｐ、及びｐｉｎ＿ｎｅｗ＿ｏｐの全てに、初期値として『０』を代入する処理を多連集合部品情報交換部１８が行う。
【０２３６】
次のＳ７７１は、Ｓ７７７と対になって処理のループを表している。多連集合部品情報交換部１８は、変数ｋの値が、端点要素引き当てテーブル８４のレコード数に達するまで（当該レコード数よりも小さい値ではなくなるまで）、Ｓ７７２からＳ７７６までの処理を繰り返す。
【０２３７】
次に、Ｓ７７２では、以下の処理を多連集合部品情報交換部１８が行う。
多連集合部品情報交換部１８は、まず、端点要素引き当てテーブル８４のｋ番目のレコード（但し、最初のレコードを『０』番目とする）を参照して、当該レコードの「組番号」データと「部品ピン名」データとを取得する処理を行う。次に、多連集合部品情報交換部１８は、取得した「組番号」データと変数ｇｒｏｕｐ＿ｎｅｗとの一致不一致、及び、取得した「部品ピン名」データと変数ｐｉｎ＿ｎｅｗとの一致不一致を判定する処理を行う。多連集合部品情報交換部１８は、ここで、「組番号」データと変数ｇｒｏｕｐ＿ｎｅｗとが一致し、且つ、「組番号」データと変数ｇｒｏｕｐ＿ｎｅｗとが不一致である場合にのみ、その判定結果をＹｅｓとしてＳ７７３に処理を進める。一方、この他の場合には、多連集合部品情報交換部１８は、その判定結果をＮｏとしてＳ７７４に処理を進める。
【０２３８】
多連集合部品情報交換部１８は、Ｓ７７２において、以上の処理を行う。
次に、Ｓ７７３では、多連集合部品情報交換部１８は、端点要素引き当てテーブル８４のｋ番目のレコードの「部品ピン名」のデータを、変数ｐｉｎ＿ｎｅｗ＿ｏｐに代入する処理を行う。
【０２３９】
次に、Ｓ７７４では、以下の処理を多連集合部品情報交換部１８が行う。
多連集合部品情報交換部１８は、まず、端点要素引き当てテーブル８４のｋ番目のレコード（但し、最初のレコードを『０』番目とする）を参照して、当該レコードの「組番号」データと「部品ピン名」データとを取得する処理を行う。次に、多連集合部品情報交換部１８は、取得した「組番号」データと変数ｇｒｏｕｐ＿ｏｒｇとの一致不一致、及び、取得した「部品ピン名」データと変数ｐｉｎ＿ｏｒｇとの一致不一致を判定する処理を行う。多連集合部品情報交換部１８は、ここで、「組番号」データと変数ｇｒｏｕｐ＿ｏｒｇとが一致し、且つ、「組番号」データと変数ｇｒｏｕｐ＿ｏｒｇとが不一致である場合にのみ、その判定結果をＹｅｓとしてＳ７７５に処理を進める。一方、この他の場合には、多連集合部品情報交換部１８は、その判定結果をＮｏとしてＳ７７６に処理を進める。
【０２４０】
多連集合部品情報交換部１８は、Ｓ７７４において、以上の処理を行う。
次に、Ｓ７７５では、多連集合部品情報交換部１８は、端点要素引き当てテーブル８４のｋ番目のレコードの「部品ピン名」のデータを、変数ｐｉｎ＿ｏｒｇ＿ｏｐに代入する処理を行う。
【０２４１】
次に、Ｓ７７６では、変数ｋの現在の値に『１』を加算した結果の値を改めて変数Ｐに代入する処理を多連集合部品情報交換部１８が行う。
次に、Ｓ７７７では、Ｓ７７１と対になって表されている処理のループを終了するか否かを判定する処理を多連集合部品情報交換部１８が行う。多連集合部品情報交換部１８は、ここで、変数ｋの値が、端点要素引き当てテーブル８４のテーブルのレコード数に達したと判定したときには、この処理のループを終了して、図２５ＤのＳ７７８に処理を進める。
【０２４２】
図２５Ｄに進み、Ｓ７７８では、論理接続情報３２のテーブルを参照して、「終点ピン名」データが変数ｐｉｎ＿ｏｒｇの「部品ピン名」データと一致しているレコードの情報を取得する処理を多連集合部品情報交換部１８が行う。この処理により取得されたレコードの情報を「ｃｏｎｎｅｃｔ＿ｏｒｇ」と称することとする。
【０２４３】
次に、Ｓ７７９では、論理接続情報３２のテーブルを参照して、「終点ピン名」データが変数ｐｉｎ＿ｎｅｗの「部品ピン名」データと一致しているレコードの情報を取得する処理を多連集合部品情報交換部１８が行う。この処理により取得されたレコードの情報を「ｃｏｎｎｅｃｔ＿ｎｅｗ」と称することとする。
【０２４４】
次に、Ｓ７８０では、論理接続情報３２のテーブルを参照して、「終点ピン名」データが変数ｐｉｎ＿ｏｒｇ＿ｏｐの「部品ピン名」データと一致しているレコードの情報を取得する処理を多連集合部品情報交換部１８が行う。この処理により取得されたレコードの情報を「ｃｏｎｎｅｃｔ＿ｏｒｇ＿ｏｐ」と称することとする。
【０２４５】
次に、Ｓ７８１では、論理接続情報３２のテーブルを参照して、「終点ピン名」データが変数ｐｉｎ＿ｎｅｗ＿ｏｐの「部品ピン名」データと一致しているレコードの情報を取得する処理を多連集合部品情報交換部１８が行う。この処理により取得されたレコードの情報を「ｃｏｎｎｅｃｔ＿ｎｅｗ＿ｏｐ」と称することとする。
【０２４６】
次に、Ｓ７８２では、ｃｏｎｎｅｃｔ＿ｏｒｇとｃｏｎｎｅｃｔ＿ｎｅｗとの間で「終点ピン名」データを入れ換えて、論理接続情報３２のテーブルに戻す処理を多連集合部品情報交換部１８が行う。
【０２４７】
次に、Ｓ７８３では、ｃｏｎｎｅｃｔ＿ｏｒｇ＿ｏｐとｃｏｎｎｅｃｔ＿ｎｅｗ＿ｏｐとの間で「終点ピン名」データを入れ換えて、論理接続情報３２のテーブルに戻す処理を多連集合部品情報交換部１８が行う。
【０２４８】
次に、Ｓ７８４では、変数Ｐの現在の値に『１』を加算した結果の値を改めて変数Ｐに代入する処理を多連集合部品情報交換部１８が行う。
次に、Ｓ７８５では、図２５ＡのＳ７５２と対になって表されている処理のループを終了するか否かを判定する処理を多連集合部品情報交換部１８が行う。多連集合部品情報交換部１８は、ここで、変数Ｐの値が、端点要素引き当てテーブル８４のテーブルのレコード数に達したと判定したときには、この処理のループを終了する。この処理のループが終了すると、多連集合部品情報交換処理が終了する。
【０２４９】
以上の各処理をＭＰＵ１０が行うことによって、配線経路の自動設計を、図１の配線設計支援装置１が行えるようになる。
次に、プリント配線板上の配線を用いて差動信号を伝送する場合における、配線設計支援装置１による当該配線の経路についての自動設計について、図２６Ａ及び図２６Ｂについて説明する。
【０２５０】
差動信号を伝送する場合は、図２６Ａの配線経路例のように、一対の差動信号を伝送する２線１組の差動信号伝送用配線９１の経路を、なるべく平行になるように配置することが好ましい。
【０２５１】
そこで、この場合には、まず、差動信号における伝送元である一対の端子と伝送先である一対の端子との双方から、ポジティブ側の端子若しくはネガティブ側の端子のどちらかを選択する。次に、選択された側の端子間を接続する配線経路の自動設計を、配線設計支援装置１に行わせるようにする。そして、この自動設計により得られた配線経路を、配線設計支援装置１の差動信号配線置換部１９が、２線１組の平行配線である差動信号配線に置換する。
【０２５２】
図２６Ｂのフローネットワークの作成例は、配線設計支援装置１が差動信号配線の自動設計を行う場合のものである。この図２６Ｂにおいて、１Ｐ、１Ｎ、２Ｐ、２Ｎ、…、１０Ｐ、１０Ｎは、それぞれ、差動信号配線による配線対象の端子の位置を表しており、「Ｐ」はポジティブ側端子を、また、「Ｎ」はネガティブ側端子を、それぞれ表している。
【０２５３】
また、格子点Ａは、差動信号の入力若しくは出力を行う一対の端子であるポジティブ側端子１Ｐとネガティブ側端子１Ｎとのうちから選択された端子の位置に最も近い格子点である。また、格子点Ｂ〜Ｊについても同様であり、それぞれ、端子２Ｐ、２Ｎ〜１０Ｐ、１０Ｎのうちから選択された端子の位置に最も近い格子点である。
【０２５４】
なお、ここではポジティブ側端子１Ｐ、２Ｐ、…、１０Ｐが選択されたものとして、以降の説明を行う。
このようにして結線を行う格子点を特定した後は、図７の場合と同様にしてフローネットワークの作成を行う。図２６Ｂの例は、格子点Ａ〜Ｅにそれぞれ枝を介して始点Ｓが接続され、当格子点Ｆ〜Ｊにそれぞれ枝を介して終点Ｔが接続された状態を表している。この後、配線設計支援装置１は、前述したようにして、フロー経路の探索と、その探索結果に基づく配線経路の決定を行って、ポジティブ側端子１Ｐ〜５Ｐと６Ｐ〜１０Ｐとを接続する５本の配線経路が決定される。
【０２５５】
ここで、差動信号配線置換部１９は、この５本の配線経路の各々を、２線１組の平行配線に置換する。そして、この平行配線の一方の配線をポジティブ側端子１Ｐ〜５Ｐと６Ｐ〜１０Ｐとの配線経路とし、その他方の配線をネガティブ側端子１Ｎ〜５Ｎと６Ｎ〜１０Ｎとの配線経路として各端子に配線を接続する。このようにすることで、差動信号の伝送に好適である、一対の配線を平行に配置した区間を有する経路についての自動設計も、図１の配線設計支援装置１で行うことができる。
【０２５６】
なお、この差動信号配線の経路の自動設計を行う場合には、置換後の平行配線による配線間の短絡や配線禁止領域への侵入を防止するために、有向グラフ定義部１１が定義する格子における格子点の間隔を、通常の配線経路の場合よりも広くすることが好ましい。
【０２５７】
なお、以上までに説明した実施形態に関し、更に以下の付記を開示する。
（付記１）
プリント配線板での配線経路の設計を支援する装置であって、
格子点をノードとし、隣接する格子点間を結ぶ線分を枝とする有向グラフを、前記配線経路を作成する対象領域面上に定義する有向グラフ定義部と、
前記対象領域面上において配線の配置が禁止される領域の位置を示す配線禁止領域情報についての入力を取得する配線禁止領域情報取得部と、
前記対象領域面上に定義されている前記格子点のうちで、複数の配線の各々によってそれぞれ結ばれる複数組の格子点の組の情報である結線情報についての入力を取得する結線情報取得部と、
前記有向グラフを構成している枝のうちで、前記配線禁止領域情報で示されている領域内に位置している格子点に繋がっている枝に対しフロー容量を「０」に設定すると共に、その他の枝に対しフロー容量を「１」に設定し、更に、前記複数組の格子点の各組に属している一対の格子点に、フロー容量が「１」である枝を介してフローの始点と終点とをそれぞれ接続することで、フローネットワークを作成するフローネットワーク作成部と、
前記フローネットワーク作成部が各枝について設定した前記フロー容量の下で前記始点から前記終点へのフロー量が最大となるフローの経路を、前記フローネットワークから探索するフロー経路探索部と、
前記フロー経路探索部による前記経路の探索結果に従って、前記結線情報で示されている複数組の格子点の各組に属している前記一対の格子点を各々結ぶ前記複数の配線の経路を決定する配線経路決定部と、
を備えることを特徴とする配線設計支援装置。
（付記２）
前記格子点の間隔は、前記対象領域面上での前記配線における線幅及び配線間隔の定義に基づいて設定されることを特徴とする付記１に記載の配線設計支援装置。
（付記３）
前記結線情報取得部は、前記配線により接続を行う端子の前記対象領域面上での配置位置の情報の入力から、該端子と前記格子点との対応関係を示す対応関係情報を生成し、該対応関係情報と該配線により接続を行う端子を特定する論理接続情報の入力とに基づいて前記結線情報を生成することを特徴とする付記１又は２に記載の配線設計支援装置。
（付記４）
前記論理接続情報により特定されている前記配線により接続を行う端子が２端子部品の一方の端子である場合には、前記結線情報取得部は、該２端子部品における他方の端子と前記格子点とに対しての前記対応関係情報を更に生成し、
前記フローネットワーク作成部は、前記場合においては、前記２端子部品ついての中継ノードを新規に定義して、前記一方の端子に対応する格子点と前記始点若しくは前記終点とを接続する枝の途中に該中継ノードを挿入し、更に、前記対応関係情報において前記他方の端子との対応関係が示されている格子点と該中継ノードとをフロー容量が「１」である枝を介して接続し、
前記配線設計支援装置は、前記配線経路決定部が経路を決定した配線により接続される一方の接続先が前記２端子部品における前記他方の端子となった場合に、該配線により接続を行う端子の前記対象領域面上での配置位置についての前記入力された情報を変更して、該他方の端子についての該情報と該２端子部品における前記一方の端子についての該情報とを交換することによって、該配線により接続される端子を前記論理接続情報で特定される端子に一致させる２端子部品情報交換部を更に備える、
ことを特徴とする付記３に記載の配線設計支援装置。
（付記５）
前記２端子部品情報交換部は、更に、前記配線経路決定部が経路を決定した複数の配線に、接続を行う一方の接続先が同一形状の２端子部品である配線が少なくとも２つ存在することとなった場合に、該配線により接続を行う端子の前記対象領域面上での配置位置についての前記入力された情報を変更して、そのうちの１の配線に接続される２端子部品の端子についての該情報と、そのうちの別の１の配線に接続される、該２端子部品とは別の２端子部品の端子についての該情報とを交換することによって、該１の配線により接続される端子を前記論理接続情報で特定される端子に一致させることを特徴とする付記４に記載の配線設計支援装置。
（付記６）
前記配線経路決定部が経路を決定した複数の配線に、接続を行う一方の接続先が同一形状の多連集合部品である配線が少なくとも２つ存在することとなった場合に、該配線により接続を行う端子の前記対象領域面上での配置位置についての前記入力された情報を変更して、そのうちの１の配線に接続される多連集合部品の端子についての該情報と、そのうちの別の１の配線に接続される、当該多連集合部品の他の端子若しくは該多連集合部品とは別の多連集合部品の端子についての該情報とを交換することによって、該１の配線により接続される端子を前記論理接続情報で特定される端子に一致させる多連集合部品情報交換部を更に備えることを特徴とする付記３から５のうちのいずれか一項に記載の配線設計支援装置。
（付記７）
前記配線経路決定部が経路を決定した配線を、２線１組の平行配線である差動信号配線に置換する差動信号配線置換部を更に備えることを特徴とする付記１から６のうちのいずれか一項に記載の配線設計支援装置。
（付記８）
プリント配線板での配線経路の設計を支援する方法であって、
格子点をノードとし、隣接する格子点間を結ぶ線分を枝とする有向グラフを、前記配線経路を作成する対象領域面上に定義し、
前記対象領域面上において配線の配置が禁止される領域の位置を示す配線禁止領域情報についての入力を取得し、
前記対象領域面上に定義されている前記格子点のうちで、複数の配線の各々によってそれぞれ結ばれる複数組の格子点の組の情報である結線情報についての入力を取得し、
前記有向グラフを構成している枝のうちで、前記配線禁止領域情報で示されている領域内に位置している格子点に繋がっている枝に対しフロー容量を「０」に設定すると共に、その他の枝に対しフロー容量を「１」に設定し、更に、前記複数組の格子点の各組に属している一対の格子点に、フロー容量が「１」である枝を介してフローの始点と終点とをそれぞれ接続することで、フローネットワークを作成し、
前記枝の各々について設定した前記フロー容量の下で前記始点から前記終点へのフロー量が最大となるフローの経路を、前記フローネットワークから探索し、
前記経路の探索結果に従って、前記結線情報で示されている複数組の格子点の各組に属している前記一対の格子点を各々結ぶ前記複数の配線の経路を決定する、
ことを特徴とする配線設計支援方法。
（付記９）
前記格子点の間隔は、前記対象領域面上での前記配線における線幅及び配線間隔の定義に基づいて設定されることを特徴とする付記８に記載の配線設計支援方法。
（付記１０）
前記結線情報についての入力を取得するときには、前記配線により接続を行う端子の前記対象領域面上での配置位置の情報の入力から、該端子と前記格子点との対応関係を示す対応関係情報を生成し、該対応関係情報と該配線により接続を行う端子を特定する論理接続情報の入力とに基づいて前記結線情報を生成することを特徴とする付記８又は９に記載の配線設計支援方法。
（付記１１）
前記論理接続情報により特定されている前記配線により接続を行う端子が２端子部品の一方の端子である場合には、前記結線情報についての入力を取得するときに、該２端子部品における他方の端子と前記格子点とに対しての前記対応関係情報を更に生成し、
前記フローネットワークを作成するときに、前記場合においては、前記２端子部品ついての中継ノードを新規に定義して、前記一方の端子に対応する格子点と前記始点若しくは前記終点とを接続する枝の途中に該中継ノードを挿入し、更に、前記対応関係情報において前記他方の端子との対応関係が示されている格子点と該中継ノードとをフロー容量が「１」である枝を介して接続し、
前記配線の経路の決定によって決定された配線により接続される一方の接続先が前記２端子部品における前記他方の端子となった場合には、該配線により接続を行う端子の前記対象領域面上での配置位置についての前記入力された情報を変更して、該他方の端子についての該情報と該２端子部品における前記一方の端子についての該情報とを交換することによって、該配線により接続される端子を前記論理接続情報で特定される端子に一致させる、
ことを特徴とする付記１０に記載の配線設計支援方法。
（付記１２）
前記配線の経路の決定によって決定された複数の配線に、接続を行う一方の接続先が同一形状の２端子部品である配線が少なくとも２つ存在することとなった場合には、該配線により接続を行う端子の前記対象領域面上での配置位置についての前記入力された情報を変更して、そのうちの１の配線に接続される２端子部品の端子についての該情報と、そのうちの別の１の配線に接続される、該２端子部品とは別の２端子部品の端子についての該情報とを交換することによって、該１の配線により接続される端子を前記論理接続情報で特定される端子に一致させることを特徴とする付記１１に記載の配線設計支援方法。
（付記１３）
前記配線の経路の決定によって決定された複数の配線に、接続を行う一方の接続先が同一形状の多連集合部品である配線が少なくとも２つ存在することとなった場合には、該配線により接続を行う端子の前記対象領域面上での配置位置についての前記入力された情報を変更して、そのうちの１の配線に接続される多連集合部品の端子についての該情報と、そのうちの別の１の配線に接続される、当該多連集合部品の他の端子若しくは該多連集合部品とは別の多連集合部品の端子についての該情報とを交換することによって、該１の配線により接続される端子を前記論理接続情報で特定される端子に一致させることを特徴とする付記１０から１２のうちのいずれか一項に記載の配線設計支援方法。
（付記１４）
プリント配線板での配線経路の設計支援をコンピュータに実行させるプログラムであって、
格子点をノードとし、隣接する格子点間を結ぶ線分を枝とする有向グラフを、前記配線経路を作成する対象領域面上に定義し、
前記対象領域面上において配線の配置が禁止される領域の位置を示す配線禁止領域情報についての入力を取得し、
前記対象領域面上に定義されている前記格子点のうちで、複数の配線の各々によってそれぞれ結ばれる複数組の格子点の組の情報である結線情報についての入力を取得し、
前記有向グラフを構成している枝のうちで、前記配線禁止領域情報で示されている領域内に位置している格子点に繋がっている枝に対しフロー容量を「０」に設定すると共に、その他の枝に対しフロー容量を「１」に設定し、更に、前記複数組の格子点の各組に属している一対の格子点に、フロー容量が「１」である枝を介してフローの始点と終点とをそれぞれ接続することで、フローネットワークを作成し、
前記枝の各々について設定した前記フロー容量の下で前記始点から前記終点へのフロー量が最大となるフローの経路を、前記フローネットワークから探索し、
前記経路の探索結果に従って、前記結線情報で示されている複数組の格子点の各組に属している前記一対の格子点を各々結ぶ前記複数の配線の経路を決定する、
処理を前記コンピュータに実行させることを特徴とするプログラム。
（付記１５）
前記格子点の間隔は、前記対象領域面上での前記配線における線幅及び配線間隔の定義に基づいて設定されることを特徴とする付記１４に記載のプログラム。
（付記１６）
前記結線情報についての入力を取得するときには、前記配線により接続を行う端子の前記対象領域面上での配置位置の情報の入力から、該端子と前記格子点との対応関係を示す対応関係情報を生成し、該対応関係情報と該配線により接続を行う端子を特定する論理接続情報の入力とに基づいて前記結線情報を生成することを特徴とする付記１４又は１５に記載のプログラム。
（付記１７）
前記論理接続情報により特定されている前記配線により接続を行う端子が２端子部品の一方の端子である場合には、前記結線情報についての入力を取得するときに、該２端子部品における他方の端子と前記格子点とに対しての前記対応関係情報を更に生成し、
前記フローネットワークを作成するときに、前記場合においては、前記２端子部品ついての中継ノードを新規に定義して、前記一方の端子に対応する格子点と前記始点若しくは前記終点とを接続する枝の途中に該中継ノードを挿入し、更に、前記対応関係情報において前記他方の端子との対応関係が示されている格子点と該中継ノードとをフロー容量が「１」である枝を介して接続し、
前記配線の経路の決定によって決定された配線により接続される一方の接続先が前記２端子部品における前記他方の端子となった場合には、該配線により接続を行う端子の前記対象領域面上での配置位置についての前記入力された情報を変更して、該他方の端子についての該情報と該２端子部品における前記一方の端子についての該情報とを交換することによって、該配線により接続される端子を前記論理接続情報で特定される端子に一致させる処理を前記コンピュータに更に実行させる、
ことを特徴とする付記１６に記載のプログラム。
（付記１８）
前記配線の経路の決定によって決定された複数の配線に、接続を行う一方の接続先が同一形状の２端子部品である配線が少なくとも２つ存在することとなった場合には、該配線により接続を行う端子の前記対象領域面上での配置位置についての前記入力された情報を変更して、そのうちの１の配線に接続される２端子部品の端子についての該情報と、そのうちの別の１の配線に接続される、該２端子部品とは別の２端子部品の端子についての該情報とを交換することによって、該１の配線により接続される端子を前記論理接続情報で特定される端子に一致させる処理を前記コンピュータに更に実行させることを特徴とする付記１７に記載のプログラム。
（付記１９）
前記配線の経路の決定によって決定された複数の配線に、接続を行う一方の接続先が同一形状の多連集合部品である配線が少なくとも２つ存在することとなった場合には、該配線により接続を行う端子の前記対象領域面上での配置位置についての前記入力された情報を変更して、そのうちの１の配線に接続される多連集合部品の端子についての該情報と、そのうちの別の１の配線に接続される、当該多連集合部品の他の端子若しくは該多連集合部品とは別の多連集合部品の端子についての該情報とを交換することによって、該１の配線により接続される端子を前記論理接続情報で特定される端子に一致させる処理を前記コンピュータに更に実行させることを特徴とする付記１６から１８のうちのいずれか一項に記載のプログラム。
【符号の説明】
【０２５８】
１  配線設計支援装置
１０  ＭＰＵ
１１  有向グラフ定義部
１２  配線禁止領域情報取得部
１３  結線情報取得部
１４  フローネットワーク作成部
１５  フロー経路探索部
１６  配線経路決定部
１７  ２端子部品情報交換部
１８  多連集合部品情報交換部
１９  差動信号配線置換部
３０  記憶装置
３１  配線禁止領域情報
３２  論理接続情報
３３  部品情報
３４  配線経路情報
４１  表示装置
４２  マウス装置
４３  キーボード装置
４４  ＲＡＭ
４５  ＲＯＭ
４６  システムバス
５０  コンピュータ
５１  ＭＰＵ
５２  ＲＯＭ
５３  ＲＡＭ
５４  ハードディスク装置
５５  入力装置
５６  表示装置
５７  インタフェース装置
５８  記録媒体駆動装置
５９  バスライン
６０  可搬型記録媒体
７１  部品Ａ
７２  部品Ｂ
７３  部品Ｃ
８１  ノード情報テーブル
８２  枝情報テーブル
８３  使用禁止ノードテーブル
８４  端点要素引き当てテーブル
８５  枝使用量テーブル
８６  経路探索用キューテーブル
８７  参照元ノード管理テーブル
９１  差動信号伝送用配線
【図１】
0005644609.tif 000002
【図２】
0005644609.tif 000003
【図３】
0005644609.tif 000004
【図４】
0005644609.tif 000005
【図９Ａ】
0005644609.tif 000006
【図９Ｂ】
0005644609.tif 000007
【図９Ｃ】
0005644609.tif 000008
【図９Ｄ】
0005644609.tif 000009
【図１１】
0005644609.tif 000010
【図１２】
0005644609.tif 000011
【図１４Ａ】
0005644609.tif 000012
【図１４Ｂ】
0005644609.tif 000013
【図１５】
0005644609.tif 000014
【図１６】
0005644609.tif 000015
【図１７】
0005644609.tif 000016
【図１８】
0005644609.tif 000017
【図１９】
0005644609.tif 000018
【図２０Ａ】
0005644609.tif 000019
【図２０Ｂ】
0005644609.tif 000020
【図２１Ａ】
0005644609.tif 000021
【図２１Ｂ】
0005644609.tif 000022
【図２２】
0005644609.tif 000023
【図２３Ａ】
0005644609.tif 000024
【図２３Ｂ】
0005644609.tif 000025
【図２４Ａ】
0005644609.tif 000026
【図２４Ｂ】
0005644609.tif 000027
【図２５Ａ】
0005644609.tif 000028
【図２５Ｂ】
0005644609.tif 000029
【図２５Ｃ】
0005644609.tif 000030
【図２５Ｄ】
0005644609.tif 000031
【図２６Ｂ】
0005644609.tif 000032
【図５Ａ】
0005644609.tif 000033
【図５Ｂ】
0005644609.tif 000034
【図５Ｃ】
0005644609.tif 000035
【図５Ｄ】
0005644609.tif 000036
【図５Ｅ】
0005644609.tif 000037
【図６】
0005644609.tif 000038
【図７】
0005644609.tif 000039
【図８】
0005644609.tif 000040
【図１０Ａ】
0005644609.tif 000041
【図１０Ｂ】
0005644609.tif 000042
【図１３】
0005644609.tif 000043
【図２６Ａ】
0005644609.tif 000044