Skip to content

CHANGELOG.md

Latest commit

 

History

History
170 lines (143 loc) · 7.87 KB

CHANGELOG.md

File metadata and controls

170 lines (143 loc) · 7.87 KB
Raw

Changelog

All notable changes to this project are documented in this file. The format is based on Keep a Changelog, and this project adheres to Semantic Versioning.

[1.7.2] - 2026-05-25

Changed (performance — no API change)

  • Rewritten integer-indexed search engine. DijkstraSearch, DijkstraRun and the A* family now resolve vertex names to dense integer indices once per search and relax over flat int-indexed slices (no per-edge map lookups or string churn), walk a cached CSR integer adjacency that is reused across searches and rebuilt only on structural edits, reuse the priority queue and per-vertex scratch between searches, and reset stale state in O(1) via a generation counter instead of clearing every vertex.
  • Result on a 4-connected grid (BenchmarkScale, vs v1.7.1): ~2.5–3× faster with ~half the memory and a flat 7–9 allocations per search at any size — e.g. 25,600-vertex Dijkstra 12.8 ms → 4.89 ms (−62 %), 64 KB → 32 KB (−50 %); 25,600-vertex A* 868 µs → 366 µs (−58 %), 23 KB → 7.5 KB (−68 %).
  • Public API, results (same shortest paths and costs), and the documented post-search StVertex / shortest-path-tree state are unchanged. The verbose Debug(true) trace is now a post-search tree dump rather than a per-step log.

This engine was selected by benchmarking five independently implemented optimization candidates back-to-back and keeping the one best on both speed and memory.

[1.7.1] - 2026-05-25

Added

  • Graph / path display helpers — no need to loop and print yourself. Show(w io.Writer) and ShowDijkstra(w io.Writer) write the graph (or its post-search state) to any writer; ShowFunc(w, line func(StVertex) string) does the same with a caller-supplied per-vertex formatter (nil uses the exported DefaultVertexLine). PathString([]StPath) string renders a returned path as "A -> B -> C (cost 6)".
  • Package doc (doc.go), runnable programs under example/ (dijkstra, astar, compare), where compare prints a Dijkstra-vs-A* time / vertices-expanded table.

Changed

  • Print and PrintDijkstra are now thin shorthands for Show(os.Stdout) / ShowDijkstra(os.Stdout). Output content is the same but uses \n line endings (was \r\n) and now marks one-way edges.
  • Docs: the package comment, README and examples now cover A* (shipped in v1.7.0) and broader shortest-path / pathfinding keywords; removed a stale note that claimed A* was "not yet built in".

No breaking API changes.

[1.7.0] - 2026-05-25

Added

  • A* search. New AStarSearch(from, to) and AStarSearchFunc(from, to, h) return the same optimal path as DijkstraSearch but goal-directed: they stop at the goal and, guided by a heuristic, expand far fewer vertices. AStarSearch uses a built-in straight-line EuclideanHeuristic over each vertex's X/Y; AStarSearchFunc takes a custom HeuristicFunc (func(curX, curY, goalX, goalY float64) float64) — nil means Euclidean, and a heuristic that always returns 0 makes A* behave exactly like Dijkstra.
  • The built-in heuristic is admissible/consistent when edge weights are spatial distances (the geometric/AGV case), so A* returns a provably shortest path. Supply your own heuristic (e.g. Manhattan on a 4-connected grid) for other metrics.

On a 32×32 grid, a mid-range query expanded 81 vertices vs Dijkstra's 1,024 (~12× faster). Worst case (corner-to-corner, loose heuristic) is within ~5% of Dijkstra. The existing Dijkstra API and results are unchanged; the shared path-reconstruction was refactored into a common helper.

1.6.0 - 2026-05-24

Changed (performance)

  • The blocked-vertex set is now a map[string]struct{} instead of a slice, making the per-edge "is blocked?" check O(1). Searches on large graphs with many blocked vertices are dramatically faster (≈6–7× on a 10,000-vertex grid with ~10% blocked: ~43 ms → ~6 ms).
  • The priority queue is now a binary min-heap (O(log n) push/pop) that reuses its backing array, replacing the O(n)-insert sorted slice whose dequeue reslicing caused heavy reallocation. Allocation per search is far lower and flat with size (e.g. at 10,000 vertices ≈ 1.5 MB → 64 KB per search), which keeps GC pauses small. Equal-weight entries are still dequeued in insertion order. Trade-off: very small graphs (tens of vertices) are marginally slower in raw CPU but allocate less.

All public APIs and search results are unchanged.

1.5.1 - 2026-05-24

Fixed

  • LICENSE now matches the canonical MIT text exactly. The previous file had a slightly reworded warranty-disclaimer paragraph that pkg.go.dev's license detector did not recognise (0% match), so the rendered documentation was suppressed with "Documentation not displayed due to license restrictions." No code change.

1.5.0 - 2026-05-24

Added

  • Dynamic vertex blocking. Blocking is now evaluated on each search rather than baked into edge weights at VertexAdd time, so VertexBLock / VertexBLockLoad / VertexBLockRemove / VertexBLockClear take effect on the next DijkstraSearch and may be called at any time (before or after VertexAdd). A blocked vertex is treated as unreachable; you can still route out of one if it is the search's start.
  • Dynamic graph editing: VertexRemove (removes a vertex plus every edge into or out of it and drops it from the blocked set), VertexAddEdge (adds an outgoing edge to an existing vertex), and VertexRemoveEdge (removes one edge).
  • Tests for dynamic blocking and editing; statement coverage now ~71%.

Fixed

  • Legitimately long paths are no longer misreported as "no path." The previous implementation rejected any path whose cumulative cost reached the internal 1e7 blocking sentinel; that sentinel has been removed.

Changed (behavioural)

  • Edges into a blocked vertex no longer carry an inflated weight, so EdgeGetWeight reports the weight you supplied. The public API is unchanged and correctly-built graphs return the same paths; this is called out because the project pre-v1.0-style sentinel behaviour is gone. (Safe to adopt: no known external users yet.)

1.4.0 - 2026-05-24

Added

  • Native fuzz target FuzzDijkstraSearch checking that a search never panics, is deterministic, and returns a path with non-negative, non-decreasing cumulative cost from source to destination.
  • Benchmark BenchmarkDijkstraSearch over 4-connected grid graphs.
  • GitHub Actions CI (build + vet + tests across Go 1.18/1.21/stable on Linux, macOS and Windows; a race+coverage job; and a gofmt check).
  • Tests for previously uncovered public API (VertexLength, VertexSetXY, VertexToStPath, EdgeExist, EdgeGetWeight, DistanceCMToVertex, VertexBLockClear). Statement coverage 57% → 68%.

Changed

  • Performance: vertex lookup is now O(1) via an internal map[string]int name index instead of an O(V) linear scan. A search is roughly 4–40× faster (the gap widening with graph size), with far fewer allocations. No API change.
  • Path reconstruction no longer prepends on every step (which was O(path²) slice copying); it now appends and reverses once.
  • Debug-path string building is skipped entirely unless Debug(true) is set, removing per-search allocations on the hot path.

Fixed

  • VertexAdd now rejects (returns false) any vertex whose edges include a negative weight, instead of silently producing an incorrect shortest path. Dijkstra's algorithm requires non-negative weights.

[1.3.0] and earlier

See the Git history.