Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
3
Help us understand the problem. What is going on with this article?
@aosho235

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

3
Help us understand the problem. What is going on with this article?
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
aosho235
1981年生まれ。駅すぱあとの会社で新規サービスを開発しています。好きなレイヤーはOS~ミドルウェア。好きなことは開発を楽にするためのツールやフレームワークの整備、自分自身が便利と思うものを作ること。新しいものを追うより、自分が自信を持って使える技術で効率的に開発するのが好き。そのため使うライブラリやサービスの挙動は仔細に把握しておきたいものです。
val
経路検索システム「駅すぱあと」をはじめ、全国のデータと高い信頼性をベースにさまざまなサービスを展開。

Comments

No comments
Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account Login
3
Help us understand the problem. What is going on with this article?