pgr_dijkstra()で、ダイクストラの順番を壊さずにルートの座標を得る方法(getDijkstraPath())

2022年9月29日2024年5月3日

以前、pgr_dijkstra()で、ダイクストラの順番が壊れる という内容で悩んでいて、最終的に、

utsu_tram_db3=# SELECT seq, source, edge, x1, y1 FROM pgr_dijkstra('SELECT gid as id, source, target, cost, reverse_cost FROM ways', 2, 59, directed:=false) a INNER JOIN ways b ON (a.edge = b.gid) ORDER BY seq;

で、順列を壊さないで、ダイクストラの表示ができる、ということを書きました。

pgr_dijkstra()で算出したノードの座標を得る方法

ところが、まだ、これでも問題が発生することが分かりました。

ノード1799からノード3342のルート計算を以下のようにやってみました。

kitaya_db=# SELECT seq, source, target, x1, y1,x2,y2, agg_cost FROM pgr_dijkstra('SELECT gid as id, source, target, length_m as cost cost, reverse_cost FROM ways', 3342, 1799, directed:=false) a INNER JOIN ways b ON (a.edge = b.gid) ORDER BY seq;

まあ、こんな感じで、sourceとx1,x2を追っていって、ラストのtargetとx2,y2を拾えば、いいと分かりましたので、これで大丈夫だろう、と思ってコーディングしていました。

ところが、このノード1799からノード3342を逆転させて、ノード3342からノード1799のルート計算を以下のようにやってみました。

kitaya_db=# SELECT seq, source, target, x1, y1,x2,y2, agg_cost FROM pgr_dijkstra('SELECT gid as id, source, target, length_m as cost  cost, reverse_cost FROM ways', 1799, 3342, directed:=false) a INNER JOIN ways b ON (a.edge = b.gid) ORDER BY seq;

と、こんな感じで、sourceが出発点にならずに、targetの方が正しい並びとなってしまっています。つまり、こんな感じ。

で、これがどっちで出てくるのか分からないので、以下のようにしました。

(1)最初のノードがsourceに出てきたら、sourceベースで読み出し、
(2)最初のノードがtargetに出てきたら、targetベースで読み出す

実装はこんな感じにしました。

type LocInfo struct {
	Lon    float64
	Lat    float64
	Source int
}

 

// 江端修正版
func getDijkstraPath(dbMap *sql.DB, locInfoStart, locInfoGoal ldarp.LocInfo) ([]ldarp.LocInfo, float64) {
	log.Println("getDijkstraPath", locInfoStart, locInfoGoal)

	var path []ldarp.LocInfo // 経路　（返り値の一つ目）
	var totalDistanceKm float64

	rowsDijkstra, errDijkstra := dbMap.Query(
		"SELECT seq,source, target, x1, y1, x2, y2, agg_cost FROM pgr_dijkstra('SELECT gid as id, source, target, length_m as cost FROM ways', $1::bigint , $2::bigint , directed:=false) a INNER JOIN ways b ON (a.edge = b.gid) ORDER BY seq",
		locInfoStart.Source,
		locInfoGoal.Source)

	if errDijkstra != nil {
		log.Fatal(errDijkstra)
	}
	defer rowsDijkstra.Close()

	var agg_cost float64

	isFirstCheck := true
	isSourceCheck := true

	for rowsDijkstra.Next() {

		var x1, y1, x2, y2 float64

		var seq int
		var target int

		// まずnodeを読む
		if err := rowsDijkstra.Scan(&seq, &source, &target, &x1, &y1, &x2, &y2, &agg_cost); err != nil {
			fmt.Println(err)
		}

		// 最初の1回だけ入る
		if isFirstCheck {
			if source == locInfoStart.Source {
				isSourceCheck = true
			} else {
				isSourceCheck = false
			}
			isFirstCheck = false
		}

		var loc ldarp.LocInfo

		if isSourceCheck {
			loc.Source = source
			loc.Lon = x1
			loc.Lat = y1
		} else {
			loc.Source = target
			loc.Lon = x2
			loc.Lat = y2
		}

		loc.Source = target

		path = append(path, loc)
	}

	// ラストノードだけは手入力
	path = append(path, locInfoGoal)

	totalDistanceKm = agg_cost / 1000.0
	return path, totalDistanceKm
}

もっとクールな方法があるかもしれませんが、面倒なので、戦うのはやめました。

バグを発見したので、main()を含めた再修正版をアップしておきまます。

package main

import (
	"database/sql"
	"fmt"
	"log"
	"m/src/ldarp"

	_ "github.com/lib/pq"
)

func main() {
	db, err := sql.Open("postgres",
		"user=postgres password=password host=192.168.0.23 port=15432 dbname=tomioka_db_c sslmode=disable")
	if err != nil {
		log.Fatal("OpenError: ", err)
	}
	defer db.Close()

	var a_Point, b_Point ldarp.LocInfo
	a_Point.Source = 20
	b_Point.Source = 1
	path, dist := getDijkstraPath(db, a_Point, b_Point)

	fmt.Println("path:", path)
	fmt.Println("dist:", dist)

}

// 江端再修正版
func getDijkstraPath(dbMap *sql.DB, locInfoStart, locInfoGoal ldarp.LocInfo) ([]ldarp.LocInfo, float64) {
	log.Println("getDijkstraPath", locInfoStart, locInfoGoal)

	var path []ldarp.LocInfo // 経路　（返り値の一つ目）
	var totalDistanceKm float64

	rowsDijkstra, errDijkstra := dbMap.Query(
		"SELECT seq,source, target, x1, y1, x2, y2, agg_cost FROM pgr_dijkstra('SELECT gid as id, source, target, length_m as cost cost, reverse_cost FROM ways', $1::bigint , $2::bigint , directed:=false) a INNER JOIN ways b ON (a.edge = b.gid) ORDER BY seq",
		locInfoStart.Source,
		locInfoGoal.Source)

	if errDijkstra != nil {
		log.Fatal(errDijkstra)
	}
	defer rowsDijkstra.Close()

	var agg_cost float64

	var loc ldarp.LocInfo
	var x1, y1, x2, y2 float64
	var seq int
	var target int
	var source int

	isFirstCheck := true
	isSourceCheck := true

	for rowsDijkstra.Next() {

		// まずnodeを読む
		if err := rowsDijkstra.Scan(&seq, &source, &target, &x1, &y1, &x2, &y2, &agg_cost); err != nil {
			fmt.Println(err)
		}

		// 最初の1回だけチェックのために入る これについては、https://wp.kobore.net/江端さんの技術メモ/post-7668/を参照のこと
		// もし rowsDijkstra.Scanで最初のsource値を読みとり、locInfoStart.Source の値と同じであれば、x1,y1をベースとして、異なる値であれば、x2,y2をベースとする

		if isFirstCheck {
			if source == locInfoStart.Source {
				isSourceCheck = true // x1, y1をベースとする処理になる
			} else {
				isSourceCheck = false // x2,y2をベースとする処理になる
			}
			isFirstCheck = false // 最初の1回をチェックすることで、2回目はこのループには入らなくなる
		}

		//var loc ldarp.LocInfo

		if isSourceCheck { // x1, y1をベースとする処理
			loc.Source = source
			loc.Lon = x1
			loc.Lat = y1
		} else { // x2,y2をベースとする処理
			loc.Source = target
			loc.Lon = x2
			loc.Lat = y2
		}
		path = append(path, loc)
	}

	// ラストノードだけは手入力 (ここは引っくり返す)
	if isSourceCheck { // x1, y1をベースとする処理
		loc.Source = target
		loc.Lon = x2
		loc.Lat = y2
	} else { // x2,y2をベースとする処理
		loc.Source = source
		loc.Lon = x1
		loc.Lat = y1
	}

	path = append(path, loc)

	totalDistanceKm = agg_cost / 1000.0
	return path, totalDistanceKm
}

で、色々問題が出てきたので、各種ケースに対応できるように追加したもの

/*
	c:\users\ebata\tomioka3b\src\others\main49.go

	このプログラムは、PostgreSQLデータベース内の地理情報を使用して最短経路を計算するためのものです。
	
	このプログラムは、以下の機能を持ちます。

	(1)main 関数内で、PostgreSQLデータベースへの接続情報を設定し、sql.Open を使用してデータベースに接続します。
	(2)getDijkstraPath 関数は、指定された始点から終点までの最短経路を計算するための関数です。この関数は、Dijkstraアルゴリズムを使用して最短経路を計算します。
	(3)LocInfo 構造体は、地理座標とノードの情報を表現します。
	(4)main 関数内で getDijkstraPath 関数を呼び出し、最短経路とその距離を計算します。異常ノードや隣接ノード、同一ノード、2つ離れたノードなど、さまざまなケースでの最短経路をテストするために、複数の呼び出しをコメントアウトしています。
	(5)getDijkstraPath 関数内では、まず指定された始点と終点に対応する地理座標を取得します。始点と終点が同一の場合は、指定されたノードの地理座標を取得します。
	(6)次に、pgr_dijkstra 関数を使用して最短経路を計算し、結果を取得します。結果は、各ノードの地理座標と距離が含まれる配列として返されます。
	(7)最後に、最短経路の全体距離を計算し、その結果を返します。


*/

package main

import (
	"database/sql"
	"fmt"
	"log"
	"os"

	_ "github.com/lib/pq"
)

type LocInfo struct {
	Lon    float64
	Lat    float64
	Source int
}

func main() {
	// PostgreSQLへの接続情報

	// Agent_od書き込み用テーブルの初期化
	db_agent_od, err := sql.Open("postgres",
		"user=postgres password=password host=192.168.0.23 port=15432 dbname=tomioka_db_e sslmode=disable") // トミオカート地図でテスト

	if err != nil {
		log.Fatal("OpenError: ", err)
	}
	defer db_agent_od.Close()

	route, dis := getDijkstraPath(db_agent_od, LocInfo{Source: 432}, LocInfo{Source: 1070}) // 異常ノード
	//route, dis := getDijkstraPath(db_agent_od, LocInfo{Source: 856}, LocInfo{Source: 688}) // 異常ノード

	//route, dis := getDijkstraPath(db_agent_od, LocInfo{Source: 723}, LocInfo{Source: 853}) // 隣接ノード
	//route, dis := getDijkstraPath(db_agent_od, LocInfo{Source: 536}, LocInfo{Source: 171}) // 隣接ノード

	//route, dis := getDijkstraPath(db_agent_od, LocInfo{Source: 536}, LocInfo{Source: 536}) // 同一ノード
	//route, dis := getDijkstraPath(db_agent_od, LocInfo{Source: 138}, LocInfo{Source: 139}) // 同一ノード
	//route, dis := getDijkstraPath(db_agent_od, LocInfo{Source: 173}, LocInfo{Source: 853}) // 2つ離れたノード
	fmt.Println("route", route, "dis", dis)

}

// テスト中
// 1行のみの場合、ヌルになるという問題と、同一ノードに対応するため
func getDijkstraPath(dbMap *sql.DB, locInfoStart, locInfoGoal LocInfo) ([]LocInfo, float64) {

	var path []LocInfo // 経路　（返り値の一つ目）
	var totalDistanceKm float64

	// 例外処理 locInfoStart.source == locInfoGoal.source の場合
	if locInfoStart.Source == locInfoGoal.Source {
		source := locInfoStart.Source

		// SQLクエリの作成
		query := fmt.Sprintf(`
		SELECT x1, y1
		FROM ways
		WHERE source = %d;
	`, source)

		// SQLクエリの実行
		var x1, y1 float64
		err := dbMap.QueryRow(query).Scan(&x1, &y1)
		if err != nil {
			log.Fatal(err)
		}

		var loc LocInfo
		loc.Source = source
		loc.Lon = x1
		loc.Lat = y1

		path = append(path, loc)

		totalDistanceKm = 0.0
		return path, totalDistanceKm
	}

	query := `
	SELECT seq, source, target, x1, y1, x2, y2, agg_cost 
	FROM pgr_dijkstra(
		'SELECT gid as id, source, target, length_m as cost FROM ways', 
		$1::bigint, 
		$2::bigint, 
		directed:=false
	) a 
	INNER JOIN ways b ON (a.edge = b.gid) 
	ORDER BY seq
	`
	//log.Println("getDijkstraPath", locInfoStart.Source, locInfoGoal.Source)

	rowsDijkstra, errDijkstra := dbMap.Query(query, locInfoStart.Source, locInfoGoal.Source)
	if errDijkstra != nil {
		log.Fatal(errDijkstra)
		os.Exit(1)
	}
	defer rowsDijkstra.Close()

	var agg_cost float64

	var loc LocInfo
	var x1, y1, x2, y2 float64
	var seq int
	var target int
	var source int

	isFirstCheck := true
	isSourceCheck := true

	count := 0

	for rowsDijkstra.Next() {
		// まずnodeを読む
		if err := rowsDijkstra.Scan(&seq, &source, &target, &x1, &y1, &x2, &y2, &agg_cost); err != nil {
			fmt.Println(err)
		}

		// 最初の1回だけチェックのために入る これについては、https://wp.kobore.net/江端さんの技術メモ/post-7668/を参照のこと
		// もし rowsDijkstra.Scanで最初のsource値を読みとり、locInfoStart.Source の値と同じであれば、x1,y1をベースとして、異なる値であれば、x2,y2をベースとする

		if isFirstCheck {
			if source == locInfoStart.Source {
				isSourceCheck = true // x1, y1をベースとする処理になる
			} else {
				isSourceCheck = false // x2,y2をベースとする処理になる
			}
			isFirstCheck = false // 最初の1回をチェックすることで、2回目はこのループには入らなくなる
		}

		//var loc LocInfo

		if isSourceCheck { // x1, y1をベースとする処理
			loc.Source = source
			loc.Lon = x1
			loc.Lat = y1
		} else { // x2,y2をベースとする処理
			loc.Source = target
			loc.Lon = x2
			loc.Lat = y2
		}
		path = append(path, loc)

		count++
	}

	// ラストノードだけは手入力 (ここは引っくり返す)
	if isSourceCheck { // x1, y1をベースとする処理
		loc.Source = target
		loc.Lon = x2
		loc.Lat = y2
	} else { // x2,y2をベースとする処理
		loc.Source = source
		loc.Lon = x1
		loc.Lat = y1
	}

	fmt.Println("count", count)

	if count == 0 { // 1行のみの場合、ヌルになるという問題に対応するため、
		loc.Source = locInfoGoal.Source
		loc.Lon = locInfoGoal.Lon
		loc.Lat = locInfoGoal.Lat

		// 入力値の指定
		source := locInfoStart.Source
		target := locInfoGoal.Source

		// SQLクエリの作成
		query := fmt.Sprintf(`
		SELECT length_m, x1, y1, x2, y2
		FROM ways
		WHERE source = %d AND target = %d;
	`, source, target)

		// SQLクエリの実行
		var length float64
		var x1, y1, x2, y2 float64
		err := dbMap.QueryRow(query).Scan(&length, &x1, &y1, &x2, &y2)
		if err != nil {
			log.Println("First attempt failed. Retrying with swapped source and target.")
			// 入れ替えたsourceとtargetの値でクエリを再実行
			query = fmt.Sprintf(`
			SELECT length_m, x1, y1, x2, y2
			FROM ways
			WHERE source = %d AND target = %d;
		`, target, source)
			err = dbMap.QueryRow(query).Scan(&length, &x1, &y1, &x2, &y2)
			if err != nil {
				log.Fatal(err)
			}
		}

		// 結果の出力
		fmt.Printf("length_m: %f\n", length)
		fmt.Printf("source: %d\n", source)
		fmt.Printf("target: %d\n", target)
		fmt.Printf("x1: %f\n", x1)
		fmt.Printf("y1: %f\n", y1)
		fmt.Printf("x2: %f\n", x2)
		fmt.Printf("y2: %f\n", y2)

		if source == locInfoGoal.Source {
			loc.Lon = x1
			loc.Lat = y1
		} else {
			loc.Lon = x2
			loc.Lat = y2
		}

		agg_cost = length

		fmt.Println("loc", loc)
	}

	path = append(path, loc)

	totalDistanceKm = agg_cost / 1000.0
	return path, totalDistanceKm
}