Help us understand the problem. What is going on with this article?

pgRoutingをはじめて使ってみた

More than 1 year has passed since last update.

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

aosho235
1981年生まれ。駅すぱあとの会社で新規サービスを開発しています。好きなものはOS~ミドルウェアのレイヤー、開発を楽にするためのツールやフレームワークの整備、自分自身が便利だと思うものを作ること。
https://aosho235.com/
val
経路検索システム「駅すぱあと」をはじめ、全国のデータと高い信頼性をベースにさまざまなサービスを展開。
https://www.val.co.jp/
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
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  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
ユーザーは見つかりませんでした