(57)【特許請求の範囲】
【請求項１】
複数のノードがリンク接続されたネットワークにおける経路特定方法であって、
前記ネットワーク内にある複数のノードおよびリンクにより閉じられた経路（以下、閉路という。）を閉路ノードとし、２つの閉路が共有するノードあるいはリンクを当該２つの閉路を結ぶ閉路隣接リンクとして表した閉路隣接グラフと、前記閉路に含まれる包含ノードと当該包含ノードと前記閉路ノードとを結ぶリンクとを前記閉路隣接グラフに追加した閉路探索グラフと、を生成し、
前記閉路探索グラフにおいて、経路コストを基準として、所望の第１ノードと第２ノードとの間の複数の異なるグラフ経路を順次特定し、
特定されたグラフ経路ごとに含まれる閉路ノードが表す閉路を１つの閉路になるまで併合することにより、前記第１ノードと前記第２ノードとの間の複数の経路含有閉路を順次特定し、
前記複数の経路含有閉路から特定された複数の経路のうち重複した経路を削除することにより、前記ネットワークにおける前記第１ノードと前記第２ノードとの間の異なる３以上の所定数の経路を特定する、
ことを特徴とする経路特定方法。
【請求項２】
前記特定されたグラフ経路ごとに特定された一つの経路含有閉路から２本の経路を特定し、重複した経路を削除することで前記所定数の経路を特定することを特徴とする請求項１に記載の経路特定方法。
【請求項３】
複数のノードがリンク接続されたネットワークにおける経路特定装置であって、
前記ネットワーク内にある複数のノードおよびリンクにより閉じられた経路（以下、閉路という。）を閉路ノードとし、２つの閉路が共有するノードあるいはリンクを当該２つの閉路を結ぶ閉路隣接リンクとして表した閉路隣接グラフと、前記閉路に含まれる包含ノードと当該包含ノードと前記閉路ノードとを結ぶリンクとを前記閉路隣接グラフに追加した閉路探索グラフと、を生成し、前記閉路探索グラフにおいて、経路コストを基準として、所望の第１ノードと第２ノードとの間の複数の異なるグラフ経路を順次特定する制御手段と、
特定されたグラフ経路ごとに含まれる閉路ノードが表す閉路を１つの閉路になるまで併合することにより、前記第１ノードと前記第２ノードとの間の複数の経路含有閉路を順次特定する閉路特定手段と、
前記複数の経路含有閉路から特定された複数の経路のうち重複した経路を削除することにより、前記ネットワークにおける前記第１ノードと前記第２ノードとの間の異なる３以上の所定数の経路を特定する経路特定手段と、
を有することを特徴とする経路特定装置。
【請求項４】
前記経路特定手段は、前記特定されたグラフ経路ごとに特定された一つの経路含有閉路から２本の経路を特定し、重複した経路を削除することで前記所定数の経路を特定することを特徴とする請求項３に記載の経路特定装置。
【請求項５】
複数のノードがリンク接続されたネットワークにおける経路特定装置としてコンピュータを機能させるプログラムであって、
前記ネットワーク内にある複数のノードおよびリンクにより閉じられた経路（以下、閉路という。）を閉路ノードとし、２つの閉路が共有するノードあるいはリンクを当該２つの閉路を結ぶ閉路隣接リンクとして表した閉路隣接グラフと、前記閉路に含まれる包含ノードと当該包含ノードと前記閉路ノードとを結ぶリンクとを前記閉路隣接グラフに追加した閉路探索グラフと、を生成し、前記閉路探索グラフにおいて、経路コストを基準として、所望の第１ノードと第２ノードとの間の複数の異なるグラフ経路を順次特定する機能と、
特定されたグラフ経路ごとに含まれる閉路ノードが表す閉路を１つの閉路になるまで併合することにより、前記第１ノードと前記第２ノードとの間の複数の経路含有閉路を順次特定する機能と、
前記複数の経路含有閉路から特定された複数の経路のうち重複した経路を削除することにより、前記ネットワークにおける前記第１ノードと前記第２ノードとの間の異なる３以上の所定数の経路を特定する機能と、
を前記コンピュータで実現させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は複数のノードがリンク接続されたネットワークにおける経路を特定する方法および装置並びに経路特定プログラムに関する。
【背景技術】
【０００２】
複数のノードがリンク接続されたネットワークにおいて、冗長な経路を特定する方法としては、ダイクストラ（Ｄｉｊｋｓｔｒａ）法（非特許文献１を参照）を繰り返し用いる方法が最も代表的である。たとえば、各リンクにコスト値が与えられ、経路のコストがその経路が経由するリンクのコスト和で与えられるグラフを考えると、まず、２つの端点ノードを結ぶ経路として、コストが最小となる経路（第１の経路）をＤｉｊｋｓｔｒａ法に従って特定する。次いで、特定された経路に含まれる全てのリンクあるいはノードを除外し、再度、上記端点ノードを結ぶ経路として、コストが最小となる経路（第２の経路）をＤｉｊｋｓｔｒａ法に従って特定する。こうして、端点ノード間でリンクやノードを共有しない２つの異なる経路（第１の経路と第２の経路）を特定することができる。
【０００３】
しかしながら、上述したＤｉｊｋｓｔｒａ法を繰り返して適用する方法では、グラフのトポロジにトラップ構造が含まれる場合、迂回経路を特定できないことがある。例えば、図１に示したグラフにおいて、ノードＮ１００とノードＮ４００とを結ぶ経路を特定する場合を考える。まず、Ｄｉｊｋｓｔｒａ法により、リンクＬ１００−Ｌ９００−Ｌ５００−Ｌ４００をこの順に連結した経路が最小コスト経路（第１の経路）として特定されると、続いて、第１の経路に含まれる全てのリンク（図中の破線リンク）を除外する。すると、これ以上ノードＮ１００とノードＮ４００とを結ぶ経路を特定することができなくなる。即ち、このグラフのトポロジはトラップ構造を含んでいる、と言うことができる。
【０００４】
このような課題に対処するため、バンダリ（Ｂｈａｎｄａｒｉ）法が知られている（非特許文献２を参照）。この方法によれば、Ｄｉｊｋｓｔｒａ法を繰り返し用いる工程を拡張することによりグラフのトポロジの一部を変換し、トラップ構造の基となるトラップリンクを特定する。続いて、特定されたトラップリンクを除いたグラフにおいて、再度、Ｄｉｊｋｓｔｒａ法を繰り返し用いることにより、リンクを共有しない２つの異なる経路を特定する。したがって、Ｂｈａｎｄａｒｉ法を繰り返し用いることで複数の異なる経路の計算が可能である。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】E. W. Dijkstra, “A note on two problems in connexion with graphs”, Numerische Mathematik, 1(1959), pp.269-271
【非特許文献２】Ramesh Bhandari,“Survivable Networks: Algorithms for diverse routing”, Springer (1999)
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、Ｂｈａｎｄａｒｉ法を用いる方法では、トラップリンクを特定し、トラップリンクの影響を排除するための計算量が比較的大きいために、Ｂｈａｎｄａｒｉ法を繰り返し用いるとトラップ構造を避けるための処理負荷が大きくなる。たとえばｋ個の異なる経路を計算する場合、Ｄｉｊｋｓｔｒａ法あるいはそれに代わる最短経路計算法を最大で｛（ｋ２＋３ｋ−２）／２｝回繰り返す必要があり、ｋの値が大きくなるにつれて計算量が二次関数的に増加する。
【０００７】
そこで、本発明の目的は、２つのノードを結ぶ経路途中のリンク／ノードを共有しない３以上の異なる経路を特定する際の処理負荷を低減することができる経路特定方法および装置並びに経路特定プログラムを提供することにある。
【課題を解決するための手段】
【０００８】
本発明による経路特定方法は、複数のノードがリンク接続されたネットワークにおける経路特定方法であって、前記ネットワーク内にある複数のノードおよびリンクにより閉じられた経路（以下、閉路という。）を閉路ノードとし、２つの閉路が共有するノードあるいはリンクを当該２つの閉路を結ぶ閉路隣接リンクとして表した閉路隣接グラフと、前記閉路に含まれる包含ノードと当該包含ノードと前記閉路ノードとを結ぶリンクとを前記閉路隣接グラフに追加した閉路探索グラフと、を生成し、前記閉路探索グラフにおいて、経路コストを基準として、所望の第１ノードと第２ノードとの間の複数の異なるグラフ経路を順次特定し、特定されたグラフ経路ごとに含まれる閉路ノードが表す閉路を１つの閉路になるまで併合することにより、前記第１ノードと前記第２ノードとの間の複数の経路含有閉路を順次特定し、前記複数の経路含有閉路から特定された複数の経路のうち重複した経路を削除することにより、前記ネットワークにおける前記第１ノードと前記第２ノードとの間の異なる３以上の所定数の経路を特定する、ことを特徴とする。
本発明による経路特定装置は、複数のノードがリンク接続されたネットワークにおける経路特定装置であって、前記ネットワーク内にある複数のノードおよびリンクにより閉じられた経路（以下、閉路という。）を閉路ノードとし、２つの閉路が共有するノードあるいはリンクを当該２つの閉路を結ぶ閉路隣接リンクとして表した閉路隣接グラフと、前記閉路に含まれる包含ノードと当該包含ノードと前記閉路ノードとを結ぶリンクとを前記閉路隣接グラフに追加した閉路探索グラフと、を生成し、前記閉路探索グラフにおいて、経路コストを基準として、所望の第１ノードと第２ノードとの間の複数の異なるグラフ経路を順次特定する制御手段と、特定されたグラフ経路ごとに含まれる閉路ノードが表す閉路を１つの閉路になるまで併合することにより、前記第１ノードと前記第２ノードとの間の複数の経路含有閉路を順次特定する閉路特定手段と、前記複数の経路含有閉路から特定された複数の経路のうち重複した経路を削除することにより、前記ネットワークにおける前記第１ノードと前記第２ノードとの間の異なる３以上の所定数の経路を特定する経路特定手段と、を有することを特徴とする。
本発明によるプログラムは、複数のノードがリンク接続されたネットワークにおける経路特定装置としてコンピュータを機能させるプログラムであって、前記ネットワーク内にある複数のノードおよびリンクにより閉じられた経路（以下、閉路という。）を閉路ノードとし、２つの閉路が共有するノードあるいはリンクを当該２つの閉路を結ぶ閉路隣接リンクとして表した閉路隣接グラフと、前記閉路に含まれる包含ノードと当該包含ノードと前記閉路ノードとを結ぶリンクとを前記閉路隣接グラフに追加した閉路探索グラフと、を生成し、前記閉路探索グラフにおいて、経路コストを基準として、所望の第１ノードと第２ノードとの間の複数の異なるグラフ経路を順次特定する機能と、特定されたグラフ経路ごとに含まれる閉路ノードが表す閉路を１つの閉路になるまで併合することにより、前記第１ノードと前記第２ノードとの間の複数の経路含有閉路を順次特定する機能と、前記複数の経路含有閉路から特定された複数の経路のうち重複した経路を削除することにより、前記ネットワークにおける前記第１ノードと前記第２ノードとの間の異なる３以上の所定数の経路を特定する機能と、を前記コンピュータで実現させることを特徴とする。
【発明の効果】
【０００９】
本発明によれば、２つのノードを結ぶ経路途中のリンク／ノードを共有しない３以上の異なる経路を特定する際の処理負荷を低減することができる。
【図面の簡単な説明】
【００１０】
【図１】図１は背景技術による経路特定方法を説明するためのネットワークトポロジを示す図である。
【図２】図２は本発明の第１実施形態による経路特定装置の機能構成を示す概略的ブロック図である。
【図３】図３は第１実施形態による経路特定方法を説明するための模式的ネットワーク図である。
【図４】図４は図３に示すネットワークの基本グラフ情報を示す模式図である。
【図５】図５は第１実施形態における閉路隣接グラフを生成するフローチャートである。
【図６】図６は第１実施形態における全域木を概念的に示す模式図である。
【図７】図７は図６における閉路Ｃ１００の閉路情報を示す模式図である。
【図８】図８は図６における閉路Ｃ２００の閉路情報を示す模式図である。
【図９】図９は図６における閉路Ｃ３００の閉路情報を示す模式図である。
【図１０】図１０は図６における閉路Ｃ４００の閉路情報を示す模式図である。
【図１１】図１１（Ａ）は本発明の第１実施形態による経路特定方法を説明するための閉路隣接グラフを示す図であり、図１１（Ｂ）は図１１（Ａ）の閉路隣接グラフに対応する閉路隣接グラフ情報を示す模式図である。
【図１２】図１２は図１１に示す閉路隣接グラフを用いた閉路探索グラフを示す模式図である。
【図１３】図１３は第１実施形態による経路特定方法を示すフローチャートである。
【図１４】図１４は図１２に示す閉路探索グラフから探索除外リンクを除いたグラフを示す模式図である。
【図１５】図１５は第１実施形態による経路含有閉路を表す閉路情報を示す模式図である。
【図１６】図１６は本発明の第２実施形態による経路特定方法を説明するための閉路隣接グラフを示す図である。
【図１７】図１７は図１６に示す閉路隣接グラフを用いた閉路探索グラフを示す模式図である。
【図１８】図１８は本発明の第３実施形態による経路特定装置のグラフ情報記憶部に格納される併合閉路情報を示す模式図である。
【図１９】図１９は本発明の第４実施形態による経路特定方法を示すフローチャートである。
【図２０】図２０は本発明の第５実施形態による経路特定装置の機能構成を示す概略的ブロック図である。
【発明を実施するための形態】
【００１１】
本発明の実施形態によれば、複数のノードがリンクで接続されたネットワークにおいて、任意の第１ノードと第２ノードとを共通の頂点として含むｋ(>=2)個の経路含有閉路を特定し、前記k個の経路含有閉路から、重複しない(k+1)本の異なる経路を特定する。前記ｋ個以上の経路含有閉路を特定するための手続きは、前記ネットワークのトポロジに基づいて作成される閉路探索グラフにおける、最短経路計算のｋ回の繰り返しに帰着させて行う。このように、少ない計算量で、第１ノードと第２ノードとを結ぶ経路途中のリンク／ノードを共有しない３以上の異なる経路を特定することができる。
【００１２】
本発明の実施形態による経路特定装置は情報処理装置として構成可能であり、たとえばネットワーク内のサーバ装置、ネットワーク・スイッチ、ルータ、パーソナルコンピュータ、携帯電話端末、ＰＨＳ（Personal Handyphone System）、ＰＤＡ（Personal Data AssistanceあるいはPersonal Digital Assistant）、スマートフォン、カーナビゲーション端末あるいはゲーム端末等に設けることができる。すなわち、本実施形態による経路特定装置は、中央処理装置（CPU; Central Processing Unit）、一次記憶装置（RAM; Random Access Memory）および二次記憶装置（ハードディスク駆動装置（HDD; Hard Disk Drive）を備える情報処理装置に実装可能である。
【００１３】
また、本実施形態による経路決定機能は、二次記憶装置に記憶されているプログラムをＣＰＵ上で実行することにより実現されてもよいし、回路等のハードウェアにより実現されてもよい。また、プログラムは、二次記憶装置ではなく、コンピュータが読み取り可能な記録媒体に記憶されていてもよい。例えば、記録媒体としては、フレキシブルディスク、光ディスク、光磁気ディスク、および、半導体メモリ等の可搬性を有する媒体を用いることが得きる。以下、本発明の実施形態および実施例について図面を参照しながら詳細に説明する。
【００１４】
１．第１実施形態
１．１）構成
図２に示すように、本発明の第１実施形態による経路特定装置１は、経路特定装置全体の動作を制御し、各種データ処理および演算を実行する制御部１０と、グラフ情報記憶部１１と、閉路特定部１２と、閉路探索空間特定部１３と、経路含有閉路特定部１４と、経路特定部１５と、経路選定部１６と、を含む。
【００１５】
ａ）グラフ情報記憶部１１
グラフ情報記憶部１１は、基本グラフ情報と、閉路情報と、閉路隣接グラフ情報と、閉路探索グラフ情報と、経路含有閉路情報と、を記憶する。詳しくは後述するが、グラフ情報記憶部１１に格納される情報の概略は以下の通りである。
【００１６】
基本グラフ情報は、基本グラフを構成する複数の基本ノードのそれぞれを識別するための基本ノード識別子と、複数の基本リンクのそれぞれを識別するための基本リンク識別子と、複数の基本ノードの任意の２つの基本ノードを結ぶ基本リンクを特定するための情報（即ち、２つの基本ノードがある基本リンクによって接続されているか否かを表す情報）と、を含む（具体的には図３および図４を参照）。基本グラフ情報は、隣接行列あるいは隣接リスト等の形式で表されるが、情報処理装置により処理可能な他の形式により表されてもよい。
【００１７】
閉路情報は、基本グラフにおける閉路（単位閉路）を表す情報である。閉路情報は、閉路を識別するための閉路識別子と当該閉路を構成する基本リンクを特定するための情報とを含む（具体的には図７〜図１０を参照）。
【００１８】
閉路隣接グラフ情報は、閉路隣接グラフを構成する複数の閉路ノードのそれぞれを識別するための閉路ノード識別子と、複数の閉路隣接リンクのそれぞれを識別するための閉路隣接リンク識別子と、複数の閉路ノードの任意の２つの閉路ノードを結ぶ閉路隣接リンクを特定するための情報（即ち、２つの閉路ノードが閉路隣接リンクによって接続されているか否かを表す情報）と、を含む（具体的には図１１（Ｂ）を参照）。閉路隣接グラフ情報は、隣接行列あるいは隣接リスト等の形式で表されるが、情報処理装置により処理可能な他の形式により表されてもよい。
【００１９】
ここで、閉路隣接グラフは、基本グラフにおける複数の閉路（単位閉路）のそれぞれを閉路ノードにより表すとともに、２つの閉路によって基本グラフにおける基本グラフ要素（基本ノード、又は、基本リンク）が共有されていることを、当該２つの閉路を結ぶ閉路隣接リンクにより表すグラフである（具体的には図１１（Ａ）を参照）。
【００２０】
閉路探索グラフ情報は、閉路探索グラフを表す情報である。ここで、閉路探索グラフは、閉路隣接グラフに包含ノードおよび包含リンクを追加したグラフである（具体的には図１２を参照）。包含ノードは、閉路ノードが表す閉路が基本グラフにおいて通る（即ち、当該閉路に含まれる）基本ノードを表すノードである。包含リンクは、閉路ノードが表す閉路が基本グラフにおいて包含ノードを通ることを表し、且つ、当該閉路ノードと当該包含ノードとを結ぶリンクである。閉路探索グラフ情報は、閉路隣接グラフ情報に加えて、複数の包含ノードのそれぞれを識別するための包含ノード識別子と、包含ノードと閉路ノードとの任意の組のそれぞれに対して、当該包含ノードと当該閉路ノードとを結ぶ包含リンクが存在するか否かを表す情報と、を含む。したがって、グラフ情報記憶部１１は閉路隣接グラフ情報を閉路探索グラフ情報の一部として保持することもできるし、閉路探索グラフ情報とは別に保持することもできる。
【００２１】
経路含有閉路情報は、基本グラフにおける経路含有閉路を表す情報である。経路含有閉路は、基本グラフにおいて、経路の端点となる２つのノード（第１の基本ノードと第２の基本ノード）を通る閉路である。経路含有閉路情報は、経路含有閉路を識別するための経路含有閉路識別子と、当該経路含有閉路を構成する基本リンクを特定するための情報と、を含む。
【００２２】
ｂ）閉路特定部１２
閉路特定部１２は、グラフ情報記憶部１１に記憶されている基本グラフ情報に基づいて、第１の基本ノードを通る第１の閉路と第２の基本ノードを通る第２の閉路とを含む複数の閉路を特定する。閉路特定部１２は特定された閉路を表す閉路情報をグラフ情報記憶部１１に格納する。
【００２３】
ｃ）閉路探索空間特定部１３
閉路探索空間特定部１３は、閉路特定部１２により特定された複数の閉路のうち、第１の基本ノードと第２の基本ノードとを通る閉路の特定に使用可能な閉路を選定し、選定された閉路情報もしくは選定された閉路を取得するための選定条件をグラフ情報記憶部１１に格納する。
【００２４】
ｄ）経路含有閉路特定部１４
経路含有閉路特定部１４は、閉路探索空間特定部１３により選定された閉路のうち、基本グラフ要素の少なくとも１つを共有する閉路同士を併合することにより経路含有閉路を特定する。ここで、経路含有閉路特定部１４は、２つの閉路が少なくとも１つの基本リンクを共有している場合、当該２つの閉路の一方から共有リンクを除いた部分を構成するすべての基本リンクと、当該２つの閉路の他方から共有リンクを除いた部分を構成するすべての基本リンクと、を連結した閉路を、当該２つの閉路同士を併合した閉路として用いる。ここで、共有リンクは、上記２つの閉路により共有されている基本リンクである。
【００２５】
具体的には、経路含有閉路特定部１４は、グラフ情報記憶部１１に記憶されている閉路情報に基づいて閉路隣接グラフを生成し、生成された閉路隣接グラフ情報をグラフ情報記憶部１１に格納する。加えて、経路含有閉路特定部１４は、生成された閉路隣接グラフに基づいて、基本グラフにおける経路含有閉路を特定する。このとき、経路含有閉路特定部１４は、基本グラフにおける基本リンクのそれぞれに対して予め設定された基本リンクコストの総和を最小とするように、基本グラフにおける経路含有閉路を特定する。また、閉路隣接グラフ内の閉路探索空間特定部１３により選定された閉路に相当する部分のみが使用される。経路含有閉路特定部１４は、特定された経路含有閉路を表す経路含有閉路情報をグラフ情報記憶部１１に格納する。
【００２６】
ｅ）経路特定部１５
経路特定部１５は、グラフ情報記憶部１１に記憶されている、経路含有閉路特定部１４により特定された経路含有閉路情報を用いて、第１の基本ノードと第２の基本ノードとを結び、且つ、基本リンクを共有しない２つの異なる経路を特定し、これら経路情報をグラフ情報記憶部１１に格納する。
【００２７】
ｆ）経路選定部１６
経路選定部１６は、グラフ情報記憶部１１に記録されている経路情報から第１の基本ノードと第２の基本ノードとを結び、且つ、基本リンクを共有しないｋ＋１（ｋ≧１）以上の異なる経路を選定する。
【００２８】
１．２）動作
次に、図３に示す基本グラフを一例として用い、経路特定装置１の経路特定動作について説明する。ただし、ここでは、簡単のために比較的規模が小さい基本グラフを例示するが、より規模が大きい基本グラフ、又は、より規模が小さい基本グラフに対しても、本実施形態による経路特定装置１が適用可能であることは言うまでもない。
【００２９】
図３に示す基本グラフは、７つの基本ノードＮ１００〜Ｎ７００と９つの基本リンクＬ１００〜Ｌ９００とにより構成されものとし、この基本グラフが図４に示す基本グラフ情報（隣接行列）により表される。図４に示す隣接行列おいて、「Ｎ１００」〜「Ｎ７００」がそれぞれ基本ノード識別子であり、隣接行列における値「１」は、当該値の行と列にそれぞれ対応付けられた２つの基本ノードが基本リンクにより接続されていることを示す。
【００３０】
１．２．１）閉路隣接グラフの生成
先ず、経路特定装置１の制御部１０は、図５に示す手順に従って閉路特定部１２を制御し、基本グラフから閉路隣接グラフを生成する。
【００３１】
図５において、閉路特定部１２は、基本グラフにおける全域木（スパニングツリー）Ｔを計算する（ステップＳ１０１）。全域木の取得には、深さ優先探索法、幅優先探索法、Ｄｉｊｋｓｔｒａ（ダイクストラ）法あるいはプリム法等の種々の方法を利用することができる。ここでは、図３に示す基本グラフに対して、図６に示す全域木が取得された場合を想定する。すなわち、本例における全域木は、図６に示すように、基本ノード（Ｎ１００〜Ｎ７００）と、実線により示された基本リンク（Ｌ１００、Ｌ４００〜Ｌ７００およびＬ１０００）とにより構成される。
【００３２】
次いで、閉路特定部１２は、取得された全域木Ｔに含まれない基本リンクの集合Ｅ’を生成する（ステップＳ１０２）。したがって、図７に示す例に従えば、初期状態の基本リンク集合Ｅ’には、図６における破線の基本リンクＬ２００、Ｌ３００、Ｌ６００、Ｌ８００およびＬ９００がメンバとして含まれる。以下、閉路特定部１２は、ステップＳ１０３〜Ｓ１０６によって、図６に示す全域木に対して、基本リンク集合Ｅ’から読み出した基本リンクを１つずつ追加することで閉路（単位閉路）を特定し、特定された閉路に基づいて閉路隣接グラフを生成する。具体的には、以下の通りである。
【００３３】
まず、閉路特定部１２は基本リンク集合Ｅ’が空集合であるか否かを判定し（ステップＳ１０３）、空集合でない場合には（ステップＳ１０３；Ｎｏ）、基本リンク集合Ｅ’から基本リンクを１つ読み出し、この基本リンクを全域木Ｔに追加することで構成される閉路を特定すると共に、読み出された基本リンクを基本リンク集合Ｅ’から削除する（ステップＳ１０４）。
【００３４】
続いて、閉路特定部１２は、特定された閉路を表す閉路ノードを閉路隣接グラフに追加し（ステップＳ１０５）、前回までに追加されていた閉路ノードが表す閉路と、今回新たに追加された閉路ノードが表す閉路とを結ぶ閉路リンクを閉路隣接グラフに追加する（ステップＳ１０６）。以上のステップＳ１０３〜ステップＳ１０６の処理が、基本リンク集合Ｅ’が空集合になるまで繰り返され、基本リンク集合Ｅ’が空集合となると（ステップＳ１０３；Ｙｅｓ）、閉路隣接グラフ生成処理を終了する。 
【００３５】
なお、閉路特定部１２は、上記処理により得られた閉路情報と閉路隣接グラフ情報とをグラフ情報記憶部１１に格納する。
【００３６】
図５に示す閉路隣接グラフ生成処理を図６に示す全域木を例にして説明する。まず基本リンク集合Ｅ’から基本リンクＬ２００を読み出して、図６に示す全域木に追加することにより、経路Ｎ１００−Ｎ２００−Ｎ６００−Ｎ１００からなる閉路Ｃ１００が得られ、これが閉路ノードＣ１００となる。同様に、基本リンクＬ３００を追加することにより経路Ｎ２００−Ｎ３００−Ｎ７００−Ｎ２００から閉路ノードＣ２００が、基本リンクＬ８００を追加することにより経路Ｎ３００−Ｎ４００−Ｎ５００−Ｎ７００−Ｎ３００から閉路ノードＣ３００が、基本リンクＬ９００を追加することにより経路Ｎ２００−Ｎ７００−Ｎ５００−Ｎ６００−Ｎ２００から閉路ノードＣ４００が、それぞれ得られる。
【００３７】
閉路Ｃ１００は図７に示す閉路情報（隣接行列）により表され、その閉路識別子が「Ｃ１００」である。同様に、閉路Ｃ２００は図８に示す閉路情報（隣接行列）により表され閉路識別子が「Ｃ２００」、閉路Ｃ３００は図９に示す閉路情報（隣接行列）により表され閉路識別子が「Ｃ３００」、閉路Ｃ４００は図１０に示す閉路情報（隣接行列）により表され閉路識別子が「Ｃ４００」である。
【００３８】
また、図６に示すように、閉路Ｃ１００と閉路Ｃ4００とは基本リンクＬ４００を共有している。また、閉路Ｃ２００と閉路Ｃ３００とは基本リンクＬ７００を、閉路Ｃ２００と閉路Ｃ４００とは基本リンクＬ５００を、閉路Ｃ３００と閉路Ｃ４００とは基本リンクＬ１０００を、それぞれ共有している。なお、２つの閉路間で複数の連結した基本リンクを共有している場合、その２つの閉路が共有している区間の両端以外に位置するノードを臨界ノードと呼ぶものとする。
【００３９】
こうして生成された閉路隣接グラフは、図１１（Ａ）のように表現できる。すなわち、閉路ノードＣ１００と閉路ノードＣ４００とが隣接リンクＡ１００により連結し、閉路ノードＣ２００と閉路ノードＣ４００とが隣接リンクＡ２００により、閉路ノードＣ２００と閉路ノードＣ３００とが隣接リンクＡ３００により、閉路ノードＣ３００と閉路ノードＣ４００とが隣接リンクＡ４００により、それぞれ錬鉄されている。この場合、隣接リンクＡ１００は基本リンクＬ４００と、隣接リンクＡ２００は基本リンクＬ５００と、隣接リンクＡ３００は基本リンクＬ７００と、隣接リンクＡ４００は基本リンクＬ１０００と、それぞれ関連づけられている。以下、隣接リンクＡが基本リンクＬと関連づけられている状態を単に「隣接リンクＡは基本リンクＬを含む（又は、内包する）」というものとする。なお、複数の連結した基本リンクを含む隣接リンクは臨界ノードを含む。
【００４０】
図１１（Ａ）に示す閉路隣接グラフは、図１１（Ｂ）に示す閉路隣接グラフ情報（隣接行列）により表される。図１１（Ｂ）において、隣接行列における値「１」は、当該値の行と列とにそれぞれ対応付けられた閉路ノード間を結ぶ隣接リンクが存在することを表わしている。 
【００４１】
なお、経路特定装置１は、上述した方法以外の方法で閉路隣接グラフを生成してもよい。ただし、閉路隣接グラフを生成する方法は、基本グラフにおける基本リンクのそれぞれが少なくとも１つの閉路ノードに含まれていること（第１の条件）と、閉路隣接グラフが連続していること（第２の条件）との両方を満たすことが好適である。上述した方法は、基本グラフにおける各基本リンクは全域木に含まれるか、又は、閉路を構成するために追加される基本リンクであるから第１の条件を満たし、いずれの閉路も全域木の一部を含むので第２の条件も満たしている。
【００４２】
１．２．２）閉路探索グラフの生成
続いて、制御部１０は閉路探索空間特定部１３を制御して、包含ノードを閉路隣接グラフに追加するとともに、閉路ノードと当該包含ノードとを結ぶ包含リンクを閉路隣接グラフに追加することにより、閉路探索グラフを生成する。図３に示す基本グラフを用いた場合の閉路探索グラフを図１２に示す。図１２において、閉路Ｃと包括ノードＮとを接続する破線は包含リンクＥ１０１〜Ｅ１１４を表す。
【００４３】
１．２．３）経路の特定
次に、制御部１０は、経路含有閉路特定部１４、経路特定部１５および経路選定部１６を制御して、閉路隣接グラフに基づいて経路を特定する。以下、図１３〜図１５を参照しながら、本実施形態による経路特定動作について説明する。
【００４４】
上述したように、グラフ情報記憶部１１には、基本グラフ情報、閉路情報および閉路隣接グラフ情報が格納されており、以下に説明するように、制御部１０はこれらの情報に基づいて経路を特定するように制御する。
【００４５】
まず、基本グラフ情報として、各基本リンクに対して予め設定された基本リンクコストをｗ０（ｘ）とする。パラメータｘは、基本リンクを特定するための情報である。なお、基本リンクコストｗ０（ｘ）は、経路特定装置１のユーザにより入力された情報であってもよい。基本リンクコストｗ０（ｘ）はスカラ値を有し、基本リンクの長さあるいは基本リンクのその他の属性等に基づいて設定されることが好適である。ところで、基本リンクの系列としての経路ｐ（＝｛ｌ０，ｌ１，…，ｌｉ｝）のコストＷ（ｐ）は、次式（１）により表される。
【００４６】
【数１】
0005958697.tif 000002
ここで、ｌｊはｊ番目の基本リンク、ｊは０〜ｉの整数である。
【００４７】
また、制御部１０は、基本リンクコストｗ０（ｘ）に基づいて、閉路隣接グラフにおける隣接リンクのそれぞれに対する隣接リンクコストｗ（ｘ）を算出する。パラメータｘが、閉路ノードｃ０と閉路ノードｃ１とを結ぶ隣接リンクである場合において、当該隣接リンクが第１の基本ノードと第２の基本ノードとのいずれも臨界ノードとして含まないとき、制御部１０は、隣接リンクコストｗ（ｘ）を次式（２）に基づいて算出する。
【００４８】
w(x) = W(co)+W(c1)−2W(co∩c1)      (2)
【００４９】
一方、パラメータｘが、閉路ノードｃ０と閉路ノードｃ１とを結ぶ隣接リンクである場合において、当該隣接リンクが第１の基本ノード又は第２の基本ノードの少なくとも一方を臨界ノードとして含むとき、制御部１０は、隣接リンクコストｗ（ｘ）を次式（３）に基づいて算出する。
【００５０】
w(x) = ∞    (3)
【００５１】
また、パラメータｘが、包含リンクである場合において、当該包含リンクが第１の基本ノードから閉路ノードｃへのリンクであるとき、制御部１０は、探索リンクコストｗ（ｘ）を次式（４）に基づいて算出する。
【００５２】
w(x) = W(c)   (4)
【００５３】
また、パラメータｘが、包含リンクである場合において、当該包含リンクが閉路ノードｃから第２の基本ノードへのリンクであるとき、制御部１０は、探索リンクコストｗ（ｘ）を次式（５）に基づいて算出する。
【００５４】
w(x) = 0     (5)
【００５５】
また、パラメータｘが、包含リンクである場合において、当該包含リンクが、第１の基本ノード及び第２の基本ノード以外の基本ノード（包含ノード）と、閉路ノードと、を結ぶとき、経路特定装置１は、探索リンクコストｗ（ｘ）を次式（６）に基づいて算出する。
【００５６】
w(x) = ∞    (6)
【００５７】
以下、第１の基本ノードおよび第２の基本ノードをそれぞれ基本ノードＮ３００およびＮ５００とし、ノードＮ３００とＮ５００との間で求める経路の数をｋ＝３として、図１３を参照しながら、経路特定装置１の経路特定動作を説明する。
【００５８】
図１３において、まず、制御部１０は、求めるべき経路数ｋから既に決定された経路数ｍを減じた値が０より大きいか否かを判定する（ステップＳ２０１）。なお、決定経路数ｍの初期値は０である。ｋ−ｍ＞０であれば（ステップＳ２０１；Ｙｅｓ）、制御部１０は、以下の処理を実行するようにし、そうでなければ（ステップＳ２０１；Ｎｏ）、経路特定処理は終了する。
【００５９】
ｋ−ｍ＞０であれば（ステップＳ２０１；Ｙｅｓ）、閉路探索空間特定部１３は、閉路探索グラフの探索可能領域を特定する（ステップＳ２０２）。具体的には、図１２に示す閉路探索グラフのうち、第１の基本ノードＮ３００と第２の基本ノードＮ５００とを通る閉路を構成するために使用可能な閉路の集合を与える。初期状態では閉路探索グラフ全体が探索可能領域となるが、それ以降では、後述するように、初期の探索可能領域からそれまでに特定された閉路ノード間の隣接リンクを除外した残りが探索可能領域となる。
【００６０】
なお、上記閉路の使用可否は、後述の経路含有閉路特定部１４によって特定された経路含有閉路に含まれる閉路の除外処理の他、基本ノード（通信装置）や基本リンク（通信路／通信回線）の稼動状態 (故障、負荷など) やそれらに対する管理・運用ポリシなどの外部からの情報を考慮して決定しても構わない。本例では簡単のため、初期状態で除外されるべき基本ノードないし基本リンクはないものとする。
【００６１】
続いて、経路含有閉路特定部１４は、特定された閉路探索グラフ内の探索可能領域において、最小コスト経路を特定する（ステップＳ２０３）。最小コスト経路は、第１の基本ノードＮ３００と第２の基本ノードＮ５００を通る閉路をのうち、コストが最小となる閉路を与える経路である。最小コスト経路を特定する方法としては、既に述べたように、幅優先探索法や修正ダイクストラ法（バンダリ法；非特許文献２）等の負のリンクコストを許容する最短経路計算アルゴリズムを用いることができる。
【００６２】
なお、閉路探索グラフ内の探索可能領域は、閉路探索グラフ内の使用不可能な閉路ノードに接続する隣接リンクあるいは包含リンクのコストを無限大∞とすることで表現できる。コスト∞のリンクは上記最短経路計算アルゴリズム内での経路探索候補から除外されるからである。
【００６３】
あるいは、図１４に例示するように、閉路探索グラフ内の使用不可能な閉路ノードに接続する隣接リンクあるいは包含リンクおよびコスト∞のリンクをグラフ情報から除外することで表現することもできる。たとえば、図１４で包含リンクＥが一方向にしか通過できない場合には、逆方向のコストを∞にすればよい。また更に、図１４において、リンクをもたないノードＮ１００、Ｎ２００、Ｎ４００、Ｎ６００、Ｎ７００をグラフ情報から除外しても構わない。あるいは、上記の表現方法を併用して閉路探索グラフ内の探索可能領域を表現しても構わない。
【００６４】
制御部１０は、閉路探索グラフにおける最小コスト経路が特定されたか否かを判定する（ステップＳ２０４）。最小コスト経路が特定されなかった場合には（ステップＳ２０４；Ｎｏ）、制御部１０は経路特定処理を終了する。ここでは、閉路探索グラフにおける最小コスト経路として、経路Ｎ３００−Ｃ２００−Ｃ４００−Ｎ５００が特定されたものとする。制御部１０は最小コスト経路が特定されたので（ステップＳ２０４；Ｙｅｓ）、経路特定部１５を制御して、閉路探索グラフにおける最小コスト経路が通る閉路を併合することにより経路含有閉路を特定する（ステップＳ２０５）。すなわち、２つの閉路Ｃ２００およびＣ４００のそれぞれから、２つの閉路により共有されている基本リンク（共有リンク）を除去し、残りの全ての基本リンクを連結した閉路を当該２つの閉路同士を併合した閉路（経路含有閉路）として用いる。閉路情報は図７〜図１０に示すような隣接行列として芦原されるので、２つの閉路同士を併合した閉路（経路含有閉路）はそれらの閉路情報（隣接行列）の排他的論理和を計算することにより得ることができる。
【００６５】
具体的には、図６に示すように、閉路Ｃ２００と閉路Ｃ４００を併合することにより、経路含有閉路Ｎ３００−Ｎ２００−Ｎ６００−Ｎ５００−Ｎ７００−Ｎ３００を特定することができる。すなわち、閉路Ｃ２００を示す図８の閉路情報（隣接行列）と閉路Ｃ４００を示す図９の閉路情報（隣接行列）との排他的論理和を算出することにより、図１５に示す経路含有閉路を表す閉路情報を得ることができる。ただし、閉路の併合方法は、これに限定されるものではない。
【００６６】
続いて、経路特定部１５は、特定された経路含有閉路において、第１の基本ノードＮ３００と第２の基本ノードＮ５００とを結ぶ最小コスト経路（第１の経路）を特定する（ステップＳ２０６）。経路特定部１５は、基本リンクコストｗ０（ｘ）に基づいて、幅優先探索法あるいはダイクストラ法等を用いることにより最小コスト経路を特定する。あるいは、第１の基本ノードＮ３００と第２の基本ノードＮ５００で上記の経路含有閉路を２つの経路に区切り、それぞれのコストを比較して最小コスト経路を特定してもよい。ここでは、最小コスト経路（第１の経路）として、Ｎ３００−Ｎ７００−Ｎ５００が特定されたものとする。
【００６７】
同様にして、経路特定部１５は、特定された経路含有閉路において、第１の基本ノードＮ３００と第２の基本ノードＮ５００とを結ぶ、第１の経路と異なる冗長経路（第２の経路）を特定する（ステップＳ２０７）。ここでは、冗長経路（第２の経路）として、Ｎ３００−Ｎ２００−Ｎ６００−Ｎ５００が特定されたものとする。第２の経路の特定方法としては、たとえば、ステップＳ２０５にて特定された経路含有閉路を表す環状リストからステップＳ２０６にて特定された第１の経路に相当する部分を取り除くことで第２の経路を特定する。なお、ステップＳ２０６にて特定された第１の経路における中間の基本ノード又は基本リンクを使用不可とする条件を設けた状態において、深さ優先探索法あるいはダイクストラ法等を用いることにより第２の経路を特定することもできる。
【００６８】
次に、制御部１０は経路選定部１６を制御して、特定された第１の経路と第２の経路によって計算結果を更新する（ステップＳ２０８）。具体的には、今回特定した２つの経路がこれまでに得られたいずれの経路とも全く重ならない場合には、今回得られた２つの経路を計算結果に追加する。もしこれまでの経路の一部でも重なりがあれば、その経路を計算結果から削除してから、今回特定した２つの経路を計算結果に追加する。
【００６９】
本例の場合、第１の基本ノードＮ３００と第２の基本ノードＮ５００との間の２つの経路が上記のステップＳ２０６およびステップＳ２０７において初めて計算されたため、計算結果は空の状態である。したがって、経路選定部１６は、今回得られた第１の経路および第２の経路をグラフ情報記憶部１１にそのまま記録する。こうして決定経路の総数ｍを更新した後（この場合、ｍ＝２に更新した後）、ステップＳ２０１へ戻る。
【００７０】
具体的に述べると、ｋ−２＞０であるから（ステップＳ２０１；Ｙｅｓ）、ステップＳ２０２において、前回のステップＳ２０３で特定された経路Ｎ２００−Ｃ２００−Ｃ４００−Ｎ５００が通る隣接リンクＡ２００を除外する（図１４参照）。これは前述の通り、隣接リンクＡ２００のコストを∞にする、もしくは閉路探索グラフから削除することで実現できる。
【００７１】
次に、制御部１０は、ステップＳ２０３において前回同様、閉路探索グラフの探索可能領域において最小コスト経路を特定する。今回は、図１４において経路Ｎ３００−Ｃ３００−Ｎ５００を特定する。最小コスト経路が特定されたので、ステップＳ２０４に続いて、ステップＳ２０５が実行される。
【００７２】
ステップＳ２０５において、経路含有閉路特定部１４は、最小コスト経路Ｎ３００−Ｃ３００−Ｎ５００が通る閉路を併合して新たな経路含有閉路を特定する。ただし、本例ではただ一つの閉路Ｃ３００を通るため、実際の閉路の併合処理は行われない。結果として、Ｎ３００−Ｎ４００−Ｎ５００−Ｎ７００−Ｎ３００の経路含有閉路が特定される。
【００７３】
次に、ステップＳ２０５で特定した経路含有閉路Ｎ３００−Ｎ４００−Ｎ５００−Ｎ７００−Ｎ３００に対して前回同様、第１の基本ノードＮ３００と第２の基本ノードＮ５００との間の最小コスト経路を特定する。本例では第３の経路としてＮ３００−Ｎ７００−Ｎ５００を得るものとする。
【００７４】
続いて、ステップＳ２０５で特定した経路含有閉路Ｎ３００−Ｎ４００−Ｎ５００−Ｎ７００−Ｎ３００に対して前回同様、第１の基本ノードＮ３００と第２の基本ノードＮ５００との間の冗長経路を特定する。この結果、第４の経路としてＮ３００−Ｎ４００−Ｎ５００を得る。
【００７５】
そして、ステップＳ２０６およびステップＳ２０７で特定した第３の経路と第４の経路を用いて、経路計算結果を更新する。(ステップＳ２０８)。今回特定した第３の経路と第４の経路のうち、第４の経路は前回のステップＳ２０６で特定した第１の経路と基本リンクＬ７００と基本リンクＬ１０００が重複している。したがって、第１の経路を計算結果から破棄し、第３の経路と第４の経路を計算結果に追加する。この段階で、計算結果として第２の経路Ｎ３００−Ｎ２００−Ｎ６００−Ｎ５００、第３の経路Ｎ３００−Ｎ７００−Ｎ５００、および、第４の経路Ｎ３００−Ｎ４００−Ｎ５００の計３本の経路（ｍ＝３）が特定されている。
【００７６】
こうして、ステップＳ２０１に戻ると、この段階ではｍ＝３であるから、ステップｓ２０１では「Ｎｏ」となるので経路特定処理を終了する。以上、所望の値ｋが与えられると、ｋ−ｍが０になるまで（ステップＳ２０１；Ｎｏ）あるいは最小コスト経路が特定されなくなるまで（ステップＳ２０４；Ｎｏ）、ステップＳ２０１〜Ｓ２０８が繰り返され、最初に指定した本数ｋの経路を特定することができる。なお、繰り返しを制御するステップＳ２０１はステップＳ２０８の次に設けられてもよい。
【００７７】
このようにして、経路特定装置１は、閉路探索グラフを用いることにより、第１の基本ノードＮ３００と第２の基本ノードＮ５００とを結び、基本リンクを共有しないｋ本の異なる経路を特定することができる。
【００７８】
１．３）効果
以上、説明したように、本発明の第１実施形態によれば、２つの基本ノードを結び、基本リンクを共有しない３つ以上の異なる経路を確実に特定することができる。更に、２つの基本ノードを結び、基本リンクあるいは経路途中の基本ノードを共有しない２つの異なる経路を特定する際の処理負荷を低減することができる。
【００７９】
更に、本発明の第１実施形態よれば、基本グラフにおける基本リンクのそれぞれに対して予め設定された基本リンクコストの総和を最小とするように、基本グラフにおける経路含有閉路を特定する。経路含有閉路を特定することにより、基本リンクコストの総和を最小とするように２つの基本ノードを結び、基本リンクあるいは経路途中の基本ノードを共有しない３つ以上の異なる経路を、計算負荷を増大させることなく、特定することが可能となる。
【００８０】
２．第２実施形態
次に、本発明の第２実施形態による経路特定装置について説明する。本実施形態によれば、経路含有閉路特定部１４が２つの閉路を併合して経路含有閉路を特定する際に、当該２つの閉路が１つの基本ノードのみを共有している場合でも、それらを併合対象にする点で第１実施形態と異なっている。
【００８１】
たとえば、図６において、閉路Ｃ１００と閉路Ｃ２００はノードＮ２００を唯一の共有ノードとしているが、本実施形態によれば、この場合も閉路Ｃ１００と閉路Ｃ２００を併合して１つの経路含有閉路として扱い、経路特定に利用することができる。なお、閉路Ｃ２００とＣ４００のように２つの閉路が基本リンク（図６のＬ５００）を共有している状態は「強隣接状態」とも呼ばれ、閉路Ｃ１００とＣ２００のように２つの閉路が、基本リンクを共有することなく基本ノードのみ（図６のＮ２００）を共有している状態は「弱隣接状態」とも呼ばれる。以下、本発明の第２実施形態の特徴的な点を中心に説明する。
【００８２】
２．１）構成
本実施形態による経路特定装置は、図２に示す第１実施形態による経路特定装置１と基本的に同じ機能構成を有するので、構成の説明は省略し、以下、図２と同じ参照番号を用いて経路特定機能について説明する。
【００８３】
２．２）動作
２．２．１）閉路隣接グラフの生成
経路特定装置１の閉路特定部１２は上述した第１実施形態と同様に閉路を特定する。閉路Ｃ１００と閉路Ｃ２００とは、基本リンクを共有することなく、基本ノードＮ２００のみを共有しているので弱隣接状態にある。制御部１０は、図１６に示すように、弱隣接状態を表す隣接リンクである弱隣接リンクＡ５００（点線で示す）を閉路隣接グラフに追加する。なお、弱隣接状態にある２つの閉路に共有される唯一の基本ノードは臨界ノードと見なされる。すなわち、いずれの弱隣接リンクも基本リンクを含まず臨界ノードを１つ含む。
【００８４】
２．２．２）閉路探索グラフの生成
続いて、制御部１０は閉路探索空間特定部１３を制御して、包含ノードを閉路隣接グラフに追加するとともに、閉路ノードと当該包含ノードとを結ぶ包含リンクを閉路隣接グラフに追加することにより、閉路探索グラフを生成する。図３に示す基本グラフを用いた場合の閉路探索グラフを図１７に示す。図１７において、閉路Ｃと包括ノードＮとを接続する破線は包含リンクＥ１０１〜Ｅ１１４を表す。
【００８５】
２．２．３）経路の特定
次に、制御部１０は、経路含有閉路特定部１４、経路特定部１５および経路選定部１６を制御して、図１７に示す閉路隣接グラフに基づいて経路を特定する。以下、第１実施形態と同様に図１３のフローチャートを参照しながら、第２実施形態の特徴的な動作を中心として説明する。なお、以下の説明において、第１実施形態と同様の動作については説明を簡略化あるいは省略する。
【００８６】
上述した第１実施形態における式（１）〜式（６）において、パラメータｘが閉路ノードｃ０と閉路ノードｃ１とを結ぶ隣接リンクであり、かつ閉路ノードｃ０が表す閉路と閉路ノードｃ１が表す閉路とが弱隣接状態にある場合、当該隣接リンク（弱隣接リンク）に含まれる基本ノードが求めるべき経路の端点でなければ、隣接リンクコストｗ（ｘ）は次式（７）により算出される。
【００８７】
w(x) = W(c0) + W(c1)   (7)
【００８８】
ただし、弱隣接リンクは基本リンクを含まないので式（４）は式（２）と同等である。したがって、第１実施形態における式（１）〜式（６）により示した隣接リンクコストｗ（ｘ）は、第２実施形態においてもそのまま使用することができる。
【００８９】
以下、第２実施形態による経路特定機能を説明するために、第１の基本ノードがノードＮ３００、第２の基本ノードがノードＮ６００であるとし、また、求める経路数ｋ＝３とする。
【００９０】
図１７に示すように、初期状態において、閉路探索グラフにおける最小コスト経路として経路Ｎ３００−Ｃ２００−Ｃ４００−Ｎ６００を特定したものとすると、第１実施形態で説明したように図１３のステップＳ２０１〜Ｓ２０８を実行することで、第１の経路Ｎ３００−Ｎ２００−Ｎ６００および第２の経路Ｎ３００−Ｎ７００−Ｎ５００−Ｎ６００を特定し（図６参照）、グラフ情報記憶部１１の計算結果に追加する。
【００９１】
続いて、図１７に示すように、閉路探索グラフにおける最小コスト経路として経路Ｎ３００−Ｃ３００−Ｃ４００−Ｎ６００を特定したものとすると、同様に図１３のステップＳ２０１〜Ｓ２０７を実行することで、第３の経路Ｎ３００−Ｎ７００−Ｎ２００−Ｎ６００および第４の経路Ｎ３００−Ｎ４００−Ｎ５００−Ｎ６００を特定する（図６参照）。しかしながら、ステップＳ２０８において、既に特定されている第１の経路と今回特定された第３の経路とは基本リンクＬ４００で重複しており、第２の経路と第４の経路とは基本リンクＬ９００で重複している。このため、経路選定部１６は、第１の経路および第２の経路を計算結果から破棄し、第３の経路と第４の経路を計算結果に追加する。
【００９２】
続いて、図１７に示すように、閉路探索グラフにおける最小コスト経路として経路Ｎ３００−Ｃ２００−Ｃ１００−Ｎ６００を特定したものとする。この場合、ステップＳ２０５において、前回同様、最小コスト経路を通る閉路を併合して経路含有閉路を特定し、経路含有閉路Ｎ３００−Ｎ２００−Ｎ１００−Ｎ６００−Ｎ２００−Ｎ７００−Ｎ３００が特定される。
【００９３】
続くステップＳ２０６において、経路特定部１５は、前回同様、経路含有閉路Ｎ３００−Ｎ２００−Ｎ１００−Ｎ６００−Ｎ２００−Ｎ７００−Ｎ３００から、第１の基本ノードＮ３００と第２の基本ノードＮ６００との間の最小コスト経路を特定する。ここでは、第５の経路Ｎ３００−Ｎ７００−Ｎ２００−Ｎ６００が特定されたものとする。同様に、ステップＳ２０７において、経路特定部１５は、経路含有閉路Ｎ３００−Ｎ２００−Ｎ１００−Ｎ６００−Ｎ２００−Ｎ７００−Ｎ３００から第６の経路Ｎ３００−Ｎ２００−Ｎ１００−Ｎ６００を特定する。
【００９４】
ところが、第５の経路は、グラフ情報記憶部１１に記録されている第３の経路Ｎ３００−Ｎ７００−Ｎ２００−Ｎ６００と同値である。したがって、ステップＳ２０８において、第３の経路は削除され、第５の経路および第６の経路がグラフ情報記憶部１１の計算結果に追加される。
【００９５】
この時点で計算結果として、３つの経路、すなわち第４の経路Ｎ３００−Ｎ４００−Ｎ５００−Ｎ６００、第５の経路Ｎ３００−Ｎ７００−Ｎ２００−Ｎ６００、第６の経路Ｎ３００−Ｎ２００−Ｎ１００−Ｎ６００が特定されているので、ステップＳ２０１において経路特定動作は終了する。
【００９６】
２．３）効果
以上説明したように、閉路Ｃ１００と閉路Ｃ２００のように１つの基本ノードだけを共有する閉路同士を第１実施形態と同様に併合させることにより、第１実施形態による経路特定装置１と同様の作用および効果を得ることができる。
【００９７】
３．第３実施形態
本発明の第３実施形態による経路特定装置では、経路を特定する処理中に取得される閉路情報を保持しておき、保持された閉路情報を他の経路を特定する処理で利用する。これにより経路特定処理を高速化することができる。以下、かかる相違点を中心として説明する。
【００９８】
図１８に示すように、第３実施形態におけるグラフ情報記憶部１１には、図２に示す各情報の加えて、併合閉路情報が格納されている。併合閉路情報は、ある２つの閉路が併合された場合、その併合により生成された閉路を表す情報を元になる２つの閉路情報と対応付けた情報である。
【００９９】
併合閉路情報は、図１８に示すように、併合の対象となる２つの閉路のそれぞれを識別するための閉路識別子と、併合により生成された閉路を識別するための閉路識別子と、を含むテーブルである。即ち、このテーブルにおける値である識別子は、当該値の行と列にそれぞれ対応付けられた閉路識別子により識別される閉路同士を併合することにより生成された閉路の識別子である。なお、併合閉路情報は、このようなテーブル形式ではなく、情報処理装置により処理可能な他の形式により表されてもよい。
【０１００】
本実施形態による経路特定装置１は、図１３のステップＳ２０５以外の処理を第１実施形態と同様に実行する。
【０１０１】
制御部１０は、ステップＳ２０５に進んだとき、まず、グラフ情報記憶部１１に、併合の対象となる２つの閉路に係る併合閉路情報が記憶されているか否かを判定する。併合の対象となる２つの閉路に係る併合閉路情報が記憶されている場合、制御部１０は、当該併合閉路情報から併合により生成された閉路を表す情報を取得する。
【０１０２】
一方、併合の対象となる２つの閉路に係る併合閉路情報が記憶されていない場合、制御部１０は、第１実施形態と同様に、２つの閉路同士を併合することにより経路含有閉路を生成する。更に、この場合、併合の対象となる２つの閉路の閉路識別子と併合により生成された閉路の閉路識別子とを対応付けて上記テーブル形式で記憶する。
【０１０３】
たとえば、閉路Ｃ２００とＣ４００を併合することにより閉路Ｃ５００が生成される場合を想定する。この場合、２つの閉路同士を併合する前は、併合閉路情報はＴ１の状態であるが、閉路Ｃ２００とＣ４００とを併合して閉路Ｃ５００が生成されると、併合閉路情報はＴ２の状態となる。このように保持された併合閉路情報を利用することで経路特定処理を高速化することができる。
【０１０４】
４．第４実施形態
本発明の第４実施形態による経路特定装置では、基本グラフに基づいて経路を特定できなかった場合にのみ閉路探索グラフを用いることにより経路を特定する。その他は、上述した第１〜第３実施形態と同様であるから、かかる相違点を中心として説明する。
【０１０５】
図１９において、経路特定装置１は、基本グラフに基づいて（即ち、閉路探索グラフを用いることなく）経路を特定する（ステップＳ４０１）。ここでは、ダイクストラ法を繰り返し用いることにより基本ノード間を結び互いに基本ノードを共有しない２つ以上の異なる経路を特定する。即ち、第１の経路を特定し、その後、第１の経路が通る基本ノードを基本グラフから除去したグラフに基づいて、第２の経路を特定する。同様にして、第(ｉ−１)経路を特定し、その後、第１〜第（ｉ−１）経路が通る基本ノードを基本グラフから除去したグラフに基づいて、第ｉ経路を特定する。ただし、１＜ｉ≦ｋである。なお、他の方法で経路を特定してもよい。
【０１０６】
ここで、基本グラフから基本ノードを除去する操作は、基本グラフのデータ構造から実際に基本ノードを除去する他、基本グラフのデータ構造に対して除去すべき基本ノードを隠蔽するマスキング処理を施す、あるいは、該基本ノードに接続する基本リンクのコストを∞にするなど、ダイクストラ法あるいは他の経路計算に用いられるアルゴリズムで該基本ノードが選択されないような処理であればよい。
【０１０７】
なお、第２実施形態あるいはそれに基づく第３実施形態のように、閉路隣接グラフにおける弱隣接リンクを許容する場合は、上記の特定した経路が通る基本ノードを基本グラフから除去する代わりに、上記の特定した経路が通る基本リンクを基本グラフから除去する。
【０１０８】
ステップＳ４０１の処理により特定される第１の経路は、基本グラフにおいてコストが最小となる経路である。一方、このように特定された第１の経路および第２の経路は、第１の経路のコストと第２の経路のコストとの和が最小であるとは限らない。
【０１０９】
次いで、制御部１０は、ステップＳ４０２にて、経路が特定されたか否かを判定する。ステップＳ４０１にて経路が特定されなかった場合、ステップＳ４０３にて、第１実施形態と同様に、閉路隣接グラフを生成するとともに、生成された閉路隣接グラフに基づいて、２つの異なる経路を特定する。なお、経路が特定された場合であっても、特定された経路が、予め設定された条件を満たさなかった場合、「Ｎｏ」と判定するように構成されていてもよい。例えば、この条件は、第２の経路のコストが、予め設定された基準値よりも大きいという条件である。ステップＳ４０１にて経路が特定された場合には（ステップＳ４０２；Ｙｅｓ）、処理の実行を終了する。
【０１１０】
以上、説明したように、本発明の第４実施形態によれば、第１実施形態と同様に効果を得ることができると共に、第１〜第ｋ（ｋ≧２）経路のコストの和が最小となる他の経路を特定することもできる。
【０１１１】
５．第５実施形態
図２０を参照しながら、本発明の第５実施形態による経路特定装置について説明する。第５実施形態による経路特定装置１０００は、閉路特定部１００１と、経路含有閉路特定部１００２と、経路特定部１００３と、経路選定部１００４と、閉路探索空間特定部１００５と、を備える。
【０１１２】
閉路特定部１００１は、第１の基本ノードを通る第１の閉路と第２の基本ノードを通る第２の閉路とを含む複数の閉路を特定する。経路含有閉路特定部１００２は、特定された複数の閉路のうちの基本ノード又は基本リンクである基本グラフ要素の少なくとも１つを共有する閉路同士を併合することにより第１の基本ノードと第２の基本ノードとを通る閉路である経路含有閉路を特定する。経路特定部１００３は、特定された経路含有閉路において、第１の基本ノードと第２の基本ノードとを結び、基本ノードあるいは基本リンクを共有しない２つの異なる経路を特定する。経路選定部１００４は、特定された上記２つの異なる経路に基づいて、特定済みの経路を保持する計算結果を更新する。閉路探索空間特定部１００５は、経路含有閉路特定部１００２によって行われた閉路間の併合を次回から適用不可能な処理として記録する。
【０１１３】
更に、経路含有閉路特定部１００２〜閉路探索空間特定部１００５の一連の処理は、第１の基本ノードと第２の基本ノードとを結び基本ノードあるいは基本リンクを共有しない経路が求めるべき数だけ特定できるまで、あるいはその数だけ特定するのは不可能と判断されるまで、繰り返されるように構成される。このように構成することにより、２つの基本ノードを結び基本リンクを共有しない２つ以上の異なる経路を確実に特定することができ、その処理負荷を低減することができる。
【０１１４】
６．その他
上述した第１実施形態〜第４実施形態においては、経路特定装置１は、閉路探索グラフの生成する処理（第１の処理）と経路の特定する処理（第２の処理）とを続けて実行するように構成されていた。ところで、経路特定装置１は、第１の処理の実行結果を保持し、その後、保持されている実行結果を用いることにより、複数回、第２の処理を実行するように構成されていてもよい。
【０１１５】
また、閉路隣接グラフ又は閉路探索グラフを生成するためのプログラムと、経路を特定するためのプログラムと、は、１つのプログラムを構成していてもよいし、互いに独立した２つのプログラムであってもよい。なお、経路特定装置１は、互いに独立した２つのプログラムのそれぞれに対して、中央処理装置、一次記憶装置、及び、二次記憶装置等のプログラムを実行するために必要な計算資源を、物理的又は論理的に分離して割り当てるように構成されていてもよい。
【０１１６】
なお、上記各実施形態において経路特定装置の各機能は、ＣＰＵがプログラム（ソフトウェア）を実行することにより実現されていたが、回路等のハードウェアにより実現されていてもよい。また、上記各実施形態においてプログラムは、記憶装置に記憶されていたが、コンピュータが読み取り可能な記録媒体に記憶されていてもよい。例えば、記録媒体は、フレキシブルディスク、光ディスク、光磁気ディスク、及び、半導体メモリ等の可搬性を有する媒体である。
【０１１７】
以上、上記実施形態を参照して本願発明を説明したが、本願発明は、上述した実施形態に限定されるものではない。本願発明の構成及び詳細に、本願発明の範囲内において当業者が理解し得る様々な変更をすることができる。また、上記実施形態の他の変形例として、上述した実施形態及び変形例の任意の組み合わせが採用されてもよい。
【０１１８】
７．付記
上述した実施形態の一部あるいは全部は、以下の付記のようにも記載されうるが、これらに限定されるものではない。
（付記１）
複数のノードがリンク接続されたネットワークにおける経路特定方法であって、
前記ネットワーク内にある複数のノードおよびリンクにより閉じられた経路（以下、閉路という。）に基づいて、任意の第１ノードおよび第２ノードを通り互いに交差しないｋ個（ｋは２以上の整数）の経路含有閉路を特定し、
前記ｋ個の経路含有閉路から前記第１ノードと前記第２ノードとの間の異なる（ｋ＋１）個の経路を特定する、
ことを特徴とする経路特定方法。
（付記２）
前記ｋ個の経路含有閉路は、前記第１ノードと前記第２ノードとの間の経路コストを基準として特定されることを特徴とする付記１に記載の経路特定方法。
（付記３）
前記ｋ個の経路含有閉路からそれぞれ２本の経路を特定し、重複した経路を削除することで前記（ｋ＋１）個の経路を特定することを特徴とする付記１または２に記載の経路特定方法。
（付記４）
前記ｋ個の経路含有閉路の各々は、前記第１ノードを通る単位閉路と前記第２ノードを通る単位閉路とを含む複数の単位閉路を併合することで特定されることを特徴とする付記１−３のいずれか１項に記載の経路特定方法。
（付記５）
複数のノードがリンク接続されたネットワークにおける経路特定装置であって、
前記ネットワーク内にある複数のノードおよびリンクにより閉じられた経路（以下、閉路という。）に基づいて、任意の第１ノードおよび第２ノードを通り互いに交差しないｋ個（ｋは２以上の整数）の経路含有閉路を特定する閉路特定手段と、
前記ｋ個の経路含有閉路から前記第１ノードと前記第２ノードとの間の異なる（ｋ＋１）個の経路を特定する経路特定手段と、
を有することを特徴とする経路特定装置。
（付記６）
前記閉路特定手段は、前記第１ノードと前記第２ノードとの間の経路コストを基準として前記ｋ個の経路含有閉路を特定することを特徴とする付記５に記載の経路特定装置。
（付記７）
前記経路特定手段は、前記ｋ個の経路含有閉路からそれぞれ２本の経路を特定し、重複した経路を削除することで前記（ｋ＋１）個の経路を特定することを特徴とする付記５または６に記載の経路特定装置。
（付記８）
前記閉路特定手段は、
前記第１ノードを通る単位閉路と前記第２ノードを通る単位閉路とを含む複数の単位閉路を併合することで前記ｋ個の経路含有閉路の各々を順次特定することを特徴とする付記５−７のいずれか１項に記載の経路特定装置。
（付記９）
複数のノードがリンク接続されたネットワークにおける経路特定装置としてコンピュータを機能させるプログラムであって、
前記ネットワーク内にある複数のノードおよびリンクにより閉じられた経路（以下、閉路という。）に基づいて、任意の第１ノードおよび第２ノードを通り互いに交差しないｋ個（ｋは２以上の整数）の経路含有閉路を特定する機能と、
前記ｋ個の経路含有閉路から前記第１ノードと前記第２ノードとの間の異なる（ｋ＋１）個の経路を特定する機能と、
を前記コンピュータで実現させることを特徴とするプログラム。
（付記１０）
基本ノードと、２つの基本ノードを結ぶ基本リンクと、により構成される基本グラフにおいて第１の基本ノードと第２の基本ノードとを結ぶ経路を特定する経路特定方法であって、
ａ）前記第１の基本ノードを通る第１の閉路と前記第２の基本ノードを通る第２の閉路とを含む複数の閉路を特定し、
ｂ）前記特定された複数の閉路のうちの、基本ノード又は基本リンクである基本グラフ要素の少なくとも１つを共有する閉路同士を併合することにより、前記第１の基本ノードと前記第２の基本ノードとを通る閉路である第１の経路含有閉路を特定し、
ｃ）前記第１の基本ノードと前記第２の基本ノードを通る閉路である第(k-1)の経路含有閉路を特定した後（ただし、kは２以上の整数）、前記特定された複数の閉路のうち、前記第１の経路含有閉路から前記第(k-1)の経路含有閉路の特定過程で併合された閉路を除いた閉路集合のうちの、基本ノード又は基本リンクである基本グラフ要素の少なくとも１つを共有する閉路同士を併合することにより、前記第１の基本ノードと前記第２の基本ノードを通る閉路である第kの経路含有閉路を特定し、
ｄ）前記ｃ）をk=2からkを１ずつ増加させながら（k-1）回繰り返すことで特定されたk個の経路含有閉路から、前記第１の基本ノードと前記第２の基本ノードとを結び基本リンクまたは当該第１の基本ノード及び当該第２の基本ノード以外の基本ノードを共有しない(k+1)の異なる経路を特定する、
ことを特徴とする経路特定方法。
（付記１１）
付記１０に記載の経路特定方法であって、
前記第１の基本ノードと前記第２の基本ノードとを結ぶ経路の特定に使用可能な閉路の集合を示すこと、あるいは、前記第１の基本ノードと前記第２の基本ノードとを結ぶ経路の特定に使用不可能な閉路の集合を示すことにより、前記第１の基本ノードと前記第２の基本ノードとを結ぶ経路の特定に使用可能な閉路を選定することを特徴とする経路特定方法。
（付記１２）
付記１０または１１に記載の経路特定方法であって、
第i (i>1)の経路含有閉路より得る、前記第１の基本ノードと前記第２の基本ノードとを結ぶ第(2*i-1)および第(2*i)の経路のいずれかと、第j(j >i) の経路含有閉路より得る、前記第１の基本ノードと前記第２の基本ノードとを結ぶ第(2*j-1)および第(2*j)の経路のいずれかが前記第１の基本ノードおよび前記第２の基本ノードを除く基本ノードもしくは基本リンクを共有している場合、該当する前記第(2*i-1)の経路もしくは前記第(2*i)の経路あるいはその両方を破棄し、前記(k+1)の異なる経路を特定することを特徴とする経路特定方法。
（付記１３）
付記１０−１２のいずれか１項に記載の経路特定方法であって、
２つの閉路が少なくとも１つの基本リンクを共有している場合、当該２つの閉路の一方から、当該共有されている基本リンクである共有リンクを除いた部分を構成するすべての基本リンクと、当該２つの閉路の他方から、当該共有リンクを除いた部分を構成するすべての基本リンクと、を連結した閉路を当該２つの閉路同士を併合した閉路として用いることを特徴とする経路特定方法。
（付記１４）
付記１３に記載の経路特定方法であって、
２つの閉路が基本リンクを共有することなく基本ノードのみを共有している場合、当該２つの閉路の一方を構成するすべての基本リンクと、当該２つの閉路の他方を構成するすべての基本リンクと、を連結した閉路を当該２つの閉路同士を併合した閉路として用いること特徴とする経路特定方法。
（付記１５）
付記１３または１４に記載の経路特定方法であって、
前記特定された複数の閉路のそれぞれを閉路ノードにより表すとともに、２つの閉路によって前記基本グラフにおける基本グラフ要素が共有されていることを、当該２つの閉路のそれぞれを表す閉路ノードを結ぶ隣接リンクにより表す閉路隣接グラフを生成し、
前記生成された閉路隣接グラフに、前記閉路ノードが表す閉路が前記基本グラフにおいて通る基本ノードのそれぞれを表す包含ノードと、閉路ノードが表す閉路が前記基本グラフにおいて包含ノードを通ることを表し且つ当該閉路ノードと当該包含ノードとを結ぶ包含リンクと、を追加した、閉路探索グラフを生成し、
当該生成された閉路探索グラフに基づいて前記基本グラフにおける前記経路含有閉路を特定する、
ことを特徴とする経路特定方法。
（付記１６）
付記１０−１５のいずれか１項に記載の経路特定方法であって、
前記経路含有閉路特定手段は、前記基本グラフにおける前記基本リンクのそれぞれに対して予め設定された基本リンクコストの総和を最小とするように、前記基本グラフにおける前記経路含有閉路を特定することを特徴とする経路特定方法。
（付記１７）
基本ノードと、２つの基本ノードを結ぶ基本リンクと、により構成される基本グラフにおいて第１の基本ノードと第２の基本ノードとを結ぶ経路を特定する経路特定装置であって、
前記第１の基本ノードを通る第１の閉路と前記第２の基本ノードを通る第２の閉路とを含む複数の閉路を特定する閉路特定手段と、
前記特定された複数の閉路のうち、前記第１の基本ノードと前記第２の基本ノードとを結ぶ経路の特定に使用可能な閉路の集合を選定する閉路探索空間特定手段と、
前記特定された閉路探索空間に含まれる閉路のうちの、基本ノード又は基本リンクである基本グラフ要素の少なくとも１つを共有する閉路同士を併合することにより、前記第１の基本ノードと前記第２の基本ノードとを通る閉路である経路含有閉路を特定する経路含有閉路特定手段と、
前記特定された経路含有閉路において、前記第１の基本ノードと前記第２の基本ノードとを結び、且つ、基本リンク、又は、当該第１の基本ノード及び当該第２の基本ノード以外の基本ノードを共有しない、２つの異なる経路を特定する経路特定手段と、
前記経路含有閉路特定手段によって得る、前記第１の基本ノードと前記第２の基本ノードとを通るk個(k≧1)の経路含有閉路から前記経路特定手段によって得る2*kの経路から、(k+1)以上の異なる経路を選定する、経路選定手段と、
を備えることを特徴とする経路特定装置。
（付記１８）
基本ノードと、２つの基本ノードを結ぶ基本リンクと、により構成される基本グラフにおいて第１の基本ノードと第２の基本ノードとを結ぶ経路を特定する経路特定機能をコンピュータに実現するためのプログラムであって、
ａ）前記第１の基本ノードを通る第１の閉路と前記第２の基本ノードを通る第２の閉路とを含む複数の閉路を特定し、
ｂ）前記特定された複数の閉路のうちの、基本ノード又は基本リンクである基本グラフ要素の少なくとも１つを共有する閉路同士を併合することにより、前記第１の基本ノードと前記第２の基本ノードとを通る閉路である第１の経路含有閉路を特定し、
ｃ）前記第１の基本ノードと前記第２の基本ノードを通る閉路である第(k-1)の経路含有閉路を特定した後（ただし、kは２以上の整数）、前記特定された複数の閉路のうち、前記第１の経路含有閉路から前記第(k-1)の経路含有閉路の特定過程で併合された閉路を除いた閉路集合のうちの、基本ノード又は基本リンクである基本グラフ要素の少なくとも１つを共有する閉路同士を併合することにより、前記第１の基本ノードと前記第２の基本ノードを通る閉路である第kの経路含有閉路を特定し、
ｄ）前記ｃ）をk=2からkを１ずつ増加させながら（k-1）回繰り返すことで特定されたk個の経路含有閉路から、前記第１の基本ノードと前記第２の基本ノードとを結び基本リンクまたは当該第１の基本ノード及び当該第２の基本ノード以外の基本ノードを共有しない(k+1)の異なる経路を特定する、
ように前記コンピュータを機能させることを特徴とする経路特定プログラム。
【産業上の利用可能性】
【０１１９】
本発明は第１のノードと第２のノードとを結ぶ経路を特定する機能を有するサーバ装置などに適用可能である。
【符号の説明】
【０１２０】
１  経路特定装置
１１  グラフ情報記憶部 
１２  閉路特定部 
１３  閉路探索空間特定部
１４  経路含有閉路特定部 
１５  経路特定部 
１６  経路選定部
１０００  経路特定装置 
１００１  閉路特定部
１００２  経路含有閉路特定部 
１００３  経路特定部
１００４  経路選定部
１００５  閉路探索空間特定部
【図１】
0005958697.tif 000003
【図２】
0005958697.tif 000004
【図３】
0005958697.tif 000005
【図４】
0005958697.tif 000006
【図５】
0005958697.tif 000007
【図６】
0005958697.tif 000008
【図７】
0005958697.tif 000009
【図８】
0005958697.tif 000010
【図９】
0005958697.tif 000011
【図１０】
0005958697.tif 000012
【図１１】
0005958697.tif 000013
【図１２】
0005958697.tif 000014
【図１３】
0005958697.tif 000015
【図１４】
0005958697.tif 000016
【図１５】
0005958697.tif 000017
【図１６】
0005958697.tif 000018
【図１７】
0005958697.tif 000019
【図１８】
0005958697.tif 000020
【図１９】
0005958697.tif 000021
【図２０】
0005958697.tif 000022