2 dimensional bit vector approach Mikio Kubo. TIGER/Line graph DC.tmp 9559 nodes and 29818 arcs Shortest Paths between all border nodes of 2 regions.

Presentation on theme: "2 dimensional bit vector approach Mikio Kubo. TIGER/Line graph DC.tmp 9559 nodes and 29818 arcs Shortest Paths between all border nodes of 2 regions."— Presentation transcript:

1 2 dimensional bit vector approach Mikio Kubo

2 TIGER/Line graph DC.tmp 9559 nodes and 29818 arcs Shortest Paths between all border nodes of 2 regions

3 Source region border nodes (red) and other nodes (yellow)

4 Target region border nodes (red) and other nodes (yellow)

5 Connecting network

6 After concatenation of degree 2 nodes

7 After shrinking the nodes around the source and target regions By storing all shortest path length between transit (cut) nodes, the shortest path problem between 2 regions is reduced to the problem on the graph above.

8 TIGER/Line graph USA-road-d.NY 264346 nodes and 733846 arcs

9 degree frequency histogram [0, 28, 440, 32] Arcs on shortest paths between border nodes (red)

10 Connecting network and the graph after concatenation and shrinking the nodes in the regions

11 終点領域から遠い順に最短路を解き， 最短路木内の点を削除する（ 59 回解くべきところを 25 回に削減）

12 始点付近の拡大図

13 Implementation (Python +networkX)

14 Read data and construct graph n=len(x_cord) for i in range(n): # 点集合の追加 G.add_node(i) G.position[i]=(x_cord[i], y_cord[i]) m=len(edge_info) for (i,j,length) in edge_info: # 枝集合の追加 G.add_edge(i,j,length) from pylab import * from networkx import * # モジュールの読み込み G=XGraph() # グラフインスタンスの生成 G.position={} # 座標保管用の辞書 点の座標のリスト x_cord[],y_cord[] 枝情報 (i,j,length) のリスト edge_info[]

15 draw(G,G.position,node_size=1000/n,with_labels=None,width=1, node_color='b',edge_color='g') グラフの表示（ position 指定，サイズ 1000/n, ラベルなし，線幅 1 ，点色 b ，枝色 g ）

16 最大の連結成分の抽出 # グラフ G の最大の連結成分（ 0 番目）を H に入れる H=connected_component_subgraphs(G) [0] # 点の座標の更新 H.position={} for node in H.nodes_iter(): (x,y)=G.position[node] H.position[node]=(x,y) connected_component_subgraphs(G) は networkX の関数

17 バケット（ 2 次元格子）に点を入れる

18 バケットの準備 # 各バケットにおおよそ 100 の点を入れるようにバケット数を決 める n_bucket=int(sqrt(n/100)) # バケット (i,j) に所属する点のリストを準備 bucket=[ [ [] for i in range(n_bucket) ] for j in range(n_bucket) ] G.bucket={} # 点の所属するバケットを保管する辞書を準備 for node in G.nodes_iter(): (x,y)=G.position[node] i=int(x*n_bucket) j=int(y*n_bucket) bucket[i][j].append(node) # バケット (i,j) のリストに点を追加 G.bucket[node]=(i,j) # 辞書にバケット番号を保管

19 バケットの縁の点集合 # 縁の点集合を保管するリストの準備 border=[[[] for i in range(n_bucket)] for j in range(n_bucket)] for i in range(n_bucket): for j in range(n_bucket): if len(bucket[i][j])>0: # 空でないバケットに対して for node in bucket[i][j]: for n1 in G.neighbors(node): # 隣接点集合 （ networkX ） if G.bucket[node] <> G.bucket[n1]: # 隣接点が異なるバケットに含まれているなら # 縁の点集合に追加 border[i][j].append(node)

20 点の重複の除去 startnodes=set(border[start_i][start_j]) 開始バケット（ stgart_i,start_j) の縁の点集合の抽出 set() はリストから集合（重複がない要素の集まり）を抽出する関数

21 2 バケット間の最短路計算 paths=[] # パスを保管するリストの準備 for s in set(border[start_i][start_j]): #networkX の最短路は遅い ->BoostGraphLibrary(BGL) を利用 pred=BoostGraph.findAllShortestPath(s) for t in set(border[end_i][end_j]): dst=t ＃終点 t から最短路木を辿る sp = [dst] while s != dst: # 最短路木の前の点 pred へ移動 dst=BoostGraph.vertexesid[ pred[BoostGraph.vertexes[dst]] ] sp.append(dst) sp.reverse() # 終点からの点列を逆にす る paths.append(sp) # パスリストに追加

22 G.clear() # グラフのクリア for sp in paths: G.add_path(sp) # パスの追加 # ３倍の枝幅で描画 draw(G,G.position,node_size=1000/n,with_labels=None, width=3,node_color='b',edge_color='r')

23 点の次数のヒストグラム degseq=G.degree() # 次数を計算してリストを返す関数 dmax=max(degseq)+1 # 最大の次数を計算（ max は python の関 数） freq= [ 0 for d in range(dmax) ] # 頻度を保管するリストの準備 for d in degseq: freq[d] += 1 print "degree frequency histgram",freq 結果 degree frequency histgram [0, 39, 648, 97, 18]