ランダムウォークをpostGISで実現できないかの検討(pgr_ksp()の利用)
上記のDBはpostGISで構成されており、ways, ways_vertices_pgr があり、SQLでダイクストラ計算が行えます。
ここで以下のようなステップを行うランダムウォークをpostGISを使ったpostgreSQLを使ってGo言語で作成してみました。
(Step.1) ランダムォークの終了地点は、天神駅とする
(Step.2) 出発地点を乱数デ適当に選んで下さい。出発地点は、天神駅から1km程度の地点を適当に抽出する
(Step.3)天神駅の座標から最も近いNode(以下、これを天神ノードといいます)と、出発地点から最も近いNode(以下、これを出発ノードと言います)を抽出する
(Step.4) 出発ノードと天神ノードを直線で繋いで、出発ノードから-90度から+90度の範囲のノードを一つ選ぶ
(Step.5)上記で見つかったノードを次の出発ノードとする。正し、すでに出発ノードとしたノードを、新しい出発ノードにはできないようにする
(Step.6)上記(Step.4)に戻って、天神ノードに到着するまで、出発ノードを更新し続ける。なお更新される出発ノードは全てノド番号と緯度と座標を表示させる
というようなアルゴリズムで、ランダムウォークを作ろうとしたのですが、ダメでした。
一言でいうと「どんつき」の路地に入る→袋小路に入ってしまって、そこで動けなくなるからです。
これを回避するアルゴリズムを考えるの面倒になって、pgr_ksp()を使うことにしました。
pgr_ksp()は、最短経路問題の1、2、3、4番目を出してくれるので、これで1000番目とかを仕えば、そこそこランダムウォークになるかな、と思いまして。
// G:\home\ebata\hakata\src\others\main25\main.go
package main
import (
"database/sql"
"encoding/csv"
"fmt"
"log"
"os"
_ "github.com/lib/pq"
)
const (
connStr = "user=postgres password=password host=127.0.0.1 port=15432 dbname=hakata_db sslmode=disable"
)
type PathResult struct {
PathID int
Node int
Lat float64
Lon float64
}
func main() {
// PostgreSQLデータベースへの接続
db, err := sql.Open("postgres", connStr)
if err != nil {
log.Fatal(err)
}
defer db.Close()
// すべてのパス結果を一度に取得
results, err := getPathResults(db)
if err != nil {
log.Fatal(err)
}
// 各パスIDの結果をCSVに保存
pathIDs := []int{1, 5, 10, 100, 1000, 10000}
for _, pathID := range pathIDs {
filename := fmt.Sprintf("path_id_%d.csv", pathID)
err := saveResultsToCSV(results, pathID, filename)
if err != nil {
log.Fatal(err)
}
}
fmt.Println("CSV files created successfully.")
}
// getPathResults すべてのパス結果を取得
func getPathResults(db *sql.DB) ([]PathResult, error) {
// クエリで指定のpath_idの結果をすべて取得
query := `
WITH ksp_result AS (
SELECT * FROM pgr_ksp(
'SELECT gid AS id, source, target, cost FROM ways',
35382, -- 出発ノードID
40922, -- 目的ノードID
10000, -- 上位10000本の経路を取得
false -- エッジの向きを考慮しない
)
)
SELECT ksp.path_id, ksp.node, ST_Y(wv.the_geom) AS lat, ST_X(wv.the_geom) AS lon
FROM ksp_result AS ksp
JOIN ways_vertices_pgr AS wv ON ksp.node = wv.id
WHERE ksp.path_seq > 0
ORDER BY ksp.path_id, ksp.path_seq;
`
// クエリの実行
rows, err := db.Query(query)
if err != nil {
return nil, err
}
defer rows.Close()
// 結果をメモリに保存
var results []PathResult
for rows.Next() {
var result PathResult
err := rows.Scan(&result.PathID, &result.Node, &result.Lat, &result.Lon)
if err != nil {
return nil, err
}
results = append(results, result)
}
return results, nil
}
// saveResultsToCSV 指定されたpath_idの結果をCSVに保存
func saveResultsToCSV(results []PathResult, pathID int, filename string) error {
// CSVファイルの作成
file, err := os.Create(filename)
if err != nil {
return err
}
defer file.Close()
writer := csv.NewWriter(file)
defer writer.Flush()
// CSVのヘッダーを作成
err = writer.Write([]string{"Node", "Latitude", "Longitude"})
if err != nil {
return err
}
// 結果をCSVに書き込む
for _, result := range results {
if result.PathID == pathID {
err := writer.Write([]string{
fmt.Sprintf("%d", result.Node),
fmt.Sprintf("%f", result.Lat),
fmt.Sprintf("%f", result.Lon),
})
if err != nil {
return err
}
}
}
return nil
}
1番目、10番目、1000番目を表示してみました。
まあ、ランダムウォークという感じではないですが、私たちが移動するときも、まあ、こんな感じだと思うので、とりあえずこれで進めようかなと思います。