search

func AStar ¶

func AStar[W Weight](
	c *csr.CSR[W],
	src, dst graph.NodeID,
	h func(graph.NodeID) W,
) ([]graph.NodeID, W, error)

AStar computes a shortest path from src to dst on c, guided by the caller-supplied heuristic h. h must be admissible (h(n) is a lower bound on the true cost from n to dst) for optimality; if h is also consistent (h(u) <= w(u,v) + h(v) for every edge u->v) the search never re-expands a node. Admissibility and consistency are caller contracts; AStar does not validate them.

Returns the path from src to dst (inclusive) with the corresponding total cost, or ErrNoPath when dst is unreachable. Returns ErrNegativeWeight if any edge weight in c is strictly negative. For floating-point Weight types it validates that no edge weight is NaN or +/-Inf and returns ErrInvalidInput otherwise; integer Weight types skip that pass.

For hot loops, prefer the zero-allocation primitive AStarInto.

package main

import (
	"fmt"

	"github.com/FlavioCFOliveira/GoGraph/graph"
	"github.com/FlavioCFOliveira/GoGraph/graph/adjlist"
	"github.com/FlavioCFOliveira/GoGraph/graph/csr"
	"github.com/FlavioCFOliveira/GoGraph/search"
)

// buildWeighted assembles a CSR over int64-weighted edges and returns
// it together with the mapper. directed selects a directed graph; when
// false the AdjList mirrors every edge, yielding the symmetric CSR the
// undirected algorithms (Kruskal, Prim) expect.
func buildWeighted(directed bool, edges [][3]int) (*csr.CSR[int64], *graph.Mapper[int]) {
	a := adjlist.New[int, int64](adjlist.Config{Directed: directed})
	for _, e := range edges {
		_ = a.AddEdge(e[0], e[1], int64(e[2]))
	}
	return csr.BuildFromAdjList(a), a.Mapper()
}

// resolvePath maps a path expressed in NodeID space back to the
// user-facing int values, so output is stable regardless of the
// opaque NodeIDs the mapper assigns.
func resolvePath(m *graph.Mapper[int], path []graph.NodeID) []int {
	out := make([]int, len(path))
	for i, id := range path {
		out[i], _ = m.Resolve(id)
	}
	return out
}

func main() {
	c, m := buildWeighted(true, [][3]int{
		{0, 1, 10}, {0, 2, 3},
		{1, 3, 1},
		{2, 1, 4}, {2, 3, 8},
	})
	src, _ := m.Lookup(0)
	dst, _ := m.Lookup(3)

	// Zero heuristic: never overestimates the remaining cost.
	path, cost, err := search.AStar(c, src, dst, func(graph.NodeID) int64 { return 0 })
	if err != nil {
		fmt.Println("error:", err)
		return
	}
	fmt.Printf("path %v cost %d\n", resolvePath(m, path), cost)
}

Output:
path [0 2 1 3] cost 8

func AStarCtx ¶

func AStarCtx[W Weight](
	ctx context.Context,
	c *csr.CSR[W],
	src, dst graph.NodeID,
	h func(graph.NodeID) W,
) ([]graph.NodeID, W, error)

AStarCtx is the context-aware variant of AStar. ctx.Err() is checked every 4096 heap pops; on cancellation returns (nil, zero, wrapped ctx.Err()).

func AStarInto ¶

func AStarInto[W Weight](
	ctx context.Context,
	c *csr.CSR[W],
	src, dst graph.NodeID,
	h func(graph.NodeID) W,
	dist []W,
	parent []graph.NodeID,
	found []bool,
	path *[]graph.NodeID,
) (W, error)

AStarInto is the zero-allocation primitive behind AStar. The caller provides the dist, parent, and found scratch slices (each at least c.MaxNodeID()) and a path destination slice that is truncated and appended to. The returned cost matches AStar.

If any scratch slice is too small, ErrBufferTooSmall is returned.

Concurrency: the caller's buffers are written in-place; concurrent callers must supply separate buffers.

func BFS ¶

func BFS[W any](c *csr.CSR[W], src graph.NodeID, visit func(node graph.NodeID, depth int) bool)

BFS performs breadth-first traversal of c starting at src. The visit callback is invoked for every reached node in non-decreasing depth order, with depth starting at 0 for src; returning false from visit terminates the traversal early. The traversal visits each node at most once.

BFS is allocation-free on the hot path after the first call (working buffers are reused via sync.Pool). Memory consumption per call is bounded by O(maxFrontierWidth) instead of O(reachableSize) thanks to the wavefront design: the current level's nodes are consumed and the next level is built in a separate buffer; the two buffers swap per level.

package main

import (
	"fmt"

	"github.com/FlavioCFOliveira/GoGraph/graph"
	"github.com/FlavioCFOliveira/GoGraph/graph/adjlist"
	"github.com/FlavioCFOliveira/GoGraph/graph/csr"
	"github.com/FlavioCFOliveira/GoGraph/search"
)

// buildDirected assembles a directed, unweighted CSR from (src, dst)
// integer pairs and returns it together with the mapper that resolves
// NodeIDs back to the user-facing int values.
func buildDirected(edges [][2]int) (*csr.CSR[struct{}], *graph.Mapper[int]) {
	a := adjlist.New[int, struct{}](adjlist.Config{Directed: true})
	for _, e := range edges {
		_ = a.AddEdge(e[0], e[1], struct{}{})
	}
	return csr.BuildFromAdjList(a), a.Mapper()
}

func main() {
	// Chain: 0 -> 1 -> 2 -> 3.
	c, m := buildDirected([][2]int{{0, 1}, {1, 2}, {2, 3}})
	src, _ := m.Lookup(0)

	depth := map[int]int{}
	search.BFS(c, src, func(node graph.NodeID, d int) bool {
		v, _ := m.Resolve(node)
		depth[v] = d
		return true // keep traversing
	})

	for v := 0; v < 4; v++ {
		fmt.Printf("node %d at depth %d\n", v, depth[v])
	}
}

Output:
node 0 at depth 0
node 1 at depth 1
node 2 at depth 2
node 3 at depth 3

func BFSCtx ¶

func BFSCtx[W any](ctx context.Context, c *csr.CSR[W], src graph.NodeID, visit func(node graph.NodeID, depth int) bool) error

BFSCtx is the context-aware variant of BFS. ctx.Err() is checked once per BFS level; on cancellation the traversal returns the wrapped ctx.Err() without invoking visit on the partially-explored frontier.

func BFSDirectionOpt ¶

func BFSDirectionOpt[W any](c *csr.CSR[W], src graph.NodeID, visit func(node graph.NodeID, depth int) bool)

BFSDirectionOpt performs direction-optimising breadth-first search (Beamer, Asanovic, Patterson — SC 2012) over the symmetric adjacency captured by c. The algorithm dynamically switches between top-down (push, expand the current frontier forward) and bottom-up (pull, scan unvisited nodes and check whether any of their neighbours are in the frontier) phases based on the alpha threshold from the paper, giving 3-7x speedups on power-law graphs at the cost of one extra full scan per direction switch.

The implementation expects c to be symmetric (typical for undirected graphs built with [adjlist.Config.Directed]=false). For a directed graph callers should pre-build a symmetric CSR containing both edges and their reverses; the v1 algorithm does not maintain a separate in-edge CSR.

Memory: visited and frontier bitmaps and the cur/next list slices are acquired from a pool; in the steady state BFSDirectionOpt is zero-allocation per call.

func BellmanFordInto ¶

func BellmanFordInto[W Weight](
	ctx context.Context,
	c *csr.CSR[W],
	src graph.NodeID,
	dist []W,
	parent []graph.NodeID,
	found []bool,
) error

BellmanFordInto is the zero-allocation primitive behind BellmanFord. It writes single-source shortest-path results directly into the caller-provided slices, each of which must have length at least c.MaxNodeID(); otherwise it returns ErrBufferTooSmall. The slices are reset in-place before the traversal.

Concurrency: the caller's slices are written in-place; concurrent callers must supply separate buffers.

func BiBFS ¶

func BiBFS[W any](c *csr.CSR[W], src, dst graph.NodeID) ([]graph.NodeID, error)

BiBFS performs bidirectional breadth-first search from src to dst on the unweighted graph captured by c. For undirected graphs (a symmetric directed CSR) the same CSR feeds both the forward and reverse expansion; for directed graphs c must be paired with the reverse CSR via BiBFSOn.

Returns the shortest path from src to dst inclusive, or ErrNoPath when the two endpoints are not connected. The returned path length always equals the true unweighted shortest distance: BiBFS completes the current level expansion on the chosen side and picks the global minimum-total collision before terminating, so it never returns a strictly longer path because of neighbour iteration order.

The two frontiers expand alternately; the iteration always grows the smaller frontier next so the search space approximates O(b^(d/2)) instead of O(b^d) for forward-only BFS, where b is the branching factor and d is the path length.

func BiBFSCtx ¶

func BiBFSCtx[W any](ctx context.Context, c *csr.CSR[W], src, dst graph.NodeID) ([]graph.NodeID, error)

BiBFSCtx is the context-aware variant of BiBFS. ctx.Err() is checked at every alternation between the forward and backward frontier expansion; on cancellation returns (nil, wrapped ctx.Err()).

On undirected (symmetric) input it walks c in both directions; on directed input it builds the reverse CSR once and delegates to BiBFSOnCtx. The internal reverse build is O(V + E); callers running BiBFS many times on the same graph should hoist the build out via BiBFSOnCtx. The level-complete intersection rule documented on BiBFS is preserved.

func BiBFSOn ¶

func BiBFSOn[W any](c, rev *csr.CSR[W], src, dst graph.NodeID) ([]graph.NodeID, error)

BiBFSOn is BiBFS with a caller-provided reverse CSR. Required for directed graphs (where the symmetric closure differs from c) and recommended for any high-frequency caller — the O(V+E) reverse-CSR construction is hoisted out of the inner loop. The level-complete intersection rule documented on BiBFS is preserved.

func BiBFSOnCtx ¶

func BiBFSOnCtx[W any](ctx context.Context, c, rev *csr.CSR[W], src, dst graph.NodeID) ([]graph.NodeID, error)

BiBFSOnCtx is the context-aware variant of BiBFSOn. The level-complete intersection rule documented on BiBFS is preserved: after the first cross-frontier collision the loop performs at most one additional expansion on the opposite side and then commits to the global-minimum (forwardDepth + backwardDepth) meet recorded across both expansions.

func BidirectionalDijkstra ¶

func BidirectionalDijkstra[W Weight](c *csr.CSR[W], src, dst graph.NodeID) ([]graph.NodeID, W, error)

BidirectionalDijkstra computes a shortest path from src to dst in c using bidirectional Dijkstra: a forward search from src on the original CSR and a simultaneous reverse search from dst on the transposed CSR (csr.CSR.BuildReverse). Both searches relax non- negative edges with the same heap invariant as Dijkstra; the algorithm terminates when the minimum-key sum across both heaps reaches or exceeds the best meeting-edge cost seen so far.

For random-access graphs the asymptotic gain over one-way Dijkstra is roughly sqrt of the unidirectional ball, with concrete >2x speedups on road-network workloads (deep, low-degree shortest paths).

The reverse CSR is rebuilt internally; callers that issue many point-to-point queries on the same graph should hoist the build out of the hot loop with BidirectionalDijkstraOn.

Returns the path (inclusive of src and dst) and its total cost, ErrNoPath when no s-t path exists, or ErrNegativeWeight if c contains any negative-weight edge. For floating-point Weight types it validates that no edge weight is NaN or +/-Inf and returns ErrInvalidInput otherwise; integer Weight types skip that pass.

func BidirectionalDijkstraOn ¶

func BidirectionalDijkstraOn[W Weight](c, rev *csr.CSR[W], src, dst graph.NodeID) ([]graph.NodeID, W, error)

BidirectionalDijkstraOn is BidirectionalDijkstra with a pre- built reverse CSR. Use this when running many point-to-point queries on the same graph; the reverse-CSR construction is O(V+E) and is the only allocation outside the algorithm's working state.

func BidirectionalDijkstraOnCtx ¶

func BidirectionalDijkstraOnCtx[W Weight](ctx context.Context, c, rev *csr.CSR[W], src, dst graph.NodeID) ([]graph.NodeID, W, error)

BidirectionalDijkstraOnCtx is the context-aware variant of BidirectionalDijkstraOn. ctx.Err() is checked every 4096 heap pops; on cancellation returns (nil, zero, wrapped ctx.Err()).

func CountTriangles ¶

func CountTriangles[W any](c *csr.CSR[W]) (total int64, perNode []int64)

CountTriangles returns the total number of triangles in the undirected graph c, plus a per-NodeID count of how many triangles each vertex participates in. c is expected to be a symmetric directed CSR (each undirected edge appears as both (u, v) and (v, u)) — typical of [adjlist.AdjList] with Directed=false.

Algorithm ¶

The implementation is the node-iterator algorithm with degree ordering: at every vertex v we examine pairs of neighbours (u, w) only when both have a strictly higher canonical rank than v. Canonical rank breaks ties on raw NodeID, so each triangle is counted exactly once.

Complexity ¶

Time: O(sum over v of deg(v)^2 in the degree-ordered subgraph),

bounded by O(E * sqrt(E)) per Chiba & Nishizeki 1985.
For uniform-degree graphs this collapses to
O(E * d_avg); for power-law graphs the sqrt(E) bound
is tight.

Space: O(V) for the per-node count array plus O(d_max) scratch

for the per-vertex neighbour scan (reused across
vertices).

Streaming variant ¶

CountTriangles requires the full CSR in memory: the inner loop random-accesses neighbour lists of arbitrary vertices. A streaming variant for graphs that do not fit in RAM is not provided — the implementation cost is non-trivial (reservoir sampling à la TRIEST, or a wedge-based estimator) and no production caller has asked for it. If such a caller surfaces, the natural seam is in search/extern/triangles.go alongside the existing semi-external BFS and PageRank.

Concurrency: CountTriangles is safe to invoke concurrently on a shared CSR.

func CountTrianglesCtx ¶

func CountTrianglesCtx[W any](ctx context.Context, c *csr.CSR[W]) (total int64, perNode []int64, err error)

CountTrianglesCtx is the context-aware variant of CountTriangles. ctx.Err() is checked every 4096 outer-loop iterations; on cancellation returns (0, nil, wrapped ctx.Err()).

func DFS ¶

func DFS[W any](c *csr.CSR[W], src graph.NodeID, visit func(node graph.NodeID, depth int) bool)

DFS performs iterative depth-first traversal of c starting at src. The visit callback receives every reached node and its depth from src (depth=0 for src); returning false terminates the traversal early. The traversal is iterative (it uses an explicit stack) so graphs with arbitrarily long paths do not risk a Go goroutine stack overflow. Each node is visited at most once. Visitation order is deterministic for any given CSR (it follows the order in which out-neighbours appear in the underlying edges array).

DFS is allocation-free on the hot path after the first call.

package main

import (
	"fmt"

	"github.com/FlavioCFOliveira/GoGraph/graph"
	"github.com/FlavioCFOliveira/GoGraph/graph/adjlist"
	"github.com/FlavioCFOliveira/GoGraph/graph/csr"
	"github.com/FlavioCFOliveira/GoGraph/search"
)

// buildDirected assembles a directed, unweighted CSR from (src, dst)
// integer pairs and returns it together with the mapper that resolves
// NodeIDs back to the user-facing int values.
func buildDirected(edges [][2]int) (*csr.CSR[struct{}], *graph.Mapper[int]) {
	a := adjlist.New[int, struct{}](adjlist.Config{Directed: true})
	for _, e := range edges {
		_ = a.AddEdge(e[0], e[1], struct{}{})
	}
	return csr.BuildFromAdjList(a), a.Mapper()
}

func main() {
	// Chain: 0 -> 1 -> 2 -> 3.
	c, m := buildDirected([][2]int{{0, 1}, {1, 2}, {2, 3}})
	src, _ := m.Lookup(0)

	search.DFS(c, src, func(node graph.NodeID, d int) bool {
		v, _ := m.Resolve(node)
		fmt.Printf("visit %d (depth %d)\n", v, d)
		return true // keep traversing
	})
}

Output:
visit 0 (depth 0)
visit 1 (depth 1)
visit 2 (depth 2)
visit 3 (depth 3)

func DFSCtx ¶

func DFSCtx[W any](ctx context.Context, c *csr.CSR[W], src graph.NodeID, visit func(node graph.NodeID, depth int) bool) error

DFSCtx is the context-aware variant of DFS. ctx.Err() is checked every 4096 frame pops; on cancellation the traversal returns the wrapped ctx.Err() without further visit invocations.

func Diameter ¶

func Diameter[W any](c *csr.CSR[W]) (lo, hi int, exact bool)

Diameter estimates the diameter of c — the longest shortest-path distance between any two vertices — using a 2-sweep BFS lower bound combined with an iFUB-style fringe upper-bound refinement. Returns (lo, hi, exact) where lo <= true diameter <= hi; exact is true when the bounds have converged and the value is exact.

2-sweep alone is the standard heuristic for road-network-shaped graphs and consistently delivers lo == true diameter in practice; the iFUB refinement tightens hi to lo on most real-world inputs. On adversarial inputs (e.g. expanders) hi may remain strictly above lo, in which case the caller can choose to accept the lower bound or to brute-force the true diameter (V * BFS).

Concurrency: Diameter is safe to invoke concurrently on a shared CSR. The implementation expects c to encode an undirected graph (symmetric directed CSR).

func DiameterCtx ¶

func DiameterCtx[W any](ctx context.Context, c *csr.CSR[W]) (lo, hi int, exact bool, err error)

DiameterCtx is the context-aware variant of Diameter. ctx.Err() is checked once per BFS sweep; on cancellation returns (0, 0, false, wrapped ctx.Err()).

func DijkstraInto ¶

func DijkstraInto[W Weight](
	ctx context.Context,
	c *csr.CSR[W],
	src graph.NodeID,
	dist []W,
	parent []graph.NodeID,
	found []bool,
) error

DijkstraInto is the zero-allocation primitive behind Dijkstra. It writes single-source shortest-path results directly into the caller-provided dist, parent, and found slices, each of which must have length at least c.MaxNodeID(); otherwise it returns ErrBufferTooSmall. The slices are reset in-place before the traversal, so any previous contents are overwritten.

On return, dist[i] holds the cost from src to node i when found[i] is true and parent[i] is the predecessor on the shortest path (with parent[src] = src by convention). When found[i] is false, dist[i] is the zero value of W and parent[i] is zero.

The only heap allocation performed is the priority queue itself, which is obtained from a per-W sync.Pool and is therefore zero in the steady state.

Concurrency: the caller's slices are written in-place; concurrent callers must supply separate buffers. The internal heap pool is safe for concurrent acquisition.

func Hierholzer ¶

func Hierholzer[W any](c *csr.CSR[W]) ([]graph.NodeID, error)

Hierholzer computes an Eulerian circuit (or path) over a directed graph captured by c. The algorithm is the classical Hierholzer (1873) iterative form running in O(E).

Returns the trail as a slice of NodeIDs (length = E + 1) or ErrNoEulerian when the necessary conditions (every vertex has in-degree == out-degree for a circuit, or at most one vertex with out-in==1 and one with in-out==1 for a path) are not met, or the graph is not connected through its non-zero degree vertices.

func HierholzerCtx ¶

func HierholzerCtx[W any](ctx context.Context, c *csr.CSR[W]) ([]graph.NodeID, error)

HierholzerCtx is the context-aware variant of Hierholzer. ctx.Err() is checked every 4096 trail steps; on cancellation returns (nil, wrapped ctx.Err()).

func HierholzerUndirected ¶

func HierholzerUndirected[W any](c *csr.CSR[W]) ([]graph.NodeID, error)

HierholzerUndirected computes an Eulerian circuit (or path) over the undirected graph captured by c. c is expected to be a symmetric directed CSR (every {u, v} edge appears as both (u, v) and (v, u)) — typical of [adjlist.AdjList] with Directed=false.

Returns the trail as a slice of NodeIDs (length = E + 1 where E is the number of distinct undirected edges) or ErrNoEulerian when the preconditions are not met. For an Eulerian circuit every non-isolated vertex must have even degree; for an Eulerian path, exactly two vertices may have odd degree (these become the path's endpoints).

func HierholzerUndirectedCtx ¶

func HierholzerUndirectedCtx[W any](ctx context.Context, c *csr.CSR[W]) ([]graph.NodeID, error)

HierholzerUndirectedCtx is the context-aware variant of HierholzerUndirected. ctx.Err() is checked every 4096 trail steps; on cancellation returns (nil, wrapped ctx.Err()).

func KCore ¶

func KCore[W any](c *csr.CSR[W]) []int

KCore computes the coreness number of every vertex in c via the Batagelj-Zaversnik 2003 linear-time peeling algorithm. The result is a NodeID-indexed slice; ghost slots (no incident edge) report 0 — the same coreness as a live but degree-0 vertex.

The coreness of v is the largest k such that v belongs to a connected k-core of c. The algorithm proceeds by repeatedly peeling the lowest-degree vertex, recording its current degree as its coreness, and decrementing the remaining degree of each of its neighbours. Total time is O(V + E) via bucket-list peeling.

Concurrency: KCore is safe to invoke concurrently on a shared CSR.

func KCoreCtx ¶

func KCoreCtx[W any](ctx context.Context, c *csr.CSR[W]) ([]int, error)

KCoreCtx is the context-aware variant of KCore. ctx.Err() is checked every 4096 peeled vertices; on cancellation returns (nil, wrapped ctx.Err()).

func PrimMST ¶

func PrimMST[W Weight](c *csr.CSR[W], src graph.NodeID) (parent []graph.NodeID, found []bool, totalWeight W, err error)

PrimMST computes a minimum spanning tree of c rooted at src using Prim's algorithm with a binary-heap priority queue. The returned parent slice maps each NodeID to its predecessor in the tree (parent[src] == src; nodes unreachable from src have parent[i] == 0 but found[i] == false — distinguishable by a parallel found bitmap, returned as the third value).

For a connected undirected graph PrimMST and KruskalMST return trees of identical total weight (the MST weight is unique for distinct-weighted inputs, and tied inputs may yield different but equally-weighted trees).

For floating-point Weight types it validates that no edge weight is NaN or +/-Inf and returns ErrInvalidInput otherwise; integer Weight types skip that pass.

Concurrency: PrimMST is safe to invoke concurrently on a shared CSR — it allocates its own working storage.

func PrimMSTCtx ¶

func PrimMSTCtx[W Weight](ctx context.Context, c *csr.CSR[W], src graph.NodeID) (parent []graph.NodeID, found []bool, totalWeight W, err error)

PrimMSTCtx is the context-aware variant of PrimMST. ctx.Err() is checked every 4096 heap pops; on cancellation returns (nil, nil, zero, wrapped ctx.Err()).

func TarjanSCC ¶

func TarjanSCC[W any](c *csr.CSR[W]) [][]graph.NodeID

TarjanSCC returns the strongly connected components of the directed graph captured by c using Tarjan's algorithm (1972). Each component is returned as a slice of NodeIDs. The implementation is iterative (using an explicit work stack) so it does not risk Go goroutine stack overflow on graphs with deep DFS chains.

Complexity is O(V + E). The implementation is single-threaded.

Only NodeIDs that participate in at least one edge (as source or destination) are considered; NodeIDs that were assigned by the Mapper but never gained an edge are not emitted as singleton SCCs.

package main

import (
	"fmt"
	"sort"

	"github.com/FlavioCFOliveira/GoGraph/graph"
	"github.com/FlavioCFOliveira/GoGraph/graph/adjlist"
	"github.com/FlavioCFOliveira/GoGraph/graph/csr"
	"github.com/FlavioCFOliveira/GoGraph/search"
)

// buildDirected assembles a directed, unweighted CSR from (src, dst)
// integer pairs and returns it together with the mapper that resolves
// NodeIDs back to the user-facing int values.
func buildDirected(edges [][2]int) (*csr.CSR[struct{}], *graph.Mapper[int]) {
	a := adjlist.New[int, struct{}](adjlist.Config{Directed: true})
	for _, e := range edges {
		_ = a.AddEdge(e[0], e[1], struct{}{})
	}
	return csr.BuildFromAdjList(a), a.Mapper()
}

// resolvePath maps a path expressed in NodeID space back to the
// user-facing int values, so output is stable regardless of the
// opaque NodeIDs the mapper assigns.
func resolvePath(m *graph.Mapper[int], path []graph.NodeID) []int {
	out := make([]int, len(path))
	for i, id := range path {
		out[i], _ = m.Resolve(id)
	}
	return out
}

func main() {
	// {0,1,2} form a cycle; 2->3 and 3 is its own component.
	c, m := buildDirected([][2]int{{0, 1}, {1, 2}, {2, 0}, {2, 3}})

	sccs := search.TarjanSCC(c)

	normalised := make([][]int, 0, len(sccs))
	for _, comp := range sccs {
		vs := resolvePath(m, comp)
		sort.Ints(vs)
		normalised = append(normalised, vs)
	}
	sort.Slice(normalised, func(i, j int) bool { return normalised[i][0] < normalised[j][0] })

	fmt.Printf("%d components: %v\n", len(normalised), normalised)
}

Output:
2 components: [[0 1 2] [3]]

func TarjanSCCCtx ¶

func TarjanSCCCtx[W any](ctx context.Context, c *csr.CSR[W]) ([][]graph.NodeID, error)

TarjanSCCCtx is the context-aware variant of TarjanSCC. ctx.Err() is checked at every restart of the outer DFS loop (i.e. before each new root); on cancellation returns (nil, wrapped ctx.Err()).

func TopologicalSort ¶

func TopologicalSort[W any](c *csr.CSR[W]) ([]graph.NodeID, error)

TopologicalSort returns a topological ordering of the directed acyclic graph captured by c using Kahn's algorithm. Vertices with no incoming edges are repeatedly emitted; removing them exposes new sources. If any vertex remains unemitted after the algorithm completes, the input has a cycle and ErrCycle is returned.

The returned ordering covers every NodeID for which the CSR has a non-empty out-edge range or at least one incoming edge. Sparse gaps in the NodeID space (NodeIDs that were never assigned by the Mapper) are omitted from the output.

package main

import (
	"fmt"

	"github.com/FlavioCFOliveira/GoGraph/graph"
	"github.com/FlavioCFOliveira/GoGraph/graph/adjlist"
	"github.com/FlavioCFOliveira/GoGraph/graph/csr"
	"github.com/FlavioCFOliveira/GoGraph/search"
)

// buildDirected assembles a directed, unweighted CSR from (src, dst)
// integer pairs and returns it together with the mapper that resolves
// NodeIDs back to the user-facing int values.
func buildDirected(edges [][2]int) (*csr.CSR[struct{}], *graph.Mapper[int]) {
	a := adjlist.New[int, struct{}](adjlist.Config{Directed: true})
	for _, e := range edges {
		_ = a.AddEdge(e[0], e[1], struct{}{})
	}
	return csr.BuildFromAdjList(a), a.Mapper()
}

// resolvePath maps a path expressed in NodeID space back to the
// user-facing int values, so output is stable regardless of the
// opaque NodeIDs the mapper assigns.
func resolvePath(m *graph.Mapper[int], path []graph.NodeID) []int {
	out := make([]int, len(path))
	for i, id := range path {
		out[i], _ = m.Resolve(id)
	}
	return out
}

func main() {
	// DAG chain: 0 -> 1 -> 2 -> 3 -> 4.
	c, m := buildDirected([][2]int{{0, 1}, {1, 2}, {2, 3}, {3, 4}})

	order, err := search.TopologicalSort(c)
	if err != nil {
		fmt.Println("error:", err)
		return
	}
	fmt.Println(resolvePath(m, order))
}

Output:
[0 1 2 3 4]

func TopologicalSortCtx ¶

func TopologicalSortCtx[W any](ctx context.Context, c *csr.CSR[W]) ([]graph.NodeID, error)

TopologicalSortCtx is the context-aware variant of TopologicalSort. ctx.Err() is checked every 4096 emits; on cancellation returns (nil, wrapped ctx.Err()).

func WCC ¶

func WCC[W any](c *csr.CSR[W]) (component []int, k int, err error)

WCC computes the weakly-connected components of c — equivalence classes induced by the symmetric closure of c's edge relation. Returns one int per live NodeID labelling its component in [0, K), where K is the number of components, plus K itself. Ghost slots (no incident edge) report -1.

Internally WCC walks every edge once and unions the endpoints in a slice-backed Union-Find; final component IDs are compacted into [0, K) preserving order of first occurrence so the output is deterministic across runs of the same graph.

Concurrency: WCC is safe to invoke concurrently on a shared CSR.

package main

import (
	"fmt"

	"github.com/FlavioCFOliveira/GoGraph/graph"
	"github.com/FlavioCFOliveira/GoGraph/graph/adjlist"
	"github.com/FlavioCFOliveira/GoGraph/graph/csr"
	"github.com/FlavioCFOliveira/GoGraph/search"
)

// buildDirected assembles a directed, unweighted CSR from (src, dst)
// integer pairs and returns it together with the mapper that resolves
// NodeIDs back to the user-facing int values.
func buildDirected(edges [][2]int) (*csr.CSR[struct{}], *graph.Mapper[int]) {
	a := adjlist.New[int, struct{}](adjlist.Config{Directed: true})
	for _, e := range edges {
		_ = a.AddEdge(e[0], e[1], struct{}{})
	}
	return csr.BuildFromAdjList(a), a.Mapper()
}

func main() {
	// Two components: {0,1,2} and {3,4}.
	c, m := buildDirected([][2]int{{0, 1}, {1, 2}, {3, 4}})

	comp, k, err := search.WCC(c)
	if err != nil {
		fmt.Println("error:", err)
		return
	}
	id0, _ := m.Lookup(0)
	id2, _ := m.Lookup(2)
	id3, _ := m.Lookup(3)

	fmt.Printf("components: %d\n", k)
	fmt.Printf("0 and 2 together: %v\n", comp[id0] == comp[id2])
	fmt.Printf("0 and 3 together: %v\n", comp[id0] == comp[id3])
}

Output:
components: 2
0 and 2 together: true
0 and 3 together: false

func WCCCtx ¶

func WCCCtx[W any](ctx context.Context, c *csr.CSR[W]) (component []int, k int, err error)

WCCCtx is the context-aware variant of WCC. ctx.Err() is checked once before the union sweep and once before the relabel sweep; on cancellation returns (nil, 0, wrapped ctx.Err()).