道路ネットワークのグラフ生成（OpenStreetMap）

こんにちは。
OpenStreetMap データを用いて、道路ネットワークの混合グラフの生成¹および各種機能を作りました。

• https://github.com/kkdd/GraphFromOSM

元々グラフ生成機能を持つオリジナル（https://github.com/MatveiT/GraphFromOSM ）がすでにあり、今回これに下記の機能を追加しました。どの機能も混合グラフ（directed と undirected edge が混在）に対処しています²。

• displayGraph(graph): 地図上可視化
• extractConnectedWith(graph, highway): 指定した highway タイプの道路およびそれにグラフ的に連結した部分を抽出
• simplifyGraph(graph): simplification³ すなわち interstitial degree-2 vertices の削除⁴
• dijkstra(source, destination, graph)⁵: 最短経路

地図上可視化例

高速道路（highway=motorway）に連結した道路の可視化例です⁶。連結対象は highway=motorway_link, service を指定しています⁷。また最短経路例を黄色線で表示しています。

console.log

The imported OSM data contains 1582029 nodes and 338083 ways.
The converted graph contains 608127 vertices and 461491 edges.
The simplified graph contains 566531 vertices and 419895 edges.
The extracted graph contains 6530 vertices and 8622 edges.
The shortest path has 160 edges

拡大表示

上記を拡大表示すると、interstitial degree-2 vertices が除去されており、また連結対象道路が抽出されていることが確認できます。

directed and undirected ways が混在する例

有向辺と無向辺を水色と緑色の線で区別していることが確認できます。

1. OpenStreetMap データモデルは、mixed multigraph と見なすことができます（directed and undirected ways が混在）。 ↩

2. 先行する実現例が見つからず今回自力で作りました。 ↩

3. 参考解説例：OSMnx: Python for Street Networks の中の "3. Correct and simplify network topology" ↩

4. directed edge に対しては simplification の削除対象は indegree 1 and outdegree 1 の vertex です。 ↩

5. 参考例：「Dijkstra 法（priority queue 付き Map 利用, Javascript）」 ↩

6. 参考例：「日本の高速道路を OSM データから抽出」 ↩

7. 今回 highway=service も対象としているため、これより広い領域のデータ取得は成功しませんでした。 ↩