Dijkstra.go

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

package dijkstra

import "fmt"

// DijkstraInit clears per-vertex Dijkstra state on every vertex
// (Visited, MaskSearch, Weight, Parent, and the per-edge isShort
// flag). The search engine resets its own working state on every call,
// so this is no longer required before a search; it remains for callers
// who want to explicitly clear the exported per-vertex fields.
func (g *StGraph) DijkstraInit() {
	g.mu.Lock()
	defer g.mu.Unlock()
	g.dijkstraInitLocked()
}

func (g *StGraph) dijkstraInitLocked() {
	for i := range g.vertex {
		g.vertex[i].Visited = false
		g.vertex[i].MaskSearch = false
		g.vertex[i].Weight = 0
		g.vertex[i].Parent = ""
		for j := range g.vertex[i].Edges {
			g.vertex[i].Edges[j].isShort = false
		}
	}
}

// DijkstraRun does the main relaxation pass starting from
// startVertex. After it returns, every reachable vertex has its
// Visited flag set, its cumulative Weight populated, its Parent
// pointer set, and the edges belonging to the shortest-path tree
// have their isShort flag set.
//
// Returns false only if startVertex doesn't exist in the graph.
func (g *StGraph) DijkstraRun(startVertex string) bool {
	g.mu.Lock()
	defer g.mu.Unlock()
	return g.dijkstraRunLocked(startVertex)
}

func (g *StGraph) dijkstraRunLocked(startVertex string) bool {
	start := g.vertexFindLocked(startVertex)
	if start < 0 {
		return false
	}

	// Integer-indexed relaxation over reusable scratch (no per-edge name
	// lookups, no per-search allocation once warm), then mirror the result
	// into the exported StVertex / isShort fields so the documented
	// post-search state is preserved exactly. See search.go.
	g.searchBegin(len(g.vertex))
	g.runSearchLocked(int32(start), -1, nil) // -1: no early exit (full tree)
	g.reconcileLocked()

	if g.debugEn {
		g.debugDijkstraDump()
	}
	return true
}

// debugDijkstraDump prints the post-search shortest-path tree, replacing
// the verbose per-step trace the loop used to emit. Only called when Debug
// is enabled (no test depends on the exact text).
func (g *StGraph) debugDijkstraDump() {
	path := ""
	for _, ti := range g.search.touched {
		v := &g.vertex[ti]
		if v.Parent == "" {
			continue
		}
		path += " " + v.Name
		fmt.Printf("\t\tSet Weight on Vertex %s = %1.2f (parent %s)\r\n",
			v.Name, v.Weight, v.Parent)
	}
	fmt.Printf("End\r\n\r\nPath : %s\r\n", path)
}

// DijkstraSearch finds the shortest path from fromVertex to toVertex.
//
// On success returns ok = true and a slice of StPath nodes ordered
// from source to destination, with cumulative Cost on each entry.
// On failure (either endpoint missing, no path, or the only path
// crosses a blocked vertex) returns ok = false and a nil slice.
//
// Calling DijkstraSearch implicitly resets all per-vertex Dijkstra
// state on the graph. The graph's internal mutex is held for the
// full duration of the call, so concurrent calls on the same graph
// serialise (they remain safe -- no data races -- but do not run
// in parallel).
func (g *StGraph) DijkstraSearch(fromVertex, toVertex string) (bool, []StPath) {
	g.mu.Lock()
	defer g.mu.Unlock()

	if !g.vertexIsExistLocked(fromVertex) || !g.vertexIsExistLocked(toVertex) {
		return false, nil
	}

	if !g.dijkstraRunLocked(fromVertex) {
		return false, nil
	}

	if !g.vertexIsVisitedLocked(toVertex) {
		if g.debugEn {
			fmt.Printf("No path to target vertex\r\n")
		}
		return false, nil
	}

	ok, allPath := g.extractPathLocked(fromVertex, toVertex)
	if !ok {
		return false, nil
	}
	if g.debugEn {
		fmt.Printf("Path : %s\r\n", joinArrow(allPath))
	}
	return true, allPath
}

// extractPathLocked walks Parent pointers from toVertex back to
// fromVertex and returns the path in source->destination order, with
// each node's cumulative Cost. It assumes a completed search has
// populated Weight and Parent (DijkstraRun or aStarRunLocked), and
// that toVertex was reached. Returns false if the parent chain is
// broken before reaching the source.
//
// Nodes are appended destination-first (O(1) amortised) and the slice
// is reversed once at the end, rather than prepending each step (which
// would copy the whole slice every time, i.e. O(path^2)).
func (g *StGraph) extractPathLocked(fromVertex, toVertex string) (bool, []StPath) {
	var allPath []StPath
	name := toVertex
	for {
		ok, p := g.vertexToStPathLocked(name)
		if !ok {
			return false, nil
		}
		allPath = append(allPath, p)
		if name == fromVertex {
			break
		}
		next := g.vertexGetParentLocked(name)
		if next == "" || next == name {
			// Parent chain broken before reaching the source --
			// state is inconsistent; treat as no-path.
			return false, nil
		}
		name = next
	}
	for i, j := 0, len(allPath)-1; i < j; i, j = i+1, j-1 {
		allPath[i], allPath[j] = allPath[j], allPath[i]
	}
	return true, allPath
}

// joinArrow renders a path as "A -> B -> C" for debug logging.
func joinArrow(path []StPath) string {
	out := ""
	for i, p := range path {
		if i > 0 {
			out += " -> "
		}
		out += p.Name
	}
	return out
}