JPH0773202A - 有向グラフ再構成方法 - Google Patents

Abstract

(57)【要約】 【目的】 有向グラフによりネットワ−クのデ−タ構造
を表現してデータ探索を行なう場合に、データ探索速度
を高速化できる構造の有向グラフに再構成する有向グラ
フ再構成方法を提供する。 【構成】 有向グラフの開始節からの深さごとに所定の
ラベル分割数を定め、該ラベル分割数で、節から発する
辺集合の各辺のラベルを構成しているビット列を分割
し、分割した各々のビット列をラベルとする辺を直列に
接続したサブ有向グラフ群に変換し、変換したサブ有向
グラフ群に対して更に同じ節から発する同じラベルを持
つ辺を１つにまとめ、サブ有向グラフ群からなる有向グ
ラフに再構成する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、有向グラフ再構成方法
に関し、有向グラフにおける辺のラベルを分割したサブ
有向グラフに基づいて有向グラフを再構成し、有向グラ
フにおける辺のラベルの探索が高速に行なわれるように
した有向グラフの再構成方法に関するものである。

【０００２】

【従来の技術】有向グラフは、これを要素として、木構
造、ネットワ−ク構造をそのままの形状で表現できるた
め、最近のデ−タ処理システムにおいては、効率よくデ
−タを表現するデ−タ構造として多く利用されるように
なっている。例えば、デ−タベ−スを構成する場合に
は、木構造のデ−タ構造でデータベーススキーマを作成
して階層的な検索処理に利用される。また、このように
構成されたデータベースにおいては、ネットワ−ク構造
の表現によって関係する関連デ−タまでもの検索が可能
になる。

【０００３】ところで、有向グラフで表現されたデータ
構造のデータ群に対して、検索を行う場合、従来から一
般に用いられている有向グラフの辺のラベルの探索方法
は、有向グラフの各節から発する辺集合に対し、各辺上
のラベルの値を見て、条件に合致していれば、その辺を
辿ってその辺が指す節に移動し、条件に合致していなけ
れば、辺集合の中の次の辺を対象として条件に合致して
いるかを調べる探索方法がある。このような探索方法
で、データベースのデータ検索が行なわれる。

【０００４】このような探索方法によれば、例えば、こ
こでの検索対象のデータが、１つの節から発する辺集合
のｉ番目の要素が条件に合致する辺のラベルのデータで
あるとすると、その節の辺の探索に関しては、条件に合
致するかどうかの比較をｉ番目までｉ回繰り返すことに
なる。したがって、各々の節の辺集合について、多くの
比較処理を繰り返し行なわなければならず、有向グラフ
で表現されたデータ構造のデータベースでは、データ検
索の比較回数が膨大なものとなる。

【０００５】

【発明が解決しようとする課題】上述のような有向グラ
フの探索方法においては、各節での辺のラベルの探索に
より次に辿る辺を見つけて、次の節への移動を行うの
で、探索の対象となる有向グラフの各々の節の辺集合の
要素数をｎとすると、有向グラフの検索では、明らかに
１つの節に対して平均（ｎ＋１）／２回の辺のラベル比
較が必要となる。

【０００６】このため、大規模な有向グラフでネットワ
−クが構成されたデータ構造の有向グラフの探索処理を
行う場合は、その多くの辺の数に応じて、比較すべき辺
のラベル数も多くなる。したがって、大規模な有向グラ
フのネットワ−クを探索する場合、多くの辺数に応じ
て、比較すべき辺数も多くなり、このような有向グラフ
で表現されているデータ構造のデータから探索を行う場
合には、多くの辺にかかる比較処理のために、そのデ−
タ処理速度に関して多大な負荷を強いられることにな
る。

【０００７】本発明は上記のような課題を解決するため
になされたものであり、本発明の目的は、有向グラフに
よりネットワ−クのデ−タ構造を表現してデータ探索を
行なう場合に、データ探索速度を高速化できる構造の有
向グラフに再構成する有向グラフ再構成方法を提供する
ことにある。

【０００８】

【課題を解決するための手段】上述のような目的を達成
するため、本発明の第１の特徴とする有向グラフ再構成
方法は、有向グラフの開始節からの深さごとに所定のラ
ベル分割数を定め、該ラベル分割数で、節から発する辺
集合の各辺のラベルを構成しているビット列を分割し、
分割した各々のビット列をラベルとする辺を直列に接続
したサブ有向グラフ群に変換し、変換したサブ有向グラ
フ群に対して更に同じ節から発する同じラベルを持つ辺
を１つにまとめ、サブ有向グラフ群からなる有向グラフ
に再構成することを特徴とする。

【０００９】また、本発明の第２の特徴とする有向グラ
フ再構成方法は、所定のラベル分割数で節から発する辺
集合の各辺のラベルを構成するビット列を分割し、分割
した各々のビット列をラベルとする辺を直列に接続した
サブ有向グラフ群に変換し、変換したサブ有向グラフ群
に対して更に同じ節から発する同じラベルを持つ辺を１
つにまとめて、サブ有向グラフ群を再構成し、再構成し
たサブ有向グラフ群について、辺集合における比較回数
の平均値が元の変換前の有向グラフより少ないか否かを
判定し、辺集合における比較回数の平均値が変換前の有
向グラフより少ない場合に、再構成したサブ有向グラフ
群を残し、平均値が元の有向グラフの辺集合における比
較回数の平均値より多いか等しい場合には当該サブ有向
グラフ群を破棄し、元の有向グラフを残す変換を行い、
有向グラフを再構成することを特徴とする。

【００１０】

【作用】本発明の第１の特徴とする有向グラフ再構成方
法においては、まず、有向グラフの開始節からの深さご
とに所定のラベル分割数を定める。再構成の対象とする
有向グラフに対して、このラベル分割数により、節から
発する辺集合の各辺のラベルを構成しているビット列を
分割する。そして、分割した各々のビット列をラベルと
する辺を直列に接続したサブ有向グラフ群に変換する。
ここで、変換したサブ有向グラフ群に対して、更に同じ
節から発する同じラベルを持つ辺を１つにまとめ、サブ
有向グラフ群からなる有向グラフに再構成する。

【００１１】これにより、再構成された有向グラフは、
その要素のサブ有向グラフ群に関して、サブ有向グラフ
群の各々の辺のラベルは、再構成前のラベルを構成して
いたビット列が分割され、その分割単位での同じビット
列のラベルがまとめられ、１つの辺のラベルとなってい
る。このため、サブ有向グラフ群の辺のラベルの比較回
数は、まとめられた辺のラベルの数だけ少なくて済む。

【００１２】また、本発明の第２の特徴とする有向グラ
フ再構成方法においては、まず、所定のラベル分割数で
節から発する辺集合の各辺のラベルを構成するビット列
を分割する。次に、分割した各々のビット列をラベルと
する辺を直列に接続したサブ有向グラフ群に変換する。
そして、変換したサブ有向グラフ群に対して、更に同じ
節から発する同じラベルを持つ辺を１つにまとめて、サ
ブ有向グラフ群を再構成する。

【００１３】ここでは、更に、再構成したサブ有向グラ
フ群について、検索の際のラベル比較回数が少なく、好
ましい状態の有向グラフに再構成されているかを検証し
て、良好な状態の有向グラフに変換する。そのため、続
いて、再構成したサブ有向グラフ群について辺集合にお
ける比較回数の平均値が元の変換前の有向グラフより少
ないか否かを判定する。この判定の結果として、辺集合
における比較回数の平均値が元の変換前の有向グラフよ
り少ない場合に、再構成したサブ有向グラフ群を残す変
換を行う。また、辺集合における比較回数の平均値が元
の有向グラフの辺集合における比較回数の平均値より多
いか等しい場合には当該サブ有向グラフ群を破棄し、元
の有向グラフを残す変換を行う。

【００１４】これにより、再構成された有向グラフは、
その要素のサブ有向グラフ群に関して、サブ有向グラフ
群の各々の辺のラベルは、再構成前のラベルを構成して
いたビット列が分割され、その分割単位での同じビット
列のラベルはまとめられ、１つの辺のラベルとなってい
る。このため、サブ有向グラフ群の辺のラベルの比較回
数は、まとめられた辺のラベルの数だけ少なくて済むよ
うになる。

【００１５】ここでは、元のラベルのビット列を分割
し、新たなラベルとして、その分割単位で同じビット列
のラベルはまとめられるが、新たに形成したラベルで同
じものが少なく、ラベルが十分にまとめられない場合が
存在する。この場合、元の有向グラフの１つのラベル比
較に対して、そのラベル分割数だけラベルを増すので、
新たなラベルの比較回数が増える。このため、再構成し
たサブ有向グラフ群について、検索の際のラベル比較回
数が十分に少なく、最適な状態の有向グラフに再構成さ
れているかを検証して、最適な状態の有向グラフに変換
する。その場合、ラベル分割数を変えて、各々の場合で
有向グラフ再構成を行い、比較回数の判定により最適な
状態の有向グラフに再構成を行う。

【００１６】

【実施例】以下、本発明の実施例を図面を用いて具体的
に説明する。図１は、本発明の有向グラフ再構成方法の
処理の流れを説明するＰＡＤ(Problem Analysis Diagra
m)図である。この処理では、処理対象の有向グラフの各
々の節に対し、その節から発する各々の辺に対して、辺
のラベルのビット列の分割処理を行い、分割した辺のビ
ット列の新たな辺としたサブ有向グラフとして、有向グ
ラフを再構成する。

【００１７】図１を参照して、有向グラフ再構成方法の
処理を流れを説明すると、処理を開始すると、まず、繰
り返し処理制御ブロック１１において、有向グラフの全
ての節集合の各要素（節）に対して繰り返し処理を行う
制御を行い、更に、次の繰り返し処理制御ブロック１２
において、対象の節から発する全ての要素（辺）に対す
る繰り返し処理の制御を行う。これにより、次の処理ブ
ロック１３から処理ブロック１８までの処理を、全ての
節集合の各要素（節）に対して、その各要素の節に対し
更にその節から発する全ての辺に対して、処理を順次に
実行する制御を行ない、個々の辺に対する処理を行な
う。

【００１８】個々の辺に対する処理では、まず、処理ブ
ロック１３において、辺のラベルを構成しているビット
列を分割し、次の処理ブロック１４において、分割され
たビット列をラベルとする辺が直列に接続された構造
（辺直列のサブ有向グラフ）に再構成する。次に、処理
ブロック１５において、再構成した有向グラフ（サブ有
向グラフ）の同じ節から発する同じラベルを持つ辺をひ
とつにまとめ、次に、判定処理ブロック１６，処理ブロ
ック１７，および処理ブロック１８において、ここで再
構成したサブ有向グラフを評価する。

【００１９】この有向グラフの評価の処理では、判定処
理ブロック１６において、再構成した辺集合における比
較回数の平均値が元のものより少ないか否かを判定す
る。この判定の結果、辺集合における比較回数の平均値
が元のものより少ない場合は、次の処理ブロック１７に
おいて、再構成した辺集合の方を残して、１つの節から
発する当該辺に対する処理を終了する。また、判定処理
ブロック１６の判定において、辺集合における比較回数
の平均値が元のものより少なくない場合は、処理ブロッ
ク１８において、元の辺集合の方を残し、１つの節から
発する当該辺に対する処理を終了する。

【００２０】このようにして、１つの節から発する当該
辺に対する処理を終了すると、繰り返し処理制御ブロッ
ク１２の制御により、辺を変えて、処理ブロック１３か
ら処理ブロック１８までの処理を繰り返し行い、処理対
象の節から発する全ての辺に対する処理を行う。１つの
節から発する全ての辺に対する処理を終了すると、更
に、繰り返し処理制御ブロック１１の制御に戻り、節を
変えて、再び、繰り返し処理制御ブロック１２から処理
ブロック１８までの処理を繰り返し行い、処理対象の節
に対する処理を行う。全ての節集合の各要素（節）に対
する処理が終了すると、ここでの一連の処理を終了す
る。

【００２１】図２〜図５は、この実施例にかかる有向グ
ラフ再構成方法により、再構成する有向グラフを具体的
なデータの例に基づいて説明する図である。図２は本実
施例にかかる有向グラフの表記法を説明する図であり、
図３は辺のラベルのビット列を分割しない場合のラベル
比較を説明する図である。図４は辺のラベルのビット列
を２分割した場合のラベル比較を説明する図である。ま
た、図５は辺のラベルのビット列を４分割した場合のラ
ベル比較を説明する図である。

【００２２】ここでの有向グラフは、図２に示すよう
に、節２１の集合および各々の節から発する辺２２の集
合から構成される。各辺２２には、ラベル２３が設けら
れる。そのグラフ形式で表現するグラフ表記２０では、
図２の上部側に示すように、節２１を丸印で表記し、節
２１から発する辺２２を矢印で表記する。その辺の矢印
の近傍に、当該辺が有するラベル２３の値を付記してい
る。

【００２３】ここでは、図が煩雑になるのを防ぐため、
図２に示す有向グラフでは、有向グラフの一部のみを示
し、同じ節を指す複数の辺が存在しない場合（木構造）
の有向グラフを表示している。しかし、同じ節を指す複
数の辺がある場合（ネットワーク構造）の有向グラフに
対しても、以下に説明する本実施例の有向グラフ再構成
方法は適用可能であることは明らかである。

【００２４】以下に説明する本実施例の有向グラフ再構
成方法の処理の例では、処理対象を木構造の有向グラフ
とするが、更に、このような木構造の有向グラフのグラ
フ表記２０を、見やすく簡略化した表現するとするた
め、図２に下部側に示すようなテーブル形式で表現する
テーブル表記２４とする。ここでのグラフ表記２０とテ
ーブル表記２４とは同じ内容の有向グラフを表現してい
る。すなわち、テーブル表記２４では、各々の矩形ブロ
ック２５が辺を表現しており、その中にラベルを表示
し、矩形ブロック２５の右側の線（右辺）がここでの節
と対応する。

【００２５】次に、このように表現された有向グラフの
辺のラベル比較を行う場合、本発明に従って、各辺のラ
ベルのビット列を分割しサブ有向グラフに再構成して比
較する場合と各辺のラベルのビット列を分割しないで比
較する場合とを対比して説明する。以下の説明ではテー
ブル表記で有向グラフが表現されているものとする。

【００２６】図３は辺のラベルのビット列を分割しない
場合のラベル比較を説明する図である。このテーブル表
記の有向グラフでは、ある節から発する２２個の辺を示
している。２２個の各辺を特定するため、ここでは、左
側に１から２２の番号を付与してある。各々の辺のラベ
ルのビット列は１６進数で表現し、辺の矩形ブロックの
内にＡ４，Ｂ０，…などと表記している。

【００２７】各々の辺のラベルを検索対象とする場合の
比較回数は、各々の辺の矩形ブロックの右側に示してい
る。ここでの１番目の辺のラベル“Ａ４”が検索対象と
なっている場合には、１番目の辺のラベル“Ａ４”との
比較の一致により、検索されるので、比較回数は１回と
なるが、例えば、３番目の辺のラベル“Ｂ４”が検索対
象となっている場合は、１番目の辺のラベル“Ａ４”と
の比較の不一致と、２番目の辺のラベル“Ｂ０”との比
較の不一致と、３番目の辺のラベル“Ｂ４”との比較の
一致とを経ることになるので、この場合の比較回数は３
回となる。

【００２８】このようにして、各々の辺のラベルが検索
対象となっている場合に対して、各辺のラベルの比較回
数を求めると、各々の辺の矩形ブロックの右側に示して
いるような比較回数となる。したがって、この場合の有
向グラフの１つの節から発する辺集合に対しては、その
総比較回数が２５３回となり、辺のラベルの平均比較回
数は、１１．５０（＝２５３÷２２）となる。

【００２９】図３の有向グラフと同じ内容の有向グラフ
に対して、本発明による有向グラフ再構成方法を適用し
た場合のラベル比較の例を説明する。辺のラベルのビッ
ト列を２分割した場合には、図４に示すようになる。図
４において、有向グラフの各々の辺のラベルのビット列
は２分割され、分割辺１と分割辺２との新たな２つの辺
のラベルとして再構成されている。前述したように、こ
の場合に新たな辺のラベルで同じ節から発する同じもの
は１つにまとめる。

【００３０】すなわち、再構成前の１番目の辺のラベル
“Ａ４”はそのビット列が２つに分割され、ラベル
“Ａ”の分割辺１とラベル“４”の分割辺２とが（新た
な節を介して）直列に接続された構造となる。再構成前
の２番目の辺のラベル“Ｂ０”はそのビット列が２つに
分割され、ラベル“Ｂ”の分割辺１とラベル“０”の分
割辺２が（新たな節を介して）直列に接続された構造と
なる。同様に、再構成前の３番目の辺のラベル“Ｂ４”
はそのビット列が２つに分割され、ラベル“Ｂ”の分割
辺１とラベル“４”の分割辺２が（新たな節を介して）
直列に接続された構造となる。ここで、３番目の辺の分
割辺１のラベル“Ｂ”と、２番目の辺の分割辺１のラベ
ル“Ｂ”とは同じであり、また、同じ節から発している
ので、３番目の辺の分割辺１と２番目の辺の分割辺１と
は１つにまとめられる。以下、同様にして、４番目の辺
から２２番目の辺までの辺を２分割して再構成を行う
と、図４に示すような有向グラフ（テーブル表記）が得
られる。

【００３１】このようにして、２分割して再構成した有
向グラフを評価するため、前述の図３で説明した場合と
同様に、各々の辺のラベルを検索対象とした場合のそれ
ぞれの比較回数を求める。各々の辺のラベルを検索対象
とした場合の比較回数は、各々の分割辺２の矩形ブロッ
クの右側に示されている。この場合の比較は辺直列法で
の比較を行う。すなわち、１番目の辺のラベル“Ａ４”
が検索対象となっている場合、１番目の分割辺１のラベ
ル“Ａ”との比較の一致と、１番目の分割辺２のラベル
“４”との比較の一致とにより検索されるので、その比
較回数は２回となる。２番目の辺のラベル“Ｂ０”が検
索対象となっている場合は、１番目の分割辺１のラベル
“Ａ”との比較の不一致と、２番目の分割辺１のラベル
“Ｂ”との比較の一致と、２番目の分割辺２のラベル
“０”との比較の一致とを経ることになるので、この場
合の比較回数は３回となる。

【００３２】また、３番目の辺のラベル“Ｂ４”が検索
対象となっている場合は、１番目の分割辺１のラベル
“Ａ”との比較の不一致と、２番目の分割辺１のラベル
“Ｂ”との比較の一致と、２番目の分割辺２のラベル
“０”との比較の不一致と、３番目の分割辺２のラベル
“４”との比較の一致とを経ることになるので、この場
合の比較回数は４回となる。以下、同様にして、２２番
目の辺のラベル“ＣＦ”が検索対象となっている場合ま
での比較回数を求める。

【００３３】このようにして、各々の辺のラベルが検索
対象となっている場合に対して、各辺のラベルの比較回
数を求めることにより、各々の分割辺２の矩形ブロック
の右側に示しているような比較回数が得られる。この場
合、図３に示す有向グラフと同じ内容の有向グラフの１
つの節から発する辺集合に対して、その総比較回数が１
８４回となり、平均比較回数は、８．３６（＝１８４÷
２２）となる。明らかに、辺のビット列を分割しない場
合（図３）に比較して、辺のビット列を分割した場合
（図４）の平均比較回数が減少している。このため、こ
のように、有向グラフの辺のビット列を分割して、サブ
有向グラフに再構成することにより、有向グラフでの探
索処理が高速化できる。

【００３４】図５は、辺のビット列を更に分割して、辺
のラベルのビット列を４分割した場合のラベル比較を説
明する図である。辺のラベルのビット列を４分割して再
構成した場合の有向グラフは、図５に示すようになる。
図５において、有向グラフの各々の辺のラベルのビット
列は４分割され、２ビットずつのラベルを有する辺の集
合からなるサブ有向グラフとして再構成される。すなわ
ち、各々の辺のラベルのビット列は、分割辺１，分割辺
２，分割辺３および分割辺４との新たな４つの辺のラベ
ルとして再構成される。前述の場合と同様に、新たな辺
のラベルで同じ節から発するもので、同じものは１つに
まとめられる。

【００３５】再構成前の１番目の辺のラベルの１６進数
表記の“Ａ４”は、そのビット列が４つに分割され、２
ビットずつのビット列の４つのラベルとなる（以下の説
明では各々のラベルの２ビットの表記を４進数で表記す
るが併せて適宜に括弧内にビット表記する）。この場
合、図５に示すように、１番目の辺のラベル“Ａ４（１
０１００１００）”のビット列は、４つの分割され、ラ
ベル“２（１０）”の分割辺１と、ラベル“２（１
０）”の分割辺２と、ラベル“１（０１）”の分割辺３
と、ラベル“０（００）”の分割辺４とが（各々が新た
な節を介して）直列に接続された構造となる。

【００３６】同じく、再構成前の２番目の辺のラベル
“Ｂ０（１０１１００００）”のビット列は、４つのビ
ット列に分割され、ラベル“２（１０）”の分割辺１
と、ラベル“３（１１）”の分割辺２と、ラベル“０
（００）”の分割辺３と、ラベル“０（００）”の分割
辺４とが、直列に接続された構造となる。このような再
構成では、２番目の辺の分割辺１のラベル“２”と、１
番目の辺の分割辺１のラベル“２”とは同じであり、ま
た、同じ節から発しているので、２番目の辺の分割辺１
と１番目の辺の分割辺１とは、１つにまとめられる。

【００３７】また、再構成前の３番目の辺のラベル“Ｂ
４（１０１１０１００）”は、そのビット列が４つに分
割されて、ラベル“２（１０）”の分割辺１と、ラベル
“３（１１）”の分割辺２と、ラベル“１（０１）”の
分割辺３と、ラベル“０（００）”の分割辺４とが、直
列に接続された構造となる。この再構成では、３番目の
辺の分割辺１のラベル“２”は１番目の辺の分割辺１の
ラベル“２”とは同じであり、また、同じ節から発して
いるので、３番目の辺の分割辺１と１番目の辺の分割辺
１とは１つにまとめられ、また、３番目の辺の分割辺２
のラベル“３”は２番目の辺の分割辺２のラベル“３”
とは同じで、共に同じ節から発しているので、３番目の
辺の分割辺２と２番目の辺の分割辺２とは１つにまとめ
られる。

【００３８】このようにして、同じ節から発している同
じ内容のラベルの辺は１つにまとめられる。以下、同様
にして、４番目の辺から２２番目の辺までの辺を４分割
して再構成し、同じ節から発している同じ内容のラベル
の辺は１つにまとめて、サブ有向グラフに再構成を行う
と、図５に示すような有向グラフ（テーブル表記）が得
られる。

【００３９】また、同じく、ここで４分割し再構成した
有向グラフを評価するため、前述の図３により説明した
場合と同様に、各々の辺のラベルを検索対象とした場合
のそれぞれの比較回数を求め、その平均比較回数を求め
る。各々の辺のラベルを検索対象とした場合の比較回数
は、各々の分割辺４の矩形ブロックの右側に示されてい
る。前述の場合と同様に、この場合の比較は辺直列法で
の比較を行う。すなわち、１番目の辺のラベル“Ａ４”
が検索対象となっている場合、ビット列を辺のラベルと
する比較が辺直列法で行なわれ、１番目の分割辺１のラ
ベル“２”との比較の一致と、１番目の分割辺２のラベ
ル“２”との比較の一致と、１番目の分割辺３のラベル
“１”との比較の一致と、１番目の分割辺４のラベル
“０”との比較の一致とにより検索されるので、比較回
数は４回となる。

【００４０】２番目の辺のラベル“Ｂ０”が検索対象と
なっている場合は、１番目の分割辺１のラベル“２”と
の比較の一致と、１番目の分割辺２のラベル“２”との
比較の不一致と、２番目の分割辺２のラベル“３”との
比較の一致と、２番目の分割辺３のラベル“０”との比
較の一致と、２番目の分割辺４のラベル“０”との比較
の一致とを経ることになるので、この場合の比較回数は
５回となる。

【００４１】３番目の辺のラベル“Ｂ４”が検索対象と
なっている場合は、１番目の分割辺１のラベル“２”と
の比較の一致と、１番目の分割辺２のラベル“２”との
比較の不一致と、２番目の分割辺２のラベル“３”との
比較の一致と、２番目の分割辺３のラベル“０”との比
較の不一致と、３番目の分割辺３のラベル“１”との比
較の一致と、３番目の分割辺４のラベル“０”の比較の
一致とを経ることになるので、この場合の比較回数は６
回となる。以下、同様にして、辺直列法による分割され
たビット列の比較により、２２番目の辺のラベル“Ｃ
Ｆ”が検索対象となっている場合までの比較回数を求め
る。

【００４２】上述のようにして、各々の辺のラベルが検
索対象となっている場合に対して、各辺のラベルの比較
回数を求めると、各々の分割辺４の矩形ブロックの右側
に示しているような比較回数が得られる。この場合、図
３に示す有向グラフと同じ内容の有向グラフの１つの節
から発する辺集合に対して、辺のラベルを４分割した場
合の総比較回数が１６２回となり、平均比較回数は、
７．３６（＝１６４÷２２）となる。明らかに、辺のビ
ット列を分割しない場合（図３）に比較して、辺のビッ
ト列を分割した場合（図５）の平均比較回数が大幅に減
少している。すなわち、有向グラフに対して、このよう
な有向グラフの辺のビット列を分割して、サブ有向グラ
フに再構成することにより、有向グラフでの探索処理が
高速化できることになる。

【００４３】また、ここでの有向グラフの再構成方法で
は、辺のラベルのビット列を２分割した場合と、４分割
した場合とを対比して説明しているが、各々の辺のラベ
ルのビット列の分割数は、各々の辺のラベルのデータ内
容（ビット幅），同じ節から発する辺数（辺集合）など
に応じて、その最適なラベル分割数が決定されて、有向
グラフの再構成が行なわれる。その評価では、図３〜図
５により説明したように、その辺集合のラベルの比較に
おいて、辺のラベル分割数が異なる場合の各々の場合を
評価して、その平均比較回数が最小のものを選ぶことに
なる。

【００４４】この実施例の場合には、図５に示した４分
割した場合が、その平均比較回数が最も少ないので、こ
の４分割により再構成した有向グラフを選ぶ。１つの節
から発する辺集合に対して、このような有向グラフの再
構成を行って、その評価を行い、有向グラフの各々の節
に対する評価を行い、節集合の全体にわたってこの作業
を繰り返す。これにより、辺のラベルの探索処理が高速
化できるように再構成された有向グラフが得られる。

【００４５】以上に説明したように、本実施例の有向グ
ラフ再構成方法によれば、有向グラフの開始節から始め
て、各々の節の辺集合に対して例えば辺の数ごとに、ラ
ベルの分割数を決め、それの分割数に応じて節から発す
る辺集合の各辺のラベルを構成するビット列を分割し、
複数の分割された各ビット列をラベルとする辺が直列に
接続された構造に再構成する。更に、同じ節から発する
同じラベルを持つ辺をひとつにまとめて再構成したもの
を、元のものと置き換える。

【００４６】また、節から発する辺集合の各辺のラベル
を構成するビット列を分割し、複数の分割された各ビッ
ト列をラベルとする辺が直列に接続した構造とし、更に
同じ節から発する同じラベルを持つ辺をひとつにまとめ
て再構成し、再構成した辺集合におけるラベル検索の比
較回数の平均値が、元のものより少ない場合には再構成
したものを残し、元のものより多いか等しい場合には元
のものを残す。これを有向グラフを構成するすべての辺
集合について、このような操作を行なう。

【００４７】これにより、再構成された有向グラフは、
ある節の辺集合において、複数の分割されたビット列を
ラベルとする辺が直列に接続した部分を含む有向グラフ
となっており、その有向グラフの節の辺集合において、
複数の分割されたビット列をラベルとする辺が直列に接
続された部分は、元の辺集合に比べて、平均比較回数が
減少している。したがって、有向グラフ全体について見
た場合にも、平均比較回数は減少している。このため、
再構成した有向グラフによりネットワ−クのデ−タ構造
を表現して探索を行なう場合に、比較のための処理速度
が高速化した構造の有向グラフとなる。

【００４８】

【発明の効果】以上に説明したように、本発明の有向グ
ラフ再構成方法によれば、有向グラフの開始節からの深
さごとに所定のラベル分割数を定め、再構成の対象とす
る有向グラフに対して、このラベル分割数により、節か
ら発する辺集合の各辺のラベルを構成しているビット列
を分割する。そして、分割した各々のビット列をラベル
とする辺を直列に接続したサブ有向グラフ群に変換す
る。ここで、変換したサブ有向グラフ群に対して、更に
同じ節から発する同じラベルを持つ辺を１つにまとめ
て、サブ有向グラフ群からなる有向グラフに再構成す
る。

【００４９】これにより、再構成された有向グラフは、
その要素のサブ有向グラフ群に関して、サブ有向グラフ
群の各々の辺のラベルは、再構成前のラベルを構成して
いたビット列が分割され、その分割単位で同じビット列
のラベルはまとめられ１つの辺のラベルとなっている。
このため、サブ有向グラフ群の辺のラベルの比較回数
は、まとめられた辺のラベルの数だけ少なくて済む。こ
のため、再構成した有向グラフによりネットワ−クのデ
−タ構造を表現し、探索を行なう場合に、比較のための
処理速度が高速化された構造の有向グラフを実現でき
る。

【図面の簡単な説明】

【図１】 図１は本発明の有向グラフ再構成方法の処理
の流れを説明するＰＡＤ図、

【図２】 図２は本実施例にかかる有向グラフの表記法
を説明する図、

【図３】 図３は辺のラベルのビット列を分割しない場
合のラベル比較を説明する図、

【図４】 図４は図４は辺のラベルのビット列を２分割
した場合のラベル比較を説明する図、

【図５】 図５は辺のラベルのビット列を４分割した場
合のラベル比較を説明する図である。

【符号の説明】

１１〜１８…ＰＡＤの処理ブロック、２０…グラフ表
記、２１…節、２２…辺、２３…ラベル、２４…テーブ
ル表記、２５…辺の矩形ブロック。

Claims (2)

【特許請求の範囲】
1. 【請求項１】 有向グラフの開始節からの深さごとに所
   定のラベル分割数を定め、該ラベル分割数で、節から発
   する辺集合の各辺のラベルを構成しているビット列を分
   割し、分割した各々のビット列をラベルとする辺を直列
   に接続したサブ有向グラフ群に変換し、変換したサブ有
   向グラフ群に対して更に同じ節から発する同じラベルを
   持つ辺を１つにまとめ、サブ有向グラフ群からなる有向
   グラフに再構成することを特徴とする有向グラフ再構成
   方法。
2. 【請求項２】 所定のラベル分割数で節から発する辺集
   合の各辺のラベルを構成するビット列を分割し、 分割した各々のビット列をラベルとする辺を直列に接続
   したサブ有向グラフ群に変換し、 変換したサブ有向グラフ群に対して更に同じ節から発す
   る同じラベルを持つ辺を１つにまとめて、サブ有向グラ
   フ群を再構成し、 再構成したサブ有向グラフ群について、辺集合における
   比較回数の平均値が元の変換前の有向グラフより少ない
   か否かを判定し、 辺集合における比較回数の平均値が変換前の有向グラフ
   より少ない場合に、再構成したサブ有向グラフ群を残
   し、平均値が元の有向グラフの辺集合における比較回数
   の平均値より多いか等しい場合には当該サブ有向グラフ
   群を破棄し、元の有向グラフを残す変換を行い、 有向グラフを再構成することを特徴とする有向グラフ再
   構成方法。