Example_test.go

// SPDX-License-Identifier: MIT
// Copyright (c) 2026 MaIII Themd

package dijkstra_test

import (
	"fmt"

	dijkstra "github.com/ultramcu/go-dijkstra"
)

func ExampleStGraph_DijkstraSearch() {
	var g dijkstra.StGraph

	// A directed graph:
	//
	//   A --1--> B --2--> C
	//   |                  ^
	//   +---------5--------+   (direct A->C, but slower)
	g.VertexAdd("A", 0, 0, 0,
		dijkstra.StEdge{ToVertexName: "B", Weight: 1, IsOneWay: true},
		dijkstra.StEdge{ToVertexName: "C", Weight: 5, IsOneWay: true},
	)
	g.VertexAdd("B", 1, 0, 0,
		dijkstra.StEdge{ToVertexName: "C", Weight: 2, IsOneWay: true},
	)
	g.VertexAdd("C", 2, 0, 0)

	ok, path := g.DijkstraSearch("A", "C")
	if !ok {
		fmt.Println("no path")
		return
	}
	for _, p := range path {
		fmt.Printf("%s (cost %.0f)\n", p.Name, p.Cost)
	}
	// Output:
	// A (cost 0)
	// B (cost 1)
	// C (cost 3)
}

// ExampleStGraph_AStarSearch finds the same shortest path as
// DijkstraSearch but goal-directed, using the built-in straight-line
// heuristic over the vertices' (X, Y) coordinates.
func ExampleStGraph_AStarSearch() {
	var g dijkstra.StGraph

	// Vertices on a line at x = 0,1,2,3. Edge weights equal the
	// straight-line distance, so the built-in heuristic is admissible.
	// A direct S->T hop exists but is slower than going via A, B.
	g.VertexAdd("S", 0, 0, 0,
		dijkstra.StEdge{ToVertexName: "A", Weight: 1, IsOneWay: true},
		dijkstra.StEdge{ToVertexName: "T", Weight: 5, IsOneWay: true},
	)
	g.VertexAdd("A", 1, 0, 0, dijkstra.StEdge{ToVertexName: "B", Weight: 1, IsOneWay: true})
	g.VertexAdd("B", 2, 0, 0, dijkstra.StEdge{ToVertexName: "T", Weight: 1, IsOneWay: true})
	g.VertexAdd("T", 3, 0, 0)

	ok, path := g.AStarSearch("S", "T")
	if !ok {
		fmt.Println("no path")
		return
	}
	for _, p := range path {
		fmt.Printf("%s (cost %.0f)\n", p.Name, p.Cost)
	}
	// Output:
	// S (cost 0)
	// A (cost 1)
	// B (cost 2)
	// T (cost 3)
}

// ExampleStGraph_VertexBLock shows dynamic blocking: a vertex blocked at
// runtime makes the next search reroute around it.
func ExampleStGraph_VertexBLock() {
	var g dijkstra.StGraph
	g.VertexAdd("A", 0, 0, 0,
		dijkstra.StEdge{ToVertexName: "C", Weight: 1, IsOneWay: true},
		dijkstra.StEdge{ToVertexName: "B", Weight: 1, IsOneWay: true},
	)
	g.VertexAdd("B", 0, 0, 0, dijkstra.StEdge{ToVertexName: "D", Weight: 5, IsOneWay: true})
	g.VertexAdd("C", 0, 0, 0, dijkstra.StEdge{ToVertexName: "D", Weight: 1, IsOneWay: true})
	g.VertexAdd("D", 0, 0, 0)

	show := func(path []dijkstra.StPath) {
		out := ""
		for i, p := range path {
			if i > 0 {
				out += " -> "
			}
			out += p.Name
		}
		fmt.Println(out)
	}

	// Cheapest route is via C.
	_, path := g.DijkstraSearch("A", "D")
	show(path)

	// Block C at runtime; the next search reroutes via B.
	g.VertexBLock("C")
	_, path = g.DijkstraSearch("A", "D")
	show(path)

	// Output:
	// A -> C -> D
	// A -> B -> D
}