.
.
.
..
.
.
.
地理情報システム特論
第 8 回：グラフ
大沢 裕
埼玉大学
.
Ohsawa (Saitama Univ.)
GIS-8
1 / 38
GIS-8
2 / 38
.
. .1 グラフの種類
.
. .2 グラフの表現
.
. .3 最短経路探索
.
. .4 グラフ分割とマテリアライズ化
.
. .5 面の記述に用いられる表現
.
Ohsawa (Saitama Univ.)
.
グラフの種類
グラフの種類
D
D
E
C
E
C
G
C
G
F
Cήะࠣࡈ
㧡
Dะࠣࡈ
F
㧠
D
㧡
E
㧢 㧤
G
㧠
㧟
F
E㊀ߺઃ߈ࠣࡈ
単純グラフ：2 つの頂点間に高々1 つの辺しか存在しない
多重グラフ：2 つの頂点間に複数の辺が存在する
ループグラフ：1 つの頂点を始終点とするループが存在する
完全グラフ：頂点が全ての他の頂点と辺で結ばれている
.
Ohsawa (Saitama Univ.)
GIS-8
3 / 38
グラフの種類
グラフでの用語の定義
完全グラフにおいて頂点数を |V |，辺の数を |E | とするとき，次式が
成り立つ．
( )
|V |
|V |(|V | − 1)
|E | =
=
= O(|V |2 )
(1)
2
2
あるグラフ G = (V , E ) に対して，G ′ = (V ′ , E ′ ) (但し，V ′ ⊆ V ,
E ′ ⊆ E ) が成り立つとき，G ′ を G の部分グラフと呼ぶ．
2 頂点 vi ，vj について，辺 (vi , vj ) が E に含まれるとき，この 2 つの
頂点は隣接しているという．
ある頂点 v に接続する辺の数を，その頂点の次数という．
.
Ohsawa (Saitama Univ.)
GIS-8
4 / 38
.
グラフの表現
グラフの表現
隣接行例：要素数は，O(|V |2 )
隣接リスト：要素数は，O(|V | + |E |)
CDEFG
C
D
D
C
E
G
E
E
D
F
G
F
F
E
G
G
C
D
C
D
G
ޓC㓞ធⴕ
.
Ohsawa (Saitama Univ.)
G
E
F
D㓞ធࠬ࠻
GIS-8
5 / 38
グラフの表現
隣接リストの管理 (1)
経路探索では隣接リストにより，直接接続しているノードとその
ノードへの距離を得る
例
ノード A に直接隣接しているノードは，B∼E の４つ．
ノード A に関しては下右図の隣接リストが作られる．
.
Ohsawa (Saitama Univ.)
GIS-8
㞄᥋䝜䞊䝗
㊥㞳
B
300
C
250
D
330
E
340
6 / 38
.
グラフの表現
隣接リストの管理 (2)
隣接リストは通常 2 次記憶上に置かれる（アクセス速度が遅い）
複数のノードの隣接リストをブロック化し，必要なブロックを主記
憶中のバッファに読み込み参照する．
バッファ内のどのレコードに注目ノードの隣接リストが存在するか
高速に決定する必要がある．
点の位置に対する順序付けが必要になる．
.
Ohsawa (Saitama Univ.)
GIS-8
7 / 38
グラフの表現
点に対する順序付け
䝷䝇䝍䞊䝇䜻䝱䞁
.
Ohsawa (Saitama Univ.)
Z䝇䜻䝱䞁
Peano-Hilbert䝇䜻䝱䞁
GIS-8
8 / 38
.
グラフの表現
バッファーの LRU 管理
Aho らの論文（Principles of Optimal Page Replacement, JACM,
1971）以来，多くの研究が行われている．
基本方式は，LRU や Clock，しかしキャッシュ高速化に関しては予測
に基づく方法なども研究されている．
バッファーを参照したらチェックを入
れる．
空きブロックが必要になったとき，
clock が巡回し，チェックが入っていれ
ば外し，次を調べる．
チェックが無いブロックを発見したと
き，それを返す．
次回の空き検出は，前回の次の位置か
ら探し始める．
.
Ohsawa (Saitama Univ.)
GIS-8
9 / 38
グラフの表現
グラフの巡回
グラフ G において，v1 と vn を結ぶ辺路
((v1 , v2 ), (v2 .v3 , . . . , (vn−1 , vn )) が存在するとき，頂点列
(v1 , v2 , . . . , vn ) を v1 から vn への道 (path) と呼ぶ．
v1 = vn の道を閉路と呼ぶ．
閉路において全ての頂点が異なるものをサイクルと呼ぶ．
次のような目的でグラフの探索が必要になる．
2 頂点間のパスを求めたい
2 頂点間の最短路を求めたい
経路探索の方法
幅優先探索
深さ優先探索
最適優先探索
.
Ohsawa (Saitama Univ.)
GIS-8
10 / 38
.
グラフの表現
グラフ探索の基本処理
step1 集合 R と集合 F を用意し，それらを空にする
step2 探索の開始点となる頂点 Vs を集合 R に入れる．
step3 集合 R が空でないうち，R から 1 つの要素 V を取り出し以
下の処理を実行する．
step3-1 V を集合 F に追加する．
step3-2 V に直接連結する頂点を全て求め，それらの内集合 F 中に
含まれないものを集合 R に追加する．
step3-3 (step3) に戻る．
step4 集合 F に含まれる要素が，頂点 Vs に連結する頂点である．
閉路が存在するとき，その閉路を構成する辺を 1 回のみたどる工夫
が必要：集合 F の役割
集合 R の構成により次の探索が行える
深さ優先探索：スタック
幅優先探索：キュー
最適優先探索：プライオリティーキュー
.
Ohsawa (Saitama Univ.)
GIS-8
11 / 38
グラフの表現
幅優先探索：キューを使用
E
F
H
G
D
.
Ohsawa (Saitama Univ.)
対象頂点
a
b
e
c
d
GIS-8
キューの内容
b,e
e,c
c,d
d
-
集合 F の内容
a
a,b
a,b,e
a,b,e,c
a,b,e,c,d
12 / 38
.
グラフの表現
深さ優先探索：スタックを使用
E
F
H
G
対象頂点
a
b
c
d
e
D
.
Ohsawa (Saitama Univ.)
スタックの内容
b,e
c,e
d,e
e
-
集合 F の内容
a
a,b
a,b,c
a,b,c,d
a,b,c,d,e
GIS-8
13 / 38
最短経路探索
最短経路探索
J
K
H
I
5
C
F
G
D
'
E
代表的なアルゴリズム
Dijkstra アルゴリズム
A*アルゴリズム
.
Ohsawa (Saitama Univ.)
GIS-8
14 / 38
.
最短経路探索
Dijkstra アルゴリズムと A*アルゴリズム
探索始点（赤）から目的地（緑）を目指してノード（交差点）をた
どる．
ノード同士の隣接関係は隣接リストで管理する．
.
Ohsawa (Saitama Univ.)
GIS-8
15 / 38
最短経路探索
Dijkstra アルゴリズム
検索に用いるレコー
ド:< cost, Ncur , Nprev >
Algorithm 1 Dijkstra’s algorithm
J
1: R.enqueue(< 0, s, − >)
2: F = ∅
3: while R ̸= ∅ do
4:
r = R.dequeue()
5:
if r .Ncur == d then
6:
break
7:
end if
8:
if r .Ncur ∈ F then
9:
continue;
10:
end if
11:
N = neighbor (r .Ncur )
12:
for each v ∈ N do
13:
d(v ) = d(r .cost) + dist(r .Ncur , v )
14:
R.enqueue(< d(v ), v , r .Ncur >)
15:
end for
16:
F = F ∪ {r .Ncur }
17: end while
K
H
I
C
5
F
G
D
'
E
集合 R:次に展開するノードを提供．PQ で構成 (最適優先探索)
集合 F:1 度展開したノードを入れる
.
Ohsawa (Saitama Univ.)
GIS-8
16 / 38
.
最短経路探索
最短路の復元
集合 F を用いて，目的地から出発地に向けてレコードを探しつつたどる．
J
ののみ．まず，Ncur が E のレコードを
探し，その Nprev が Ncur になっている
レコードを Ncur が S になるまでたどる．
H
C
I
.
集合 F の内容．但し，説明に必要なも
K
5
D
cost
0
4
7
10
F
G
'
E
Ohsawa (Saitama Univ.)
Ncur
S
e
d
E
Nprev
s
e
d
GIS-8
17 / 38
最短経路探索
A*アルゴリズム
最適優先探索を用いる
時間を尺度とするときには，最も速い手段での移動時間をヒューリ
スティクスに用いる
h(p, E ) は，dN (p, E ) の下限値でなければならない．即ち，
h(p, E ) ≤ dN (p, E )
距離による最短路探索では，h(p, E ) に dE (p, E ) を用いる
F
5R
f (n) = dN (S, p) + h(p, E )
5
.
Ohsawa (Saitama Univ.)
GIS-8
R
J
R' '
18 / 38
.
最短経路探索
最短路探索高速化の工夫
連結リストによる最短路探索方式
Dijkstra’s algorithm
A* algorithm
双方向探索
道路階層による距離のマテリアライズ化
高速道路，国道，一般道，など道路属性による分割とマテリアライ
ズ化
一般にカーナビなどで用いられている
グラフ分割による距離のマテリアライズ化
HEPV(hierarchical encoded path view)
HiTi グラフ
.
Ohsawa (Saitama Univ.)
GIS-8
19 / 38
最短経路探索
双方向探索による最短路探索
始点と終点の両方から探索を開始することにより，最短路探索時間
を短縮できる．その際に，Dijkstra 法，A*アルゴリズムが共に利用
可能．
.
Ohsawa (Saitama Univ.)
GIS-8
20 / 38
.
グラフ分割とマテリアライズ化
最短パスのマテリアライズ化
Jing et al., 1998
.
Ohsawa (Saitama Univ.)
GIS-8
21 / 38
グラフ分割とマテリアライズ化
最短経路探索のための前処理
n1
n1
n1
n2
n3
n4
n5
n6
n7
6
3
6
9
14
19
4
7
5
11
16
3
6
11
16
12
8
13
n2
n3
n4
n5
n6
n7
2
3
3
3
3
3
n1
3
3
5
5
5
n2
6
4
5
4
4
n3
3
4
5
6
6
n4
6
7
3
6
6
n5
9
5
6
12
7
n6
14
11
11
8
6
n7
19
16
16
13
11
n2
1
n3
1
2
n4
3
3
3
n5
3
2
3
4
n6
4
5
4
4
5
n7
6
6
6
6
6
6
6
11
5
5
ノード数が N のとき，表のサイズは
O(N 2 )（但し，N は膨大）最短路の
探索は「次に訪れるノード」を次々
にたどればよい．2 ノード間の距離
は「距離」表で求まる．
.
Ohsawa (Saitama Univ.)
GIS-8
22 / 38
.
グラフ分割とマテリアライズ化
地図のカラーコーディング
Sakaranarayanan et al., 2005
n1
n1
.
n2
n3
n4
n5
n6
n7
2
3
3
3
3
3
n2
1
n3
1
2
3
3
5
5
5
4
5
4
4
n4
3
3
3
n5
3
2
3
4
5
6
6
6
n6
4
5
4
4
5
n7
6
6
6
6
6
6
次に訪れるノードは，位置的に相関
を持つ次に訪れるノードにより，地
図を色分けする同じ色のノードを
Morton block で記述 Morton block
は空間データ構造で管理最短経路の
他，k-NN，空間ジョインなど，多様
な探索を高速に実行できる
7
6
Ohsawa (Saitama Univ.)
GIS-8
23 / 38
グラフ分割とマテリアライズ化
部分グラフへの分割
F
6*
E
H
D
6*
F
G
G
E
I
D
K J
K
I
D
Ohsawa (Saitama Univ.)
6*
J
6*
.
H
6*
E
GIS-8
24 / 38
.
グラフ分割とマテリアライズ化
分割グラフのマテリアライズ化
D
E
D
F
E
G G
F
H H
6*
6*
6*
D
E
○：内部ノード
●：境界ノード
.
Ohsawa (Saitama Univ.)
GIS-8
25 / 38
グラフ分割とマテリアライズ化
距離表
D I
J
E
f
g
h
.
a
3
7
10
K
b
6
2
5
F
a
b
c
d
e
c
5
9
12
Ohsawa (Saitama Univ.)
G
H
d
8
4
7
e
12
8
5
a
b
c
d
e
f
g
h
GIS-8
a
0
9
8
11
15
b
9
0
11
6
10
c
8
11
0
13
17
d
11
6
13
0
4
e
15
10
17
4
0
a
b
c
d
e
f
g
h
0
9
8
11
15
3
7
10
9
0
11
6
10
5
2
5
8
11
0
13
17
6
9
13
11
6
13
0
4
8
4
7
15
10
17
4
0
12
8
5
3
6
5
8
12
0
4
7
7
2
9
4
8
4
0
3
10
5
12
7
5
7
3
0
26 / 38
.
グラフ分割とマテリアライズ化
探索に用いるデータ形式
< p, Cost, dfs, fSG , phase >
p: currently noticed node (s or bi ∈ BVs )
Cost: dN (s, p) + dE (p, d)
dfs: dN (s, p)
fSG : sub-graph ID in which p belong
phase: a value to show the progress of the processing (between
PHASE0 (initial state) to PHASE 3 (final state))
.
Ohsawa (Saitama Univ.)
GIS-8
27 / 38
グラフ分割とマテリアライズ化
Phase 0
V
G
for all bi ∈ BVs do
Cost = dE (s, bi ) + dE (bi , d)
r =< bi , Cost, 0, SGs , PHASE 0 >
EnQueue r
end for
.
Ohsawa (Saitama Univ.)
GIS-8
28 / 38
.
グラフ分割とマテリアライズ化
Phase 1
V
G
E
dequeue e from PQ
Cost = e.dfs + dN (p, e.p) + dE (e.p, d)
r =< e.p, Cost, e.dfs + dN (p, e.p), SGn , PHASE 1 >
EnQueue r
.
Ohsawa (Saitama Univ.)
GIS-8
29 / 38
グラフ分割とマテリアライズ化
Phase 2
V
G
E
dequeue e from PQ
for all bi ∈ BVn do
Cost = e.dfs + dN (p, bi ) + dE (bi , d)
r =< e.p, e.dfs + dE (e.p, d), e.dfs, e.fSG , PHASE 2 >
EnQueue r
end for
.
Ohsawa (Saitama Univ.)
GIS-8
30 / 38
.
グラフ分割とマテリアライズ化
Phase 2 Cont.
V
E
G
E
dequeue e from PQ
if e.fSG = SGd then
Cost = e.dfs + dE (e.p, d)
r =< e.p, e.dfs + dE (e.p, d), e.dfs, SGd , PHASE 2 >
EnQueue r
end if
.
Ohsawa (Saitama Univ.)
GIS-8
31 / 38
グラフ分割とマテリアライズ化
Phase 3
V
E
G
E
dequeue e from PQ
Cost = e.dfs + dN (p, bi ) + dN (bi , d)
r =< e.p, e.dfs + dN (e.p, d), e.dfs, SGd , PHASE 3 >
EnQueue r
.
Ohsawa (Saitama Univ.)
GIS-8
32 / 38
.
グラフ分割とマテリアライズ化
距離とルートの決定法
s から SGs のボーダーノード及び d から SGd のボーダーノードへの
距離の決定法
SPFLM: 隣接リストを用いた A*アルゴリズム
SPFMM: IBDT
SPFFM: NNDT
部分グラフ内の境界ノード間の最短経路の決定法
SPFLM: 隣接リストを用いた A*アルゴリズム
SPFMM: 隣接リストを用いた A*アルゴリズム
SPFFM: NNDT
.
Ohsawa (Saitama Univ.)
GIS-8
33 / 38
グラフ分割とマテリアライズ化
各表のサイズの例
.
map name
MapS
MapM
MapL
# of nodes
16,284
109,373
465,245
# of links
24,914
81,233
638,282
map name
MapS
MapM
MapL
PWA*
1.5
6.8
39.7
SPFLM
2.6
11.3
65.8
Ohsawa (Saitama Univ.)
area size
168 km2
284 km2
3,797 km2
Adj. List
1.5MB
6.8MB
39.7MB
SPFMM
6.7
28.7
166.6
GIS-8
BBDT
1.1MB
4.5MB
26.1MB
SPFFM
14.5
70.1
400.0
IBDT
4.1MB
17.4MB
100.8MB
HEPV
30.1
376.1
8,287.6
NNDT
13.4MB
65.6MB
373.8MB
Next Hop
13.4
65.6
373.8
34 / 38
.
グラフ分割とマテリアライズ化
最短路探索性能の比較 (1)
0.2
A*
HEPV
SPFSM
SPFLM
Processing Time (s)
0.15
0.1
0.05
0
0
.
5
10
dist (km)
Ohsawa (Saitama Univ.)
15
20
GIS-8
35 / 38
グラフ分割とマテリアライズ化
最短路探索性能の比較 (2)
1
3
A*
SPFSM
SPFLM
0.4
0.2
2
1.5
1
0.5
0
4
3
2
1
0
0
0.001
A*
SPFSM
SPFLM
5
Processing Time (s)
Processing Time (s)
Processing Time (s)
0.6
6
A*
SPFSM
SPFLM
2.5
0.8
0.01
0.001
Prob
0.01
Prob
(a) MapS
(b) MapM
0.0001
0.001
Prob
(c) MapL
0.3
SPFLM(150)
SPFSM(150)
SPFLM(240)
SPFSM(240)
SPFLM(320)
SPFSM(320)
SPFLM(800)
SPFSM(800)
Processing Time (s)
0.25
0.2
0.15
0.1
0.05
0
0.001
0.01
Prob
.
Ohsawa (Saitama Univ.)
GIS-8
(d) Subgraph
size
36 / 38
.
グラフ分割とマテリアライズ化
公共交通における最短経路
⊒
%
&
〝✢㧞
dc: ノード C における
最短経路推定値
⌕
#
〝✢㧝
$
lB→C ： バスを用いて
B から C へ移動する
時間
dC = dB + lB→C
lB→C = rB→C + wB→C
rB→C ： B から C への
バスでの移動時間
〝✢㧞
&
'
%
.
wB→C ： C における待
ち時間
(
#
〝✢㧝
$
)
ᓤᱠߦࠃࠆ⒖േ
*
〝✢㧟
Ohsawa (Saitama Univ.)
GIS-8
37 / 38
面の記述に用いられる表現
2 重連結辺リスト (DCEL)
Table: Preparata-Shamos の DCEL 表現
C
G
G
G̉
G̉
G̉
G
D
G̉
G
G
E
G̉
F
#
1
2
3
4
5
V1
a
b
a
a
c
V2
b
c
c
d
d
F1
1
1
1
0
2
F2
0
0
2
2
0
P1
3
1
4
1
3
P2
2
5
2
5
4
頂点の集合を V = v1 , . . . , vn ，辺の集合を E = e1 , . . . , em とするとき，このグラ
フを，H[1..n]，VERTEX [1..2m]，NEXT [1..2m] の 3 つの表で表現する
H[1..n] は，頂点 vj に接続する辺を，反時計回りに並べたリストの最初の要素へ
のポインタからなる配列である．そのリストの要素は，VERTEX [1..2m] と
NEXT [1..2m] で構成される．つまり，(VERTEX [i], NEXT [i]) で辺を構成する．
.
Ohsawa (Saitama Univ.)
GIS-8
38 / 38
© Copyright 2024 ExpyDoc
