pgRoutingのインストール

brew install pgroutingでもインストールできるっぽいけど、依存パッケージにgccなどがあって時間がかかりそうだったので、Dockerでサクっと。

cd
docker run -d --rm --name pgrouting -e POSTGRES_PASSWORD=test -p 5432:5432 -v $(pwd)/pgdata:/var/lib/postgresql/data starefossen/pgrouting

ホームディレクトリ下のpgdataにデータを保存させる

Dockerが起動したらpsqlで接続する:
パスワードはtest。

psql --host=localhost --user=postgres postgres

AWS RDSでpgRoutingを使う

RDSのpostgresはpgRoutingに対応しており、これだけで使えるようになるのでRDSでも良いかもしれない。

create extension postgis;
create extension pgrouting;

経路探索してみる

データベースを作成し、extensionを導入：

CREATE DATABASE d1;
\c d1
CREATE EXTENSION postgis;
CREATE EXTENSION pgrouting;

ダイクストラ法で経路探索してみる。
Wikipediaに載ってるこの無向グラフをedgesテーブルに投入する。

CREATE TABLE edges (id serial, source int, target int, cost int);
INSERT INTO edges (source, target, cost) VALUES (1, 2, 7), (1, 3, 9), (1, 6, 14), (2, 3, 10), (2, 4, 15), (3, 4, 11), (3, 6, 2), (4, 5, 6), (5, 6, 9);
SELECT seq, node, edge, cost FROM pgr_dijkstra('SELECT id, source, target, cost FROM edges', 1, 5, directed:=false);
 seq | node | edge | cost
-----+------+------+------
   1 |    1 |    2 |    9
   2 |    3 |    7 |    2
   3 |    6 |    9 |    9
   4 |    5 |   -1 |    0
(4 rows)

ちゃんと1→3→6→5という経路が求まっている。

pgr_dijkstraのリファレンス

もっと巨大なグラフで試したい

9th DIMACS Implementation Challenge: Shortest Paths
にあるgr.gzファイルが手頃な大きさ。権利はパブリックドメインと書いてある。
Distance graphは辺のコストが物理的な距離のもの、Travel time graphはコストが移動時間のもの。有向グラフっぽい。データの仕様はこちら
下記スクリプトでSQLへ変換できる：

#!/usr/bin/env ruby

filename = ARGV[0] || "USA-road-d.NY.gr"
table_name = "edges"

puts <<EOF
INSERT INTO #{table_name} (source, target, cost) VALUES
EOF

i = 0
IO.foreach(filename) do |line|
  a = line.split
  if i != 0
    print ","
  end
  if a[0] == "a"
    puts <<~EOF
    (#{a[1]}, #{a[2]}, #{a[3]})
EOF
    i += 1
  end
end

puts <<EOF
;
EOF

A*

pgRoutingでA*経路探索してみた