ランダムウォークをpostGISで実現できないかの検討(pgr_ksp()の利用)

2024年10月28日

上記の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番目を表示してみました。
まあ、ランダムウォークという感じではないですが、私たちが移動するときも、まあ、こんな感じだと思うので、とりあえずこれで進めようかなと思います。