JPH11341004A

JPH11341004A - ネットワーク追跡用データ作成装置、ネットワーク追跡装置、ネットワーク追跡用データ作成方法、ネットワーク追跡方法、および記録媒体

Info

Publication number: JPH11341004A
Application number: JP14971698A
Authority: JP
Inventors: Toshihiro Seki; 敏弘関; Masatake Toyoshima; 正剛豊島
Original assignee: Tokyo Gas Co Ltd
Current assignee: Tokyo Gas Co Ltd
Priority date: 1998-05-29
Filing date: 1998-05-29
Publication date: 1999-12-10
Anticipated expiration: 2018-05-29
Also published as: JP3905641B2

Abstract

(57)【要約】【課題】頂点と辺とで構成される方向を有するネット
ワークにおいて、頂点や辺のデータから効率良く上下流
追跡作業を行うこと。【解決手段】マンホールデータ３５及び管データ４５
を基に、頂点データ５１及び辺データ５５を作成する。
管渠の上流側頂点及び下流側頂点に関しても仮想マンホ
ールとして同様に頂点データ５１を作成する。正真マン
ホールと仮想マンホールの重複を検索することにより、
ネットワークにおける辺の流出入関係を明確にする。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、下水道マッピング
システムなどの方向性を有するネットワークについての
ネットワーク追跡用データ作成装置、ネットワーク追跡
装置、ネットワーク追跡用データ作成方法、ネットワー
ク追跡方法、および記録媒体に関するものである。

【０００２】

【従来の技術】一般に、流れの方向性を有する例えば下
水道などのネットワークを管理するために、下水管渠の
配管および下水の流れ方向の表示された下水配管図（マ
ンホール管渠グラフ）などの図面が用いられる。

【０００３】下水道を管理する際に、例えば有害危険物
や汚染物質が発見された場合には、迅速に発見地点の上
流側で流入地点や汚染源を特定したり、下流側への影響
予測を行わなくてはならない。このような上流追跡や下
流追跡は、熟練技術者が下水配管図を目視して手作業に
より行なっていた。

【０００４】また、昨今では、コンピュータによる下水
マッピングシステムなども用いられている。下水マッピ
ングシステムにおいては、例えば下水管渠の配管位置や
流れ方向、マンホールの位置、その他のデータを整理し
た下水データベースが設けられており、下水配管図など
もコンピュータ出力されている。

【０００５】

【発明が解決しようとする課題】しかしながら、現在で
は下水管渠の配管が増加し複雑化しつつあり、また下水
配管図を取り扱う熟練技術者が減少しつつある。したが
って、上流側および下流側の追跡を、下水配管図面の目
視および手作業によって迅速に行なうことは困難であ
る。

【０００６】また、コンピュータ処理に於いても、上下
流追跡を行なう場合には、辺や頂点の上下関係や連続性
を調べるために順番に数多くの辺や頂点を検索して座標
を比較するなど、大量のデータを処理する必要があり、
膨大な時間を要していた。

【０００７】また、膨大なデータ量を扱うために、地域
を矩形などのメッシュに分割してメッシュ毎にデータを
区分する場合があり、その場合にはメッシュ境界と辺や
頂点とが重複した場合に特殊な処理を行なわなくてはな
らないという問題があった。

【０００８】本発明は、このような問題に鑑みてなされ
たもので、その目的とするところは、下水道などのネッ
トワークの辺および頂点のデータを基にして、効率的な
上下流追跡の可能なネットワークデータベースを構築す
ることのできるネットワーク記録装置、ネットワーク記
録方法および記録媒体を提供することにある。

【０００９】

【課題を解決するための手段】前述した目的を達成する
ために、第１の発明は、複数の頂点が辺によって接続さ
れたネットワークで、前記辺の両端の座標と流れ方向を
示すデータを少なくとも有する辺データと、前記頂点の
座標を有する頂点データと、を有するデータベースと、
前記各頂点に接続する辺へのリンク情報を示す頂点リス
トを作成する手段と、前記各辺の上流または下流頂点へ
のリンク情報を示す辺リストを作成する手段と、前記辺
データの両端を頂点リストに追加する手段と、前記頂点
リストに前記追加された辺データの上流側または下流側
の一端と前記頂点とが一致すれば、この頂点に接続する
辺のリンク情報を当該辺とし、この辺の上流頂点または
下流頂点へのリンク情報を当該頂点とする手段と、を具
備することを特徴とするネットワーク追跡用データ作成
装置である。

【００１０】また、第２の発明は、ネットワーク追跡用
データ作成装置で作成されたデータを用いてネットワー
クを追跡するネットワーク追跡装置であって、（ａ）あ
る頂点を指定すると、頂点リストの流出辺へのリンク情
報を参照して、この頂点に対する流出辺を算出し、
（ｂ）算出された流出辺に対して、辺リストの下流頂点
へのリンク情報を参照してこの辺に対する下流側の頂点
を算出し、（ｃ）（ａ）〜（ｂ）を繰り返すことによっ
て下流追跡を行うことを特徴とするネットワーク追跡装
置である。

【００１１】また、第３の発明は、複数の頂点が辺によ
って接続されたネットワークで、前記辺の両端の座標と
流れ方向を示すデータを少なくとも有する辺データと、
前記頂点の座標を有する頂点データと、を有するデータ
ベースと、前記各頂点に接続する辺へのリンク情報を示
す頂点リストを作成する工程と、前記各辺の上流または
下流頂点へのリンク情報を示す辺リストを作成する工程
と、前記辺データの両端を頂点リストに追加する工程
と、前記頂点リストに前記追加された辺データの上流側
または下流側の一端と前記頂点とが一致すれば、この頂
点に接続する辺のリンク情報を当該辺とし、この辺の上
流頂点または下流頂点へのリンク情報を当該頂点とする
工程と、を具備することを特徴とするネットワーク追跡
用データ作成方法である。

【００１２】また、第４の発明は、ネットワーク追跡用
データ作成方法で作成されたデータを用いてネットワー
クを追跡するネットワーク追跡方法であって、（ａ）あ
る頂点を指定すると、頂点リストの流出辺へのリンク情
報を参照して、この頂点に対する流出辺を算出し、
（ｂ）算出された流出辺に対して、辺リストの下流頂点
へのリンク情報を参照してこの辺に対する下流側の頂点
を算出し、（ｃ）（ａ）〜（ｂ）を繰り返すことによっ
て下流追跡を行うことを特徴とするネットワーク追跡方
法である。

【００１３】また、第５の発明は、複数の頂点が辺によ
って接続されたネットワークで、前記辺の両端の座標と
流れ方向を示すデータを少なくとも有する辺データと、
前記頂点の座標を有する頂点データと、を有するデータ
ベースと、前記各頂点に接続する辺へのリンク情報を示
す頂点リストを作成する手段と、前記各辺の上流または
下流頂点へのリンク情報を示す辺リストを作成する手段
と、前記辺データの両端を頂点リストに追加する手段
と、前記頂点リストに前記追加された辺データの上流側
または下流側の一端と前記頂点とが一致すれば、この頂
点に接続する辺のリンク情報を当該辺とし、この辺の上
流頂点または下流頂点へのリンク情報を当該頂点とする
手段と、を具備するネットワーク追跡用データ作成装置
として、コンピュータを機能させるためのプログラムを
記録した記録媒体である。

【００１４】

【発明の実施の形態】以下、図面に基づいて、本発明の
第１の実施の形態について、下水を例にとり、ネットワ
ークデータ作成から上下流追跡までの過程を詳細に説明
する。図１は本発明の実施の形態に係るネットワーク検
索システム１の機器構成を示す図であり、図２は下水配
管図（マンホール管渠グラフ）３１の模式図である。

【００１５】図１に示すように、ネットワーク検索シス
テム１は、ホストコンピュータ３、端末側コンピュータ
５、データベース７及びＣＤ−ＲＯＭ１５から構成され
る。端末側コンピュータ５からホストコンピュータ３に
検索命令等が入力され、データベース７に格納された各
種のデータをホストコンピュータ３が読み出し、検索処
理を行う。

【００１６】データベース７には地形データ１１、ネッ
トワークデータ１３が格納される。ネットワークデータ
１３には、マンホールデータ３５と管データ４５があ
る。ＣＤ−ＲＯＭ１５はホストコンピュータ３に検索処
理を行わせるためのプログラムを格納し、更に、地形デ
ータ１１やネットワークデータ１３を格納することも可
能である。

【００１７】図２の下水配管図３１の模式図は下水設備
の一部を示したものだが、下水設備は管渠ｋ１、ｋ２、
……およびマンホールｍ１、ｍ２、……から構成され
る。なお、ｋ１、ｋ２、……はパイプ、管路、開渠、暗
渠などであってもかまわない。また、マンホールには、
複数の管渠を接続し管理するための通常マンホールの
他、最上流端点、下水処理場などの下流側末端施設など
がある。

【００１８】図１に示すマンホールデータ３５は下水設
備に存在する図２に示されるマンホールｍ１、ｍ２、…
…に関するデータである。図３はマンホールデータ３５
のフォーマットを示す。マンホールデータ３５は、頂点
番号７１、座標３０５、属性３０７からなる。

【００１９】ここで、頂点番号７１は、全てのマンホー
ルｍｉを識別するために付けられた通し番号であり、座
標３０５は、下水設備をｘｙ平面に写した際のマンホー
ルｍｉの位置座標を示す。属性３０７はマンホールｍｉ
の建設年度、修理業者、種別、材料等のデータである。

【００２０】また、図１に示す管データ４５は図２に示
される管渠ｋ１、ｋ２、……に関するデータであり、図
４は管データ４５のフォーマットを示す。管データ４５
は、辺番号８１、上流側頂点座標４０５、下流側頂点座
標４０７、属性４０９及び中間座標列４１１からなる。

【００２１】ここで、辺番号８１は全ての管渠ｋｉを識
別するために付けられた通し番号である。上流側頂点座
標４０５及び下流側頂点座標４０７は管渠ｋｉの上流側
端点及び下流側端点の座標であり、属性４０９は、管渠
の管種、口径、長さを示すものである。

【００２２】また、中間座標列４１１は、管渠の始点と
終点及び管渠が折れ曲がっている場合の曲点の座標であ
る。管データ４５において、上流側頂点座標４０５及び
下流側頂点座標４０７は中間座標列４１１の始点或いは
終点の座標と一致する。

【００２３】次に、図２の下水配管図３１の例に示され
る管渠ｋｉおよびマンホールｍｉについて、上流側およ
び下流側の接続関係を明確にする方法について説明す
る。図５はマンホールデータ３５及び管データ４５から
マンホールｍｉと管渠ｋｉの接続関係を求める処理のフ
ローチャートである。

【００２４】マンホールｍｉのマンホールデータ３５を
任意の順番で読み込み、順番付きの頂点レコード５１及
び頂点リスト５３を作成する（ステップ５０１）。次
に、管渠ｋｉの管データを任意の順番で読み込み、順番
付きの辺レコード５５及び辺リスト５７を作成する（ス
テップ５０２）。

【００２５】管渠ｋｉの上流側頂点および下流側頂点に
ついて頂点レコード５１を作成し、頂点リスト５３に追
加し（ステップ５０３）、上流側頂点及び下流側頂点と
辺リスト５７内の管渠ｋｉとの流出入関係をデータ化す
る（ステップ５０４）。

【００２６】次に、頂点リスト５３内の各マンホールｍ
ｉと上流側頂点または下流側頂点とが重複している場合
にはマンホールｍｉに統合し、頂点リスト５３及び辺リ
スト５７内の流出入データを再調整する。（ステップ５
０５）以下、図５に示す各ステップの処理について詳細に説明
する。

【００２７】ステップ５０１図６は頂点レコード５１のフォーマットを示す図であ
り、図７は頂点リスト５３を示す図である。頂点レコー
ド５１及び頂点リスト５３はマンホールデータ３５を基
にして作成され、図８は頂点リスト５３を作成する方法
を示すフローチャートである。

【００２８】マンホールデータ３５のファイルを開き
（ステップ８０１）、頂点リストの先頭のアドレスを確
認する（ステップ８０２）。ここで、頂点リスト５３の
先頭アドレスをＬＭＬとする。次に一番目のマンホール
データ３５を読み出し（ステップ８０３）、頂点レコー
ド５１及び頂点リスト５３を作成する（ステップ８０
４）。

【００２９】図６に示す頂点レコード５１は、頂点番号
７１、座標３０５、属性５１１、ダミーフラグ５１３、
ポインタ５１４、抽出フラグ７９からなる。頂点レコー
ド５１における頂点番号７１、座標３０５、属性５１１
には、マンホールデータ３５における頂点番号７１、座
標３０５、そして属性３０７の内必要なデータが読み出
され、格納される。尚、頂点レコード５１において属性
データ５１１は省略しても構わない。

【００３０】また、ダミーフラグ５１３は、正真マンホ
ールであるか、又は後述する仮想マンホールであるかを
区別するためのものである。マンホールデータ３５から
作成する頂点レコード５１は、実在の正真マンホールｍ
ｉに関するデータであるため、ダミーフラグ５１３は例
えば「０」とする。

【００３１】また、ポインタ５１４においては、第１流
出辺７３は当該マンホールから流出する下水管のうちの
１番目のもの、第１流入辺７５は当該マンホールに流入
する下水管のうちの１番目のものを、それぞれデータの
存在する先頭アドレスによって示す。この段階では第１
流出辺７３および第１流入辺７５は不明であるため、そ
れぞれ「ｎｕｌｌ」とする。

【００３２】正真マンホールｍ１、ｍ２、………には一
連の頂点番号７１がつけられている。次の入力頂点７７
のデータは、当該頂点の次の頂点番号７１の頂点レコー
ド５１の先頭アドレスとする。すなわち、頂点レコード
５１のデータ長をＬＭとすると、ｉ番目の頂点レコード
５１内の「次の入力頂点７７ｉ」は（ｉ＋１）番目の頂
点の先頭アドレスであり、「ＬＭＬ＋ｉＬＭ」となる。

【００３３】次に、当該頂点、即ちｉ番目の頂点レコー
ド５１をアドレス「ＬＭＬ＋（ｉ−１）ＬＭ」に保管し
（ステップ８０５）、ｉを正真マンホール数ｎＭとして
記憶する（ステップ８０６）。マンホールデータ３５が
終りかどうかを判断し（ステップ８０７）、マンホール
データ３５が存在すればｉを一つ増し（ステップ８０
９）、ステップ８０４からステップ８０７の処理を繰り
返し行う。読み出すマンホールデータ３５がなくなった
とき、ｎＭを正真マンホール数として保管する（ステッ
プ８０８）。

【００３４】以上のような処理により、頂点レコード５
１及び図７に示される頂点リスト５３が作成される。例
えば、図２に示す下水配管図３１においてマンホールｍ
１から頂点レコード５１の作成を始めるとすると、頂点
レコード５１ａの先頭アドレス７０３は「ＬＭＬ」とな
る。尚、図７において先頭アドレス７０３は便宜上示し
たものであり、頂点レコード５１には先頭アドレス７０
３は含まれない。

【００３５】頂点レコード５１ａにおいて、頂点番号７
１ａは「ｍ１」となり、第１流出辺７３ａ及び第１流入
辺７５ａは「ｎｕｌｌ」となり、次の頂点番号がマンホ
ールｍ２であれば、次の入力頂点７７ａはマンホールｍ
２に関する頂点レコード５１ｂが格納される先頭アドレ
ス「ＬＭＬ＋ＬＭ」となる。尚、以下の説明において、
例えば、ポインタデータとして入力頂点７７ａに「ｍ
２」と記入された場合、マンホールｍ２に関する頂点レ
コードが格納されたアドレスを示すものである。

【００３６】次に、アドレス「ＬＭＬ＋ＬＭ」にマンホ
ールｍ２に関する頂点レコード５１ｂが同様に作成さ
れ、格納される。以下、マンホールｍ３、……に関する
頂点レコード５１が作成され、格納され、頂点リスト５
３が作成される。従って、ｎＭ個の正真マンホールが存
在する場合、頂点レコード５１ｎＭはアドレス「ＬＭＬ
＋（ｎＭ−１）ＬＭ」に格納される。

【００３７】ステップ５０２、ステップ５０３、ステッ
プ５０４次に、管データ４５から辺レコード５５を作成し、更
に、仮想の頂点レコード５１を作成する方法について説
明する。図９は辺レコード５５を示す図であり、図１０
は辺レコード５５及び仮想マンホールに対する頂点レコ
ード５１を作成する方法を示すフローチャートである。

【００３８】管データ４５が格納されているファイルを
開き（ステップ１００１）、頂点リスト５３のファイル
を開く（ステップ１００２）。次に、辺リスト５７の先
頭アドレスを確認する。以下、辺リストの先頭アドレス
を「ＬＬＬ」として説明を行う。ｉに１を代入し（ステ
ップ１００４）、ｉ番目の管データ４５を読み出す（ス
テップ１００５）。管データ４５から辺データ５５を作
成するために必要なデータを取り出し（ステップ１００
６）、辺レコード５５を作成する（ステップ１００
７）。

【００３９】図９に示すように、辺レコード５５は、辺
番号８１、上流側頂点座標４０５、下流側頂点座標４０
７、属性４０９、ポインタ４１０、抽出フラグ９９から
なる。この内、辺番号８１、上流側頂点座標４０５、下
流側頂点座標４０７、属性４０９のデータは、管データ
４５と共通するデータである。尚、辺レコード５５にお
いて、属性４０９のデータは省略しても構わない。

【００４０】ポインタ４１０は、次の流入辺８５、次の
流出辺８３、次の入力辺８７、上流側頂点８９及び下流
側頂点９１のデータが格納されている先頭アドレスを示
す。辺レコード５５のデータ長を「ＬＬ」とすると、次
の流出辺８３および次の流入辺８５は「ｎｕｌｌ」、次
の入力辺８７は「ＬＬＬ＋ｉＬＬ」、上流側頂点８９は
「ＬＭＬ＋（ｎＭ−１＋２ｉ−１）ＬＭ」、下流側頂点
９１は「ＬＭＬ＋（ｎＭ−１＋２ｉ）ＬＭ」となる。こ
のように作成された当該辺レコード、即ちｉ番目の辺レ
コード５５は、アドレス「ＬＬＬ＋（ｉ−１）ＬＬ」に
保管される。

【００４１】次に、当該辺の上流側頂点を仮想マンホー
ルとみなし、頂点レコード５１を作成し、作成した頂点
レコード５１を頂点リスト５３のアドレス「ＬＭＬ＋
（ｎＭ−１＋２ｉ−１）ＬＭ」に追加する（ステップ１
００８）。

【００４２】このとき、上流側頂点にとって当該辺は第
１の流出辺に相当するから、頂点レコード５１のポイン
タにおいて第１流出辺７３はアドレス「ＬＬＬ＋（ｉ−
１）ＬＬ」となる。更に、第１の流入辺７５は「ｎｕｌ
ｌ」、次の入力頂点７７はアドレス「ＬＭＬ＋（ｎＭ−
１＋２ｉ）ＬＭ」となる。尚、仮想マンホールに関して
作成した頂点レコード５１において、ダミーフラグ５０
３を例えば「１」とし、正真マンホールと区別する。

【００４３】次に、当該辺の下流側頂点も同様に仮想マ
ンホールとみなし、頂点レコード５１を作成し、作成し
た頂点レコード５１を頂点リスト５３のアドレス「ＬＭ
Ｌ＋（ｎＭ−１＋２ｉ）ＬＭ」に追加する（ステップ１
００９）。

【００４４】このとき、下流側頂点にとって当該辺は第
１の流入辺に相当するから、頂点レコード５１のポイン
タにおいて第１の流入辺７５はアドレス「ＬＬＬ＋（ｉ
−１）ＬＬ」となる。更に、第１流出辺７３は「ｎｕｌ
ｌ」、次の入力頂点７７はアドレス「ＬＭＬ＋（ｎＭ−
１＋２ｉ＋１）ＬＭ」となる。

【００４５】次に、管データ４５が終了かどうかを判定
し（ステップ１０１０）、まだ管データ４５が存在する
場合はｉを一つ増し（ステップ１０１１）、管データ４
５がなくなるまで、ステップ１００５からステップ１０
１０までの作業を繰り返す。

【００４６】図１１は下水配管図３１の模式図を示す。
図１１に示されるように、管渠ｋ１、管渠ｋ２、…にお
ける上流側頂点をｋｕ１、ｋｕ２、…、下流側頂点をｋ
ｄ１、ｋｄ２、…とし、それらの頂点を仮想マンホール
とみなして、辺リスト５７と追加の頂点リスト５３を作
成する。図１２は、図１１に示す下水配管図３１に従っ
て作成した辺リスト５７と頂点リスト５３の内容を示す
図である。

【００４７】図１０のフローチャートに従って、ｉ＝１
として管渠ｋ１の管データ４５を読み出す。図１０のス
テップ１００７に従って、管渠ｋ１に関する辺レコード
５５ａを作成する。以下、辺レコード５５ａにおけるポ
インタには、便宜上、辺番号や頂点番号が記入される
が、記入された辺番号や頂点番号はそれらのレコードが
保管されるアドレスを示すものである。

【００４８】図１２に示すように、辺レコード５５ａに
おいて、辺番号８１ａは「ｋ１」、次の流入辺８３ａ及
び次の流出辺８５ａは「ｎｕｌｌ」、次の入力辺８７ａ
は「ｋ２」、上流側頂点８９ａは「ｋｕ１」、下流側頂
点９１ａは「ｋｄ１」となる。作成された辺レコード５
５ａは先頭アドレス７０５が「ＬＬＬ」に保管される。
尚、図１２において「ｎｕｌｌ」は空白で示される。ま
た、先頭アドレス７０５は便宜上示したものであり、辺
レコード５５には含まれない。

【００４９】次に、図１０のステップ１００８に従っ
て、管渠ｋ１の上流側頂点ｋｕ１に関する頂点レコード
５１ｄを作成する。頂点レコード５１ｄにおいて、第１
の流出辺７３ｄは「ｋ１」となり、第１の流入辺７５ｄ
は「ｎｕｌｌ」、次の入力頂点７７ｄは「ｋｄ１」とな
る。作成された頂点レコード５１ｄは先頭アドレスが
「ＬＭＬ＋（ｎＭ−１＋２ｉ−１）ＬＭ」、即ち、正真
マンホール数ｎＭ＝３、ｉ＝１とすればアドレス「ＬＭ
Ｌ＋３ＬＭ」に保管される。

【００５０】次に、図１０のステップ１００９に従っ
て、管渠ｋ１の下流側頂点ｋｄ１に関する頂点レコード
５１ｅを作成する。頂点レコード５１ｅにおいて、第１
の流出辺７３ｅは「ｎｕｌｌ」となり、第１の流入辺７
５ｅは「ｋ１」、次の入力頂点７７ｅは「ｋｕ２」とな
る。作成された頂点レコード５１ｅは先頭アドレスが
「ＬＭＬ＋（ｎＭ−１＋２ｉ）ＬＭ」、即ち、正真マン
ホール数ｎＭ＝３、ｉ＝１とすればアドレス「ＬＭＬ＋
４ＬＭ」に保管される。

【００５１】以上のように、図１１に示す管渠ｋ２、ｋ
３、…、ｋ１０に関する辺レコード５５ｂ、５５ｃ、
…、５５ｊ及び管渠ｋ２、ｋ３、…、ｋ１０のそれぞれ
の上流側頂点と下流側頂点に関する頂点レコード５１
ｆ、…、５１ｗを同様に作成し、保管する。このように
して、図１２に示す辺リスト５７及び頂点リスト５３が
作成される。

【００５２】ステップ５０５次に、作成した頂点リスト５３及び辺リスト５７を基に
管渠の流出入関係を求める方法について説明する。図１
３、図１４及び図１５は正真マンホールと仮想マンホー
ルの重複を探索することで管渠の流出入関係を求める方
法を示すフローチャートである。図１６は、図１３から
図１５のフローに従って流出入関係を明確にした下水配
管図３１の辺リスト５７及び頂点リスト５３を示す図で
ある。以下、図１１に示す下水配管図を例に挙げて処理
を説明する。

【００５３】頂点リスト５３及び辺リスト５７のファイ
ルを開く（ステップ１３０１、ステップ１３０２）。ｉ
＝１とし（ステップ１３０３）、頂点リスト５３のｉ番
目の頂点レコード５１から座標（Ｘｉ，Ｙｉ）を取り出
す（ステップ１３０４）。

【００５４】次に、ｉｉに正真マンホール数ｎＭを代入
し（ステップ１３０５）、ｉｉ番目、すなわち正真マン
ホールのうち最後尾の頂点の座標（Ｘ，Ｙ）を取り出し
（ステップ１３０６）、座標（Ｘ，Ｙ）と座標（Ｘｉ，
Ｙｉ）とが一致するか否かを判定する（ステップ１３０
７）。すなわち、ｉ番目の頂点が最後の正真マンホール
であるか否かを調べる。

【００５５】ステップ１３０７において頂点の座標が一
致しないと判定された場合には、ｉｉにｉｉ＋１を代入
して（ステップ１３１３）、次の頂点レコード５１が終
りか否かを判定する（ステップ１３１４）。第１回目の
ステップ１３１４で頂点レコードが存在する場合は、す
なわち、ｎＭ個の正真マンホールの他に仮想マンホール
に関する頂点レコードが存在する。

【００５６】したがって、ステップ１３０６に戻り、仮
想マンホールの座標を取り出して、ｉ番目の正真マンホ
ールの座標とｉｉ番目の仮想マンホールの座標とを比較
し（ステップ１３０７）、一致しない場合には、ステッ
プ１３１３に進んで、次のｉｉ番目の仮想マンホールの
頂点レコード５１が存在するか否かを判定する（ステッ
プ１３１４）。こうして、ステップ１３０７においてｉ
ｉ番目の頂点座標がｉ番目の正真マンホールの座標（Ｘ
ｉ，Ｙｉ）と一致するまで作業を繰り返す。

【００５７】例えば、図１２の頂点リスト５３におい
て、ｉ＝１として頂点ｍ１の頂点レコード５１ａから座
標を取り出す。更に、正真マンホール数ｎＭは「３」で
あるため、３番目の頂点である頂点ｍ３の頂点レコード
５１ｃから頂点座標を取り出し、頂点ｍ１の座標と比較
する。

【００５８】当然ながら頂点ｍ３と頂点ｍ１の座標は異
なるため、ｉｉ＝４として４番目の頂点ｋｕ１の頂点レ
コード５１ｄから座標を取り出し、頂点ｍ１の座標と比
較する。頂点ｋｕ１と頂点ｍ１の座標は異なるため、ｉ
ｉ＝５として５番目の頂点ｋｄ１の頂点レコード５１ｅ
から座標を取り出し、頂点ｍ１と比較する。図１１から
も判るように、頂点ｋｄ１と頂点ｍ１の座標は一致す
る。

【００５９】ステップ１３０７において正真マンホール
と仮想マンホールの座標が一致すると判定された場合に
は、ｉｉ番目の頂点データ５１において第１流出辺７３
にデータがあるか、それとも第１流入辺７５にデータが
あるかを判定する（ステップ１３０８）。

【００６０】例えば、頂点ｋｄ１と頂点ｍ１の座標は一
致するため、頂点ｋｄ１の頂点レコード５１ｅの第１流
出辺７３ｅあるいは第１流入辺７５ｅのどちらにデータ
があるかを判断する。この場合データは第１流出辺７５
ｅに存在する。

【００６１】ステップ１３０８において第１流出辺７３
にデータがあると判定された場合には、ｉ番目の第１流
出辺７３が「ｎｕｌｌ」であるかを判定する（ステップ
１３０９）。ステップ１３０９において、第１流出辺７
３が「ｎｕｌｌ」でなければ、後述するように図１５の
ステップ１５０１に進む。

【００６２】次に、第１流出辺７３が「ｎｕｌｌ」デー
タである場合には、ｉ番目の第１流出辺７３に、ｉｉ番
目の第１流出辺７３のデータを入れ、更に第１流出辺７
３に保持されたデータ（管渠ｋｉ）に相当する辺レコー
ド５５の上流側頂点８９をｉ番目の頂点とする（ステッ
プ１３１０）。即ち、管渠ｋｉの辺レコード５５の上流
側頂点８９にはｉ番目の頂点の頂点レコードが保持され
たアドレスが入る。

【００６３】また、ステップ１３０８において第１流入
辺７５にデータがあると判定された場合には、ｉ番目の
第１流入辺７５が「ｎｕｌｌ」であるかを判定する（ス
テップ１３１２）。ステップ１３１１において、第１流
入辺７５が「ｎｕｌｌ」でなければ、後述するように図
１４のステップ１４０１に進む。

【００６４】次に、第１流入辺７５が「ｎｕｌｌ」デー
タである場合には、ｉ番目の第１流入辺７５に、ｉｉ番
目の第１流入辺７５のデータを入れ、更に第１流入辺７
５に保持されたデータ（管渠ｋｉ）に相当する辺レコー
ド５５の下流側頂点９１をｉ番目の頂点とする（ステッ
プ１３１２）。即ち、管渠ｋｉの辺レコード５５の下流
側頂点９１にはｉ番目の頂点の頂点レコードが保持され
たアドレスが入る。

【００６５】従って、頂点ｋｄ１の場合は第１流出辺７
５ｅにデータ「ｋ１」があり、頂点ｍ１の頂点レコード
５１ａの第１流出辺７５ａが「ｎｕｌｌ」であるため、
図１６に示されるように頂点ｍ１の第１流出辺７３ａを
「ｋ１」とする。更に、「ｋ１」の辺レコード５５ａに
おいて下流側頂点９１ａを「ｍ１」に変更する。

【００６６】次に、ｉｉにｉｉ＋１を代入し（ステップ
１３１３）、頂点リスト５３内の頂点レコード５１が終
りであるかどうかを判定し（ステップ１３１４）、頂点
レコード５１がまだ存在するようであれば、ステップ１
３０６に戻り、以上の操作を繰り返す。即ち、ｉ番目の
頂点座標と頂点リストに追加された全ての仮想マンホー
ルの座標が同じかどうかを判定し、一致した場合は以上
のような統合処理を行う。

【００６７】例えば、下水配管図３１の例では、次にｉ
ｉ＝６として６番目の頂点ｋｕ２の頂点レコード５１ｆ
から座標を取り出し、頂点ｍ１の座標と比較する。頂点
ｍ１と頂点ｋｕ２の座標は一致し、頂点ｋｕ２の頂点レ
コード５５ｆの第１流出辺７３ｆにデータ「ｋ２」が存
在することから、ステップ１３０９に進む。

【００６８】このとき頂点ｍ１の頂点レコード５１ａに
おいて第１流出辺７３ａが「ｎｕｌｌ」であるから、図
１６に示されるように頂点ｍ１の第１流出辺７３ａを
「ｋ２」とし、更に、「ｋ２」の辺レコード５５ｂにお
いて上流側頂点８９ｂを「ｍ１」に変更する。

【００６９】次に、ステップ１３１１において、ｉ番目
の第１流入辺７５が「ｎｕｌｌ」でない場合は図１４に
示されるフローチャートに従って処理を行う。即ち、図
１４に示される処理は、ｉ番目の頂点に複数の流入辺が
存在するときに行われる。ｉ番目の第１流入辺７５に相
当する辺レコード５５を取り出す（ステップ１４０
１）。次に、ｉｉ番目の第１流入辺７５の辺レコード番
号８１を記憶する（ステップ１４０２）。

【００７０】ｉ番目の辺レコード５５の次の流入辺８３
は「ｎｕｌｌ」であるかどうかを判定し（ステップ１４
０３）、「ｎｕｌｌ」であれば、ステップ１４０１で読
み出した辺レコード５５の次の流入辺８３にステップ１
４０２で記憶した辺レコード番号８１を入力し、保管す
る（ステップ１４０５）。更に、ｉｉ番目の第１流入辺
７５の辺レコード５５における下流側頂点９１にｉ番目
の頂点、即ち正真マンホールｍｉを入力し、保管する
（ステップ１４０６）。

【００７１】ステップ１４０３において、ｉ番目の辺レ
コード５５の次の流入辺８３が「ｎｕｌｌ」でなけれ
ば、そこに記入されている辺の辺レコード５５を取り出
し（ステップ１４０４）、ステップ１４０２に戻る。ス
テップ１４０６において辺レコードを保管したら、図１
３に示すステップ１３１３に戻る。

【００７２】例えば、図１２に示す頂点リスト５３にお
いて図１３に示される処理を続け、ｉｉ番目の頂点とし
て頂点ｋｄ３を取り出す。頂点ｍ１と頂点ｋｄ３の座標
は一致し、頂点ｋｄ３の第１流入辺７５ｊにデータがあ
るが（ステップ１３０８）、頂点ｍ１の第１流入辺７５
ａにも前述のようにデータ「ｋ１」があるため、ステッ
プ１３１１において図１４の処理に進む。

【００７３】ステップ１４０１において頂点ｍ１の第１
流入辺７５ａのデータ「ｋ１」の辺レコード５５ａを取
り出し、頂点ｋｄ３の第１流入辺７５ｊのデータ「ｋ
３」を記憶し、「ｋ１」の辺レコード５５の次の流入辺
８３ａが「ｎｕｌｌ」となっているため、そこに先ほど
記憶したデータ「ｋ３」を入力し、保管する。更に、辺
「ｋ３」の辺レコード５５ｃにおいて下流側頂点９１ｃ
を「ｍ１」と変更し、保管する。その後、図１３に示す
ステップ１３１３に戻る。

【００７４】次に、ステップ１３０９において、ｉ番目
の第１流出辺７３が「ｎｕｌｌ」でない場合は図１５に
示されるフローチャートに従って処理を行う。即ち、図
１５に示される処理は、ｉ番目の頂点に複数の流出辺が
存在するときに行われる。ｉ番目の第１流出辺７３に相
当する辺レコード５５を取り出す（ステップ１５０
１）。次に、ｉｉ番目の第１流出辺７３の辺レコード番
号８１を記憶する（ステップ１５０２）。

【００７５】ｉ番目の辺レコード５５の次の流出辺８５
は「ｎｕｌｌ」であるかどうかを判定し（ステップ１５
０３）、「ｎｕｌｌ」であれば、ステップ１５０１で読
み出した辺レコード５５の次の流出辺８５にステップ１
５０２で記憶した辺レコード番号８１を入力し、保管す
る（ステップ１５０５）。更に、ｉｉ番目の第１流出辺
７３の辺レコード５５における上流側頂点８９にｉ番目
の頂点、即ち正真マンホールｍｉを入力し、保管する
（ステップ１５０６）。

【００７６】ステップ１５０３において、ｉ番目の辺レ
コード５５の次の流出辺８５が「ｎｕｌｌ」でなけれ
ば、そこに記入されている辺の辺レコード５５を取り出
し（ステップ１５０４）、ステップ１５０２に戻る。ス
テップ１５０６において辺レコードを保管したら、図１
３に示すステップ１３１３に戻る。

【００７７】例えば、図１３に従って前述のような処理
を更に続け、ｉｉ番目の頂点として頂点ｋｕ４を取り出
す。頂点ｍ１と頂点ｋｕ４の座標は一致し、頂点ｋｕ４
の第１流出辺７３ｋにデータがあり（ステップ１３０
８）、頂点ｍ１の第１流出辺７３ａにも図１６に示すよ
うに既にデータ「ｋ２」があるため、ステップ１３０９
において図１５の処理に進む。

【００７８】ステップ１５０１において頂点ｍ１の第１
流出辺７３ａのデータ「ｋ２」の辺レコード５５ｂを取
り出しす。次に、頂点ｋｕ４の第１流出辺７３ｋのデー
タ「ｋ４」を記憶し、「ｋ２」の辺レコード５５ｂの次
の流入辺８３ａが「ｎｕｌｌ」となっているため、そこ
に先ほど記憶したデータ「ｋ４」を入力し、保管する。
更に、辺「ｋ４」の辺レコード５５ｄにおいて上流側頂
点８９ｄを「ｍ１」と変更し、保管する。その後、図１
３に示すステップ１３１３に戻る。

【００７９】以上説明した作業をｉが正真マンホール数
ｎＭに等しくなるまで繰り返す。即ち、正真マンホール
の座標と仮想マンホールの座標を比較し、重複したマン
ホールを統合することによって管渠の流出入関係を明確
にし、図１６に示すような辺リスト５７及び頂点リスト
５３を求める。

【００８０】図１６に示す辺リスト５７及び頂点リスト
５３を用いて、例えばマンホールｍ１に接続する管渠の
流出入関係を確認する。マンホールｍ１の頂点データ５
１ａより、マンホールｍ１の第１流出辺７３ａは「ｋ
２」、第１流入辺７５ａは「ｋ１」であることが判る。

【００８１】次に、管渠「ｋ２」の辺レコード５５ｂの
次の流出辺８５ｂが「ｋ４」であり、また、管渠「ｋ
１」の辺レコード５５ａの次の流入辺８３ａが「ｋ３」
であることが判る。このようにして、マンホールｍ１で
は管渠「ｋ１」、「ｋ３」が流入し、管渠「ｋ２」、
「ｋ４」が流出することが求められる。

【００８２】次に、図１６に示すような辺リスト５７、
頂点リスト５３を用いて、上下流追跡を行なう方法につ
いて説明する。例えば、図１１に示す下水配管図３１の
マンホールｍ１に異物が混入したとして下流への影響を
追及する場合を例に挙げて説明する。

【００８３】図１７は下流追跡の処理を示すフローチャ
ートである。辺リスト５７、頂点リスト５３のファイル
をオープンする（ステップ１７０１）。従って、図１６
に示す辺リスト５７、頂点リスト５３のファイルをオー
プンする。追跡の基点となる辺あるいは頂点を指示、入
力する（ステップ１７０２）。辺或いは頂点は、頂点番
号、辺番号、あるいは、座標等により、もしくは、マウ
ス等でコンピュータディスプレイ上の位置を指示するこ
となどにより入力される。例えば、図１に示す端末側コ
ンピュータ３からマンホールｍ１が起点であると入力す
る。

【００８４】次に、起点が辺であるか頂点であるかを判
定する（ステップ１７０３）。起点が頂点である場合に
は、当該頂点の第１流出辺７３の辺レコード５５を取り
出して（ステップ１７０４）、当該第１流出辺７３の次
の流出辺８５のデータが「ｎｕｌｌ」であるか否かを判
定する（ステップ１７０５）。ステップ１７０３で起点
が辺である場合には直接ステップ１７０５に進む。ステ
ップ１７０３以降の処理は、図１に示すホストコンピュ
ータ３上で行われる。

【００８５】例えば、起点として入力したマンホールｍ
１は頂点であるため、頂点ｍ１の第１流出辺７３ａのデ
ータ「ｋ２」の辺レコード５５ｂを取り出し、次の流出
辺８５ｂのデータが「ｎｕｌｌ」であるか否かを判定す
る。

【００８６】ステップ１７０５で次の流出辺８５のデー
タが「ｎｕｌｌ」でない場合には、スタッカに次の流出
辺８５のデータを保管し（ステップ１７０６）、当該辺
の抽出フラグを「オン」にする（ステップ１７０７）。
ここで、スタッカとは内部メモリ等である。ステップ１
７０５で、次の流出辺８５のデータが「ｎｕｌｌ」であ
る場合には、直接ステップ１７０７に進む。

【００８７】例えば、起点として入力したマンホールｍ
１は頂点であるため、頂点ｍ１の第１流出辺７３ａのデ
ータ「ｋ２」の辺レコード５５ｂを取り出し、次の流出
辺８５ｂにはデータ「ｋ４」が存在するので、「ｋ４」
のデータをスタッカに保管し、当該辺である「ｋ２」の
抽出フラグ９９を「オン」、例えば「１」にする。

【００８８】次に、当該辺の下流側頂点のレコードを取
り出し（ステップ１７０８）、当該頂点の抽出フラグを
オンにする（ステップ１７０９）。そして、当該頂点の
第１流出辺７３のデータを取り出し（ステップ１７１
０）、第１流出辺７３のデータが「ｎｕｌｌ」であるか
否かを判定する（ステップ１７１１）。

【００８９】第１流出辺７３のデータが「ｎｕｌｌ」で
ある場合には、スタッカにデータがあるか否かを判定す
る（ステップ１７１２）。スタッカにデータがある場合
には、当該辺データを取り出し（ステップ１７１３）、
ステップ１７０５に戻る。第１流出辺７３のデータが
「ｎｕｌｌ」の場合には、処理を終了する。

【００９０】例えば、当該辺である「ｋ２」の抽出フラ
グを「１」とし、「ｋ２」の下流側頂点９１ｂのデータ
「ｍ２」を取り出し、その頂点レコード５１ｂにおいて
抽出フラグ７９を「１」とし、第１の流出辺７３ｂのデ
ータが「ｎｕｌｌ」でなく、データ「ｋ６」が存在する
ことが確認される。

【００９１】次に、ステップ１７０５に戻り、「ｋ６」
の辺レコード５５ｆを取り出し、次の流出辺８５ｆのデ
ータ「ｋ７」をスタッカに保管し、当該辺となる「ｋ
６」の抽出フラグを「１」とする。「ｋ６」の下流側頂
点９１ｆのデータは「ｎｕｌｌ」であるため、ステップ
１７１１における第１の流出辺７３のデータも「ｎｕｌ
ｌ」となり、次にスタッカに保管したデータに対して同
様の処理を行う。

【００９２】このとき、スタッカには「ｋ４」及び「ｋ
７」のデータが保管されており、それぞれの抽出フラグ
を「１」する。尚、「ｋ４」、「ｋ７」の下流側頂点９
１及びその頂点における次の流出辺７３のデータはいず
れも「ｎｕｌｌ」であるため、処理を終了する。このよ
うに下流追跡フローに従って、頂点ｍ１に異物が混入し
た場合に、辺ｋ２、ｋ４、ｋ６、ｋ７及び頂点ｍ２が抽
出される。

【００９３】上流追跡についても図１５とほぼ同様であ
る。すなわち、ステップ１７０４およびステップ１７１
０における「第１流出辺７３」の代わりに「第１流入辺
７５」、ステップ１７０５およびステップ１７０６にお
ける「次の流出辺８５」の代わりに「次の流入辺８３」
と変更すれば、上流追跡の方法となる。

【００９４】以上のような上下流追跡によって抽出した
辺及び頂点は図１に示すホストコンピュータ３や端末側
コンピュータ５のディスプレイ上で色を変えて表示する
などによって、一目で作業者に提示することが可能であ
る。

【００９５】本実施の形態によれば、図１に示す端末側
コンピュータ５より起点を指示すると、ホストコンピュ
ータ３において図５に示す全ての作業及び追跡作業が行
われるが、このとき作業はホストコンピュータ３のメモ
リ上で行われるため、追跡作業は非常に迅速に行われ
る。従って、ホストコンピュータ３は、マンホールデー
タ３５と管データ４５のみを保持すればよい。

【００９６】また、図５に示すステップ５０３におい
て、全ての管渠に対する上流側頂点及び下流側頂点を仮
想マンホールとして考慮することにより、正真マンホー
ルに登録されていないマンホールが存在した場合でも検
索することが可能である。

【００９７】また、本実施の形態によれば、管渠あるい
はマンホールに変更や追加があった場合には、データベ
ース７に保管される管データ４５あるいはマンホールデ
ータ３５を変更、追加するだけでよく、管理が容易であ
る。また、図１に示す地形データ１１が領域毎に分割さ
れて管理されていても、本実施の形態による効果は変わ
らない。

【００９８】また、本実施の形態においては、マンホー
ルｍ１、ｍ２、………および管渠ｋ１、ｋ２、………を
含む頂点リスト５３および辺リスト５７の作成が済んで
から、マンホールｍ１、ｍ２、………と、上流頂点ｋｕ
１、ｋｕ２、………、下流頂点ｋｄ１、ｋｄ２、………
との統合を行なうものとしたが、管渠ｋ１、ｋ２、……
…のデータ作成の都度に、統合処理を行なってもよい。

【００９９】また、本実施の形態においては、マンホー
ルｍ１、ｍ２、………の頂点データ５１ａ、５１ｂ、…
……のうち次の入力頂点７７ａ、７７ｂ、………のデー
タは、マンホールデータ３５の順番のままであるものと
したが、別の順番を決めてもよい。管渠ｋ１、ｋ２、…
……についても同様である。

【０１００】また、本実施の形態においては、マンホー
ルデータ３５および管データ４５が既にデータベースに
保管されているものとして説明したが、ネットワーク図
などから頂点番号あるいは辺番号とともに接続関係を逐
次入力して頂点リスト５３および辺リスト５７を作成す
るものとしてもよい。

【０１０１】

【発明の効果】以上、詳細に説明したように、本発明に
よれば、上下水道などの頂点と辺とで構成される方向を
有するネットワークにおいて、頂点や辺のデータから効
率良く上下流追跡作業を行うことができる。

【図面の簡単な説明】

【図１】本発明の実施の形態に係るネットワーク検索
システム１を示す図

【図２】下水配管図（マンホール管渠グラフ）３１の
模式図

【図３】マンホールデータ３５のデータフォーマット
を示す図

【図４】管データ４５のデータフォーマットを示す図

【図５】管渠の接続関係を求める方法を示すフローチ
ャート

【図６】頂点レコード５１のデータフォーマットを示
す図

【図７】頂点リスト５３を示す図

【図８】マンホールデータ３５から頂点リスト５３を
作成する方法を示すフローチャート

【図９】辺レコード５５のデータフォーマットを示す
図

【図１０】辺リスト５７を作成する方法を示すフロー
チャート

【図１１】下水配管図（マンホール管渠グラフ）３１
の模式図

【図１２】仮想マンホールを含む頂点リスト５３およ
び辺リスト５７の内容を示す図

【図１３】管渠の流出入関係を明確化した頂点リスト
５３及び辺リスト５７を作成する方法を示すフローチャ
ート

【図１４】複数の流出辺が存在する場合の頂点リスト
５３及び辺リスト５７を作成する方法を示すフローチャ
ート

【図１５】複数の流入辺が存在する場合の頂点リスト
５３及び辺リスト５７を作成する方法を示すフローチャ
ート

【図１６】管渠の流出入関係を明確化した頂点リスト
５３および辺リスト５７の内容を示す図

【図１７】下流追跡の処理を示すフローチャート

【符号の説明】

１……ネットワーク検索システム１３……ホストコンピュータ５……端末側コンピュータ７……データベース１５……ＣＤ−ＲＯＭ３５……マンホールデータ４５……管データ５１……頂点レコード５３……頂点リスト５５……辺レコード５７……辺リスト

Claims

【特許請求の範囲】

【請求項１】複数の頂点が辺によって接続されたネッ
トワークで、前記辺の両端の座標と流れ方向を示すデータを少なくと
も有する辺データと、前記頂点の座標を有する頂点デー
タと、を有するデータベースと、前記各頂点に接続する辺へのリンク情報を示す頂点リス
トを作成する手段と、前記各辺の上流または下流頂点へのリンク情報を示す辺
リストを作成する手段と、前記辺データの両端を頂点リストに追加する手段と、前記頂点リストに前記追加された辺データの上流側また
は下流側の一端と前記頂点とが一致すれば、この頂点に
接続する辺のリンク情報を当該辺とし、この辺の上流頂
点または下流頂点へのリンク情報を当該頂点とする手段
と、を具備することを特徴とするネットワーク追跡用データ
作成装置。
【請求項２】複数の頂点が辺によって接続されたネッ
トワークで、前記辺の両端の座標と流れ方向を示すデータを少なくと
も有する辺データと、前記頂点の座標を有する頂点デー
タと、を有するデータベースと、前記各頂点の流出辺へのリンク情報を示す頂点リストを
作成する手段と、前記各辺の下流頂点へのリンク情報を示す辺リストを作
成する手段と、前記辺データの両端を頂点リストに追加する手段と、前記頂点リストに前記追加された辺データの上流側の一
端と前記頂点とが一致すれば、この頂点の流出辺のリン
ク情報を当該辺とし、この辺の上流頂点へのリンク情報
を当該頂点とする手段と、を具備することを特徴とするネットワーク追跡用データ
作成装置。
【請求項３】複数の頂点が辺によって接続されたネッ
トワークで、前記辺の両端の座標と流れ方向を示すデータを少なくと
も有する辺データと、前記頂点の座標を有する頂点デー
タと、を有するデータベースと、前記各頂点の流入辺へのリンク情報を示す頂点リストを
作成する手段と、前記各辺の上流頂点へのリンク情報を示す辺リストを作
成する手段と、前記辺データの両端を頂点リストに追加する手段と、前記頂点リストに前記追加された辺データの下流側の一
端と前記頂点とが一致すれば、この頂点の流入辺のリン
ク情報を当該辺とし、この辺の下流頂点へのリンク情報
を当該頂点とする手段と、を具備することを特徴とするネットワーク追跡用データ
作成装置。
【請求項４】請求項１記載のネットワーク追跡用デー
タ作成装置において、前記辺リスト、前記頂点リスト及
び前記各リンク情報を保持する手段を更に具備すること
を特徴とするネットワーク追跡用データ作成装置。
【請求項５】請求項２記載のネットワーク追跡用デー
タ作成装置において、前記辺リスト、前記頂点リスト及
び前記各リンク情報を保持する手段を更に具備すること
を特徴とするネットワーク追跡用データ作成装置。
【請求項６】請求項３記載のネットワーク追跡用デー
タ作成装置において、前記辺リスト、前記頂点リスト及
び前記各リンク情報を保持する手段を更に具備すること
を特徴とするネットワーク追跡用データ作成装置。
【請求項７】請求項２記載のネットワーク追跡用デー
タ作成装置で作成されたデータを用いてネットワークを
追跡するネットワーク追跡装置であって、（ａ）ある頂点を指定すると、頂点リストの流出辺への
リンク情報を参照して、この頂点に対する流出辺を算出
し、（ｂ）算出された流出辺に対して、辺リストの下流頂点
へのリンク情報を参照してこの辺に対する下流側の頂点
を算出し、（ｃ）（ａ）〜（ｂ）を繰り返すことによって下流追跡
を行うことを特徴とするネットワーク追跡装置。
【請求項８】請求項３記載のネットワーク追跡用デー
タ作成装置で作成されたデータを用いてネットワークを
追跡するネットワーク追跡装置であって、（ａ）ある頂点を指定すると、頂点リストの流入辺への
リンク情報を参照して、この頂点に対する流入辺を算出
し、（ｂ）算出された流入辺に対して、辺リストの上流頂点
へのリンク情報を参照してこの辺に対する上流側の頂点
を算出し、（ｃ）（ａ）〜（ｂ）を繰り返すことによって上流追跡
を行うことを特徴とするネットワーク追跡装置。
【請求項９】前記辺は、管路、開渠、暗渠、電線、輸
送路を含むことを特徴とする請求項１から請求項３のい
ずれかに記載のネットワーク追跡用データ作成装置。
【請求項１０】請求項７記載のネットワーク追跡装置
において、算出された流出辺及び下流側頂点を色を変え
て表示することを特徴とするネットワーク追跡装置。
【請求項１１】請求項８記載のネットワーク追跡装置
において、算出された流入辺及び上流側頂点を色を変え
て表示することを特徴とするネットワーク追跡装置。
【請求項１２】請求項７または請求項８記載のいずれ
かのネットワーク追跡装置において、更に地形データを
重ねて表示することを特徴とするネットワーク追跡装
置。
【請求項１３】複数の頂点が辺によって接続されたネ
ットワークで、前記辺の両端の座標と流れ方向を示すデータを少なくと
も有する辺データと、前記頂点の座標を有する頂点デー
タと、を有するデータベースと、前記各頂点に接続する辺へのリンク情報を示す頂点リス
トを作成する工程と、前記各辺の上流または下流頂点へのリンク情報を示す辺
リストを作成する工程と、前記辺データの両端を頂点リストに追加する工程と、前記頂点リストに前記追加された辺データの上流側また
は下流側の一端と前記頂点とが一致すれば、この頂点に
接続する辺のリンク情報を当該辺とし、この辺の上流頂
点または下流頂点へのリンク情報を当該頂点とする工程
と、を具備することを特徴とするネットワーク追跡用データ
作成方法。
【請求項１４】複数の頂点が辺によって接続されたネ
ットワークで、前記辺の両端の座標と流れ方向を示すデータを少なくと
も有する辺データと、前記頂点の座標を有する頂点デー
タと、を有するデータベースと、前記各頂点の流出辺へのリンク情報を示す頂点リストを
作成する工程と、前記各辺の下流頂点へのリンク情報を示す辺リストを作
成する工程と、前記辺データの両端を頂点リストに追加する工程と、前記頂点リストに前記追加された辺データの上流側の一
端と前記頂点とが一致すれば、この頂点の流出辺のリン
ク情報を当該辺とし、この辺の上流頂点へのリンク情報
を当該頂点とする工程と、を具備することを特徴とするネットワーク追跡用データ
作成方法。
【請求項１５】複数の頂点が辺によって接続されたネ
ットワークで、前記辺の両端の座標と流れ方向を示すデータを少なくと
も有する辺データと、前記頂点の座標を有する頂点デー
タと、を有するデータベースと、前記各頂点の流入辺へのリンク情報を示す頂点リストを
作成する工程と、前記各辺の上流頂点へのリンク情報を示す辺リストを作
成する工程と、前記辺データの両端を頂点リストに追加する工程と、前記頂点リストに前記追加された辺データの下流側の一
端と前記頂点とが一致すれば、この頂点の流入辺のリン
ク情報を当該辺とし、この辺の下流頂点へのリンク情報
を当該頂点とする工程と、を具備することを特徴とするネットワーク追跡用データ
作成方法。
【請求項１６】請求項１３記載のネットワーク追跡用
データ作成方法において、前記辺リスト、前記頂点リス
ト及び前記各リンク情報を保持する工程を更に具備する
ことを特徴とするネットワーク追跡用データ作成方法。
【請求項１７】請求項１４記載のネットワーク追跡用
データ作成方法において、前記辺リスト、前記頂点リス
ト及び前記各リンク情報を保持する工程を更に具備する
ことを特徴とするネットワーク追跡用データ作成方法。
【請求項１８】請求項１５記載のネットワーク追跡用
データ作成方法において、前記辺リスト、前記頂点リス
ト及び前記各リンク情報を保持する工程を更に具備する
ことを特徴とするネットワーク追跡用データ作成方法。
【請求項１９】請求項１４記載のネットワーク追跡用
データ作成方法で作成されたデータを用いてネットワー
クを追跡するネットワーク追跡方法であって、（ａ）
ある頂点を指定すると、頂点リストの流出辺へのリンク
情報を参照して、この頂点に対する流出辺を算出し、（ｂ）算出された流出辺に対して、辺リストの下流頂点
へのリンク情報を参照してこの辺に対する下流側の頂点
を算出し、（ｃ）（ａ）〜（ｂ）を繰り返すことによって下流追跡
を行うことを特徴とするネットワーク追跡方法。
【請求項２０】請求項１５記載のネットワーク追跡用
データ作成方法で作成されたデータを用いてネットワー
クを追跡するネットワーク追跡方法であって、（ａ）
ある頂点を指定すると、頂点リストの流入辺へのリンク
情報を参照して、この頂点に対する流入辺を算出し、（ｂ）算出された流入辺に対して、辺リストの上流頂点
へのリンク情報を参照してこの辺に対する上流側の頂点
を算出し、（ｃ）（ａ）〜（ｂ）を繰り返すことによって上流追跡
を行うことを特徴とするネットワーク追跡方法。
【請求項２１】前記辺は、管路、開渠、暗渠、電線、
輸送路を含むことを特徴とする請求項１３から請求項１
５のいずれかに記載のネットワーク追跡用データ作成方
法。
【請求項２２】請求項１９記載のネットワーク追跡装
置において、算出された流出辺及び下流側頂点を色を変
えて表示することを特徴とするネットワーク追跡方法。
【請求項２３】請求項２０記載のネットワーク追跡方
法において、算出された流入辺及び上流側頂点を色を変
えて表示することを特徴とするネットワーク追跡方法。
【請求項２４】請求項１９または請求項２０記載のい
ずれかのネットワーク追跡方法において、更に地形デー
タを重ねて表示することを特徴とするネットワーク追跡
方法。
【請求項２５】複数の頂点が辺によって接続されたネ
ットワークで、前記辺の両端の座標と流れ方向を示すデータを少なくと
も有する辺データと、前記頂点の座標を有する頂点デー
タと、を有するデータベースと、前記各頂点に接続する辺へのリンク情報を示す頂点リス
トを作成する手段と、前記各辺の上流または下流頂点へのリンク情報を示す辺
リストを作成する手段と、前記辺データの両端を頂点リストに追加する手段と、前記頂点リストに前記追加された辺データの上流側また
は下流側の一端と前記頂点とが一致すれば、この頂点に
接続する辺のリンク情報を当該辺とし、この辺の上流頂
点または下流頂点へのリンク情報を当該頂点とする手段
と、を具備するネットワーク追跡用データ作成装置として、
コンピュータを機能させるためのプログラムを記録した
記録媒体。
【請求項２６】複数の頂点が辺によって接続されたネ
ットワークで、前記辺の両端の座標と流れ方向を示すデータを少なくと
も有する辺データと、前記頂点の座標を有する頂点デー
タと、を有するデータベースと、前記各頂点の流出辺へのリンク情報を示す頂点リストを
作成する手段と、前記各辺の下流頂点へのリンク情報を示す辺リストを作
成する手段と、前記辺データの両端を頂点リストに追加する手段と、前記頂点リストに前記追加された辺データの上流側の一
端と前記頂点とが一致すれば、この頂点の流出辺のリン
ク情報を当該辺とし、この辺の上流頂点へのリンク情報
を当該頂点とする手段と、を具備するネットワーク追跡用データ作成装置として、
コンピュータを機能させるためのプログラムを記録した
記録媒体。
【請求項２７】複数の頂点が辺によって接続されたネ
ットワークで、前記辺の両端の座標と流れ方向を示すデータを少なくと
も有する辺データと、前記頂点の座標を有する頂点デー
タと、を有するデータベースと、前記各頂点の流入辺へのリンク情報を示す頂点リストを
作成する手段と、前記各辺の上流頂点へのリンク情報を示す辺リストを作
成する手段と、前記辺データの両端を頂点リストに追加する手段と、前記頂点リストに前記追加された辺データの下流側の一
端と前記頂点とが一致すれば、この頂点の流入辺のリン
ク情報を当該辺とし、この辺の下流頂点へのリンク情報
を当該頂点とする手段と、を具備するネットワーク追跡用データ作成装置として、
コンピュータを機能させるためのプログラムを記録した
記録媒体。
【請求項２８】請求項２５記載の記録媒体において、
前記辺リスト、前記頂点リスト及び前記各リンク情報を
保持する手段を更に具備するネットワーク追跡用データ
作成装置として、コンピュータを機能させるためのプロ
グラムを記録した記録媒体。
【請求項２９】請求項２６記載の記録媒体において、
前記辺リスト、前記頂点リスト及び前記各リンク情報を
保持する手段を更に具備するネットワーク追跡用データ
作成装置として、コンピュータを機能させるためのプロ
グラムを記録した記録媒体。
【請求項３０】請求項２７記載の記録媒体において、
前記辺リスト、前記頂点リスト及び前記各リンク情報を
保持する手段を更に具備するネットワーク追跡用データ
作成装置として、コンピュータを機能させるためのプロ
グラムを記録した記録媒体。
【請求項３１】請求項２６記載のネットワーク追跡用
データ作成装置で作成されたデータを用いて、（ａ）ある頂点を指定すると、頂点リストの流出辺への
リンク情報を参照して、この頂点に対する流出辺を算出
し、（ｂ）算出された流出辺に対して、辺リストの下流頂点
へのリンク情報を参照してこの辺に対する下流側の頂点
を算出し、（ｃ）（ａ）〜（ｂ）を繰り返すことによって下流追跡
を行うように、コンピュータを機能させるためのプログ
ラムを記録した記録媒体。
【請求項３２】請求項２７記載のネットワーク追跡用
データ作成装置で作成されたデータを用いて、（ａ）ある頂点を指定すると、頂点リストの流入辺への
リンク情報を参照して、この頂点に対する流入辺を算出
し、（ｂ）算出された流入辺に対して、辺リストの上流頂点
へのリンク情報を参照してこの辺に対する上流側の頂点
を算出し、（ｃ）（ａ）〜（ｂ）を繰り返すことによって上流追跡
を行うように、コンピュータを機能させるプログラムを
記録した記録媒体。
【請求項３３】前記辺は、管路、開渠、暗渠、電線、
輸送路を含むことを特徴とする請求項２５から請求項２
７のいずれかに記載の記録媒体。
【請求項３４】請求項３１記載の記録媒体において、
算出された流出辺及び下流側頂点を色を変えて表示する
ように、コンピュータを機能させるためのプログラムを
記録した記録媒体。
【請求項３５】請求項３２記載の記録媒体において、
算出された流入辺及び上流側頂点を色を変えて表示する
ように、コンピュータを機能させるためのプログラムを
記録した記録媒体。
【請求項３６】請求項３１または請求項３２記載の記
憶媒体において、更に地形データを重ねて表示するよう
に、コンピュータを機能させるためのプログラムを記録
した記録媒体。