経路特定装置、経路特定方法、及び、経路特定プログラム
【課題】２つのノードを結び、且つ、リンク又はノードを共有しない、２つの異なる経路を特定する際の処理負荷を低減することが可能な経路特定装置を提供すること。
【解決手段】経路特定装置１０００は、基本ノードと２つの基本ノードを結ぶ基本リンクとにより構成される基本グラフにて第１の基本ノードと第２の基本ノードとを結ぶ経路を特定する。経路特定装置は、第１の基本ノードを通る閉路と第２の基本ノードを通る閉路とを含む複数の閉路を特定する閉路特定部１００１と、複数の閉路のうちの、基本ノード又は基本リンクを共有する閉路同士を併合することにより、第１の基本ノードと第２の基本ノードとを通る経路含有閉路を特定する経路含有閉路特定部１００２と、経路含有閉路において、第１の基本ノードと第２の基本ノードとを結び且つ基本リンク又は基本ノードを共有しない、２つの異なる経路を特定する経路特定部１００３と、を備える。
【解決手段】経路特定装置１０００は、基本ノードと２つの基本ノードを結ぶ基本リンクとにより構成される基本グラフにて第１の基本ノードと第２の基本ノードとを結ぶ経路を特定する。経路特定装置は、第１の基本ノードを通る閉路と第２の基本ノードを通る閉路とを含む複数の閉路を特定する閉路特定部１００１と、複数の閉路のうちの、基本ノード又は基本リンクを共有する閉路同士を併合することにより、第１の基本ノードと第２の基本ノードとを通る経路含有閉路を特定する経路含有閉路特定部１００２と、経路含有閉路において、第１の基本ノードと第２の基本ノードとを結び且つ基本リンク又は基本ノードを共有しない、２つの異なる経路を特定する経路特定部１００３と、を備える。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、第１のノードと第２のノードとを結ぶ経路を特定する経路特定装置に関する。
【背景技術】
【０００２】
ノードと、２つのノードを結ぶリンクと、により構成されるグラフにおいて、第１のノードと第２のノードとを結ぶ経路を特定する経路特定装置が知られている。この種の経路特定装置は、例えば、通信網等のネットワーク状に通信装置が接続された通信システムにおける通信装置間の経路を特定するために用いられる。
【０００３】
特に、経路特定装置は、ある経路を特定するとともに、その経路に対して冗長な経路も特定する（即ち、２つのノードを結び、且つ、リンクやノードを共有しない２つの異なる経路を特定する）ように構成されることが好適である。これによれば、システムは、障害の発生により、ある経路が使用不能となっても、その経路に対して冗長な経路を使用することができる。
【０００４】
ところで、冗長な経路を特定するための最も代表的な方法として、Ｄｉｊｋｓｔｒａ法（非特許文献１を参照）を繰り返し用いる方法が知られている。各リンクにコスト値が与えられ、経路のコストがその経路が経由するリンクのコスト和で与えられるグラフにおいて、この方法は、先ず、第１のノードと第２のノードとを結ぶ経路として、コストが最小となる経路（第１の経路）を、Ｄｉｊｋｓｔｒａ法に従って特定する。次いで、この方法は、特定された経路に含まれる、すべてのリンクを除外したグラフにおいて、再度、第１のノードと第２のノードとを結ぶ経路として、コストが最小となる経路（第２の経路）を、Ｄｉｊｋｓｔｒａ法に従って特定する。又は、この方法は、特定された経路に含まれる、すべての中間ノードを除外したグラフにおいて、再度、第１のノードと第２のノードとを結ぶ経路として、コストが最小となる経路（第２の経路）をＤｉｊｋｓｔｒａ法に従って特定する。
【０００５】
この方法を用いることにより、経路特定装置は、第１のノードと第２のノードとを結び、且つ、リンクやノードを共有しない２つの異なる経路（第１の経路、及び、第２の経路）を特定することができる。
【０００６】
しかしながら、上記方法によれば、経路を特定する対象となるグラフのトポロジがトラップ構造を含む場合、第１のノードと第２のノードとを結び、且つ、リンクを共有しない２つの異なる経路が存在しているときであっても、これらの経路を特定することができないことがある。
【０００７】
例えば、図１に示したグラフにおいて、第１のノードＮ１００と第２のノードＮ４００とを結ぶ経路を特定する場合を想定する。この場合において、リンクＬ１００、リンクＬ９００、リンクＬ５００、及び、リンクＬ４００をこの順に連結した経路（第１の経路）が、コストが最小となる経路である場合を想定する。
【０００８】
この場合、第１の経路に含まれる、すべてのリンクを除外したグラフは、図２に示したグラフである。ここで、破線は、除外されたリンクを表す。従って、このグラフにおいては、第１のノードＮ１００と第２のノードＮ４００とを結ぶ経路を特定することができない。即ち、このグラフのトポロジは、トラップ構造を含んでいる、と言うことができる。
【０００９】
このような課題に対処するため、Ｂｈａｎｄａｒｉ法（非特許文献２を参照）が知られている。この方法は、Ｄｉｊｋｓｔｒａ法を繰り返し用いる工程を拡張することにより、グラフのトポロジの一部を変換し、その結果、トラップ構造の基となるリンクであるトラップリンクを特定する。更に、この方法は、特定されたトラップリンクを除いたグラフにおいて、再度、Ｄｉｊｋｓｔｒａ法を繰り返し用いることにより、リンクを共有しない２つの異なる経路を特定する。
【先行技術文献】
【非特許文献】
【００１０】
【非特許文献１】E. W. Dijkstra、“A note on two problems in connexion with graphs”、 NumerischeMathematik 1、１９５９年、 pp. 269 − 271
【非特許文献２】Ramesh Bhandari、“Survivable Networks: Algorithms for diverse routing”、Springer、１９９９年
【発明の概要】
【発明が解決しようとする課題】
【００１１】
しかしながら、上記非特許文献２に記載の技術においては、トラップリンクを特定し、特定したトラップリンクの影響を排除するための処理の負荷（処理負荷）が比較的大きい。即ち、上記非特許文献２に記載の技術においては、２つのノードを結び、且つ、リンク、又は、当該２つのノード以外のノード（即ち、経路途中のノード）を共有しない、２つの異なる経路を特定する際の処理負荷が過大であるという問題があった。
【００１２】
このため、本発明の目的は、上述した課題である「２つのノードを結び、且つ、リンク、又は、経路途中のノードを共有しない、２つの異なる経路を特定する際の処理負荷が過大であること」を解決することが可能な経路特定装置を提供することにある。
【課題を解決するための手段】
【００１３】
かかる目的を達成するため本発明の一形態である経路特定装置は、
基本ノードと、２つの基本ノードを結ぶ基本リンクと、により構成される基本グラフにおいて、第１の基本ノードと第２の基本ノードとを結ぶ経路を特定する装置である。
【００１４】
更に、この経路特定装置は、
上記第１の基本ノードを通る第１の閉路と、上記第２の基本ノードを通る第２の閉路と、を含む複数の閉路を特定する閉路特定手段と、
上記特定された複数の閉路のうちの、基本ノード又は基本リンクである基本グラフ要素の少なくとも１つを共有する閉路同士を併合することにより、上記第１の基本ノードと上記第２の基本ノードとを通る閉路である経路含有閉路を特定する経路含有閉路特定手段と、
上記特定された経路含有閉路において、上記第１の基本ノードと上記第２の基本ノードとを結び、且つ、基本リンク、又は、当該第１の基本ノード及び当該第２の基本ノード以外の基本ノードを共有しない、２つの異なる経路を特定する経路特定手段と、
を備える。
【００１５】
また、本発明の他の形態である経路特定方法は、
基本ノードと、２つの基本ノードを結ぶ基本リンクと、により構成される基本グラフにおいて、第１の基本ノードと第２の基本ノードとを結ぶ経路を特定する方法である。
【００１６】
更に、この経路特定方法は、
上記第１の基本ノードを通る第１の閉路と、上記第２の基本ノードを通る第２の閉路と、を含む複数の閉路を特定し、
上記特定された複数の閉路のうちの、基本ノード又は基本リンクである基本グラフ要素の少なくとも１つを共有する閉路同士を併合することにより、上記第１の基本ノードと上記第２の基本ノードとを通る閉路である経路含有閉路を特定し、
上記特定された経路含有閉路において、上記第１の基本ノードと上記第２の基本ノードとを結び、且つ、基本リンク、又は、当該第１の基本ノード及び当該第２の基本ノード以外の基本ノードを共有しない、２つの異なる経路を特定する方法である。
【００１７】
また、本発明の他の形態である経路特定プログラムは、
情報処理装置に、
基本ノードと、２つの基本ノードを結ぶ基本リンクと、により構成される基本グラフにおいて、第１の基本ノードと第２の基本ノードとを結ぶ経路を特定する処理を実行させるためのプログラムである。
【００１８】
更に、上記処理は、
上記第１の基本ノードを通る第１の閉路と、上記第２の基本ノードを通る第２の閉路と、を含む複数の閉路を特定し、
上記特定された複数の閉路のうちの、基本ノード又は基本リンクである基本グラフ要素の少なくとも１つを共有する閉路同士を併合することにより、上記第１の基本ノードと上記第２の基本ノードとを通る閉路である経路含有閉路を特定し、
上記特定された経路含有閉路において、上記第１の基本ノードと上記第２の基本ノードとを結び、且つ、基本リンク、又は、当該第１の基本ノード及び当該第２の基本ノード以外の基本ノードを共有しない、２つの異なる経路を特定するように構成される。
【発明の効果】
【００１９】
本発明は、以上のように構成されることにより、２つのノードを結び、且つ、リンク、又は、経路途中のノードを共有しない、２つの異なる経路を特定する際の処理負荷を低減することができる。
【図面の簡単な説明】
【００２０】
【図１】背景技術に係る、経路が特定される対象となるグラフを示した図である。
【図２】背景技術に係る、第１の経路に含まれる、すべてのリンクを除外したグラフを示した図である。
【図３】本発明の第１実施形態に係る経路特定装置の機能の概略を表すブロック図である。
【図４】本発明の第１実施形態に係る、経路が特定される対象となる基本グラフを示した図である。
【図５】本発明の第１実施形態に係る基本グラフ情報を示したテーブルである。
【図６】本発明の第１実施形態に係る経路特定装置が、閉路隣接グラフを生成するために実行する処理を示したフローチャートである。
【図７】本発明の第１実施形態に係る経路特定装置が取得する全域木を概念的に示した説明図である。
【図８】本発明の第１実施形態に係る閉路情報を示したテーブルである。
【図９】本発明の第１実施形態に係る閉路情報を示したテーブルである。
【図１０】本発明の第１実施形態に係る閉路情報を示したテーブルである。
【図１１】本発明の第１実施形態に係る経路特定装置が生成した閉路隣接グラフを示した図である。
【図１２】本発明の第１実施形態に係る閉路隣接グラフ情報を示したテーブルである。
【図１３】本発明の第１実施形態に係る経路特定装置が、閉路隣接グラフに基づいて経路を特定するために実行する処理を示したフローチャートである。
【図１４】本発明の第１実施形態に係る、経路含有閉路を表す閉路情報を示したテーブルである。
【図１５】本発明の第２実施形態に係る、経路が特定される対象となる基本グラフを示した図である。
【図１６】本発明の第２実施形態に係る経路特定装置が生成した閉路隣接グラフを示した図である。
【図１７】本発明の第３実施形態に係る、経路が特定される対象となる基本グラフを示した図である。
【図１８】本発明の第３実施形態に係る経路特定装置が、閉路隣接グラフを生成するために実行する処理を示したフローチャートである。
【図１９】本発明の第３実施形態に係る経路特定装置が生成した閉路隣接グラフを示した図である。
【図２０】本発明の第４実施形態に係る併合閉路情報を示したテーブルである。
【図２１】本発明の第４実施形態に係る併合閉路情報を示したテーブルである。
【図２２】本発明の第５実施形態に係る経路特定装置が生成した閉路探索グラフを示した図である。
【図２３】本発明の第５実施形態に係る経路特定装置が生成した閉路探索グラフから、探索リンクコストが∞であるリンクを除去したグラフを示した図である。
【図２４】本発明の第６実施形態に係る経路特定装置が、経路を特定するために実行する処理を示したフローチャートである。
【図２５】本発明の第７実施形態に係る経路特定装置の機能の概略を表すブロック図である。
【発明を実施するための形態】
【００２１】
以下、本発明に係る、経路特定装置、経路特定方法、及び、経路特定プログラム、の各実施形態について図１〜図２５を参照しながら説明する。
【００２２】
＜第１実施形態＞
（構成）
図３に示したように、第１実施形態に係る経路特定装置１は、情報処理装置（本例では、サーバ装置）である。なお、経路特定装置１は、ネットワーク・スイッチ、ルーター、パーソナル・コンピュータ、携帯電話端末、ＰＨＳ（Ｐｅｒｓｏｎａｌ Ｈａｎｄｙｐｈｏｎｅ Ｓｙｓｔｅｍ）、ＰＤＡ（Ｐｅｒｓｏｎａｌ Ｄａｔａ Ａｓｓｉｓｔａｎｃｅ、Ｐｅｒｓｏｎａｌ Ｄｉｇｉｔａｌ Ａｓｓｉｓｔａｎｔ）、スマートフォン、カーナビゲーション端末、又は、ゲーム端末等であってもよい。
【００２３】
経路特定装置１は、図示しない中央処理装置（ＣＰＵ；Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）、一次記憶装置（メモリ（ＲＡＭ；Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ））、及び、二次記憶装置（ハードディスク駆動装置（ＨＤＤ；Ｈａｒｄ Ｄｉｓｋ Ｄｒｉｖｅ））を備える。
【００２４】
経路特定装置１は、二次記憶装置に記憶されているプログラムをＣＰＵが実行することにより、後述する機能を実現するように構成されている。
【００２５】
なお、経路特定装置１の各機能は、回路等のハードウェアにより実現されていてもよい。また、プログラムは、二次記憶装置に記憶されていたが、コンピュータが読み取り可能な記録媒体に記憶されていてもよい。例えば、記録媒体は、フレキシブルディスク、光ディスク、光磁気ディスク、及び、半導体メモリ等の可搬性を有する媒体である。
【００２６】
（機能）
図３は、上記のように構成された経路特定装置１の機能を表すブロック図である。経路特定装置１の機能は、基本ノードと、２つの基本ノードを結ぶ基本リンクと、により構成される基本グラフにおいて、第１の基本ノードと第２の基本ノードとを結ぶ経路を特定する。例えば、基本ノードは、通信装置を表す。また、基本リンクは、２つの通信装置を接続する、通信線又は通信回線を表す。
【００２７】
具体的には、経路特定装置１の機能は、グラフ情報記憶部１１と、閉路特定部（閉路特定手段）１２と、経路含有閉路特定部（経路含有閉路特定手段）１３と、経路特定部（経路特定手段）１４と、を含む。
【００２８】
グラフ情報記憶部１１は、基本グラフ情報と、閉路情報と、閉路隣接グラフ情報と、経路含有閉路情報と、を記憶する。
【００２９】
基本グラフ情報は、基本グラフを構成する、複数の基本ノードのそれぞれを識別するための基本ノード識別子と、複数の基本ノードの任意の２つの組のそれぞれに対して、当該２つの基本ノードを結ぶ基本リンクが存在する（即ち、２つの基本ノードが接続されている）か否かを表す情報と、を含む。
【００３０】
閉路情報は、基本グラフにおける閉路を表す情報である。閉路情報は、閉路を識別するための閉路識別子と、当該閉路を構成する基本リンクを特定するための情報と、を含む。
【００３１】
閉路隣接グラフ情報は、閉路隣接グラフを構成する、複数の閉路ノードのそれぞれを識別するための閉路ノード識別子と、複数の閉路ノードの任意の２つの組のそれぞれに対して、当該２つの閉路ノードを結ぶ隣接リンクが存在する（即ち、２つの閉路ノードが接続されている）か否かを表す情報と、を含む。
【００３２】
ここで、閉路隣接グラフは、基本グラフにおける複数の閉路のそれぞれを閉路ノードにより表すとともに、２つの閉路によって基本グラフにおける基本グラフ要素（基本ノード、又は、基本リンク）が共有されていることを、当該２つの閉路のそれぞれを表す閉路ノードを結ぶ隣接リンクにより表すグラフである。
【００３３】
経路含有閉路情報は、基本グラフにおける経路含有閉路を表す情報である。経路含有閉路は、基本グラフにおいて、第１の基本ノードと第２の基本ノードとを通る閉路である。経路含有閉路情報は、経路含有閉路を識別するための経路含有閉路識別子と、当該経路含有閉路を構成する基本リンクを特定するための情報と、を含む。
【００３４】
なお、基本グラフ、及び、閉路隣接グラフを表す情報は、隣接行列、又は、隣接リスト等により表される。なお、基本グラフ、及び、閉路隣接グラフを表す情報は、情報処理装置により処理可能な他の形式により表されてもよい。
【００３５】
閉路特定部１２は、グラフ情報記憶部１１に記憶されている基本グラフ情報に基づいて、第１の基本ノードを通る第１の閉路と、第２の基本ノードを通る第２の閉路と、を含む複数の閉路を特定する。閉路特定部１２は、特定された閉路を表す閉路情報をグラフ情報記憶部１１に記憶させる。
【００３６】
経路含有閉路特定部１３は、閉路特定部１２により特定された複数の閉路のうちの、基本グラフ要素の少なくとも１つを共有する閉路同士を併合することにより、経路含有閉路を特定する。
【００３７】
ここで、経路含有閉路特定部１３は、２つの閉路が少なくとも１つの基本リンクを共有している場合、当該２つの閉路の一方から共有リンクを除いた部分を構成するすべての基本リンクと、当該２つの閉路の他方から共有リンクを除いた部分を構成するすべての基本リンクと、を連結した閉路を、当該２つの閉路同士を併合した閉路として用いる。ここで、共有リンクは、上記２つの閉路により共有されている基本リンクである。
【００３８】
具体的には、経路含有閉路特定部１３は、グラフ情報記憶部１１に記憶されている閉路情報に基づいて閉路隣接グラフを生成する。更に、経路含有閉路特定部１３は、生成された閉路隣接グラフを表す閉路隣接グラフ情報をグラフ情報記憶部１１に記憶させる。
【００３９】
加えて、経路含有閉路特定部１３は、生成された閉路隣接グラフに基づいて、基本グラフにおける経路含有閉路を特定する。このとき、経路含有閉路特定部１３は、基本グラフにおける基本リンクのそれぞれに対して予め設定された基本リンクコストの総和を最小とするように、基本グラフにおける経路含有閉路を特定する。
【００４０】
経路含有閉路特定部１３は、特定された経路含有閉路を表す経路含有閉路情報をグラフ情報記憶部１１に記憶させる。
【００４１】
経路特定部１４は、グラフ情報記憶部１１に記憶されている経路含有閉路情報が表す経路含有閉路（即ち、経路含有閉路特定部１３により特定された経路含有閉路）において、第１の基本ノードと第２の基本ノードとを結び、且つ、基本リンクを共有しない、２つの異なる経路を特定する。
【００４２】
（作動）
次に、上述した経路特定装置１の作動について説明する。
本例では、図４に示した基本グラフにおいて経路を特定する際の経路特定装置１の作動について説明する。この基本グラフは、７つの基本ノードＮ１００〜Ｎ７００と、９つの基本リンクＬ１００〜Ｌ９００と、により構成される。
【００４３】
図４に示した基本グラフは、図５に示した基本グラフ情報（隣接行列）により表される。本例では、経路特定装置１は、基本グラフ情報を予め記憶している。図５において、「Ｎ１００」〜「Ｎ７００」のそれぞれは、基本ノード識別子である。また、隣接行列における値「１」は、当該値の行と対応付けられた基本ノード識別子により識別される基本ノードと、当該値の列と対応付けられた基本ノード識別子により識別される基本ノードと、を結ぶ基本リンクが存在することを表す。
【００４４】
なお、本例では、図４に示したように、簡単のために、比較的規模が小さい基本グラフに経路特定装置１が適用されているが、より規模が大きい基本グラフ、又は、より規模が小さい基本グラフに経路特定装置１が適用されてもよい。
【００４５】
＜＜１．閉路隣接グラフの生成＞＞
先ず、経路特定装置１は、基本グラフに基づいて閉路隣接グラフを生成する。図６は、経路特定装置１が、閉路隣接グラフを生成するために実行する処理を示したフローチャートである。以下、図４に示した基本グラフに基づいて閉路隣接グラフを生成する際の、経路特定装置１の作動について説明する。なお、経路特定装置１は、図４に示した基本グラフ以外の基本グラフに対しても同様に作動する。
【００４６】
初めに、経路特定装置１は、ステップＳ１０１にて、基本グラフにおける全域木（スパニングツリー）を取得する。全域木を取得する方法は、深さ優先探索法、幅優先探索法、Ｄｉｊｋｓｔｒａ（ダイクストラ）法、又は、プリム法等の種々の方法のいずれかである。ここでは、図４に示した基本グラフに対して、図７に示した全域木（すべての基本ノードと、実線により示された基本リンクと、により構成される部分）が取得された場合を想定する。
【００４７】
次いで、経路特定装置１は、ステップＳ１０２にて、ステップＳ１０１にて取得された全域木に含まれない基本リンクの集合（基本リンク集合）を取得する。
【００４８】
そして、経路特定装置１は、ステップＳ１０３〜Ｓ１０６にて、図７に示した全域木に対して、全域木に含まれていない基本リンクを１つずつ追加することにより閉路を取得（特定）し、取得された閉路に基づいて閉路隣接グラフを生成する。
【００４９】
具体的には、経路特定装置１は、ステップＳ１０３にて、上記基本リンク集合が空集合であるか否かを判定する。経路特定装置１は、上記基本リンク集合が空集合でない場合、「Ｎｏ」と判定してステップＳ１０４へ進む。
【００５０】
そして、経路特定装置１は、基本リンク集合から基本リンクを１つ取得し、取得された基本リンクを基本リンク集合から削除する。更に、経路特定装置１は、取得された基本リンクと、当該基本リンクにより結ばれる（当該基本リンクを構成する）２つの基本ノードを、全域木において結ぶ経路を構成する、すべての基本リンクと、を連結した閉路を取得（特定）する。
【００５１】
次いで、経路特定装置１は、ステップＳ１０５にて、特定された閉路を表す閉路ノードを閉路隣接グラフに追加する。更に、経路特定装置１は、ステップＳ１０６にて、前回までに追加されていた閉路ノードが表す閉路と、今回、新たに追加された閉路ノードが表す閉路と、に基づいて、隣接リンクを閉路隣接グラフに追加する。
【００５２】
そして、経路特定装置１は、ステップＳ１０３へ戻り、ステップＳ１０３〜ステップＳ１０６の処理を、基本リンク集合が空集合となるまで繰り返し実行する。そして、基本リンク集合が空集合となると、経路特定装置１は、ステップＳ１０３にて「Ｙｅｓ」と判定して図６に示した処理の実行を終了する。
【００５３】
なお、経路特定装置１は、図６に示した処理を実行することにより取得された閉路のそれぞれを表す閉路情報と、当該処理を実行することにより取得された閉路隣接グラフを表す閉路隣接グラフ情報と、を記憶装置に記憶させる。
【００５４】
例えば、図７に示した全域木においては、基本リンクＬ６００を追加することにより、閉路Ｎ１００−Ｎ２００−Ｎ６００−Ｎ１００が取得される。同様に、基本リンクＬ５００を追加することにより、閉路Ｎ２００−Ｎ３００−Ｎ７００−Ｎ５００−Ｎ６００−Ｎ２００が取得される。また、基本リンクＬ４００を追加することにより、閉路Ｎ３００−Ｎ４００−Ｎ５００−Ｎ７００−Ｎ３００が取得される。
【００５５】
本例では、経路特定装置１が、上述した３つの閉路を取得した場合を想定する。閉路Ｎ１００−Ｎ２００−Ｎ６００−Ｎ１００は、図８に示した閉路情報（隣接行列）により表される。閉路Ｎ１００−Ｎ２００−Ｎ６００−Ｎ１００を識別するための閉路識別子は、「Ｃ１００」である。
【００５６】
同様に、閉路Ｎ２００−Ｎ３００−Ｎ７００−Ｎ５００−Ｎ６００−Ｎ２００は、図９に示した閉路情報（隣接行列）により表される。閉路Ｎ２００−Ｎ３００−Ｎ７００−Ｎ５００−Ｎ６００−Ｎ２００を識別するための閉路識別子は、「Ｃ２００」である。
【００５７】
また、閉路Ｎ３００−Ｎ４００−Ｎ５００−Ｎ７００−Ｎ３００は、図１０に示した閉路情報（隣接行列）により表される。閉路Ｎ３００−Ｎ４００−Ｎ５００−Ｎ７００−Ｎ３００を識別するための閉路識別子は、「Ｃ３００」である。
【００５８】
また、本例では、閉路Ｃ１００と閉路Ｃ２００とは、基本リンクＬ９００を共有している。また、閉路Ｃ２００とＣ３００とは、基本リンクＬ７００、及び、基本リンクＬ８００を共有している。また、閉路Ｃ１００とＣ３００とは、基本リンクを共有していない。なお、閉路Ｃ２００と閉路Ｃ３００に対する基本ノードＮ７００のように、２つの閉路が共有している区間の両端以外に位置するノードを臨界ノードと呼ぶ。
【００５９】
従って、経路特定装置１により生成される閉路隣接グラフは、図１１に示したように、閉路ノードＣ１００と閉路ノードＣ２００とを結ぶ隣接リンクＡ１００と、閉路ノードＣ２００と閉路ノードＣ３００とを結ぶ隣接リンクＡ２００と、を含む。すなわち、隣接リンクＡ１００は基本リンクＬ９００と、隣接リンクＡ２００は基本リンクＬ７００およびＬ８００と関連づけられている。隣接リンクＡが基本リンクＬと関連づけられている状態を単に、隣接リンクＡは基本リンクＬを含む、又は、内包する、と表現することにする。また、複数の連結した基本リンクを含む隣接リンクは臨界ノードを含む。図１１の例において、隣接リンクＡ２００は臨界ノードＮ７００を含む。
【００６０】
図１１に示した閉路隣接グラフは、図１２に示した閉路隣接グラフ情報（隣接行列）により表される。図１２において、「Ｃ１００」〜「Ｃ３００」のそれぞれは、閉路ノード識別子である。また、隣接行列における値「１」は、当該値の行と対応付けられた閉路ノード識別子により識別される閉路ノードと、当該値の列と対応付けられた閉路ノード識別子により識別される閉路ノードと、を結ぶ隣接リンクが存在することを表す。
【００６１】
なお、経路特定装置１は、上述した方法以外の方法を用いることにより、閉路隣接グラフを生成するように構成されていてもよい。なお、閉路隣接グラフを生成する方法は、基本グラフにおける基本リンクのそれぞれが少なくとも１つの閉路ノードに含まれているという第１の条件と、閉路隣接グラフが連結であるという第２の条件と、の両方が満たされる方法であることが好適である。
【００６２】
なお、上述した方法においては、基本グラフにおける各基本リンクは、全域木に含まれるか、又は、閉路を構成するために追加される基本リンクである。従って、上述した方法は、第１の条件を満たす。更に、いずれの閉路も全域木の一部を含む。従って、上述した方法は、第２の条件も満たす。
【００６３】
＜＜２．経路の特定＞＞
次に、経路特定装置１は、生成された閉路隣接グラフに基づいて経路を特定する。図１３は、経路特定装置１が、閉路隣接グラフに基づいて経路を特定するために実行する処理を示したフローチャートである。
【００６４】
経路特定装置１は、記憶装置に記憶されている、基本グラフ情報、閉路情報、及び、閉路隣接グラフ情報、に基づいて経路を特定する。なお、経路特定装置１は、基本グラフにおける基本リンクのそれぞれに対して予め設定された基本リンクコストｗ０（ｘ）を予め記憶している。ここで、パラメータｘは、基本リンクを特定するための情報である。なお、基本リンクコストｗ０（ｘ）は、経路特定装置１のユーザにより入力された情報であってもよい。
【００６５】
基本リンクコストｗ０（ｘ）は、スカラ値を有する。基本リンクコストｗ０（ｘ）は、基本リンクの長さ、又は、基本リンクのその他の属性等に基づいて設定されることが好適である。ところで、基本リンクの系列としての経路ｐ（＝｛ｌ０，ｌ１，…，ｌｉ｝、ここで、ｌｊは、ｊ番目の基本リンクであり、ｊは、０〜ｉの整数である）のコストＷ（ｐ）は、数式１により表される。
【数１】
【００６６】
また、経路特定装置１は、基本リンクコストｗ０（ｘ）に基づいて、閉路隣接グラフにおける隣接リンクのそれぞれに対する隣接リンクコストｗ（ｘ）を算出する。パラメータｘが、閉路ノードｃ０と閉路ノードｃ１とを結ぶ隣接リンクである場合において、当該隣接リンクが第１の基本ノードと第２の基本ノードとのいずれも臨界ノードとして含まないとき、経路特定装置１は、隣接リンクコストｗ（ｘ）を数式２に基づいて算出する。
【数２】
【００６７】
一方、パラメータｘが、閉路ノードｃ０と閉路ノードｃ１とを結ぶ隣接リンクである場合において、当該隣接リンクが第１の基本ノード又は第２の基本ノードの少なくとも一方を臨界ノードとして含むとき、経路特定装置１は、隣接リンクコストｗ（ｘ）を数式３に基づいて算出する。
【数３】
【００６８】
ここでは、第１の基本ノードが基本ノードＮ１００であり、第２の基本ノードが基本ノードＮ４００である場合を想定する。即ち、経路特定装置１が、第１の基本ノードＮ１００と、第２の基本ノードＮ４００と、を結び、且つ、基本リンクを共有しない、２つの異なる経路を特定する場合を想定する。
【００６９】
経路特定装置１は、図１３のステップＳ２０１にて、閉路隣接グラフにおいて、最小コスト経路を特定する。最小コスト経路は、第１の基本ノードＮ１００を通る閉路を表す閉路ノードＣ１００と、第２の基本ノードＮ４００を通る閉路を表す閉路ノードＣ３００と、を結び、且つ、コストが最小となる経路である。
【００７０】
最小コスト経路を特定する方法は、幅優先探索法、又は、修正ダイクストラ法（非特許文献２）等の負のリンクコストを許容する最短経路計算アルゴリズムである。
【００７１】
本例では、経路特定装置１は、閉路隣接グラフにおける最小コスト経路として、経路Ｃ１００−Ｃ２００−Ｃ３００を特定する。
【００７２】
経路特定装置１は、ステップＳ２０２にて、閉路隣接グラフにおける最小コスト経路が特定されたか否かを判定する。本例では、経路特定装置１は、「Ｙｅｓ」と判定し、ステップＳ２０３へ進む。なお、最小コスト経路が特定されなかった場合、経路特定装置１は、図１３に示した処理の実行を終了する。
【００７３】
次いで、経路特定装置１は、ステップＳ２０３にて、閉路隣接グラフにおける最小コスト経路において隣接する２つの閉路ノードが表す２つの閉路同士を併合することにより、第１の基本ノードＮ１００と第２の基本ノードＮ４００とを通る閉路である経路含有閉路を特定する。
【００７４】
本例では、経路特定装置１は、２つの閉路のそれぞれから、２つの閉路により共有されている基本リンク（共有リンク）を除いた部分を構成する、すべての基本リンクを連結した閉路を、当該２つの閉路同士を併合した閉路として用いる。
【００７５】
本例では、閉路情報は、図８乃至図１０に示したように隣接行列により表されている。従って、経路特定装置１は、２つの閉路のそれぞれを表す隣接行列の排他的論理和を算出することにより、当該２つの閉路同士を併合した閉路を表す閉路情報を取得する。
【００７６】
具体的には、経路特定装置１は、閉路Ｃ１００〜Ｃ３００を併合することにより、経路含有閉路Ｎ１００−Ｎ２００−Ｎ３００−Ｎ４００−Ｎ５００−Ｎ６００−Ｎ１００を特定する。本例では、経路特定装置１は、図８乃至図１０に示した隣接行列の排他的論理和を算出することにより、経路含有閉路を表す閉路情報としての、図１４に示した隣接行列を取得する。
【００７７】
なお、経路特定装置１は、他の方法を用いることにより、２つの閉路同士を併合した閉路を表す閉路情報を取得するように構成されていてもよい。
【００７８】
次いで、経路特定装置１は、ステップＳ２０３にて特定された経路含有閉路において、第１の基本ノードＮ１００と第２の基本ノードＮ４００とを結ぶ最小コスト経路（第１の経路）を特定する（ステップＳ２０４）。このとき、経路特定装置１は、基本リンクコストｗ０（ｘ）に基づいて最小コスト経路を特定する。
【００７９】
具体的には、経路特定装置１は、幅優先探索法、又は、ダイクストラ法等を用いることにより、最小コスト経路を特定する。ここでは、経路特定装置１は、最小コスト経路Ｎ１００−Ｎ２００−Ｎ３００−Ｎ４００を特定する。
【００８０】
次いで、経路特定装置１は、ステップＳ２０３にて特定された経路含有閉路において、第１の経路と異なる経路であり、且つ、第１の基本ノードＮ１００と第２の基本ノードＮ４００とを結ぶ経路である冗長経路（第２の経路）を特定する（ステップＳ２０５）。ここでは、経路特定装置１は、冗長経路Ｎ１００−Ｎ６００−Ｎ５００−Ｎ４００を特定する。
【００８１】
具体的には、経路特定装置１は、ステップＳ２０３にて特定された経路含有閉路を表す環状リストから、ステップＳ２０４にて特定された第１の経路に相当する部分を取り除くことにより、第２の経路を特定する。なお、経路特定装置１は、ステップＳ２０４にて特定された第１の経路における中間の基本ノード又は基本リンクを使用不可とする条件を設けた状態において、深さ優先探索法、又は、ダイクストラ法等を用いることにより第２の経路を特定してもよい。
【００８２】
このようにして、経路特定装置１は、閉路隣接グラフを用いることにより、第１の基本ノードＮ１００と第２の基本ノードＮ４００とを結び、且つ、基本リンクを共有しない、２つの異なる経路（第１の経路、及び、第２の経路）を特定する。
【００８３】
以上、説明したように、本発明の第１実施形態に係る経路特定装置１によれば、２つの基本ノードを結び、且つ、基本リンクを共有しない、２つの異なる経路を確実に特定することができる。更に、２つの基本ノードを結び、且つ、基本リンク、又は、経路途中の（即ち、第１の基本ノード及び第２の基本ノード以外の）基本ノードを共有しない、２つの異なる経路を特定する際の処理負荷を低減することができる。
【００８４】
更に、本発明の第１実施形態に係る経路特定装置１は、基本グラフにおける基本リンクのそれぞれに対して予め設定された基本リンクコストの総和を最小とするように、基本グラフにおける経路含有閉路を特定する。
【００８５】
これによれば、基本リンクコストの総和を最小とするように、２つの基本ノードを結び、且つ、基本リンク、又は、経路途中の基本ノードを共有しない、２つの異なる経路を特定することができる。
【００８６】
＜第２実施形態＞
次に、本発明の第２実施形態に係る経路特定装置について説明する。第２実施形態に係る経路特定装置は、上記第１実施形態に係る経路特定装置に対して、２つの閉路が基本ノードのみを共有している場合、当該２つの閉路のそれぞれを構成するすべての基本リンクを連結した閉路を、当該２つの閉路同士を併合した閉路として用いる点において相違している。従って、以下、かかる相違点を中心として説明する。
【００８７】
（機能）
第２実施形態に係る経路含有閉路特定部１３は、２つの閉路が基本リンクを共有することなく基本ノードのみを共有している場合、当該２つの閉路の一方を構成するすべての基本リンクと、当該２つの閉路の他方を構成するすべての基本リンクと、を連結した閉路を、当該２つの閉路同士を併合した閉路として用いる。
【００８８】
本例では、２つの閉路が基本リンクを共有している状態は、強隣接状態とも呼ばれる。また、２つの閉路が基本リンクを共有することなく基本ノードのみを共有している状態は、弱隣接状態とも呼ばれる。
【００８９】
（作動）
次に、上述した経路特定装置１の作動について説明する。
本例では、図１５に示した基本グラフにおいて経路を特定する際の経路特定装置１の作動について説明する。この基本グラフは、９つの基本ノードＮ１００〜Ｎ９００と、１２個の基本リンクＬ１００〜Ｌ１２００と、により構成される。
【００９０】
＜＜１．閉路隣接グラフの生成＞＞
経路特定装置１は、第１実施形態と同様に、閉路を特定する。本例では、経路特定装置１は、閉路Ｃ１００、閉路Ｃ２００、及び、閉路Ｃ３００に加えて、閉路Ｃ７００（Ｎ４００−Ｎ８００−Ｎ９００−Ｎ４００）も特定する。
【００９１】
閉路Ｃ３００と閉路Ｃ７００とは、基本リンクを共有することなく、基本ノードＮ４００のみを共有している。即ち、閉路Ｃ３００と閉路Ｃ７００とは、弱隣接状態にある。経路特定装置１は、図１６に示したように、弱隣接状態を表す隣接リンク（弱隣接リンク）Ａ３００を閉路隣接グラフに追加する。なお、弱隣接状態にある２つの閉路に共有される唯一の基本ノードは、臨界ノードと見なされる。すなわち、いずれの弱隣接リンクも基本リンクを含まず、且つ、臨界ノードを１つ含む。
【００９２】
＜＜２．経路の特定＞＞
経路特定装置１は、第１実施形態と同様に、図１６に示した閉路隣接グラフに基づいて経路を特定する。
【００９３】
本例では、パラメータｘが、閉路ノードｃ０と閉路ノードｃ１とを結ぶ隣接リンクであり、且つ、閉路ノードｃ０が表す閉路と閉路ノードｃ１が表す閉路とが弱隣接状態にある場合において、当該隣接リンク（弱隣接リンク）が含んでいる基本ノードが第１の基本ノードと第２の基本ノードのいずれでもないとき、経路特定装置１は、隣接リンクコストｗ（ｘ）を数式４に基づいて算出する。ただし、本例において導入した弱隣接リンクは基本リンクを含まないため、数式４は数式２と同等である。すなわち、第１実施形態において数式１〜３により示した隣接リンクコストｗ（ｘ）を、本例においてもそのまま使用することができる。
【数４】
【００９４】
ここでは、第１の基本ノードが基本ノードＮ１００であり、第２の基本ノードが基本ノードＮ８００である場合を想定する。即ち、経路特定装置１が、第１の基本ノードＮ１００と、第２の基本ノードＮ８００と、を結び、且つ、基本リンクを共有しない、２つの異なる経路を特定する場合を想定する。
【００９５】
経路特定装置１は、図１３のステップＳ２０１にて、閉路隣接グラフにおいて、最小コスト経路を特定する。最小コスト経路は、第１の基本ノードＮ１００を通る閉路を表す閉路ノードＣ１００と、第２の基本ノードＮ８００を通る閉路を表す閉路ノードＣ７００と、を結び、且つ、コストが最小となる経路である。
【００９６】
最小コスト経路を特定する方法は、幅優先探索法、又は、修正ダイクストラ法（非特許文献２）等の負のリンクコストを許容する最短経路計算アルゴリズムである。
【００９７】
本例では、経路特定装置１は、閉路隣接グラフにおける最小コスト経路として、経路Ｃ１００−Ｃ２００−Ｃ３００−Ｃ７００を特定する。
【００９８】
経路特定装置１は、ステップＳ２０２にて、閉路隣接グラフにおける最小コスト経路が特定されたか否かを判定する。本例では、経路特定装置１は、「Ｙｅｓ」と判定し、ステップＳ２０３へ進む。なお、最小コスト経路が特定されなかった場合、経路特定装置１は、図１３に示した処理の実行を終了する。
【００９９】
次いで、経路特定装置１は、ステップＳ２０３にて、閉路隣接グラフにおける最小コスト経路において隣接する２つの閉路ノードが表す２つの閉路同士を併合することにより、第１の基本ノードＮ１００と第２の基本ノードＮ８００とを通る閉路である経路含有閉路を特定する。
【０１００】
本例では、経路特定装置１は、２つの閉路が基本リンクを共有している場合、当該２つの閉路のそれぞれから、２つの閉路により共有されている基本リンク（共有リンク）を除いた部分を構成する、すべての基本リンクを連結した閉路を、当該２つの閉路同士を併合した閉路として用いる。更に、経路特定装置１は、２つの閉路が基本リンクを共有することなく基本ノードを共有している場合、当該２つの閉路のそれぞれを構成する、すべての基本リンクを連結した閉路を、当該２つの閉路同士を併合した閉路として用いる。
【０１０１】
具体的には、経路特定装置１は、２つの閉路のそれぞれを表す隣接行列の排他的論理和を算出することにより、当該２つの閉路同士を併合した閉路を表す閉路情報を取得する。
【０１０２】
本例では、経路特定装置１は、閉路Ｃ１００〜Ｃ３００，Ｃ７００を併合することにより、経路含有閉路Ｎ１００−Ｎ２００−Ｎ３００−Ｎ４００−Ｎ８００−Ｎ９００−Ｎ４００−Ｎ５００−Ｎ６００−Ｎ１００を特定する。
【０１０３】
なお、経路特定装置１は、他の方法を用いることにより、２つの閉路同士を併合した閉路を表す閉路情報を取得するように構成されていてもよい。
【０１０４】
次いで、経路特定装置１は、ステップＳ２０３にて特定された経路含有閉路において、第１の基本ノードＮ１００と第２の基本ノードＮ８００とを結ぶ最小コスト経路（第１の経路）を特定する（ステップＳ２０４）。このとき、経路特定装置１は、基本リンクコストｗ０（ｘ）に基づいて最小コスト経路を特定する。
【０１０５】
具体的には、経路特定装置１は、幅優先探索法、又は、ダイクストラ法等を用いることにより、最小コスト経路を特定する。ここでは、経路特定装置１は、最小コスト経路Ｎ１００−Ｎ２００−Ｎ３００−Ｎ４００−Ｎ８００を特定する。
【０１０６】
次いで、経路特定装置１は、ステップＳ２０３にて特定された経路含有閉路において、第１の経路と異なる経路であり、且つ、第１の基本ノードＮ１００と第２の基本ノードＮ８００とを結ぶ経路である冗長経路（第２の経路）を特定する（ステップＳ２０５）。ここでは、経路特定装置１は、冗長経路Ｎ１００−Ｎ６００−Ｎ５００−Ｎ４００−Ｎ９００−Ｎ８００を特定する。
【０１０７】
具体的には、経路特定装置１は、ステップＳ２０３にて特定された経路含有閉路を表す環状リストから、ステップＳ２０４にて特定された第１の経路に相当する部分を取り除くことにより、第２の経路を特定する。なお、経路特定装置１は、ステップＳ２０４にて特定された第１の経路における中間の基本ノード又は基本リンクを使用不可とする条件を設けた状態において、深さ優先探索法、又は、ダイクストラ法等を用いることにより第２の経路を特定してもよい。
【０１０８】
このようにして、経路特定装置１は、閉路隣接グラフを用いることにより、第１の基本ノードＮ１００と第２の基本ノードＮ８００とを結び、且つ、基本リンク、又は、経路途中の基本ノードを共有しない、２つの異なる経路（第１の経路、及び、第２の経路）を特定する。
【０１０９】
以上、説明したように、本発明の第２実施形態に係る経路特定装置１によっても、第１実施形態に係る経路特定装置１と同様の作用及び効果が奏される。
【０１１０】
＜第３実施形態＞
次に、本発明の第３実施形態に係る経路特定装置について説明する。第３実施形態に係る経路特定装置は、上記第１実施形態に係る経路特定装置に対して、閉路を構成しない基本ノードが存在する場合において、一部の基本リンクを共有する２つの異なる経路を特定する点において相違している。従って、以下、かかる相違点を中心として説明する。
【０１１１】
本例では、閉路隣接グラフは、いずれの閉路にも含まれない（いずれの閉路も構成しない）基本ノードを閉路ノード（疑似閉路ノード）として含む。更に、閉路隣接グラフは、いずれの閉路にも含まれない（いずれの閉路も構成しない）基本リンクを隣接リンク（疑似隣接リンク）として含む。
【０１１２】
（作動）
次に、上述した経路特定装置１の作動について説明する。
本例では、図１７に示した基本グラフにおいて経路を特定する際の経路特定装置１の作動について説明する。この基本グラフは、１１個の基本ノードＮ１００〜Ｎ１１００と、１４個の基本リンクＬ１００〜Ｌ１４００と、により構成される。
【０１１３】
＜＜１．閉路隣接グラフの生成＞＞
経路特定装置１は、図６に示したフローチャートに代えて、図１８に示したフローチャートにより表される処理を、閉路隣接グラフを生成するために実行する。図１８に示した処理は、図６に示した処理と同様のステップＳ３０１〜ステップＳ３０６の処理の後に、ステップＳ３０７〜ステップＳ３１０の処理を追加した処理である。
【０１１４】
経路特定装置１は、第１実施形態と同様に、ステップＳ３０１〜ステップＳ３０６の処理を実行することにより、閉路Ｃ１００、閉路Ｃ２００、及び、閉路Ｃ３００に加えて、閉路Ｃ９００（Ｎ１１００−Ｎ８００−Ｎ９００−Ｎ１１００）を特定する。経路特定装置１は、特定された閉路に基づいて閉路隣接グラフを生成する。
【０１１５】
この時点では、閉路隣接グラフにおいて、閉路Ｃ９００を表す閉路ノードは、他の閉路ノードと接続されていない。
【０１１６】
そして、経路特定装置１は、ステップＳ３０７へ進み、いずれの閉路にも含まれない基本ノードの集合である基本ノード集合を取得する。本例では、経路特定装置１は、基本ノードのそれぞれに対して、閉路に含まれた回数（例えば、ステップＳ３０５の処理を実行した回数）を数えることにより、基本ノード集合を取得する。
【０１１７】
次いで、経路特定装置１は、ステップＳ３０８にて、上記基本ノード集合が空集合であるか否かを判定する。経路特定装置１は、上記基本ノード集合が空集合でない場合、「Ｎｏ」と判定してステップＳ３０９へ進む。
【０１１８】
そして、経路特定装置１は、基本ノード集合から基本ノードを１つ取得し、取得された基本ノードを基本ノード集合から削除する。更に、経路特定装置１は、取得された基本ノードを閉路ノード（疑似閉路ノード）として閉路隣接グラフに追加する（ステップＳ３０９）。
【０１１９】
更に、経路特定装置１は、ステップＳ３１０にて、上記疑似閉路ノードとしての基本ノードに接続されている基本リンクのそれぞれを、隣接リンク（疑似隣接リンク）として閉路隣接グラフに追加する。
【０１２０】
そして、経路特定装置１は、ステップＳ３０８へ戻り、ステップＳ３０８〜ステップＳ３１０の処理を、基本ノード集合が空集合となるまで繰り返し実行する。そして、基本ノード集合が空集合となると、経路特定装置１は、ステップＳ３０８にて「Ｙｅｓ」と判定して図１８に示した処理の実行を終了する。
【０１２１】
このようにして、本例では、経路特定装置１は、基本ノードＮ１０００を、疑似閉路ノードＣ８００として閉路隣接グラフに追加するとともに、基本リンクＬ１３００を疑似隣接リンクＡ４００として閉路隣接グラフに追加し、且つ、基本リンクＬ１４００を疑似隣接リンクＡ５００として閉路隣接グラフに追加する。これにより、経路特定装置１は、図１９に示したように、閉路隣接グラフを生成する。
【０１２２】
なお、経路特定装置１は、閉路隣接グラフを生成する方法として、他の方法を用いるように構成されていてもよい。
【０１２３】
＜＜２．経路の特定＞＞
経路特定装置１は、第１実施形態と同様に、図１９に示した閉路隣接グラフに基づいて経路を特定する。
【０１２４】
本例では、パラメータｘが、疑似隣接リンクである場合、経路特定装置１は、隣接リンクコストｗ（ｘ）として、疑似隣接リンクの実体である基本リンクｌに対する基本リンクコストｗ０（ｌ）を用いる。
【０１２５】
ここでは、第１の基本ノードが基本ノードＮ１００であり、第２の基本ノードが基本ノードＮ８００である場合を想定する。即ち、経路特定装置１が、第１の基本ノードＮ１００と、第２の基本ノードＮ８００と、を結ぶ、２つの異なる経路を特定する場合を想定する。
【０１２６】
経路特定装置１は、図１３のステップＳ２０１にて、閉路隣接グラフにおいて、最小コスト経路を特定する。最小コスト経路は、第１の基本ノードＮ１００を通る閉路を表す閉路ノードＣ１００と、第２の基本ノードＮ８００を通る閉路を表す閉路ノードＣ９００と、を結び、且つ、コストが最小となる経路である。
【０１２７】
最小コスト経路を特定する方法は、幅優先探索法、又は、修正ダイクストラ法（非特許文献２）等の負のリンクコストを許容する最短経路計算アルゴリズムである。
【０１２８】
本例では、経路特定装置１は、閉路隣接グラフにおける最小コスト経路として、経路Ｃ１００−Ｃ２００−Ｃ３００−Ｃ８００−Ｃ９００を特定する。
【０１２９】
経路特定装置１は、ステップＳ２０２にて、閉路隣接グラフにおける最小コスト経路が特定されたか否かを判定する。本例では、経路特定装置１は、「Ｙｅｓ」と判定し、ステップＳ２０３へ進む。なお、最小コスト経路が特定されなかった場合、経路特定装置１は、図１３に示した処理の実行を終了する。
【０１３０】
本例では、基本グラフは、任意の２つの基本ノードを連結可能なグラフである。従って、ステップＳ２０１において、必ず、最小コスト経路が特定される。このため、経路特定装置１は、ステップＳ２０２の処理を省略した処理を実行するように構成されていてもよい。
【０１３１】
次いで、経路特定装置１は、ステップＳ２０３にて、閉路隣接グラフにおける最小コスト経路において隣接する２つの閉路ノードが表す２つの閉路同士を併合することにより、第１の基本ノードＮ１００と第２の基本ノードＮ８００とを通る閉路である経路含有閉路を特定する。
【０１３２】
本例では、経路特定装置１は、２つの閉路が基本リンクを共有している場合、当該２つの閉路のそれぞれから、２つの閉路により共有されている基本リンク（共有リンク）を除いた部分を構成する、すべての基本リンクを連結した閉路を、当該２つの閉路同士を併合した閉路として用いる。
【０１３３】
更に、経路特定装置１は、２つの閉路の一方が、疑似閉路ノードとしての基本ノードである（即ち、２つの閉路が基本リンク及び基本ノードのいずれも共有していない）場合、当該２つの閉路の他方を構成する、すべての基本リンクと、疑似閉路ノードとしての基本ノードに接続されている基本リンクと、を連結した閉路（疑似閉路）を、当該２つの閉路同士を併合した閉路として用いる。
【０１３４】
具体的には、経路特定装置１は、２つの閉路のそれぞれを表す隣接行列の排他的論理和を算出することにより、当該２つの閉路同士を併合した閉路を表す閉路情報を取得する。
【０１３５】
本例では、経路特定装置１は、閉路Ｃ１００〜Ｃ３００，Ｃ８００，Ｃ９００を併合することにより、経路含有閉路Ｎ１００−Ｎ２００−Ｎ３００−Ｎ４００−Ｎ１０００−Ｎ１１００−Ｎ８００−Ｎ９００−Ｎ１１００−Ｎ１０００−Ｎ４００−Ｎ５００−Ｎ６００−Ｎ１００を特定する。
【０１３６】
なお、経路特定装置１は、他の方法を用いることにより、２つの閉路同士を併合した閉路を表す閉路情報を取得するように構成されていてもよい。
【０１３７】
次いで、経路特定装置１は、ステップＳ２０３にて特定された経路含有閉路において、第１の基本ノードＮ１００と第２の基本ノードＮ８００とを結ぶ最小コスト経路（第１の経路）を特定する（ステップＳ２０４）。このとき、経路特定装置１は、基本リンクコストｗ０（ｘ）に基づいて最小コスト経路を特定する。
【０１３８】
具体的には、経路特定装置１は、幅優先探索法、又は、ダイクストラ法等を用いることにより、最小コスト経路を特定する。ここでは、経路特定装置１は、最小コスト経路Ｎ１００−Ｎ２００−Ｎ３００−Ｎ４００−Ｎ１０００−Ｎ１１００−Ｎ８００を特定する。
【０１３９】
次いで、経路特定装置１は、ステップＳ２０３にて特定された経路含有閉路において、第１の経路と異なる経路であり、且つ、第１の基本ノードＮ１００と第２の基本ノードＮ８００とを結ぶ経路である冗長経路（第２の経路）を特定する（ステップＳ２０５）。ここでは、経路特定装置１は、冗長経路Ｎ１００−Ｎ６００−Ｎ５００−Ｎ４００−Ｎ１０００−Ｎ１１００−Ｎ９００−Ｎ８００を特定する。
【０１４０】
具体的には、経路特定装置１は、ステップＳ２０３にて特定された経路含有閉路を表す環状リストから、ステップＳ２０４にて特定された第１の経路に相当する部分を取り除くことにより、第２の経路を特定する。
【０１４１】
なお、経路特定装置１は、ステップＳ２０４にて特定された第１の経路における中間の基本ノード又は基本リンクのうちの、疑似閉路ノードＮ１０００、及び、疑似隣接リンクＬ１３００，Ｌ１４００以外の基本グラフ要素を使用不可とする条件を設けた状態において、深さ優先探索法、又は、ダイクストラ法等を用いることにより第２の経路を特定してもよい。
【０１４２】
このようにして、経路特定装置１は、閉路隣接グラフを用いることにより、第１の基本ノードＮ１００と第２の基本ノードＮ８００とを結ぶ、２つの異なる経路（第１の経路、及び、第２の経路）を特定する。
【０１４３】
以上、説明したように、本発明の第３実施形態に係る経路特定装置１によっても、第１実施形態に係る経路特定装置１と同様の作用及び効果が奏される。
【０１４４】
＜第４実施形態＞
次に、本発明の第４実施形態に係る経路特定装置について説明する。第４実施形態に係る経路特定装置は、上記第１実施形態に係る経路特定装置に対して、経路を特定する処理中に取得される閉路情報を保持するとともに、他の経路を特定する処理において、保持されている閉路情報を用いることにより、経路を特定する処理を高速化する点において相違している。従って、以下、かかる相違点を中心として説明する。
【０１４５】
第４実施形態に係るグラフ情報記憶部１１は、２つの閉路のそれぞれを表す情報と、当該２つの閉路同士を併合することにより生成された閉路を表す情報と、を対応付けた併合閉路情報を記憶する。
【０１４６】
本例では、併合閉路情報は、図２０及び図２１に示したように、併合の対象となる２つの閉路のそれぞれを識別するための閉路識別子と、併合により生成された閉路を識別するための閉路識別子と、を含むテーブルである。即ち、このテーブルにおける値は、当該値の行と対応付けられた閉路識別子により識別される閉路と、当該値の列と対応付けられた閉路識別子により識別される閉路と、を併合することにより生成された閉路を識別するための閉路識別子である。
なお、併合閉路情報は、情報処理装置により処理可能な他の形式により表されてもよい。
【０１４７】
（作動）
次に、上述した経路特定装置１の作動について説明する。
経路特定装置１は、図１３のステップＳ２０３の処理以外の処理を、第１実施形態と同様に実行する。
【０１４８】
経路特定装置１は、図１３のステップＳ２０３に進んだとき、併合の対象となる２つの閉路に係る併合閉路情報が記憶されているか否かを判定する。併合の対象となる２つの閉路に係る併合閉路情報が記憶されている場合、経路特定装置１は、当該併合閉路情報から、併合により生成された閉路を表す情報を取得する。
【０１４９】
一方、併合の対象となる２つの閉路に係る併合閉路情報が記憶されていない場合、経路特定装置１は、第１実施形態と同様に、２つの閉路同士を併合することにより閉路を生成する処理を実行する。更に、この場合、経路特定装置１は、併合の対象となる２つの閉路のそれぞれを識別するための閉路識別子と、併合により生成された閉路を識別するための閉路識別子と、を対応付けて記憶する。
【０１５０】
ここで、閉路Ｃ１００〜Ｃ３００を併合する例について説明する。いま、閉路Ｃ１００と閉路Ｃ２００とを併合することにより閉路Ｃ４００が生成されるとともに、閉路Ｃ２００と閉路Ｃ３００とを併合することにより閉路Ｃ５００が生成される場合を想定する。更に、閉路Ｃ１００〜Ｃ３００を併合することにより閉路Ｃ６００が生成される場合を想定する。
【０１５１】
この場合、経路特定装置１が、２つの閉路同士を併合する処理を実行する前の時点においては、経路特定装置１が記憶している併合閉路情報は、図２０に示した状態である。その後、経路特定装置１が、２つの閉路同士を併合する処理を実行することにより、最終的に、経路特定装置１が記憶している併合閉路情報は、図２１に示した状態となる。
【０１５２】
以上、説明したように、本発明の第４実施形態に係る経路特定装置１によっても、第１実施形態に係る経路特定装置１と同様の作用及び効果が奏される。
更に、本発明の第４実施形態に係る経路特定装置１によれば、経路を特定する処理を高速化することができる。
【０１５３】
＜第５実施形態＞
次に、本発明の第５実施形態に係る経路特定装置について説明する。第５実施形態に係る経路特定装置は、上記第１実施形態に係る経路特定装置に対して、特定すべき経路の端点（経路の端を構成する基本ノード、即ち、第１の基本ノード又は第２の基本ノード）が複数の閉路に含まれる場合における、経路を特定する処理を高速化する点において相違している。例えば、図４に示した基本グラフにおいて、基本ノードＮ２００は、２つの閉路Ｃ１００，Ｃ２００に含まれている。
以下、かかる相違点を中心として説明する。
【０１５４】
例えば、第１実施形態〜第４実施形態に係る経路特定装置１において、基本ノードＮ２００と基本ノードＮ４００とを結ぶ経路を特定する場合、閉路隣接グラフにて、閉路ノードＣ１００と閉路ノードＣ３００とを結ぶ経路と、閉路ノードＣ２００と閉路ノードＣ３００とを結ぶ経路と、の２つの経路を特定し、それぞれのコストを比較する必要が生じる。一方、本実施形態に係る経路特定装置１によれば、これらの計算を一元化することができるので、経路を特定する処理を高速化することができる。
【０１５５】
（機能）
第５実施形態に係るグラフ情報記憶部１１は、閉路隣接グラフ情報に代えて、閉路探索グラフ情報を記憶する。
【０１５６】
閉路探索グラフ情報は、閉路探索グラフを表す情報である。ここで、閉路探索グラフは、閉路隣接グラフに、包含ノードと、包含リンクと、を追加したグラフである。包含ノードは、閉路ノードが表す閉路が基本グラフにおいて通る（即ち、当該閉路に含まれる）基本ノードを表すノードである。包含リンクは、閉路ノードが表す閉路が基本グラフにおいて包含ノードを通ることを表し、且つ、当該閉路ノードと当該包含ノードとを結ぶリンクである。
【０１５７】
閉路探索グラフ情報は、閉路隣接グラフ情報に加えて、複数の包含ノードのそれぞれを識別するための包含ノード識別子と、包含ノードと閉路ノードとの任意の組のそれぞれに対して、当該包含ノードと当該閉路ノードとを結ぶ包含リンクが存在するか否かを表す情報と、を含む。
【０１５８】
（作動）
次に、上述した経路特定装置１の作動について説明する。
本例では、図１７に示した基本グラフにおいて経路を特定する際の経路特定装置１の作動について説明する。この基本グラフは、１１個の基本ノードＮ１００〜Ｎ１１００と、１４個の基本リンクＬ１００〜Ｌ１４００と、により構成される。
【０１５９】
＜＜１．閉路探索グラフの生成＞＞
先ず、経路特定装置１は、第１実施形態と同様に、閉路隣接グラフを生成する。その後、経路特定装置１は、基本グラフにおける各基本ノードに対して、当該基本ノードを包含ノードとして閉路隣接グラフに追加するとともに、当該基本ノードを基本グラフにおいて通る閉路を表す閉路ノードと当該包含ノードとを結ぶ包含リンクを閉路隣接グラフに追加することにより、閉路探索グラフを生成する。
【０１６０】
ここでは、経路特定装置１が、図４に示した基本グラフに基づいて閉路探索グラフを生成する場合を想定する。この場合、経路特定装置１により生成される閉路探索グラフは、図２２に示したようになる。図２２における破線は、包含リンクＥ１００〜Ｅ７１０を表す。
【０１６１】
＜＜２．経路の特定＞＞
経路特定装置１は、図２２に示した閉路探索グラフに基づいて経路を特定する。
本例では、パラメータｘが、閉路ノードｃ０と閉路ノードｃ１とを結ぶ隣接リンクである場合において、当該隣接リンクが第１の基本ノードと第２の基本ノードとのいずれも臨界ノードとして含まないとき、経路特定装置１は、探索リンクコストｗ（ｘ）を数式５に基づいて算出する。
【数５】
【０１６２】
一方、パラメータｘが、閉路ノードｃ０と閉路ノードｃ１とを結ぶ隣接リンクである場合において、当該隣接リンクが第１の基本ノード又は第２の基本ノードを臨界ノードとして含むとき、経路特定装置１は、探索リンクコストｗ（ｘ）を数式６に基づいて算出する。
【数６】
【０１６３】
また、パラメータｘが、疑似隣接リンクＬである場合、経路特定装置１は、探索リンクコストｗ（ｘ）を数式７に基づいて算出する。
【数７】
【０１６４】
また、パラメータｘが、包含リンクである場合において、当該包含リンクが第１の基本ノードから閉路ノードｃへのリンクであるとき、経路特定装置１は、探索リンクコストｗ（ｘ）を数式８に基づいて算出する。
【数８】
【０１６５】
また、パラメータｘが、包含リンクである場合において、当該包含リンクが閉路ノードｃから第２の基本ノードへのリンクであるとき、経路特定装置１は、探索リンクコストｗ（ｘ）を数式９に基づいて算出する。
【数９】
【０１６６】
また、パラメータｘが、包含リンクである場合において、当該包含リンクが、第１の基本ノード及び第２の基本ノード以外の基本ノード（包含ノード）と、閉路ノードと、を結ぶとき、経路特定装置１は、探索リンクコストｗ（ｘ）を数式１０に基づいて算出する。
【数１０】
【０１６７】
ここでは、第１の基本ノードが基本ノードＮ２００であり、第２の基本ノードが基本ノードＮ４００である場合を想定する。即ち、経路特定装置１が、第１の基本ノードＮ２００と、第２の基本ノードＮ４００と、を結び、且つ、基本リンクを共有しない、２つの異なる経路を特定する場合を想定する。
【０１６８】
経路特定装置１は、図１３のステップＳ２０１の処理に代えて、閉路探索グラフにおいて、最小コスト経路を特定する処理を実行する。ここで、最小コスト経路は、閉路探索グラフにおいて、第１の基本ノードＮ２００と、第２の基本ノードＮ４００と、を結び、且つ、コストが最小となる経路である。
【０１６９】
ところで、探索リンクコストｗ（ｘ）が∞であるリンクが、最小コスト経路に含まれることはない。従って、経路特定装置１は、探索リンクコストｗ（ｘ）が∞であるリンクを、予め閉路探索グラフから除去した、図２３に示したグラフに基づいて、最小コスト経路を特定するように構成されることが好適である。
【０１７０】
なお、閉路探索グラフにおいて最小コスト経路を特定することは、２つの経路（経路Ｎ２００−Ｃ１００−Ｃ２００−Ｃ３００−Ｎ４００、及び、経路Ｎ２００−Ｃ２００−Ｃ３００−Ｎ４００）のうちの、コストが小さい方の経路を特定することに対応している。
【０１７１】
更に、経路特定装置１は、特定された最小コスト経路から、第１の基本ノードＮ２００、及び、第２の基本ノードＮ４００を除去した経路を特定し、当該経路に基づいて、第１実施形態と同様に、ステップＳ２０２〜ステップＳ２０５の処理を実行する。これにより、経路特定装置１は、閉路探索グラフを用いることにより、第１の基本ノードＮ２００と第２の基本ノードＮ４００とを結び、且つ、基本リンクを共有しない、２つの異なる経路（第１の経路、及び、第２の経路）を特定する。
【０１７２】
以上、説明したように、本発明の第５実施形態に係る経路特定装置１によっても、第１実施形態に係る経路特定装置１と同様の作用及び効果が奏される。
更に、本発明の第５実施形態に係る経路特定装置１によれば、特定すべき経路の端点が複数の閉路に含まれる場合において、経路を特定する処理を高速化することができる。
【０１７３】
＜第６実施形態＞
次に、本発明の第６実施形態に係る経路特定装置について説明する。第６実施形態に係る経路特定装置は、上記第１実施形態に係る経路特定装置に対して、基本グラフに基づいて経路を特定できなかった場合にのみ、閉路隣接グラフを用いることにより経路を特定する点において相違している。従って、以下、かかる相違点を中心として説明する。
【０１７４】
第６実施形態に係る経路特定装置１は、図２４にフローチャートにより示した処理を実行する。
【０１７５】
具体的には、経路特定装置１は、ステップＳ４０１にて、基本グラフに基づいて（即ち、閉路隣接グラフを用いることなく）、経路を特定する。本例では、経路特定装置１は、ダイクストラ法を繰り返し用いることにより、２つの基本ノードを結び、且つ、基本リンクを共有しない、２つの異なる経路を特定する。即ち、経路特定装置１は、第１の経路を特定し、その後、第１の経路が通る基本リンクを基本グラフから除去したグラフに基づいて、第２の経路を特定する。
【０１７６】
ステップＳ４０１の処理により特定される第１の経路は、基本グラフにおいてコストが最小となる経路である。一方、このように特定された、第１の経路及び第２の経路は、第１の経路のコストと第２の経路のコストとの和が最小であるとは限らない。
なお、経路特定装置１は、他の方法を用いることにより、２つの異なる経路を特定するように構成されていてもよい。
【０１７７】
次いで、経路特定装置１は、ステップＳ４０２にて、経路が特定されたか否かを判定する。ステップＳ４０１にて経路が特定されなかった場合、経路特定装置１は、「Ｎｏ」と判定してステップＳ４０３へ進む。
【０１７８】
なお、経路特定装置１は、経路が特定された場合であっても、特定された経路が、予め設定された条件を満たさなかった場合、「Ｎｏ」と判定するように構成されていてもよい。例えば、この条件は、第２の経路のコストが、予め設定された基準値よりも大きいという条件である。
【０１７９】
そして、経路特定装置１は、ステップＳ４０３にて、第１実施形態と同様に、閉路隣接グラフを生成するとともに、生成された閉路隣接グラフに基づいて、２つの異なる経路を特定する。
なお、ステップＳ４０１にて経路が特定された場合、経路特定装置１は、ステップＳ４０２にて「Ｙｅｓ」と判定して、図２４に示した処理の実行を終了する。
【０１８０】
以上、説明したように、本発明の第６実施形態に係る経路特定装置１によっても、第１実施形態に係る経路特定装置１と同様の作用及び効果が奏される。
更に、本発明の第６実施形態に係る経路特定装置１によれば、第１の経路のコストと第２の経路のコストとの和が最小となる、２つの経路以外の経路を特定することもできる。
【０１８１】
なお、第６実施形態に係る経路特定装置１は、基本グラフに基づいて経路を特定できなかった場合に、閉路隣接グラフに基づいて経路を特定するように構成されていたが、閉路探索グラフに基づいて経路を特定するように構成されていてもよい。
【０１８２】
第１実施形態〜第６実施形態においては、経路特定装置１は、閉路隣接グラフ又は閉路探索グラフの生成する処理（第１の処理）と経路の特定する処理（第２の処理）とを続けて実行するように構成されていた。ところで、経路特定装置１は、第１の処理の実行結果を保持し、その後、保持されている実行結果を用いることにより、複数回、第２の処理を実行するように構成されていてもよい。
【０１８３】
また、閉路隣接グラフ又は閉路探索グラフを生成するためのプログラムと、経路を特定するためのプログラムと、は、１つのプログラムを構成していてもよいし、互いに独立した２つのプログラムであってもよい。なお、経路特定装置１は、互いに独立した２つのプログラムのそれぞれに対して、中央処理装置、一次記憶装置、及び、二次記憶装置等のプログラムを実行するために必要な計算資源を、物理的又は論理的に分離して割り当てるように構成されていてもよい。
【０１８４】
＜第７実施形態＞
次に、本発明の第７実施形態に係る経路特定装置について図２５を参照しながら説明する。
第７実施形態に係る経路特定装置１０００は、
基本ノードと、２つの基本ノードを結ぶ基本リンクと、により構成される基本グラフにおいて、第１の基本ノードと第２の基本ノードとを結ぶ経路を特定する装置である。
【０１８５】
更に、この経路特定装置１０００は、
上記第１の基本ノードを通る第１の閉路と、上記第２の基本ノードを通る第２の閉路と、を含む複数の閉路を特定する閉路特定部（閉路特定手段）１００１と、
上記特定された複数の閉路のうちの、基本ノード又は基本リンクである基本グラフ要素の少なくとも１つを共有する閉路同士を併合することにより、上記第１の基本ノードと上記第２の基本ノードとを通る閉路である経路含有閉路を特定する経路含有閉路特定部（経路含有閉路特定手段）１００２と、
上記特定された経路含有閉路において、上記第１の基本ノードと上記第２の基本ノードとを結び、且つ、基本リンクを共有しない、２つの異なる経路を特定する経路特定部（経路特定手段）１００３と、
を備える。
【０１８６】
これによれば、２つの基本ノードを結び、且つ、基本リンクを共有しない、２つの異なる経路を確実に特定することができる。更に、２つの基本ノードを結び、且つ、基本リンクを共有しない、２つの異なる経路を特定する際の処理負荷を低減することができる。
【０１８７】
以上、上記実施形態を参照して本願発明を説明したが、本願発明は、上述した実施形態に限定されるものではない。本願発明の構成及び詳細に、本願発明の範囲内において当業者が理解し得る様々な変更をすることができる。
【０１８８】
なお、上記各実施形態において経路特定装置の各機能は、ＣＰＵがプログラム（ソフトウェア）を実行することにより実現されていたが、回路等のハードウェアにより実現されていてもよい。
【０１８９】
また、上記各実施形態においてプログラムは、記憶装置に記憶されていたが、コンピュータが読み取り可能な記録媒体に記憶されていてもよい。例えば、記録媒体は、フレキシブルディスク、光ディスク、光磁気ディスク、及び、半導体メモリ等の可搬性を有する媒体である。
【０１９０】
また、上記実施形態の他の変形例として、上述した実施形態及び変形例の任意の組み合わせが採用されてもよい。
【０１９１】
＜付記＞
上記実施形態の一部又は全部は、以下の付記のように記載され得るが、以下には限られない。
【０１９２】
（付記１）
基本ノードと、２つの基本ノードを結ぶ基本リンクと、により構成される基本グラフにおいて、第１の基本ノードと第２の基本ノードとを結ぶ経路を特定する経路特定装置であって、
前記第１の基本ノードを通る第１の閉路と、前記第２の基本ノードを通る第２の閉路と、を含む複数の閉路を特定する閉路特定手段と、
前記特定された複数の閉路のうちの、基本ノード又は基本リンクである基本グラフ要素の少なくとも１つを共有する閉路同士を併合することにより、前記第１の基本ノードと前記第２の基本ノードとを通る閉路である経路含有閉路を特定する経路含有閉路特定手段と、
前記特定された経路含有閉路において、前記第１の基本ノードと前記第２の基本ノードとを結び、且つ、基本リンク、又は、当該第１の基本ノード及び当該第２の基本ノード以外の基本ノードを共有しない、２つの異なる経路を特定する経路特定手段と、
を備える経路特定装置。
【０１９３】
これによれば、２つの基本ノードを結び、且つ、基本リンク、又は、経路途中の（即ち、第１の基本ノード及び第２の基本ノード以外の）基本ノードを共有しない、２つの異なる経路を確実に特定することができる。更に、２つの基本ノードを結び、且つ、基本リンクを共有しない、２つの異なる経路を特定する際の処理負荷を低減することができる。
【０１９４】
（付記２）
付記１に記載の経路特定装置であって、
前記経路含有閉路特定手段は、２つの閉路が少なくとも１つの基本リンクを共有している場合、当該２つの閉路の一方から、当該共有されている基本リンクである共有リンクを除いた部分を構成するすべての基本リンクと、当該２つの閉路の他方から、当該共有リンクを除いた部分を構成するすべての基本リンクと、を連結した閉路を、当該２つの閉路同士を併合した閉路として用いるように構成された経路特定装置。
【０１９５】
（付記３）
付記１又は付記２に記載の経路特定装置であって、
前記経路含有閉路特定手段は、２つの閉路が基本リンクを共有することなく基本ノードのみを共有している場合、当該２つの閉路の一方を構成するすべての基本リンクと、当該２つの閉路の他方を構成するすべての基本リンクと、を連結した閉路を、当該２つの閉路同士を併合した閉路として用いるように構成された経路特定装置。
【０１９６】
（付記４）
付記１乃至付記３のいずれかに記載の経路特定装置であって、
前記経路含有閉路特定手段は、前記特定された複数の閉路のそれぞれを閉路ノードにより表すとともに、２つの閉路によって前記基本グラフにおける基本グラフ要素が共有されていることを、当該２つの閉路のそれぞれを表す閉路ノードを結ぶ隣接リンクにより表す閉路隣接グラフを生成し、当該生成された閉路隣接グラフに基づいて前記基本グラフにおける前記経路含有閉路を特定するように構成された経路特定装置。
【０１９７】
（付記５）
付記４に記載の経路特定装置であって、
前記経路含有閉路特定手段は、前記生成された閉路隣接グラフに、前記閉路ノードが表す閉路が前記基本グラフにおいて通る基本ノードのそれぞれを表す包含ノードと、閉路ノードが表す閉路が前記基本グラフにおいて包含ノードを通ることを表し且つ当該閉路ノードと当該包含ノードとを結ぶ包含リンクと、を追加した、閉路探索グラフを生成し、当該生成された閉路探索グラフに基づいて前記基本グラフにおける前記経路含有閉路を特定するように構成された経路特定装置。
【０１９８】
（付記６）
付記１乃至付記５のいずれかに記載の経路特定装置であって、
前記経路含有閉路特定手段は、前記基本グラフにおける前記基本リンクのそれぞれに対して予め設定された基本リンクコストの総和を最小とするように、前記基本グラフにおける前記経路含有閉路を特定するように構成された経路特定装置。
【０１９９】
これによれば、基本リンクコストの総和を最小とするように、２つの基本ノードを結び、且つ、基本リンク、又は、経路途中の基本ノードを共有しない、２つの異なる経路を特定することができる。
【０２００】
（付記７）
基本ノードと、２つの基本ノードを結ぶ基本リンクと、により構成される基本グラフにおいて、第１の基本ノードと第２の基本ノードとを結ぶ経路を特定する経路特定方法であって、
前記第１の基本ノードを通る第１の閉路と、前記第２の基本ノードを通る第２の閉路と、を含む複数の閉路を特定し、
前記特定された複数の閉路のうちの、基本ノード又は基本リンクである基本グラフ要素の少なくとも１つを共有する閉路同士を併合することにより、前記第１の基本ノードと前記第２の基本ノードとを通る閉路である経路含有閉路を特定し、
前記特定された経路含有閉路において、前記第１の基本ノードと前記第２の基本ノードとを結び、且つ、基本リンク、又は、当該第１の基本ノード及び当該第２の基本ノード以外の基本ノードを共有しない、２つの異なる経路を特定する、経路特定方法。
【０２０１】
（付記８）
付記７に記載の経路特定方法であって、
２つの閉路が少なくとも１つの基本リンクを共有している場合、当該２つの閉路の一方から、当該共有されている基本リンクである共有リンクを除いた部分を構成するすべての基本リンクと、当該２つの閉路の他方から、当該共有リンクを除いた部分を構成するすべての基本リンクと、を連結した閉路を、当該２つの閉路同士を併合した閉路として用いるように構成された経路特定方法。
【０２０２】
（付記９）
付記７又は付記８に記載の経路特定方法であって、
２つの閉路が基本リンクを共有することなく基本ノードのみを共有している場合、当該２つの閉路の一方を構成するすべての基本リンクと、当該２つの閉路の他方を構成するすべての基本リンクと、を連結した閉路を、当該２つの閉路同士を併合した閉路として用いるように構成された経路特定方法。
【０２０３】
（付記１０）
情報処理装置に、
基本ノードと、２つの基本ノードを結ぶ基本リンクと、により構成される基本グラフにおいて、第１の基本ノードと第２の基本ノードとを結ぶ経路を特定する処理を実行させるための経路特定プログラムであって、
前記処理は、
前記第１の基本ノードを通る第１の閉路と、前記第２の基本ノードを通る第２の閉路と、を含む複数の閉路を特定し、
前記特定された複数の閉路のうちの、基本ノード又は基本リンクである基本グラフ要素の少なくとも１つを共有する閉路同士を併合することにより、前記第１の基本ノードと前記第２の基本ノードとを通る閉路である経路含有閉路を特定し、
前記特定された経路含有閉路において、前記第１の基本ノードと前記第２の基本ノードとを結び、且つ、基本リンク、又は、当該第１の基本ノード及び当該第２の基本ノード以外の基本ノードを共有しない、２つの異なる経路を特定するように構成された経路特定プログラム。
【０２０４】
（付記１１）
付記１０に記載の経路特定プログラムであって、
前記処理は、２つの閉路が少なくとも１つの基本リンクを共有している場合、当該２つの閉路の一方から、当該共有されている基本リンクである共有リンクを除いた部分を構成するすべての基本リンクと、当該２つの閉路の他方から、当該共有リンクを除いた部分を構成するすべての基本リンクと、を連結した閉路を、当該２つの閉路同士を併合した閉路として用いるように構成された経路特定プログラム。
【０２０５】
（付記１２）
付記１０又は付記１１に記載の経路特定プログラムであって、
前記処理は、２つの閉路が基本リンクを共有することなく基本ノードのみを共有している場合、当該２つの閉路の一方を構成するすべての基本リンクと、当該２つの閉路の他方を構成するすべての基本リンクと、を連結した閉路を、当該２つの閉路同士を併合した閉路として用いるように構成された経路特定プログラム。
【産業上の利用可能性】
【０２０６】
本発明は、第１のノードと第２のノードとを結ぶ経路を特定する経路特定装置等に適用可能である。
【符号の説明】
【０２０７】
１ 経路特定装置
１１ グラフ情報記憶部
１２ 閉路特定部
１３ 経路含有閉路特定部
１４ 経路特定部
１０００ 経路特定装置
１００１ 閉路特定部
１００２ 経路含有閉路特定部
１００３ 経路特定部
【技術分野】
【０００１】
本発明は、第１のノードと第２のノードとを結ぶ経路を特定する経路特定装置に関する。
【背景技術】
【０００２】
ノードと、２つのノードを結ぶリンクと、により構成されるグラフにおいて、第１のノードと第２のノードとを結ぶ経路を特定する経路特定装置が知られている。この種の経路特定装置は、例えば、通信網等のネットワーク状に通信装置が接続された通信システムにおける通信装置間の経路を特定するために用いられる。
【０００３】
特に、経路特定装置は、ある経路を特定するとともに、その経路に対して冗長な経路も特定する（即ち、２つのノードを結び、且つ、リンクやノードを共有しない２つの異なる経路を特定する）ように構成されることが好適である。これによれば、システムは、障害の発生により、ある経路が使用不能となっても、その経路に対して冗長な経路を使用することができる。
【０００４】
ところで、冗長な経路を特定するための最も代表的な方法として、Ｄｉｊｋｓｔｒａ法（非特許文献１を参照）を繰り返し用いる方法が知られている。各リンクにコスト値が与えられ、経路のコストがその経路が経由するリンクのコスト和で与えられるグラフにおいて、この方法は、先ず、第１のノードと第２のノードとを結ぶ経路として、コストが最小となる経路（第１の経路）を、Ｄｉｊｋｓｔｒａ法に従って特定する。次いで、この方法は、特定された経路に含まれる、すべてのリンクを除外したグラフにおいて、再度、第１のノードと第２のノードとを結ぶ経路として、コストが最小となる経路（第２の経路）を、Ｄｉｊｋｓｔｒａ法に従って特定する。又は、この方法は、特定された経路に含まれる、すべての中間ノードを除外したグラフにおいて、再度、第１のノードと第２のノードとを結ぶ経路として、コストが最小となる経路（第２の経路）をＤｉｊｋｓｔｒａ法に従って特定する。
【０００５】
この方法を用いることにより、経路特定装置は、第１のノードと第２のノードとを結び、且つ、リンクやノードを共有しない２つの異なる経路（第１の経路、及び、第２の経路）を特定することができる。
【０００６】
しかしながら、上記方法によれば、経路を特定する対象となるグラフのトポロジがトラップ構造を含む場合、第１のノードと第２のノードとを結び、且つ、リンクを共有しない２つの異なる経路が存在しているときであっても、これらの経路を特定することができないことがある。
【０００７】
例えば、図１に示したグラフにおいて、第１のノードＮ１００と第２のノードＮ４００とを結ぶ経路を特定する場合を想定する。この場合において、リンクＬ１００、リンクＬ９００、リンクＬ５００、及び、リンクＬ４００をこの順に連結した経路（第１の経路）が、コストが最小となる経路である場合を想定する。
【０００８】
この場合、第１の経路に含まれる、すべてのリンクを除外したグラフは、図２に示したグラフである。ここで、破線は、除外されたリンクを表す。従って、このグラフにおいては、第１のノードＮ１００と第２のノードＮ４００とを結ぶ経路を特定することができない。即ち、このグラフのトポロジは、トラップ構造を含んでいる、と言うことができる。
【０００９】
このような課題に対処するため、Ｂｈａｎｄａｒｉ法（非特許文献２を参照）が知られている。この方法は、Ｄｉｊｋｓｔｒａ法を繰り返し用いる工程を拡張することにより、グラフのトポロジの一部を変換し、その結果、トラップ構造の基となるリンクであるトラップリンクを特定する。更に、この方法は、特定されたトラップリンクを除いたグラフにおいて、再度、Ｄｉｊｋｓｔｒａ法を繰り返し用いることにより、リンクを共有しない２つの異なる経路を特定する。
【先行技術文献】
【非特許文献】
【００１０】
【非特許文献１】E. W. Dijkstra、“A note on two problems in connexion with graphs”、 NumerischeMathematik 1、１９５９年、 pp. 269 − 271
【非特許文献２】Ramesh Bhandari、“Survivable Networks: Algorithms for diverse routing”、Springer、１９９９年
【発明の概要】
【発明が解決しようとする課題】
【００１１】
しかしながら、上記非特許文献２に記載の技術においては、トラップリンクを特定し、特定したトラップリンクの影響を排除するための処理の負荷（処理負荷）が比較的大きい。即ち、上記非特許文献２に記載の技術においては、２つのノードを結び、且つ、リンク、又は、当該２つのノード以外のノード（即ち、経路途中のノード）を共有しない、２つの異なる経路を特定する際の処理負荷が過大であるという問題があった。
【００１２】
このため、本発明の目的は、上述した課題である「２つのノードを結び、且つ、リンク、又は、経路途中のノードを共有しない、２つの異なる経路を特定する際の処理負荷が過大であること」を解決することが可能な経路特定装置を提供することにある。
【課題を解決するための手段】
【００１３】
かかる目的を達成するため本発明の一形態である経路特定装置は、
基本ノードと、２つの基本ノードを結ぶ基本リンクと、により構成される基本グラフにおいて、第１の基本ノードと第２の基本ノードとを結ぶ経路を特定する装置である。
【００１４】
更に、この経路特定装置は、
上記第１の基本ノードを通る第１の閉路と、上記第２の基本ノードを通る第２の閉路と、を含む複数の閉路を特定する閉路特定手段と、
上記特定された複数の閉路のうちの、基本ノード又は基本リンクである基本グラフ要素の少なくとも１つを共有する閉路同士を併合することにより、上記第１の基本ノードと上記第２の基本ノードとを通る閉路である経路含有閉路を特定する経路含有閉路特定手段と、
上記特定された経路含有閉路において、上記第１の基本ノードと上記第２の基本ノードとを結び、且つ、基本リンク、又は、当該第１の基本ノード及び当該第２の基本ノード以外の基本ノードを共有しない、２つの異なる経路を特定する経路特定手段と、
を備える。
【００１５】
また、本発明の他の形態である経路特定方法は、
基本ノードと、２つの基本ノードを結ぶ基本リンクと、により構成される基本グラフにおいて、第１の基本ノードと第２の基本ノードとを結ぶ経路を特定する方法である。
【００１６】
更に、この経路特定方法は、
上記第１の基本ノードを通る第１の閉路と、上記第２の基本ノードを通る第２の閉路と、を含む複数の閉路を特定し、
上記特定された複数の閉路のうちの、基本ノード又は基本リンクである基本グラフ要素の少なくとも１つを共有する閉路同士を併合することにより、上記第１の基本ノードと上記第２の基本ノードとを通る閉路である経路含有閉路を特定し、
上記特定された経路含有閉路において、上記第１の基本ノードと上記第２の基本ノードとを結び、且つ、基本リンク、又は、当該第１の基本ノード及び当該第２の基本ノード以外の基本ノードを共有しない、２つの異なる経路を特定する方法である。
【００１７】
また、本発明の他の形態である経路特定プログラムは、
情報処理装置に、
基本ノードと、２つの基本ノードを結ぶ基本リンクと、により構成される基本グラフにおいて、第１の基本ノードと第２の基本ノードとを結ぶ経路を特定する処理を実行させるためのプログラムである。
【００１８】
更に、上記処理は、
上記第１の基本ノードを通る第１の閉路と、上記第２の基本ノードを通る第２の閉路と、を含む複数の閉路を特定し、
上記特定された複数の閉路のうちの、基本ノード又は基本リンクである基本グラフ要素の少なくとも１つを共有する閉路同士を併合することにより、上記第１の基本ノードと上記第２の基本ノードとを通る閉路である経路含有閉路を特定し、
上記特定された経路含有閉路において、上記第１の基本ノードと上記第２の基本ノードとを結び、且つ、基本リンク、又は、当該第１の基本ノード及び当該第２の基本ノード以外の基本ノードを共有しない、２つの異なる経路を特定するように構成される。
【発明の効果】
【００１９】
本発明は、以上のように構成されることにより、２つのノードを結び、且つ、リンク、又は、経路途中のノードを共有しない、２つの異なる経路を特定する際の処理負荷を低減することができる。
【図面の簡単な説明】
【００２０】
【図１】背景技術に係る、経路が特定される対象となるグラフを示した図である。
【図２】背景技術に係る、第１の経路に含まれる、すべてのリンクを除外したグラフを示した図である。
【図３】本発明の第１実施形態に係る経路特定装置の機能の概略を表すブロック図である。
【図４】本発明の第１実施形態に係る、経路が特定される対象となる基本グラフを示した図である。
【図５】本発明の第１実施形態に係る基本グラフ情報を示したテーブルである。
【図６】本発明の第１実施形態に係る経路特定装置が、閉路隣接グラフを生成するために実行する処理を示したフローチャートである。
【図７】本発明の第１実施形態に係る経路特定装置が取得する全域木を概念的に示した説明図である。
【図８】本発明の第１実施形態に係る閉路情報を示したテーブルである。
【図９】本発明の第１実施形態に係る閉路情報を示したテーブルである。
【図１０】本発明の第１実施形態に係る閉路情報を示したテーブルである。
【図１１】本発明の第１実施形態に係る経路特定装置が生成した閉路隣接グラフを示した図である。
【図１２】本発明の第１実施形態に係る閉路隣接グラフ情報を示したテーブルである。
【図１３】本発明の第１実施形態に係る経路特定装置が、閉路隣接グラフに基づいて経路を特定するために実行する処理を示したフローチャートである。
【図１４】本発明の第１実施形態に係る、経路含有閉路を表す閉路情報を示したテーブルである。
【図１５】本発明の第２実施形態に係る、経路が特定される対象となる基本グラフを示した図である。
【図１６】本発明の第２実施形態に係る経路特定装置が生成した閉路隣接グラフを示した図である。
【図１７】本発明の第３実施形態に係る、経路が特定される対象となる基本グラフを示した図である。
【図１８】本発明の第３実施形態に係る経路特定装置が、閉路隣接グラフを生成するために実行する処理を示したフローチャートである。
【図１９】本発明の第３実施形態に係る経路特定装置が生成した閉路隣接グラフを示した図である。
【図２０】本発明の第４実施形態に係る併合閉路情報を示したテーブルである。
【図２１】本発明の第４実施形態に係る併合閉路情報を示したテーブルである。
【図２２】本発明の第５実施形態に係る経路特定装置が生成した閉路探索グラフを示した図である。
【図２３】本発明の第５実施形態に係る経路特定装置が生成した閉路探索グラフから、探索リンクコストが∞であるリンクを除去したグラフを示した図である。
【図２４】本発明の第６実施形態に係る経路特定装置が、経路を特定するために実行する処理を示したフローチャートである。
【図２５】本発明の第７実施形態に係る経路特定装置の機能の概略を表すブロック図である。
【発明を実施するための形態】
【００２１】
以下、本発明に係る、経路特定装置、経路特定方法、及び、経路特定プログラム、の各実施形態について図１〜図２５を参照しながら説明する。
【００２２】
＜第１実施形態＞
（構成）
図３に示したように、第１実施形態に係る経路特定装置１は、情報処理装置（本例では、サーバ装置）である。なお、経路特定装置１は、ネットワーク・スイッチ、ルーター、パーソナル・コンピュータ、携帯電話端末、ＰＨＳ（Ｐｅｒｓｏｎａｌ Ｈａｎｄｙｐｈｏｎｅ Ｓｙｓｔｅｍ）、ＰＤＡ（Ｐｅｒｓｏｎａｌ Ｄａｔａ Ａｓｓｉｓｔａｎｃｅ、Ｐｅｒｓｏｎａｌ Ｄｉｇｉｔａｌ Ａｓｓｉｓｔａｎｔ）、スマートフォン、カーナビゲーション端末、又は、ゲーム端末等であってもよい。
【００２３】
経路特定装置１は、図示しない中央処理装置（ＣＰＵ；Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）、一次記憶装置（メモリ（ＲＡＭ；Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ））、及び、二次記憶装置（ハードディスク駆動装置（ＨＤＤ；Ｈａｒｄ Ｄｉｓｋ Ｄｒｉｖｅ））を備える。
【００２４】
経路特定装置１は、二次記憶装置に記憶されているプログラムをＣＰＵが実行することにより、後述する機能を実現するように構成されている。
【００２５】
なお、経路特定装置１の各機能は、回路等のハードウェアにより実現されていてもよい。また、プログラムは、二次記憶装置に記憶されていたが、コンピュータが読み取り可能な記録媒体に記憶されていてもよい。例えば、記録媒体は、フレキシブルディスク、光ディスク、光磁気ディスク、及び、半導体メモリ等の可搬性を有する媒体である。
【００２６】
（機能）
図３は、上記のように構成された経路特定装置１の機能を表すブロック図である。経路特定装置１の機能は、基本ノードと、２つの基本ノードを結ぶ基本リンクと、により構成される基本グラフにおいて、第１の基本ノードと第２の基本ノードとを結ぶ経路を特定する。例えば、基本ノードは、通信装置を表す。また、基本リンクは、２つの通信装置を接続する、通信線又は通信回線を表す。
【００２７】
具体的には、経路特定装置１の機能は、グラフ情報記憶部１１と、閉路特定部（閉路特定手段）１２と、経路含有閉路特定部（経路含有閉路特定手段）１３と、経路特定部（経路特定手段）１４と、を含む。
【００２８】
グラフ情報記憶部１１は、基本グラフ情報と、閉路情報と、閉路隣接グラフ情報と、経路含有閉路情報と、を記憶する。
【００２９】
基本グラフ情報は、基本グラフを構成する、複数の基本ノードのそれぞれを識別するための基本ノード識別子と、複数の基本ノードの任意の２つの組のそれぞれに対して、当該２つの基本ノードを結ぶ基本リンクが存在する（即ち、２つの基本ノードが接続されている）か否かを表す情報と、を含む。
【００３０】
閉路情報は、基本グラフにおける閉路を表す情報である。閉路情報は、閉路を識別するための閉路識別子と、当該閉路を構成する基本リンクを特定するための情報と、を含む。
【００３１】
閉路隣接グラフ情報は、閉路隣接グラフを構成する、複数の閉路ノードのそれぞれを識別するための閉路ノード識別子と、複数の閉路ノードの任意の２つの組のそれぞれに対して、当該２つの閉路ノードを結ぶ隣接リンクが存在する（即ち、２つの閉路ノードが接続されている）か否かを表す情報と、を含む。
【００３２】
ここで、閉路隣接グラフは、基本グラフにおける複数の閉路のそれぞれを閉路ノードにより表すとともに、２つの閉路によって基本グラフにおける基本グラフ要素（基本ノード、又は、基本リンク）が共有されていることを、当該２つの閉路のそれぞれを表す閉路ノードを結ぶ隣接リンクにより表すグラフである。
【００３３】
経路含有閉路情報は、基本グラフにおける経路含有閉路を表す情報である。経路含有閉路は、基本グラフにおいて、第１の基本ノードと第２の基本ノードとを通る閉路である。経路含有閉路情報は、経路含有閉路を識別するための経路含有閉路識別子と、当該経路含有閉路を構成する基本リンクを特定するための情報と、を含む。
【００３４】
なお、基本グラフ、及び、閉路隣接グラフを表す情報は、隣接行列、又は、隣接リスト等により表される。なお、基本グラフ、及び、閉路隣接グラフを表す情報は、情報処理装置により処理可能な他の形式により表されてもよい。
【００３５】
閉路特定部１２は、グラフ情報記憶部１１に記憶されている基本グラフ情報に基づいて、第１の基本ノードを通る第１の閉路と、第２の基本ノードを通る第２の閉路と、を含む複数の閉路を特定する。閉路特定部１２は、特定された閉路を表す閉路情報をグラフ情報記憶部１１に記憶させる。
【００３６】
経路含有閉路特定部１３は、閉路特定部１２により特定された複数の閉路のうちの、基本グラフ要素の少なくとも１つを共有する閉路同士を併合することにより、経路含有閉路を特定する。
【００３７】
ここで、経路含有閉路特定部１３は、２つの閉路が少なくとも１つの基本リンクを共有している場合、当該２つの閉路の一方から共有リンクを除いた部分を構成するすべての基本リンクと、当該２つの閉路の他方から共有リンクを除いた部分を構成するすべての基本リンクと、を連結した閉路を、当該２つの閉路同士を併合した閉路として用いる。ここで、共有リンクは、上記２つの閉路により共有されている基本リンクである。
【００３８】
具体的には、経路含有閉路特定部１３は、グラフ情報記憶部１１に記憶されている閉路情報に基づいて閉路隣接グラフを生成する。更に、経路含有閉路特定部１３は、生成された閉路隣接グラフを表す閉路隣接グラフ情報をグラフ情報記憶部１１に記憶させる。
【００３９】
加えて、経路含有閉路特定部１３は、生成された閉路隣接グラフに基づいて、基本グラフにおける経路含有閉路を特定する。このとき、経路含有閉路特定部１３は、基本グラフにおける基本リンクのそれぞれに対して予め設定された基本リンクコストの総和を最小とするように、基本グラフにおける経路含有閉路を特定する。
【００４０】
経路含有閉路特定部１３は、特定された経路含有閉路を表す経路含有閉路情報をグラフ情報記憶部１１に記憶させる。
【００４１】
経路特定部１４は、グラフ情報記憶部１１に記憶されている経路含有閉路情報が表す経路含有閉路（即ち、経路含有閉路特定部１３により特定された経路含有閉路）において、第１の基本ノードと第２の基本ノードとを結び、且つ、基本リンクを共有しない、２つの異なる経路を特定する。
【００４２】
（作動）
次に、上述した経路特定装置１の作動について説明する。
本例では、図４に示した基本グラフにおいて経路を特定する際の経路特定装置１の作動について説明する。この基本グラフは、７つの基本ノードＮ１００〜Ｎ７００と、９つの基本リンクＬ１００〜Ｌ９００と、により構成される。
【００４３】
図４に示した基本グラフは、図５に示した基本グラフ情報（隣接行列）により表される。本例では、経路特定装置１は、基本グラフ情報を予め記憶している。図５において、「Ｎ１００」〜「Ｎ７００」のそれぞれは、基本ノード識別子である。また、隣接行列における値「１」は、当該値の行と対応付けられた基本ノード識別子により識別される基本ノードと、当該値の列と対応付けられた基本ノード識別子により識別される基本ノードと、を結ぶ基本リンクが存在することを表す。
【００４４】
なお、本例では、図４に示したように、簡単のために、比較的規模が小さい基本グラフに経路特定装置１が適用されているが、より規模が大きい基本グラフ、又は、より規模が小さい基本グラフに経路特定装置１が適用されてもよい。
【００４５】
＜＜１．閉路隣接グラフの生成＞＞
先ず、経路特定装置１は、基本グラフに基づいて閉路隣接グラフを生成する。図６は、経路特定装置１が、閉路隣接グラフを生成するために実行する処理を示したフローチャートである。以下、図４に示した基本グラフに基づいて閉路隣接グラフを生成する際の、経路特定装置１の作動について説明する。なお、経路特定装置１は、図４に示した基本グラフ以外の基本グラフに対しても同様に作動する。
【００４６】
初めに、経路特定装置１は、ステップＳ１０１にて、基本グラフにおける全域木（スパニングツリー）を取得する。全域木を取得する方法は、深さ優先探索法、幅優先探索法、Ｄｉｊｋｓｔｒａ（ダイクストラ）法、又は、プリム法等の種々の方法のいずれかである。ここでは、図４に示した基本グラフに対して、図７に示した全域木（すべての基本ノードと、実線により示された基本リンクと、により構成される部分）が取得された場合を想定する。
【００４７】
次いで、経路特定装置１は、ステップＳ１０２にて、ステップＳ１０１にて取得された全域木に含まれない基本リンクの集合（基本リンク集合）を取得する。
【００４８】
そして、経路特定装置１は、ステップＳ１０３〜Ｓ１０６にて、図７に示した全域木に対して、全域木に含まれていない基本リンクを１つずつ追加することにより閉路を取得（特定）し、取得された閉路に基づいて閉路隣接グラフを生成する。
【００４９】
具体的には、経路特定装置１は、ステップＳ１０３にて、上記基本リンク集合が空集合であるか否かを判定する。経路特定装置１は、上記基本リンク集合が空集合でない場合、「Ｎｏ」と判定してステップＳ１０４へ進む。
【００５０】
そして、経路特定装置１は、基本リンク集合から基本リンクを１つ取得し、取得された基本リンクを基本リンク集合から削除する。更に、経路特定装置１は、取得された基本リンクと、当該基本リンクにより結ばれる（当該基本リンクを構成する）２つの基本ノードを、全域木において結ぶ経路を構成する、すべての基本リンクと、を連結した閉路を取得（特定）する。
【００５１】
次いで、経路特定装置１は、ステップＳ１０５にて、特定された閉路を表す閉路ノードを閉路隣接グラフに追加する。更に、経路特定装置１は、ステップＳ１０６にて、前回までに追加されていた閉路ノードが表す閉路と、今回、新たに追加された閉路ノードが表す閉路と、に基づいて、隣接リンクを閉路隣接グラフに追加する。
【００５２】
そして、経路特定装置１は、ステップＳ１０３へ戻り、ステップＳ１０３〜ステップＳ１０６の処理を、基本リンク集合が空集合となるまで繰り返し実行する。そして、基本リンク集合が空集合となると、経路特定装置１は、ステップＳ１０３にて「Ｙｅｓ」と判定して図６に示した処理の実行を終了する。
【００５３】
なお、経路特定装置１は、図６に示した処理を実行することにより取得された閉路のそれぞれを表す閉路情報と、当該処理を実行することにより取得された閉路隣接グラフを表す閉路隣接グラフ情報と、を記憶装置に記憶させる。
【００５４】
例えば、図７に示した全域木においては、基本リンクＬ６００を追加することにより、閉路Ｎ１００−Ｎ２００−Ｎ６００−Ｎ１００が取得される。同様に、基本リンクＬ５００を追加することにより、閉路Ｎ２００−Ｎ３００−Ｎ７００−Ｎ５００−Ｎ６００−Ｎ２００が取得される。また、基本リンクＬ４００を追加することにより、閉路Ｎ３００−Ｎ４００−Ｎ５００−Ｎ７００−Ｎ３００が取得される。
【００５５】
本例では、経路特定装置１が、上述した３つの閉路を取得した場合を想定する。閉路Ｎ１００−Ｎ２００−Ｎ６００−Ｎ１００は、図８に示した閉路情報（隣接行列）により表される。閉路Ｎ１００−Ｎ２００−Ｎ６００−Ｎ１００を識別するための閉路識別子は、「Ｃ１００」である。
【００５６】
同様に、閉路Ｎ２００−Ｎ３００−Ｎ７００−Ｎ５００−Ｎ６００−Ｎ２００は、図９に示した閉路情報（隣接行列）により表される。閉路Ｎ２００−Ｎ３００−Ｎ７００−Ｎ５００−Ｎ６００−Ｎ２００を識別するための閉路識別子は、「Ｃ２００」である。
【００５７】
また、閉路Ｎ３００−Ｎ４００−Ｎ５００−Ｎ７００−Ｎ３００は、図１０に示した閉路情報（隣接行列）により表される。閉路Ｎ３００−Ｎ４００−Ｎ５００−Ｎ７００−Ｎ３００を識別するための閉路識別子は、「Ｃ３００」である。
【００５８】
また、本例では、閉路Ｃ１００と閉路Ｃ２００とは、基本リンクＬ９００を共有している。また、閉路Ｃ２００とＣ３００とは、基本リンクＬ７００、及び、基本リンクＬ８００を共有している。また、閉路Ｃ１００とＣ３００とは、基本リンクを共有していない。なお、閉路Ｃ２００と閉路Ｃ３００に対する基本ノードＮ７００のように、２つの閉路が共有している区間の両端以外に位置するノードを臨界ノードと呼ぶ。
【００５９】
従って、経路特定装置１により生成される閉路隣接グラフは、図１１に示したように、閉路ノードＣ１００と閉路ノードＣ２００とを結ぶ隣接リンクＡ１００と、閉路ノードＣ２００と閉路ノードＣ３００とを結ぶ隣接リンクＡ２００と、を含む。すなわち、隣接リンクＡ１００は基本リンクＬ９００と、隣接リンクＡ２００は基本リンクＬ７００およびＬ８００と関連づけられている。隣接リンクＡが基本リンクＬと関連づけられている状態を単に、隣接リンクＡは基本リンクＬを含む、又は、内包する、と表現することにする。また、複数の連結した基本リンクを含む隣接リンクは臨界ノードを含む。図１１の例において、隣接リンクＡ２００は臨界ノードＮ７００を含む。
【００６０】
図１１に示した閉路隣接グラフは、図１２に示した閉路隣接グラフ情報（隣接行列）により表される。図１２において、「Ｃ１００」〜「Ｃ３００」のそれぞれは、閉路ノード識別子である。また、隣接行列における値「１」は、当該値の行と対応付けられた閉路ノード識別子により識別される閉路ノードと、当該値の列と対応付けられた閉路ノード識別子により識別される閉路ノードと、を結ぶ隣接リンクが存在することを表す。
【００６１】
なお、経路特定装置１は、上述した方法以外の方法を用いることにより、閉路隣接グラフを生成するように構成されていてもよい。なお、閉路隣接グラフを生成する方法は、基本グラフにおける基本リンクのそれぞれが少なくとも１つの閉路ノードに含まれているという第１の条件と、閉路隣接グラフが連結であるという第２の条件と、の両方が満たされる方法であることが好適である。
【００６２】
なお、上述した方法においては、基本グラフにおける各基本リンクは、全域木に含まれるか、又は、閉路を構成するために追加される基本リンクである。従って、上述した方法は、第１の条件を満たす。更に、いずれの閉路も全域木の一部を含む。従って、上述した方法は、第２の条件も満たす。
【００６３】
＜＜２．経路の特定＞＞
次に、経路特定装置１は、生成された閉路隣接グラフに基づいて経路を特定する。図１３は、経路特定装置１が、閉路隣接グラフに基づいて経路を特定するために実行する処理を示したフローチャートである。
【００６４】
経路特定装置１は、記憶装置に記憶されている、基本グラフ情報、閉路情報、及び、閉路隣接グラフ情報、に基づいて経路を特定する。なお、経路特定装置１は、基本グラフにおける基本リンクのそれぞれに対して予め設定された基本リンクコストｗ０（ｘ）を予め記憶している。ここで、パラメータｘは、基本リンクを特定するための情報である。なお、基本リンクコストｗ０（ｘ）は、経路特定装置１のユーザにより入力された情報であってもよい。
【００６５】
基本リンクコストｗ０（ｘ）は、スカラ値を有する。基本リンクコストｗ０（ｘ）は、基本リンクの長さ、又は、基本リンクのその他の属性等に基づいて設定されることが好適である。ところで、基本リンクの系列としての経路ｐ（＝｛ｌ０，ｌ１，…，ｌｉ｝、ここで、ｌｊは、ｊ番目の基本リンクであり、ｊは、０〜ｉの整数である）のコストＷ（ｐ）は、数式１により表される。
【数１】
【００６６】
また、経路特定装置１は、基本リンクコストｗ０（ｘ）に基づいて、閉路隣接グラフにおける隣接リンクのそれぞれに対する隣接リンクコストｗ（ｘ）を算出する。パラメータｘが、閉路ノードｃ０と閉路ノードｃ１とを結ぶ隣接リンクである場合において、当該隣接リンクが第１の基本ノードと第２の基本ノードとのいずれも臨界ノードとして含まないとき、経路特定装置１は、隣接リンクコストｗ（ｘ）を数式２に基づいて算出する。
【数２】
【００６７】
一方、パラメータｘが、閉路ノードｃ０と閉路ノードｃ１とを結ぶ隣接リンクである場合において、当該隣接リンクが第１の基本ノード又は第２の基本ノードの少なくとも一方を臨界ノードとして含むとき、経路特定装置１は、隣接リンクコストｗ（ｘ）を数式３に基づいて算出する。
【数３】
【００６８】
ここでは、第１の基本ノードが基本ノードＮ１００であり、第２の基本ノードが基本ノードＮ４００である場合を想定する。即ち、経路特定装置１が、第１の基本ノードＮ１００と、第２の基本ノードＮ４００と、を結び、且つ、基本リンクを共有しない、２つの異なる経路を特定する場合を想定する。
【００６９】
経路特定装置１は、図１３のステップＳ２０１にて、閉路隣接グラフにおいて、最小コスト経路を特定する。最小コスト経路は、第１の基本ノードＮ１００を通る閉路を表す閉路ノードＣ１００と、第２の基本ノードＮ４００を通る閉路を表す閉路ノードＣ３００と、を結び、且つ、コストが最小となる経路である。
【００７０】
最小コスト経路を特定する方法は、幅優先探索法、又は、修正ダイクストラ法（非特許文献２）等の負のリンクコストを許容する最短経路計算アルゴリズムである。
【００７１】
本例では、経路特定装置１は、閉路隣接グラフにおける最小コスト経路として、経路Ｃ１００−Ｃ２００−Ｃ３００を特定する。
【００７２】
経路特定装置１は、ステップＳ２０２にて、閉路隣接グラフにおける最小コスト経路が特定されたか否かを判定する。本例では、経路特定装置１は、「Ｙｅｓ」と判定し、ステップＳ２０３へ進む。なお、最小コスト経路が特定されなかった場合、経路特定装置１は、図１３に示した処理の実行を終了する。
【００７３】
次いで、経路特定装置１は、ステップＳ２０３にて、閉路隣接グラフにおける最小コスト経路において隣接する２つの閉路ノードが表す２つの閉路同士を併合することにより、第１の基本ノードＮ１００と第２の基本ノードＮ４００とを通る閉路である経路含有閉路を特定する。
【００７４】
本例では、経路特定装置１は、２つの閉路のそれぞれから、２つの閉路により共有されている基本リンク（共有リンク）を除いた部分を構成する、すべての基本リンクを連結した閉路を、当該２つの閉路同士を併合した閉路として用いる。
【００７５】
本例では、閉路情報は、図８乃至図１０に示したように隣接行列により表されている。従って、経路特定装置１は、２つの閉路のそれぞれを表す隣接行列の排他的論理和を算出することにより、当該２つの閉路同士を併合した閉路を表す閉路情報を取得する。
【００７６】
具体的には、経路特定装置１は、閉路Ｃ１００〜Ｃ３００を併合することにより、経路含有閉路Ｎ１００−Ｎ２００−Ｎ３００−Ｎ４００−Ｎ５００−Ｎ６００−Ｎ１００を特定する。本例では、経路特定装置１は、図８乃至図１０に示した隣接行列の排他的論理和を算出することにより、経路含有閉路を表す閉路情報としての、図１４に示した隣接行列を取得する。
【００７７】
なお、経路特定装置１は、他の方法を用いることにより、２つの閉路同士を併合した閉路を表す閉路情報を取得するように構成されていてもよい。
【００７８】
次いで、経路特定装置１は、ステップＳ２０３にて特定された経路含有閉路において、第１の基本ノードＮ１００と第２の基本ノードＮ４００とを結ぶ最小コスト経路（第１の経路）を特定する（ステップＳ２０４）。このとき、経路特定装置１は、基本リンクコストｗ０（ｘ）に基づいて最小コスト経路を特定する。
【００７９】
具体的には、経路特定装置１は、幅優先探索法、又は、ダイクストラ法等を用いることにより、最小コスト経路を特定する。ここでは、経路特定装置１は、最小コスト経路Ｎ１００−Ｎ２００−Ｎ３００−Ｎ４００を特定する。
【００８０】
次いで、経路特定装置１は、ステップＳ２０３にて特定された経路含有閉路において、第１の経路と異なる経路であり、且つ、第１の基本ノードＮ１００と第２の基本ノードＮ４００とを結ぶ経路である冗長経路（第２の経路）を特定する（ステップＳ２０５）。ここでは、経路特定装置１は、冗長経路Ｎ１００−Ｎ６００−Ｎ５００−Ｎ４００を特定する。
【００８１】
具体的には、経路特定装置１は、ステップＳ２０３にて特定された経路含有閉路を表す環状リストから、ステップＳ２０４にて特定された第１の経路に相当する部分を取り除くことにより、第２の経路を特定する。なお、経路特定装置１は、ステップＳ２０４にて特定された第１の経路における中間の基本ノード又は基本リンクを使用不可とする条件を設けた状態において、深さ優先探索法、又は、ダイクストラ法等を用いることにより第２の経路を特定してもよい。
【００８２】
このようにして、経路特定装置１は、閉路隣接グラフを用いることにより、第１の基本ノードＮ１００と第２の基本ノードＮ４００とを結び、且つ、基本リンクを共有しない、２つの異なる経路（第１の経路、及び、第２の経路）を特定する。
【００８３】
以上、説明したように、本発明の第１実施形態に係る経路特定装置１によれば、２つの基本ノードを結び、且つ、基本リンクを共有しない、２つの異なる経路を確実に特定することができる。更に、２つの基本ノードを結び、且つ、基本リンク、又は、経路途中の（即ち、第１の基本ノード及び第２の基本ノード以外の）基本ノードを共有しない、２つの異なる経路を特定する際の処理負荷を低減することができる。
【００８４】
更に、本発明の第１実施形態に係る経路特定装置１は、基本グラフにおける基本リンクのそれぞれに対して予め設定された基本リンクコストの総和を最小とするように、基本グラフにおける経路含有閉路を特定する。
【００８５】
これによれば、基本リンクコストの総和を最小とするように、２つの基本ノードを結び、且つ、基本リンク、又は、経路途中の基本ノードを共有しない、２つの異なる経路を特定することができる。
【００８６】
＜第２実施形態＞
次に、本発明の第２実施形態に係る経路特定装置について説明する。第２実施形態に係る経路特定装置は、上記第１実施形態に係る経路特定装置に対して、２つの閉路が基本ノードのみを共有している場合、当該２つの閉路のそれぞれを構成するすべての基本リンクを連結した閉路を、当該２つの閉路同士を併合した閉路として用いる点において相違している。従って、以下、かかる相違点を中心として説明する。
【００８７】
（機能）
第２実施形態に係る経路含有閉路特定部１３は、２つの閉路が基本リンクを共有することなく基本ノードのみを共有している場合、当該２つの閉路の一方を構成するすべての基本リンクと、当該２つの閉路の他方を構成するすべての基本リンクと、を連結した閉路を、当該２つの閉路同士を併合した閉路として用いる。
【００８８】
本例では、２つの閉路が基本リンクを共有している状態は、強隣接状態とも呼ばれる。また、２つの閉路が基本リンクを共有することなく基本ノードのみを共有している状態は、弱隣接状態とも呼ばれる。
【００８９】
（作動）
次に、上述した経路特定装置１の作動について説明する。
本例では、図１５に示した基本グラフにおいて経路を特定する際の経路特定装置１の作動について説明する。この基本グラフは、９つの基本ノードＮ１００〜Ｎ９００と、１２個の基本リンクＬ１００〜Ｌ１２００と、により構成される。
【００９０】
＜＜１．閉路隣接グラフの生成＞＞
経路特定装置１は、第１実施形態と同様に、閉路を特定する。本例では、経路特定装置１は、閉路Ｃ１００、閉路Ｃ２００、及び、閉路Ｃ３００に加えて、閉路Ｃ７００（Ｎ４００−Ｎ８００−Ｎ９００−Ｎ４００）も特定する。
【００９１】
閉路Ｃ３００と閉路Ｃ７００とは、基本リンクを共有することなく、基本ノードＮ４００のみを共有している。即ち、閉路Ｃ３００と閉路Ｃ７００とは、弱隣接状態にある。経路特定装置１は、図１６に示したように、弱隣接状態を表す隣接リンク（弱隣接リンク）Ａ３００を閉路隣接グラフに追加する。なお、弱隣接状態にある２つの閉路に共有される唯一の基本ノードは、臨界ノードと見なされる。すなわち、いずれの弱隣接リンクも基本リンクを含まず、且つ、臨界ノードを１つ含む。
【００９２】
＜＜２．経路の特定＞＞
経路特定装置１は、第１実施形態と同様に、図１６に示した閉路隣接グラフに基づいて経路を特定する。
【００９３】
本例では、パラメータｘが、閉路ノードｃ０と閉路ノードｃ１とを結ぶ隣接リンクであり、且つ、閉路ノードｃ０が表す閉路と閉路ノードｃ１が表す閉路とが弱隣接状態にある場合において、当該隣接リンク（弱隣接リンク）が含んでいる基本ノードが第１の基本ノードと第２の基本ノードのいずれでもないとき、経路特定装置１は、隣接リンクコストｗ（ｘ）を数式４に基づいて算出する。ただし、本例において導入した弱隣接リンクは基本リンクを含まないため、数式４は数式２と同等である。すなわち、第１実施形態において数式１〜３により示した隣接リンクコストｗ（ｘ）を、本例においてもそのまま使用することができる。
【数４】
【００９４】
ここでは、第１の基本ノードが基本ノードＮ１００であり、第２の基本ノードが基本ノードＮ８００である場合を想定する。即ち、経路特定装置１が、第１の基本ノードＮ１００と、第２の基本ノードＮ８００と、を結び、且つ、基本リンクを共有しない、２つの異なる経路を特定する場合を想定する。
【００９５】
経路特定装置１は、図１３のステップＳ２０１にて、閉路隣接グラフにおいて、最小コスト経路を特定する。最小コスト経路は、第１の基本ノードＮ１００を通る閉路を表す閉路ノードＣ１００と、第２の基本ノードＮ８００を通る閉路を表す閉路ノードＣ７００と、を結び、且つ、コストが最小となる経路である。
【００９６】
最小コスト経路を特定する方法は、幅優先探索法、又は、修正ダイクストラ法（非特許文献２）等の負のリンクコストを許容する最短経路計算アルゴリズムである。
【００９７】
本例では、経路特定装置１は、閉路隣接グラフにおける最小コスト経路として、経路Ｃ１００−Ｃ２００−Ｃ３００−Ｃ７００を特定する。
【００９８】
経路特定装置１は、ステップＳ２０２にて、閉路隣接グラフにおける最小コスト経路が特定されたか否かを判定する。本例では、経路特定装置１は、「Ｙｅｓ」と判定し、ステップＳ２０３へ進む。なお、最小コスト経路が特定されなかった場合、経路特定装置１は、図１３に示した処理の実行を終了する。
【００９９】
次いで、経路特定装置１は、ステップＳ２０３にて、閉路隣接グラフにおける最小コスト経路において隣接する２つの閉路ノードが表す２つの閉路同士を併合することにより、第１の基本ノードＮ１００と第２の基本ノードＮ８００とを通る閉路である経路含有閉路を特定する。
【０１００】
本例では、経路特定装置１は、２つの閉路が基本リンクを共有している場合、当該２つの閉路のそれぞれから、２つの閉路により共有されている基本リンク（共有リンク）を除いた部分を構成する、すべての基本リンクを連結した閉路を、当該２つの閉路同士を併合した閉路として用いる。更に、経路特定装置１は、２つの閉路が基本リンクを共有することなく基本ノードを共有している場合、当該２つの閉路のそれぞれを構成する、すべての基本リンクを連結した閉路を、当該２つの閉路同士を併合した閉路として用いる。
【０１０１】
具体的には、経路特定装置１は、２つの閉路のそれぞれを表す隣接行列の排他的論理和を算出することにより、当該２つの閉路同士を併合した閉路を表す閉路情報を取得する。
【０１０２】
本例では、経路特定装置１は、閉路Ｃ１００〜Ｃ３００，Ｃ７００を併合することにより、経路含有閉路Ｎ１００−Ｎ２００−Ｎ３００−Ｎ４００−Ｎ８００−Ｎ９００−Ｎ４００−Ｎ５００−Ｎ６００−Ｎ１００を特定する。
【０１０３】
なお、経路特定装置１は、他の方法を用いることにより、２つの閉路同士を併合した閉路を表す閉路情報を取得するように構成されていてもよい。
【０１０４】
次いで、経路特定装置１は、ステップＳ２０３にて特定された経路含有閉路において、第１の基本ノードＮ１００と第２の基本ノードＮ８００とを結ぶ最小コスト経路（第１の経路）を特定する（ステップＳ２０４）。このとき、経路特定装置１は、基本リンクコストｗ０（ｘ）に基づいて最小コスト経路を特定する。
【０１０５】
具体的には、経路特定装置１は、幅優先探索法、又は、ダイクストラ法等を用いることにより、最小コスト経路を特定する。ここでは、経路特定装置１は、最小コスト経路Ｎ１００−Ｎ２００−Ｎ３００−Ｎ４００−Ｎ８００を特定する。
【０１０６】
次いで、経路特定装置１は、ステップＳ２０３にて特定された経路含有閉路において、第１の経路と異なる経路であり、且つ、第１の基本ノードＮ１００と第２の基本ノードＮ８００とを結ぶ経路である冗長経路（第２の経路）を特定する（ステップＳ２０５）。ここでは、経路特定装置１は、冗長経路Ｎ１００−Ｎ６００−Ｎ５００−Ｎ４００−Ｎ９００−Ｎ８００を特定する。
【０１０７】
具体的には、経路特定装置１は、ステップＳ２０３にて特定された経路含有閉路を表す環状リストから、ステップＳ２０４にて特定された第１の経路に相当する部分を取り除くことにより、第２の経路を特定する。なお、経路特定装置１は、ステップＳ２０４にて特定された第１の経路における中間の基本ノード又は基本リンクを使用不可とする条件を設けた状態において、深さ優先探索法、又は、ダイクストラ法等を用いることにより第２の経路を特定してもよい。
【０１０８】
このようにして、経路特定装置１は、閉路隣接グラフを用いることにより、第１の基本ノードＮ１００と第２の基本ノードＮ８００とを結び、且つ、基本リンク、又は、経路途中の基本ノードを共有しない、２つの異なる経路（第１の経路、及び、第２の経路）を特定する。
【０１０９】
以上、説明したように、本発明の第２実施形態に係る経路特定装置１によっても、第１実施形態に係る経路特定装置１と同様の作用及び効果が奏される。
【０１１０】
＜第３実施形態＞
次に、本発明の第３実施形態に係る経路特定装置について説明する。第３実施形態に係る経路特定装置は、上記第１実施形態に係る経路特定装置に対して、閉路を構成しない基本ノードが存在する場合において、一部の基本リンクを共有する２つの異なる経路を特定する点において相違している。従って、以下、かかる相違点を中心として説明する。
【０１１１】
本例では、閉路隣接グラフは、いずれの閉路にも含まれない（いずれの閉路も構成しない）基本ノードを閉路ノード（疑似閉路ノード）として含む。更に、閉路隣接グラフは、いずれの閉路にも含まれない（いずれの閉路も構成しない）基本リンクを隣接リンク（疑似隣接リンク）として含む。
【０１１２】
（作動）
次に、上述した経路特定装置１の作動について説明する。
本例では、図１７に示した基本グラフにおいて経路を特定する際の経路特定装置１の作動について説明する。この基本グラフは、１１個の基本ノードＮ１００〜Ｎ１１００と、１４個の基本リンクＬ１００〜Ｌ１４００と、により構成される。
【０１１３】
＜＜１．閉路隣接グラフの生成＞＞
経路特定装置１は、図６に示したフローチャートに代えて、図１８に示したフローチャートにより表される処理を、閉路隣接グラフを生成するために実行する。図１８に示した処理は、図６に示した処理と同様のステップＳ３０１〜ステップＳ３０６の処理の後に、ステップＳ３０７〜ステップＳ３１０の処理を追加した処理である。
【０１１４】
経路特定装置１は、第１実施形態と同様に、ステップＳ３０１〜ステップＳ３０６の処理を実行することにより、閉路Ｃ１００、閉路Ｃ２００、及び、閉路Ｃ３００に加えて、閉路Ｃ９００（Ｎ１１００−Ｎ８００−Ｎ９００−Ｎ１１００）を特定する。経路特定装置１は、特定された閉路に基づいて閉路隣接グラフを生成する。
【０１１５】
この時点では、閉路隣接グラフにおいて、閉路Ｃ９００を表す閉路ノードは、他の閉路ノードと接続されていない。
【０１１６】
そして、経路特定装置１は、ステップＳ３０７へ進み、いずれの閉路にも含まれない基本ノードの集合である基本ノード集合を取得する。本例では、経路特定装置１は、基本ノードのそれぞれに対して、閉路に含まれた回数（例えば、ステップＳ３０５の処理を実行した回数）を数えることにより、基本ノード集合を取得する。
【０１１７】
次いで、経路特定装置１は、ステップＳ３０８にて、上記基本ノード集合が空集合であるか否かを判定する。経路特定装置１は、上記基本ノード集合が空集合でない場合、「Ｎｏ」と判定してステップＳ３０９へ進む。
【０１１８】
そして、経路特定装置１は、基本ノード集合から基本ノードを１つ取得し、取得された基本ノードを基本ノード集合から削除する。更に、経路特定装置１は、取得された基本ノードを閉路ノード（疑似閉路ノード）として閉路隣接グラフに追加する（ステップＳ３０９）。
【０１１９】
更に、経路特定装置１は、ステップＳ３１０にて、上記疑似閉路ノードとしての基本ノードに接続されている基本リンクのそれぞれを、隣接リンク（疑似隣接リンク）として閉路隣接グラフに追加する。
【０１２０】
そして、経路特定装置１は、ステップＳ３０８へ戻り、ステップＳ３０８〜ステップＳ３１０の処理を、基本ノード集合が空集合となるまで繰り返し実行する。そして、基本ノード集合が空集合となると、経路特定装置１は、ステップＳ３０８にて「Ｙｅｓ」と判定して図１８に示した処理の実行を終了する。
【０１２１】
このようにして、本例では、経路特定装置１は、基本ノードＮ１０００を、疑似閉路ノードＣ８００として閉路隣接グラフに追加するとともに、基本リンクＬ１３００を疑似隣接リンクＡ４００として閉路隣接グラフに追加し、且つ、基本リンクＬ１４００を疑似隣接リンクＡ５００として閉路隣接グラフに追加する。これにより、経路特定装置１は、図１９に示したように、閉路隣接グラフを生成する。
【０１２２】
なお、経路特定装置１は、閉路隣接グラフを生成する方法として、他の方法を用いるように構成されていてもよい。
【０１２３】
＜＜２．経路の特定＞＞
経路特定装置１は、第１実施形態と同様に、図１９に示した閉路隣接グラフに基づいて経路を特定する。
【０１２４】
本例では、パラメータｘが、疑似隣接リンクである場合、経路特定装置１は、隣接リンクコストｗ（ｘ）として、疑似隣接リンクの実体である基本リンクｌに対する基本リンクコストｗ０（ｌ）を用いる。
【０１２５】
ここでは、第１の基本ノードが基本ノードＮ１００であり、第２の基本ノードが基本ノードＮ８００である場合を想定する。即ち、経路特定装置１が、第１の基本ノードＮ１００と、第２の基本ノードＮ８００と、を結ぶ、２つの異なる経路を特定する場合を想定する。
【０１２６】
経路特定装置１は、図１３のステップＳ２０１にて、閉路隣接グラフにおいて、最小コスト経路を特定する。最小コスト経路は、第１の基本ノードＮ１００を通る閉路を表す閉路ノードＣ１００と、第２の基本ノードＮ８００を通る閉路を表す閉路ノードＣ９００と、を結び、且つ、コストが最小となる経路である。
【０１２７】
最小コスト経路を特定する方法は、幅優先探索法、又は、修正ダイクストラ法（非特許文献２）等の負のリンクコストを許容する最短経路計算アルゴリズムである。
【０１２８】
本例では、経路特定装置１は、閉路隣接グラフにおける最小コスト経路として、経路Ｃ１００−Ｃ２００−Ｃ３００−Ｃ８００−Ｃ９００を特定する。
【０１２９】
経路特定装置１は、ステップＳ２０２にて、閉路隣接グラフにおける最小コスト経路が特定されたか否かを判定する。本例では、経路特定装置１は、「Ｙｅｓ」と判定し、ステップＳ２０３へ進む。なお、最小コスト経路が特定されなかった場合、経路特定装置１は、図１３に示した処理の実行を終了する。
【０１３０】
本例では、基本グラフは、任意の２つの基本ノードを連結可能なグラフである。従って、ステップＳ２０１において、必ず、最小コスト経路が特定される。このため、経路特定装置１は、ステップＳ２０２の処理を省略した処理を実行するように構成されていてもよい。
【０１３１】
次いで、経路特定装置１は、ステップＳ２０３にて、閉路隣接グラフにおける最小コスト経路において隣接する２つの閉路ノードが表す２つの閉路同士を併合することにより、第１の基本ノードＮ１００と第２の基本ノードＮ８００とを通る閉路である経路含有閉路を特定する。
【０１３２】
本例では、経路特定装置１は、２つの閉路が基本リンクを共有している場合、当該２つの閉路のそれぞれから、２つの閉路により共有されている基本リンク（共有リンク）を除いた部分を構成する、すべての基本リンクを連結した閉路を、当該２つの閉路同士を併合した閉路として用いる。
【０１３３】
更に、経路特定装置１は、２つの閉路の一方が、疑似閉路ノードとしての基本ノードである（即ち、２つの閉路が基本リンク及び基本ノードのいずれも共有していない）場合、当該２つの閉路の他方を構成する、すべての基本リンクと、疑似閉路ノードとしての基本ノードに接続されている基本リンクと、を連結した閉路（疑似閉路）を、当該２つの閉路同士を併合した閉路として用いる。
【０１３４】
具体的には、経路特定装置１は、２つの閉路のそれぞれを表す隣接行列の排他的論理和を算出することにより、当該２つの閉路同士を併合した閉路を表す閉路情報を取得する。
【０１３５】
本例では、経路特定装置１は、閉路Ｃ１００〜Ｃ３００，Ｃ８００，Ｃ９００を併合することにより、経路含有閉路Ｎ１００−Ｎ２００−Ｎ３００−Ｎ４００−Ｎ１０００−Ｎ１１００−Ｎ８００−Ｎ９００−Ｎ１１００−Ｎ１０００−Ｎ４００−Ｎ５００−Ｎ６００−Ｎ１００を特定する。
【０１３６】
なお、経路特定装置１は、他の方法を用いることにより、２つの閉路同士を併合した閉路を表す閉路情報を取得するように構成されていてもよい。
【０１３７】
次いで、経路特定装置１は、ステップＳ２０３にて特定された経路含有閉路において、第１の基本ノードＮ１００と第２の基本ノードＮ８００とを結ぶ最小コスト経路（第１の経路）を特定する（ステップＳ２０４）。このとき、経路特定装置１は、基本リンクコストｗ０（ｘ）に基づいて最小コスト経路を特定する。
【０１３８】
具体的には、経路特定装置１は、幅優先探索法、又は、ダイクストラ法等を用いることにより、最小コスト経路を特定する。ここでは、経路特定装置１は、最小コスト経路Ｎ１００−Ｎ２００−Ｎ３００−Ｎ４００−Ｎ１０００−Ｎ１１００−Ｎ８００を特定する。
【０１３９】
次いで、経路特定装置１は、ステップＳ２０３にて特定された経路含有閉路において、第１の経路と異なる経路であり、且つ、第１の基本ノードＮ１００と第２の基本ノードＮ８００とを結ぶ経路である冗長経路（第２の経路）を特定する（ステップＳ２０５）。ここでは、経路特定装置１は、冗長経路Ｎ１００−Ｎ６００−Ｎ５００−Ｎ４００−Ｎ１０００−Ｎ１１００−Ｎ９００−Ｎ８００を特定する。
【０１４０】
具体的には、経路特定装置１は、ステップＳ２０３にて特定された経路含有閉路を表す環状リストから、ステップＳ２０４にて特定された第１の経路に相当する部分を取り除くことにより、第２の経路を特定する。
【０１４１】
なお、経路特定装置１は、ステップＳ２０４にて特定された第１の経路における中間の基本ノード又は基本リンクのうちの、疑似閉路ノードＮ１０００、及び、疑似隣接リンクＬ１３００，Ｌ１４００以外の基本グラフ要素を使用不可とする条件を設けた状態において、深さ優先探索法、又は、ダイクストラ法等を用いることにより第２の経路を特定してもよい。
【０１４２】
このようにして、経路特定装置１は、閉路隣接グラフを用いることにより、第１の基本ノードＮ１００と第２の基本ノードＮ８００とを結ぶ、２つの異なる経路（第１の経路、及び、第２の経路）を特定する。
【０１４３】
以上、説明したように、本発明の第３実施形態に係る経路特定装置１によっても、第１実施形態に係る経路特定装置１と同様の作用及び効果が奏される。
【０１４４】
＜第４実施形態＞
次に、本発明の第４実施形態に係る経路特定装置について説明する。第４実施形態に係る経路特定装置は、上記第１実施形態に係る経路特定装置に対して、経路を特定する処理中に取得される閉路情報を保持するとともに、他の経路を特定する処理において、保持されている閉路情報を用いることにより、経路を特定する処理を高速化する点において相違している。従って、以下、かかる相違点を中心として説明する。
【０１４５】
第４実施形態に係るグラフ情報記憶部１１は、２つの閉路のそれぞれを表す情報と、当該２つの閉路同士を併合することにより生成された閉路を表す情報と、を対応付けた併合閉路情報を記憶する。
【０１４６】
本例では、併合閉路情報は、図２０及び図２１に示したように、併合の対象となる２つの閉路のそれぞれを識別するための閉路識別子と、併合により生成された閉路を識別するための閉路識別子と、を含むテーブルである。即ち、このテーブルにおける値は、当該値の行と対応付けられた閉路識別子により識別される閉路と、当該値の列と対応付けられた閉路識別子により識別される閉路と、を併合することにより生成された閉路を識別するための閉路識別子である。
なお、併合閉路情報は、情報処理装置により処理可能な他の形式により表されてもよい。
【０１４７】
（作動）
次に、上述した経路特定装置１の作動について説明する。
経路特定装置１は、図１３のステップＳ２０３の処理以外の処理を、第１実施形態と同様に実行する。
【０１４８】
経路特定装置１は、図１３のステップＳ２０３に進んだとき、併合の対象となる２つの閉路に係る併合閉路情報が記憶されているか否かを判定する。併合の対象となる２つの閉路に係る併合閉路情報が記憶されている場合、経路特定装置１は、当該併合閉路情報から、併合により生成された閉路を表す情報を取得する。
【０１４９】
一方、併合の対象となる２つの閉路に係る併合閉路情報が記憶されていない場合、経路特定装置１は、第１実施形態と同様に、２つの閉路同士を併合することにより閉路を生成する処理を実行する。更に、この場合、経路特定装置１は、併合の対象となる２つの閉路のそれぞれを識別するための閉路識別子と、併合により生成された閉路を識別するための閉路識別子と、を対応付けて記憶する。
【０１５０】
ここで、閉路Ｃ１００〜Ｃ３００を併合する例について説明する。いま、閉路Ｃ１００と閉路Ｃ２００とを併合することにより閉路Ｃ４００が生成されるとともに、閉路Ｃ２００と閉路Ｃ３００とを併合することにより閉路Ｃ５００が生成される場合を想定する。更に、閉路Ｃ１００〜Ｃ３００を併合することにより閉路Ｃ６００が生成される場合を想定する。
【０１５１】
この場合、経路特定装置１が、２つの閉路同士を併合する処理を実行する前の時点においては、経路特定装置１が記憶している併合閉路情報は、図２０に示した状態である。その後、経路特定装置１が、２つの閉路同士を併合する処理を実行することにより、最終的に、経路特定装置１が記憶している併合閉路情報は、図２１に示した状態となる。
【０１５２】
以上、説明したように、本発明の第４実施形態に係る経路特定装置１によっても、第１実施形態に係る経路特定装置１と同様の作用及び効果が奏される。
更に、本発明の第４実施形態に係る経路特定装置１によれば、経路を特定する処理を高速化することができる。
【０１５３】
＜第５実施形態＞
次に、本発明の第５実施形態に係る経路特定装置について説明する。第５実施形態に係る経路特定装置は、上記第１実施形態に係る経路特定装置に対して、特定すべき経路の端点（経路の端を構成する基本ノード、即ち、第１の基本ノード又は第２の基本ノード）が複数の閉路に含まれる場合における、経路を特定する処理を高速化する点において相違している。例えば、図４に示した基本グラフにおいて、基本ノードＮ２００は、２つの閉路Ｃ１００，Ｃ２００に含まれている。
以下、かかる相違点を中心として説明する。
【０１５４】
例えば、第１実施形態〜第４実施形態に係る経路特定装置１において、基本ノードＮ２００と基本ノードＮ４００とを結ぶ経路を特定する場合、閉路隣接グラフにて、閉路ノードＣ１００と閉路ノードＣ３００とを結ぶ経路と、閉路ノードＣ２００と閉路ノードＣ３００とを結ぶ経路と、の２つの経路を特定し、それぞれのコストを比較する必要が生じる。一方、本実施形態に係る経路特定装置１によれば、これらの計算を一元化することができるので、経路を特定する処理を高速化することができる。
【０１５５】
（機能）
第５実施形態に係るグラフ情報記憶部１１は、閉路隣接グラフ情報に代えて、閉路探索グラフ情報を記憶する。
【０１５６】
閉路探索グラフ情報は、閉路探索グラフを表す情報である。ここで、閉路探索グラフは、閉路隣接グラフに、包含ノードと、包含リンクと、を追加したグラフである。包含ノードは、閉路ノードが表す閉路が基本グラフにおいて通る（即ち、当該閉路に含まれる）基本ノードを表すノードである。包含リンクは、閉路ノードが表す閉路が基本グラフにおいて包含ノードを通ることを表し、且つ、当該閉路ノードと当該包含ノードとを結ぶリンクである。
【０１５７】
閉路探索グラフ情報は、閉路隣接グラフ情報に加えて、複数の包含ノードのそれぞれを識別するための包含ノード識別子と、包含ノードと閉路ノードとの任意の組のそれぞれに対して、当該包含ノードと当該閉路ノードとを結ぶ包含リンクが存在するか否かを表す情報と、を含む。
【０１５８】
（作動）
次に、上述した経路特定装置１の作動について説明する。
本例では、図１７に示した基本グラフにおいて経路を特定する際の経路特定装置１の作動について説明する。この基本グラフは、１１個の基本ノードＮ１００〜Ｎ１１００と、１４個の基本リンクＬ１００〜Ｌ１４００と、により構成される。
【０１５９】
＜＜１．閉路探索グラフの生成＞＞
先ず、経路特定装置１は、第１実施形態と同様に、閉路隣接グラフを生成する。その後、経路特定装置１は、基本グラフにおける各基本ノードに対して、当該基本ノードを包含ノードとして閉路隣接グラフに追加するとともに、当該基本ノードを基本グラフにおいて通る閉路を表す閉路ノードと当該包含ノードとを結ぶ包含リンクを閉路隣接グラフに追加することにより、閉路探索グラフを生成する。
【０１６０】
ここでは、経路特定装置１が、図４に示した基本グラフに基づいて閉路探索グラフを生成する場合を想定する。この場合、経路特定装置１により生成される閉路探索グラフは、図２２に示したようになる。図２２における破線は、包含リンクＥ１００〜Ｅ７１０を表す。
【０１６１】
＜＜２．経路の特定＞＞
経路特定装置１は、図２２に示した閉路探索グラフに基づいて経路を特定する。
本例では、パラメータｘが、閉路ノードｃ０と閉路ノードｃ１とを結ぶ隣接リンクである場合において、当該隣接リンクが第１の基本ノードと第２の基本ノードとのいずれも臨界ノードとして含まないとき、経路特定装置１は、探索リンクコストｗ（ｘ）を数式５に基づいて算出する。
【数５】
【０１６２】
一方、パラメータｘが、閉路ノードｃ０と閉路ノードｃ１とを結ぶ隣接リンクである場合において、当該隣接リンクが第１の基本ノード又は第２の基本ノードを臨界ノードとして含むとき、経路特定装置１は、探索リンクコストｗ（ｘ）を数式６に基づいて算出する。
【数６】
【０１６３】
また、パラメータｘが、疑似隣接リンクＬである場合、経路特定装置１は、探索リンクコストｗ（ｘ）を数式７に基づいて算出する。
【数７】
【０１６４】
また、パラメータｘが、包含リンクである場合において、当該包含リンクが第１の基本ノードから閉路ノードｃへのリンクであるとき、経路特定装置１は、探索リンクコストｗ（ｘ）を数式８に基づいて算出する。
【数８】
【０１６５】
また、パラメータｘが、包含リンクである場合において、当該包含リンクが閉路ノードｃから第２の基本ノードへのリンクであるとき、経路特定装置１は、探索リンクコストｗ（ｘ）を数式９に基づいて算出する。
【数９】
【０１６６】
また、パラメータｘが、包含リンクである場合において、当該包含リンクが、第１の基本ノード及び第２の基本ノード以外の基本ノード（包含ノード）と、閉路ノードと、を結ぶとき、経路特定装置１は、探索リンクコストｗ（ｘ）を数式１０に基づいて算出する。
【数１０】
【０１６７】
ここでは、第１の基本ノードが基本ノードＮ２００であり、第２の基本ノードが基本ノードＮ４００である場合を想定する。即ち、経路特定装置１が、第１の基本ノードＮ２００と、第２の基本ノードＮ４００と、を結び、且つ、基本リンクを共有しない、２つの異なる経路を特定する場合を想定する。
【０１６８】
経路特定装置１は、図１３のステップＳ２０１の処理に代えて、閉路探索グラフにおいて、最小コスト経路を特定する処理を実行する。ここで、最小コスト経路は、閉路探索グラフにおいて、第１の基本ノードＮ２００と、第２の基本ノードＮ４００と、を結び、且つ、コストが最小となる経路である。
【０１６９】
ところで、探索リンクコストｗ（ｘ）が∞であるリンクが、最小コスト経路に含まれることはない。従って、経路特定装置１は、探索リンクコストｗ（ｘ）が∞であるリンクを、予め閉路探索グラフから除去した、図２３に示したグラフに基づいて、最小コスト経路を特定するように構成されることが好適である。
【０１７０】
なお、閉路探索グラフにおいて最小コスト経路を特定することは、２つの経路（経路Ｎ２００−Ｃ１００−Ｃ２００−Ｃ３００−Ｎ４００、及び、経路Ｎ２００−Ｃ２００−Ｃ３００−Ｎ４００）のうちの、コストが小さい方の経路を特定することに対応している。
【０１７１】
更に、経路特定装置１は、特定された最小コスト経路から、第１の基本ノードＮ２００、及び、第２の基本ノードＮ４００を除去した経路を特定し、当該経路に基づいて、第１実施形態と同様に、ステップＳ２０２〜ステップＳ２０５の処理を実行する。これにより、経路特定装置１は、閉路探索グラフを用いることにより、第１の基本ノードＮ２００と第２の基本ノードＮ４００とを結び、且つ、基本リンクを共有しない、２つの異なる経路（第１の経路、及び、第２の経路）を特定する。
【０１７２】
以上、説明したように、本発明の第５実施形態に係る経路特定装置１によっても、第１実施形態に係る経路特定装置１と同様の作用及び効果が奏される。
更に、本発明の第５実施形態に係る経路特定装置１によれば、特定すべき経路の端点が複数の閉路に含まれる場合において、経路を特定する処理を高速化することができる。
【０１７３】
＜第６実施形態＞
次に、本発明の第６実施形態に係る経路特定装置について説明する。第６実施形態に係る経路特定装置は、上記第１実施形態に係る経路特定装置に対して、基本グラフに基づいて経路を特定できなかった場合にのみ、閉路隣接グラフを用いることにより経路を特定する点において相違している。従って、以下、かかる相違点を中心として説明する。
【０１７４】
第６実施形態に係る経路特定装置１は、図２４にフローチャートにより示した処理を実行する。
【０１７５】
具体的には、経路特定装置１は、ステップＳ４０１にて、基本グラフに基づいて（即ち、閉路隣接グラフを用いることなく）、経路を特定する。本例では、経路特定装置１は、ダイクストラ法を繰り返し用いることにより、２つの基本ノードを結び、且つ、基本リンクを共有しない、２つの異なる経路を特定する。即ち、経路特定装置１は、第１の経路を特定し、その後、第１の経路が通る基本リンクを基本グラフから除去したグラフに基づいて、第２の経路を特定する。
【０１７６】
ステップＳ４０１の処理により特定される第１の経路は、基本グラフにおいてコストが最小となる経路である。一方、このように特定された、第１の経路及び第２の経路は、第１の経路のコストと第２の経路のコストとの和が最小であるとは限らない。
なお、経路特定装置１は、他の方法を用いることにより、２つの異なる経路を特定するように構成されていてもよい。
【０１７７】
次いで、経路特定装置１は、ステップＳ４０２にて、経路が特定されたか否かを判定する。ステップＳ４０１にて経路が特定されなかった場合、経路特定装置１は、「Ｎｏ」と判定してステップＳ４０３へ進む。
【０１７８】
なお、経路特定装置１は、経路が特定された場合であっても、特定された経路が、予め設定された条件を満たさなかった場合、「Ｎｏ」と判定するように構成されていてもよい。例えば、この条件は、第２の経路のコストが、予め設定された基準値よりも大きいという条件である。
【０１７９】
そして、経路特定装置１は、ステップＳ４０３にて、第１実施形態と同様に、閉路隣接グラフを生成するとともに、生成された閉路隣接グラフに基づいて、２つの異なる経路を特定する。
なお、ステップＳ４０１にて経路が特定された場合、経路特定装置１は、ステップＳ４０２にて「Ｙｅｓ」と判定して、図２４に示した処理の実行を終了する。
【０１８０】
以上、説明したように、本発明の第６実施形態に係る経路特定装置１によっても、第１実施形態に係る経路特定装置１と同様の作用及び効果が奏される。
更に、本発明の第６実施形態に係る経路特定装置１によれば、第１の経路のコストと第２の経路のコストとの和が最小となる、２つの経路以外の経路を特定することもできる。
【０１８１】
なお、第６実施形態に係る経路特定装置１は、基本グラフに基づいて経路を特定できなかった場合に、閉路隣接グラフに基づいて経路を特定するように構成されていたが、閉路探索グラフに基づいて経路を特定するように構成されていてもよい。
【０１８２】
第１実施形態〜第６実施形態においては、経路特定装置１は、閉路隣接グラフ又は閉路探索グラフの生成する処理（第１の処理）と経路の特定する処理（第２の処理）とを続けて実行するように構成されていた。ところで、経路特定装置１は、第１の処理の実行結果を保持し、その後、保持されている実行結果を用いることにより、複数回、第２の処理を実行するように構成されていてもよい。
【０１８３】
また、閉路隣接グラフ又は閉路探索グラフを生成するためのプログラムと、経路を特定するためのプログラムと、は、１つのプログラムを構成していてもよいし、互いに独立した２つのプログラムであってもよい。なお、経路特定装置１は、互いに独立した２つのプログラムのそれぞれに対して、中央処理装置、一次記憶装置、及び、二次記憶装置等のプログラムを実行するために必要な計算資源を、物理的又は論理的に分離して割り当てるように構成されていてもよい。
【０１８４】
＜第７実施形態＞
次に、本発明の第７実施形態に係る経路特定装置について図２５を参照しながら説明する。
第７実施形態に係る経路特定装置１０００は、
基本ノードと、２つの基本ノードを結ぶ基本リンクと、により構成される基本グラフにおいて、第１の基本ノードと第２の基本ノードとを結ぶ経路を特定する装置である。
【０１８５】
更に、この経路特定装置１０００は、
上記第１の基本ノードを通る第１の閉路と、上記第２の基本ノードを通る第２の閉路と、を含む複数の閉路を特定する閉路特定部（閉路特定手段）１００１と、
上記特定された複数の閉路のうちの、基本ノード又は基本リンクである基本グラフ要素の少なくとも１つを共有する閉路同士を併合することにより、上記第１の基本ノードと上記第２の基本ノードとを通る閉路である経路含有閉路を特定する経路含有閉路特定部（経路含有閉路特定手段）１００２と、
上記特定された経路含有閉路において、上記第１の基本ノードと上記第２の基本ノードとを結び、且つ、基本リンクを共有しない、２つの異なる経路を特定する経路特定部（経路特定手段）１００３と、
を備える。
【０１８６】
これによれば、２つの基本ノードを結び、且つ、基本リンクを共有しない、２つの異なる経路を確実に特定することができる。更に、２つの基本ノードを結び、且つ、基本リンクを共有しない、２つの異なる経路を特定する際の処理負荷を低減することができる。
【０１８７】
以上、上記実施形態を参照して本願発明を説明したが、本願発明は、上述した実施形態に限定されるものではない。本願発明の構成及び詳細に、本願発明の範囲内において当業者が理解し得る様々な変更をすることができる。
【０１８８】
なお、上記各実施形態において経路特定装置の各機能は、ＣＰＵがプログラム（ソフトウェア）を実行することにより実現されていたが、回路等のハードウェアにより実現されていてもよい。
【０１８９】
また、上記各実施形態においてプログラムは、記憶装置に記憶されていたが、コンピュータが読み取り可能な記録媒体に記憶されていてもよい。例えば、記録媒体は、フレキシブルディスク、光ディスク、光磁気ディスク、及び、半導体メモリ等の可搬性を有する媒体である。
【０１９０】
また、上記実施形態の他の変形例として、上述した実施形態及び変形例の任意の組み合わせが採用されてもよい。
【０１９１】
＜付記＞
上記実施形態の一部又は全部は、以下の付記のように記載され得るが、以下には限られない。
【０１９２】
（付記１）
基本ノードと、２つの基本ノードを結ぶ基本リンクと、により構成される基本グラフにおいて、第１の基本ノードと第２の基本ノードとを結ぶ経路を特定する経路特定装置であって、
前記第１の基本ノードを通る第１の閉路と、前記第２の基本ノードを通る第２の閉路と、を含む複数の閉路を特定する閉路特定手段と、
前記特定された複数の閉路のうちの、基本ノード又は基本リンクである基本グラフ要素の少なくとも１つを共有する閉路同士を併合することにより、前記第１の基本ノードと前記第２の基本ノードとを通る閉路である経路含有閉路を特定する経路含有閉路特定手段と、
前記特定された経路含有閉路において、前記第１の基本ノードと前記第２の基本ノードとを結び、且つ、基本リンク、又は、当該第１の基本ノード及び当該第２の基本ノード以外の基本ノードを共有しない、２つの異なる経路を特定する経路特定手段と、
を備える経路特定装置。
【０１９３】
これによれば、２つの基本ノードを結び、且つ、基本リンク、又は、経路途中の（即ち、第１の基本ノード及び第２の基本ノード以外の）基本ノードを共有しない、２つの異なる経路を確実に特定することができる。更に、２つの基本ノードを結び、且つ、基本リンクを共有しない、２つの異なる経路を特定する際の処理負荷を低減することができる。
【０１９４】
（付記２）
付記１に記載の経路特定装置であって、
前記経路含有閉路特定手段は、２つの閉路が少なくとも１つの基本リンクを共有している場合、当該２つの閉路の一方から、当該共有されている基本リンクである共有リンクを除いた部分を構成するすべての基本リンクと、当該２つの閉路の他方から、当該共有リンクを除いた部分を構成するすべての基本リンクと、を連結した閉路を、当該２つの閉路同士を併合した閉路として用いるように構成された経路特定装置。
【０１９５】
（付記３）
付記１又は付記２に記載の経路特定装置であって、
前記経路含有閉路特定手段は、２つの閉路が基本リンクを共有することなく基本ノードのみを共有している場合、当該２つの閉路の一方を構成するすべての基本リンクと、当該２つの閉路の他方を構成するすべての基本リンクと、を連結した閉路を、当該２つの閉路同士を併合した閉路として用いるように構成された経路特定装置。
【０１９６】
（付記４）
付記１乃至付記３のいずれかに記載の経路特定装置であって、
前記経路含有閉路特定手段は、前記特定された複数の閉路のそれぞれを閉路ノードにより表すとともに、２つの閉路によって前記基本グラフにおける基本グラフ要素が共有されていることを、当該２つの閉路のそれぞれを表す閉路ノードを結ぶ隣接リンクにより表す閉路隣接グラフを生成し、当該生成された閉路隣接グラフに基づいて前記基本グラフにおける前記経路含有閉路を特定するように構成された経路特定装置。
【０１９７】
（付記５）
付記４に記載の経路特定装置であって、
前記経路含有閉路特定手段は、前記生成された閉路隣接グラフに、前記閉路ノードが表す閉路が前記基本グラフにおいて通る基本ノードのそれぞれを表す包含ノードと、閉路ノードが表す閉路が前記基本グラフにおいて包含ノードを通ることを表し且つ当該閉路ノードと当該包含ノードとを結ぶ包含リンクと、を追加した、閉路探索グラフを生成し、当該生成された閉路探索グラフに基づいて前記基本グラフにおける前記経路含有閉路を特定するように構成された経路特定装置。
【０１９８】
（付記６）
付記１乃至付記５のいずれかに記載の経路特定装置であって、
前記経路含有閉路特定手段は、前記基本グラフにおける前記基本リンクのそれぞれに対して予め設定された基本リンクコストの総和を最小とするように、前記基本グラフにおける前記経路含有閉路を特定するように構成された経路特定装置。
【０１９９】
これによれば、基本リンクコストの総和を最小とするように、２つの基本ノードを結び、且つ、基本リンク、又は、経路途中の基本ノードを共有しない、２つの異なる経路を特定することができる。
【０２００】
（付記７）
基本ノードと、２つの基本ノードを結ぶ基本リンクと、により構成される基本グラフにおいて、第１の基本ノードと第２の基本ノードとを結ぶ経路を特定する経路特定方法であって、
前記第１の基本ノードを通る第１の閉路と、前記第２の基本ノードを通る第２の閉路と、を含む複数の閉路を特定し、
前記特定された複数の閉路のうちの、基本ノード又は基本リンクである基本グラフ要素の少なくとも１つを共有する閉路同士を併合することにより、前記第１の基本ノードと前記第２の基本ノードとを通る閉路である経路含有閉路を特定し、
前記特定された経路含有閉路において、前記第１の基本ノードと前記第２の基本ノードとを結び、且つ、基本リンク、又は、当該第１の基本ノード及び当該第２の基本ノード以外の基本ノードを共有しない、２つの異なる経路を特定する、経路特定方法。
【０２０１】
（付記８）
付記７に記載の経路特定方法であって、
２つの閉路が少なくとも１つの基本リンクを共有している場合、当該２つの閉路の一方から、当該共有されている基本リンクである共有リンクを除いた部分を構成するすべての基本リンクと、当該２つの閉路の他方から、当該共有リンクを除いた部分を構成するすべての基本リンクと、を連結した閉路を、当該２つの閉路同士を併合した閉路として用いるように構成された経路特定方法。
【０２０２】
（付記９）
付記７又は付記８に記載の経路特定方法であって、
２つの閉路が基本リンクを共有することなく基本ノードのみを共有している場合、当該２つの閉路の一方を構成するすべての基本リンクと、当該２つの閉路の他方を構成するすべての基本リンクと、を連結した閉路を、当該２つの閉路同士を併合した閉路として用いるように構成された経路特定方法。
【０２０３】
（付記１０）
情報処理装置に、
基本ノードと、２つの基本ノードを結ぶ基本リンクと、により構成される基本グラフにおいて、第１の基本ノードと第２の基本ノードとを結ぶ経路を特定する処理を実行させるための経路特定プログラムであって、
前記処理は、
前記第１の基本ノードを通る第１の閉路と、前記第２の基本ノードを通る第２の閉路と、を含む複数の閉路を特定し、
前記特定された複数の閉路のうちの、基本ノード又は基本リンクである基本グラフ要素の少なくとも１つを共有する閉路同士を併合することにより、前記第１の基本ノードと前記第２の基本ノードとを通る閉路である経路含有閉路を特定し、
前記特定された経路含有閉路において、前記第１の基本ノードと前記第２の基本ノードとを結び、且つ、基本リンク、又は、当該第１の基本ノード及び当該第２の基本ノード以外の基本ノードを共有しない、２つの異なる経路を特定するように構成された経路特定プログラム。
【０２０４】
（付記１１）
付記１０に記載の経路特定プログラムであって、
前記処理は、２つの閉路が少なくとも１つの基本リンクを共有している場合、当該２つの閉路の一方から、当該共有されている基本リンクである共有リンクを除いた部分を構成するすべての基本リンクと、当該２つの閉路の他方から、当該共有リンクを除いた部分を構成するすべての基本リンクと、を連結した閉路を、当該２つの閉路同士を併合した閉路として用いるように構成された経路特定プログラム。
【０２０５】
（付記１２）
付記１０又は付記１１に記載の経路特定プログラムであって、
前記処理は、２つの閉路が基本リンクを共有することなく基本ノードのみを共有している場合、当該２つの閉路の一方を構成するすべての基本リンクと、当該２つの閉路の他方を構成するすべての基本リンクと、を連結した閉路を、当該２つの閉路同士を併合した閉路として用いるように構成された経路特定プログラム。
【産業上の利用可能性】
【０２０６】
本発明は、第１のノードと第２のノードとを結ぶ経路を特定する経路特定装置等に適用可能である。
【符号の説明】
【０２０７】
１ 経路特定装置
１１ グラフ情報記憶部
１２ 閉路特定部
１３ 経路含有閉路特定部
１４ 経路特定部
１０００ 経路特定装置
１００１ 閉路特定部
１００２ 経路含有閉路特定部
１００３ 経路特定部
【特許請求の範囲】
【請求項１】
基本ノードと、２つの基本ノードを結ぶ基本リンクと、により構成される基本グラフにおいて、第１の基本ノードと第２の基本ノードとを結ぶ経路を特定する経路特定装置であって、
前記第１の基本ノードを通る第１の閉路と、前記第２の基本ノードを通る第２の閉路と、を含む複数の閉路を特定する閉路特定手段と、
前記特定された複数の閉路のうちの、基本ノード又は基本リンクである基本グラフ要素の少なくとも１つを共有する閉路同士を併合することにより、前記第１の基本ノードと前記第２の基本ノードとを通る閉路である経路含有閉路を特定する経路含有閉路特定手段と、
前記特定された経路含有閉路において、前記第１の基本ノードと前記第２の基本ノードとを結び、且つ、基本リンク、又は、当該第１の基本ノード及び当該第２の基本ノード以外の基本ノードを共有しない、２つの異なる経路を特定する経路特定手段と、
を備える経路特定装置。
【請求項２】
請求項１に記載の経路特定装置であって、
前記経路含有閉路特定手段は、２つの閉路が少なくとも１つの基本リンクを共有している場合、当該２つの閉路の一方から、当該共有されている基本リンクである共有リンクを除いた部分を構成するすべての基本リンクと、当該２つの閉路の他方から、当該共有リンクを除いた部分を構成するすべての基本リンクと、を連結した閉路を、当該２つの閉路同士を併合した閉路として用いるように構成された経路特定装置。
【請求項３】
請求項１又は請求項２に記載の経路特定装置であって、
前記経路含有閉路特定手段は、２つの閉路が基本リンクを共有することなく基本ノードのみを共有している場合、当該２つの閉路の一方を構成するすべての基本リンクと、当該２つの閉路の他方を構成するすべての基本リンクと、を連結した閉路を、当該２つの閉路同士を併合した閉路として用いるように構成された経路特定装置。
【請求項４】
請求項１乃至請求項３のいずれかに記載の経路特定装置であって、
前記経路含有閉路特定手段は、前記特定された複数の閉路のそれぞれを閉路ノードにより表すとともに、２つの閉路によって前記基本グラフにおける基本グラフ要素が共有されていることを、当該２つの閉路のそれぞれを表す閉路ノードを結ぶ隣接リンクにより表す閉路隣接グラフを生成し、当該生成された閉路隣接グラフに基づいて前記基本グラフにおける前記経路含有閉路を特定するように構成された経路特定装置。
【請求項５】
請求項４に記載の経路特定装置であって、
前記経路含有閉路特定手段は、前記生成された閉路隣接グラフに、前記閉路ノードが表す閉路が前記基本グラフにおいて通る基本ノードのそれぞれを表す包含ノードと、閉路ノードが表す閉路が前記基本グラフにおいて包含ノードを通ることを表し且つ当該閉路ノードと当該包含ノードとを結ぶ包含リンクと、を追加した、閉路探索グラフを生成し、当該生成された閉路探索グラフに基づいて前記基本グラフにおける前記経路含有閉路を特定するように構成された経路特定装置。
【請求項６】
請求項１乃至請求項５のいずれかに記載の経路特定装置であって、
前記経路含有閉路特定手段は、前記基本グラフにおける前記基本リンクのそれぞれに対して予め設定された基本リンクコストの総和を最小とするように、前記基本グラフにおける前記経路含有閉路を特定するように構成された経路特定装置。
【請求項７】
基本ノードと、２つの基本ノードを結ぶ基本リンクと、により構成される基本グラフにおいて、第１の基本ノードと第２の基本ノードとを結ぶ経路を特定する経路特定方法であって、
前記第１の基本ノードを通る第１の閉路と、前記第２の基本ノードを通る第２の閉路と、を含む複数の閉路を特定し、
前記特定された複数の閉路のうちの、基本ノード又は基本リンクである基本グラフ要素の少なくとも１つを共有する閉路同士を併合することにより、前記第１の基本ノードと前記第２の基本ノードとを通る閉路である経路含有閉路を特定し、
前記特定された経路含有閉路において、前記第１の基本ノードと前記第２の基本ノードとを結び、且つ、基本リンク、又は、当該第１の基本ノード及び当該第２の基本ノード以外の基本ノードを共有しない、２つの異なる経路を特定する、経路特定方法。
【請求項８】
請求項７に記載の経路特定方法であって、
２つの閉路が少なくとも１つの基本リンクを共有している場合、当該２つの閉路の一方から、当該共有されている基本リンクである共有リンクを除いた部分を構成するすべての基本リンクと、当該２つの閉路の他方から、当該共有リンクを除いた部分を構成するすべての基本リンクと、を連結した閉路を、当該２つの閉路同士を併合した閉路として用いるように構成された経路特定方法。
【請求項９】
請求項７又は請求項８に記載の経路特定方法であって、
２つの閉路が基本リンクを共有することなく基本ノードのみを共有している場合、当該２つの閉路の一方を構成するすべての基本リンクと、当該２つの閉路の他方を構成するすべての基本リンクと、を連結した閉路を、当該２つの閉路同士を併合した閉路として用いるように構成された経路特定方法。
【請求項１０】
情報処理装置に、
基本ノードと、２つの基本ノードを結ぶ基本リンクと、により構成される基本グラフにおいて、第１の基本ノードと第２の基本ノードとを結ぶ経路を特定する処理を実行させるための経路特定プログラムであって、
前記処理は、
前記第１の基本ノードを通る第１の閉路と、前記第２の基本ノードを通る第２の閉路と、を含む複数の閉路を特定し、
前記特定された複数の閉路のうちの、基本ノード又は基本リンクである基本グラフ要素の少なくとも１つを共有する閉路同士を併合することにより、前記第１の基本ノードと前記第２の基本ノードとを通る閉路である経路含有閉路を特定し、
前記特定された経路含有閉路において、前記第１の基本ノードと前記第２の基本ノードとを結び、且つ、基本リンク、又は、当該第１の基本ノード及び当該第２の基本ノード以外の基本ノードを共有しない、２つの異なる経路を特定するように構成された経路特定プログラム。
【請求項１】
基本ノードと、２つの基本ノードを結ぶ基本リンクと、により構成される基本グラフにおいて、第１の基本ノードと第２の基本ノードとを結ぶ経路を特定する経路特定装置であって、
前記第１の基本ノードを通る第１の閉路と、前記第２の基本ノードを通る第２の閉路と、を含む複数の閉路を特定する閉路特定手段と、
前記特定された複数の閉路のうちの、基本ノード又は基本リンクである基本グラフ要素の少なくとも１つを共有する閉路同士を併合することにより、前記第１の基本ノードと前記第２の基本ノードとを通る閉路である経路含有閉路を特定する経路含有閉路特定手段と、
前記特定された経路含有閉路において、前記第１の基本ノードと前記第２の基本ノードとを結び、且つ、基本リンク、又は、当該第１の基本ノード及び当該第２の基本ノード以外の基本ノードを共有しない、２つの異なる経路を特定する経路特定手段と、
を備える経路特定装置。
【請求項２】
請求項１に記載の経路特定装置であって、
前記経路含有閉路特定手段は、２つの閉路が少なくとも１つの基本リンクを共有している場合、当該２つの閉路の一方から、当該共有されている基本リンクである共有リンクを除いた部分を構成するすべての基本リンクと、当該２つの閉路の他方から、当該共有リンクを除いた部分を構成するすべての基本リンクと、を連結した閉路を、当該２つの閉路同士を併合した閉路として用いるように構成された経路特定装置。
【請求項３】
請求項１又は請求項２に記載の経路特定装置であって、
前記経路含有閉路特定手段は、２つの閉路が基本リンクを共有することなく基本ノードのみを共有している場合、当該２つの閉路の一方を構成するすべての基本リンクと、当該２つの閉路の他方を構成するすべての基本リンクと、を連結した閉路を、当該２つの閉路同士を併合した閉路として用いるように構成された経路特定装置。
【請求項４】
請求項１乃至請求項３のいずれかに記載の経路特定装置であって、
前記経路含有閉路特定手段は、前記特定された複数の閉路のそれぞれを閉路ノードにより表すとともに、２つの閉路によって前記基本グラフにおける基本グラフ要素が共有されていることを、当該２つの閉路のそれぞれを表す閉路ノードを結ぶ隣接リンクにより表す閉路隣接グラフを生成し、当該生成された閉路隣接グラフに基づいて前記基本グラフにおける前記経路含有閉路を特定するように構成された経路特定装置。
【請求項５】
請求項４に記載の経路特定装置であって、
前記経路含有閉路特定手段は、前記生成された閉路隣接グラフに、前記閉路ノードが表す閉路が前記基本グラフにおいて通る基本ノードのそれぞれを表す包含ノードと、閉路ノードが表す閉路が前記基本グラフにおいて包含ノードを通ることを表し且つ当該閉路ノードと当該包含ノードとを結ぶ包含リンクと、を追加した、閉路探索グラフを生成し、当該生成された閉路探索グラフに基づいて前記基本グラフにおける前記経路含有閉路を特定するように構成された経路特定装置。
【請求項６】
請求項１乃至請求項５のいずれかに記載の経路特定装置であって、
前記経路含有閉路特定手段は、前記基本グラフにおける前記基本リンクのそれぞれに対して予め設定された基本リンクコストの総和を最小とするように、前記基本グラフにおける前記経路含有閉路を特定するように構成された経路特定装置。
【請求項７】
基本ノードと、２つの基本ノードを結ぶ基本リンクと、により構成される基本グラフにおいて、第１の基本ノードと第２の基本ノードとを結ぶ経路を特定する経路特定方法であって、
前記第１の基本ノードを通る第１の閉路と、前記第２の基本ノードを通る第２の閉路と、を含む複数の閉路を特定し、
前記特定された複数の閉路のうちの、基本ノード又は基本リンクである基本グラフ要素の少なくとも１つを共有する閉路同士を併合することにより、前記第１の基本ノードと前記第２の基本ノードとを通る閉路である経路含有閉路を特定し、
前記特定された経路含有閉路において、前記第１の基本ノードと前記第２の基本ノードとを結び、且つ、基本リンク、又は、当該第１の基本ノード及び当該第２の基本ノード以外の基本ノードを共有しない、２つの異なる経路を特定する、経路特定方法。
【請求項８】
請求項７に記載の経路特定方法であって、
２つの閉路が少なくとも１つの基本リンクを共有している場合、当該２つの閉路の一方から、当該共有されている基本リンクである共有リンクを除いた部分を構成するすべての基本リンクと、当該２つの閉路の他方から、当該共有リンクを除いた部分を構成するすべての基本リンクと、を連結した閉路を、当該２つの閉路同士を併合した閉路として用いるように構成された経路特定方法。
【請求項９】
請求項７又は請求項８に記載の経路特定方法であって、
２つの閉路が基本リンクを共有することなく基本ノードのみを共有している場合、当該２つの閉路の一方を構成するすべての基本リンクと、当該２つの閉路の他方を構成するすべての基本リンクと、を連結した閉路を、当該２つの閉路同士を併合した閉路として用いるように構成された経路特定方法。
【請求項１０】
情報処理装置に、
基本ノードと、２つの基本ノードを結ぶ基本リンクと、により構成される基本グラフにおいて、第１の基本ノードと第２の基本ノードとを結ぶ経路を特定する処理を実行させるための経路特定プログラムであって、
前記処理は、
前記第１の基本ノードを通る第１の閉路と、前記第２の基本ノードを通る第２の閉路と、を含む複数の閉路を特定し、
前記特定された複数の閉路のうちの、基本ノード又は基本リンクである基本グラフ要素の少なくとも１つを共有する閉路同士を併合することにより、前記第１の基本ノードと前記第２の基本ノードとを通る閉路である経路含有閉路を特定し、
前記特定された経路含有閉路において、前記第１の基本ノードと前記第２の基本ノードとを結び、且つ、基本リンク、又は、当該第１の基本ノード及び当該第２の基本ノード以外の基本ノードを共有しない、２つの異なる経路を特定するように構成された経路特定プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【公開番号】特開２０１３−６２７３５（Ｐ２０１３−６２７３５Ａ）
【公開日】平成２５年４月４日（２０１３．４．４）
【国際特許分類】
【出願番号】特願２０１１−２００７８８（Ｐ２０１１−２００７８８）
【出願日】平成２３年９月１４日（２０１１．９．１４）
【国等の委託研究の成果に係る記載事項】（出願人による申告）平成２２年度 独立行政法人 情報通信研究機構「λユーティリティ技術の研究開発」、産業技術力強化法第１９条の適用を受ける特許出願
【出願人】（０００００４２３７）日本電気株式会社 (19,353)
【Ｆターム（参考）】
【公開日】平成２５年４月４日（２０１３．４．４）
【国際特許分類】
【出願日】平成２３年９月１４日（２０１１．９．１４）
【国等の委託研究の成果に係る記載事項】（出願人による申告）平成２２年度 独立行政法人 情報通信研究機構「λユーティリティ技術の研究開発」、産業技術力強化法第１９条の適用を受ける特許出願
【出願人】（０００００４２３７）日本電気株式会社 (19,353)
【Ｆターム（参考）】
[ Back to top ]