4
Help us understand the problem. What are the problem?

More than 3 years have passed since last update.

posted at

updated at

Organization

pgRoutingをはじめて使ってみた

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テーブルに投入する。

image.png

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*経路探索してみた

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Sign upLogin
4
Help us understand the problem. What are the problem?