Skip to content

v0.11.0

Latest

Choose a tag to compare

@hmdsefi hmdsefi released this 17 Nov 17:34
062452d

This release adds AStar, Bidirectional, KShortest, Beam and NegativeCycle to the path package, with DijkstraPaths, BellmanFordPaths and BFSPaths to return the shortest paths themselves, and Bridges, ArticulationPoints and UndirectedCuts to find the edges and vertices that split an undirected graph. Every existing function and type keeps its signature.

go get github.com/hmdsefi/gograph@v0.11.0

Added

  • path.DijkstraPaths, path.BellmanFordPaths and path.BFSPaths return a
    path.ShortestPaths with the shortest path from one vertex to each vertex it
    reaches. Distance and PathTo report false for a vertex out of reach,
    where Dijkstra gives math.MaxFloat64 and BellmanFord +Inf.
    DijkstraPaths and BFSPaths read only what the start reaches and use O(V)
    extra space for it. On a graph of 10,000 vertices and 50,000 edges,
    DijkstraPaths takes 3.9 ms and 2.4 MB where Dijkstra takes 4.7 ms and
    2.7 MB, and 0.008 ms where the start reaches 100 of the vertices.
    BellmanFordPaths gives the distances and errors of BellmanFord, and its
    paths never loop when rounding makes a zero cycle look negative.
  • path.KShortest returns up to k cheapest simple paths from one vertex to
    another, cheapest first. It's Yen's algorithm with Lawler's change, and each
    branch search is A* guided by the exact cost to the goal, found once. It keeps
    at most k-1 candidate paths and skips a branch that can't beat the worst of
    them, so extra space is O(V+E+k·V). On a 100 by 100 grid, 100 paths take
    8 ms and 5 MB, where Dijkstra branch searches take 613 ms and an unbounded
    candidate list 8.4 MB.
  • path.Beam returns a path from one vertex to another, keeping at most
    width partial paths at each step, ranked by a caller-supplied score. A small
    width can miss the cheapest path. Extra space is O(L·width) for a path of L
    edges: the kept paths share their common starts, and a step never holds more
    than width candidates. On a graph of 30 layers of 300 vertices, width 100
    takes 48 ms and 0.19 MB, where sorting every candidate takes 121 ms and
    80 MB. The new path.ErrInvalidWidth reports a width below 1.
  • path.AStar returns the cheapest path from one vertex to another and its
    cost, stopping at the goal. The caller supplies the edge cost and a heuristic
    for the remaining cost. Extra space is O(V). A heuristic that isn't consistent
    still gives the cheapest path, in O(V²) expansions where plain A* can take
    exponentially many. On a 300 by 300 grid, a Manhattan-distance heuristic takes
    0.19 ms and 165 KB, where no heuristic takes 34 ms and 10.5 MB.
  • path.Bidirectional returns the cheapest path from one vertex to another
    and its cost, searching forward from the start and backward from the goal
    until they meet. A caller-supplied cost replaces the edge weight, and the
    new path.ErrUnreachable reports a goal the start can't reach.
  • path.NegativeCycle returns one cycle whose edge weights sum to less than
    zero, searching the whole graph.
  • connectivity.Bridges and connectivity.ArticulationPoints find the edges
    and vertices whose removal splits an undirected graph into more pieces, in
    O(V+E). gograph.UndirectedCuts returns both from one search. A directed
    graph returns the new gograph.ErrNotUndirected.

Changed

  • .agents/skills/gograph/SKILL.md has a row for each function added for
    v0.11.0 that had none: UndirectedCuts, and in path, DijkstraPaths,
    BFSPaths, BellmanFordPaths, NegativeCycle, AStar, Bidirectional,
    KShortest and Beam. The rows of path.Dijkstra, path.BellmanFord,
    path.DijkstraMultiSource and traverse.BFSWithDepth point to them.

Full Changelog: v0.10.0...v0.11.0