Graph

https://github.com/sixafter/graph
Admin
Graph is a Go library for creating and manipulating graph data structures, offering generics-based...
Tokens:101,318
Snippets:726
Trust Score:7.5
License:Apache-2.0
Update:1 week ago
Show doc for...
Tokens:
Raw
### Install with go get

Source: https://github.com/sixafter/graph/blob/main/README.md

Use this command to install the package. It fetches the latest version from GitHub.

```sh
go get -u github.com/sixafter/graph
```

--------------------------------

### Install go.yaml.in/yaml/v3 with go get

Source: https://github.com/sixafter/graph/blob/main/vendor/go.yaml.in/yaml/v3/README.md

Install the yaml package using the Go module tool. Run this command in your project directory to add the dependency.

```bash
go get go.yaml.in/yaml/v3
```

--------------------------------

### Example output: Unmarshal and Marshal results

Source: https://github.com/sixafter/graph/blob/main/vendor/go.yaml.in/yaml/v3/README.md

Output produced by the preceding Go example. Shows the unmarshalled struct and map, and the marshalled YAML dumps for both.

```text
--- t:
{Easy! {2 [3 4]}}

--- t dump:
a: Easy!
b:
  c: 2
  d: [3, 4]


--- m:
map[a:Easy! b:map[c:2 d:[3 4]]]

--- m dump:
a: Easy!
b:
  c: 2
  d:
  - 3
  - 4
```

--------------------------------

### DFS usage example

Source: https://github.com/sixafter/graph/blob/main/_autodocs/api-reference/traverse.md

Example of calling DFS with a visit callback that prints each visited vertex and returns false to traverse everything reachable.

```go
err := traverse.DFS(g, 1, func(v int) bool {
	fmt.Println("visiting", v)
	return false // traverse everything reachable
})
```

--------------------------------

### DijkstraFrom usage example

Source: https://github.com/sixafter/graph/blob/main/_autodocs/api-reference/paths.md

Example call to paths.DijkstraFrom with error handling for graph.ErrTargetNotReachable. Prints the resulting path or logs a fatal error.

```go
path, err := paths.DijkstraFrom(g, 1, 5)
if err != nil {
	if errors.Is(err, graph.ErrTargetNotReachable) {
		fmt.Println("target not reachable")
	} else {
		log.Fatal(err)
	}
}
fmt.Println(path)
```

--------------------------------

### Example: NewVertexWithOptions and AddVertex

Source: https://github.com/sixafter/graph/blob/main/_autodocs/api-reference/simple.md

Shows how to create a vertex with options and add it to a graph.

```go
v := simple.NewVertexWithOptions("A", "A", graph.VertexWeight(4), graph.VertexItem("label", "Node A"))
err := g.AddVertex(v)
```

--------------------------------

### Usage example with graph and simple packages

Source: https://github.com/sixafter/graph/blob/main/_autodocs/api-reference/graph.md

Shows how to create a directed graph with string hashing, add vertices with options (VertexWeight, VertexItem), add an edge with options (EdgeWeight, EdgeItem), and retrieve vertex properties. The example prints the vertex ID, value, weight, and items map.

```go
import (
	"fmt"

	"github.com/sixafter/graph"
	"github.com/sixafter/graph/simple"
)

func main() {
	// Hash: vertex string -> key string (identity)
	g, err := simple.New(graph.StringHash, graph.Directed())
	if err != nil {
		panic(err)
	}
	_ = g.AddVertexWithOptions("A", graph.VertexWeight(4), graph.VertexItem("label", "Node A"))
	_ = g.AddVertexWithOptions("B", graph.VertexWeight(2))
	_ = g.AddEdgeWithOptions("A", "B", graph.EdgeWeight(10), graph.EdgeItem("color", "blue"))

	v, err := g.Vertex("A") // (graph.Vertex[string, string], error)
	if err != nil {
		panic(err)
	}
	fmt.Println(v.ID(), v.Value())           // "A" "A"
	fmt.Println(v.Properties().Weight())     // 4
	fmt.Println(v.Properties().Items())      // map[label:Node A]
}
```

--------------------------------

### FindAllPaths usage example

Source: https://github.com/sixafter/graph/blob/main/_autodocs/api-reference/paths.md

Example usage of FindAllPaths on a directed graph with vertices 1-4. The comment shows the expected result: [[1 2 4] [1 3 4]].

```go
g, _ := simple.New(graph.IntHash, graph.Directed())
_ = g.AddEdge(1, 2)
_ = g.AddEdge(1, 3)
_ = g.AddEdge(2, 4)
_ = g.AddEdge(3, 4)

allPaths, err := paths.FindAllPaths(g, 1, 4) // [[1 2 4] [1 3 4]]
```

--------------------------------

### Example: Adding a vertex with options

Source: https://github.com/sixafter/graph/blob/main/_autodocs/api-reference/simple.md

Shows how to add a vertex with weight, item, items, and metadata options.

```go
g.AddVertexWithOptions("A",
	graph.VertexWeight(4),
	graph.VertexItem("type", "root"),
	graph.VertexItems(map[string]any{"region": "eu"}),
	graph.VertexMetadata("customer-42"),
)
```

--------------------------------

### BFS usage example

Source: https://github.com/sixafter/graph/blob/main/_autodocs/api-reference/traverse.md

Example of calling BFS with a visit callback that prints each visited vertex and stops when vertex 3 is visited. The error is checked and logged.

```go
err := traverse.BFS(g, 1, func(v int) bool {
	fmt.Println(v)
	return v == 3 // stop traversal once 3 is visited
})
if err != nil {
	log.Fatal(err)
}
```

--------------------------------

### BFSWithDepthTracking usage example

Source: https://github.com/sixafter/graph/blob/main/_autodocs/api-reference/traverse.md

Example of calling BFSWithDepthTracking with a visit callback that prints the depth and vertex, stopping when depth exceeds 3.

```go
err := traverse.BFSWithDepthTracking(g, 1, func(v int, depth int) bool {
	fmt.Printf("depth %d: %d\n", depth, v)
	return depth > 3 // stop when depth exceeds 3
})
```

--------------------------------

### Example: NewEdgeWithOptions with edge options

Source: https://github.com/sixafter/graph/blob/main/_autodocs/api-reference/simple.md

Shows how to create an edge with multiple functional options: EdgeWeight, EdgeItem, EdgeItems, and EdgeData.

```go
e := simple.NewEdgeWithOptions("n1", "n2",
	graph.EdgeWeight(2.5),
	graph.EdgeItem("type", "road"),
	graph.EdgeItems(map[string]any{"lanes": 4}),
	graph.EdgeData(struct{ Owner string }{"dotgov"}),
)
```

--------------------------------

### Example: Unmarshal and Marshal YAML with go.yaml.in/yaml/v3

Source: https://github.com/sixafter/graph/blob/main/vendor/go.yaml.in/yaml/v3/README.md

Complete Go program demonstrating yaml.Unmarshal and yaml.Marshal on a struct and a map. The struct fields must be public for unmarshal to populate correctly. The output shows the resulting values and dumps.

```go
package main

import (
	"fmt"
	"log"

	"go.yaml.in/yaml/v3"
)

var data = `
a: Easy!
b:
  c: 2
  d: [3, 4]
`

// Note: struct fields must be public in order for unmarshal to
// correctly populate the data.
type T struct {
	A string
	B struct {
		RenamedC int   `yaml:"c"`
		D	[]int `yaml:",flow"`
	}
}

func main() {
	t := T{}

	err := yaml.Unmarshal([]byte(data), &t)
	if err != nil {
		log.Fatalf("error: %v", err)
	}
	fmt.Printf("--- t:\n%v\n\n", t)

	d, err := yaml.Marshal(&t)
	if err != nil {
		log.Fatalf("error: %v", err)
	}
	fmt.Printf("--- t dump:\n%s\n\n", string(d))

	m := make(map[interface{}]interface{})

	err = yaml.Unmarshal([]byte(data), &m)
	if err != nil {
		log.Fatalf("error: %v", err)
	}
	fmt.Printf("--- m:\n%v\n\n", m)

	d, err = yaml.Marshal(&m)
	if err != nil {
		log.Fatalf("error: %v", err)
	}
	fmt.Printf("--- m dump:\n%s\n\n", string(d))
}
```

--------------------------------

### AddEdgeWithOptions usage example

Source: https://github.com/sixafter/graph/blob/main/_autodocs/api-reference/graph-interface.md

Example call to AddEdgeWithOptions that sets an edge weight and an item property. On error, it logs a fatal message.

```go
if err := g.AddEdgeWithOptions("A", "B", graph.EdgeWeight(10), graph.EdgeItem("color", "blue")); err != nil {
	log.Fatal(err)
}
```

--------------------------------

### Vertex usage example

Source: https://github.com/sixafter/graph/blob/main/_autodocs/api-reference/graph-interface.md

Fetches a vertex and checks for not-found error.

```go
v, err := g.Vertex("A")
if errors.Is(err, graph.ErrVertexNotFound) {
	fmt.Println("not found")
}
```

--------------------------------

### EigenvectorCentrality usage example

Source: https://github.com/sixafter/graph/blob/main/_autodocs/api-reference/metrics.md

Example of computing eigenvector centrality and printing scores. Logs fatal error on failure.

```go
centrality, err := metrics.EigenvectorCentrality(g)
if err != nil {
	log.Fatalf("failed to compute eigenvector centrality: %v", err)
}
for vertex, score := range centrality {
	fmt.Printf("vertex %v score %.4f\n", vertex, score)
}
```

--------------------------------

### EmptyCursor usage example

Source: https://github.com/sixafter/graph/blob/main/_autodocs/api-reference/simple.md

Shows how to create a cursor using EmptyCursor. The returned *Cursor works with the default streaming flow; other implementations cause an "invalid cursor type" error.

```go
cursor := simple.EmptyCursor() // -> graph.Cursor
```

--------------------------------

### NewEdgeWithOptions usage example

Source: https://github.com/sixafter/graph/blob/main/_autodocs/api-reference/simple.md

Creates an edge with weight and item options, then adds it to a graph. The graph g is of type graph.Interface[string, string].

```go
edge := simple.NewEdgeWithOptions("A", "B", graph.EdgeWeight(10), graph.EdgeItem("color", "blue"))
err := g.AddEdge(edge) // g is graph.Interface[string, string]
```

--------------------------------

### TopologicalSortDeterministic usage example

Source: https://github.com/sixafter/graph/blob/main/_autodocs/api-reference/topology.md

Example call to `TopologicalSortDeterministic` with an integer graph and a `less` function. On error, it logs and exits; otherwise prints the deterministic order.

```go
order, err := topology.TopologicalSortDeterministic(g, func(a, b int) bool { return a < b })
if err != nil {
	log.Fatal(err)
}
fmt.Println(order)
```

--------------------------------

### New usage example

Source: https://github.com/sixafter/graph/blob/main/_autodocs/api-reference/simple.md

Creates a directed, weighted graph using graph.IntHash, adds vertices 1 and 2, and adds an edge with weight 3.5.

```go
g, err := simple.New(graph.IntHash, graph.Directed(), graph.Weighted())
if err != nil {
	log.Fatal(err)
}
_ = g.AddVertex(1)
_ = g.AddVertex(2)
_ = g.AddEdgeWithOptions(1, 2, graph.EdgeWeight(3.5))
```

--------------------------------

### EmptyCursor function signature

Source: https://github.com/sixafter/graph/blob/main/_autodocs/api-reference/simple.md

Returns a new cursor with position 0, the starting point for streaming operations.

```go
func EmptyCursor() graph.Cursor
```

--------------------------------

### MinimumSpanningTree usage with error handling

Source: https://github.com/sixafter/graph/blob/main/_autodocs/api-reference/paths.md

Example of calling MinimumSpanningTree and handling the ErrDirectedGraph error with errors.Is.

```go
mst, err := paths.MinimumSpanningTree(undirectedGraph)
if err != nil {
	if errors.Is(err, paths.ErrDirectedGraph) {
		log.Fatal("spanning trees require an undirected graph")
	}
	log.Fatal(err)
}
```

--------------------------------

### NewLike usage example

Source: https://github.com/sixafter/graph/blob/main/_autodocs/api-reference/simple.md

Creates a new empty graph h that mirrors the type, hash, and traits of g.

```go
h, err := simple.NewLike(g) // h is a new directed int graph, empty
```

--------------------------------

### EmptyCursor

Source: https://github.com/sixafter/graph/blob/main/_autodocs/api-reference/simple.md

Returns a new cursor with position 0, the starting point for streaming operations.

```APIDOC
## EmptyCursor

### Description
Returns a new cursor with position 0, the starting point for `StreamVerticesWithContext` / `StreamEdgesWithContext`.

### Method
EmptyCursor

### Signature
`func EmptyCursor() graph.Cursor`

### Parameters
None

### Returns
- `graph.Cursor` - A new cursor with position 0.

### Example
```go
cursor := simple.EmptyCursor() // -> graph.Cursor
```

```

--------------------------------

### UnionFind usage example

Source: https://github.com/sixafter/graph/blob/main/_autodocs/api-reference/paths.md

Shows how to use the zero value of UnionFind, which is usable with a nil parents map until Add is called. Demonstrates Add, Union, and Find behavior, including that Union points root2's parent at root1 and Find returns the vertex itself if not added.

```go
uf := &paths.UnionFind[int]{ /* not directly constructible outside the package */ }
// Instead, obtain an instance via the package's algorithms, or replicate:
// uf := newUnionFind(...) is unexported — use Add/Union/Find on an instance
// obtained from spanningTree internals. For consumer code, construct via:
var uf paths.UnionFind[int]           // zero value is usable: parents map is nil until Add
uf.Add(1); uf.Add(2); uf.Add(3)
uf.Union(1, 2)
root := uf.Find(1) // 1 (root2=2 points at root1=1)
root2 := uf.Find(2)
fmt.Println(root, root2) // 1 1
```

--------------------------------

### StreamEdgesWithContext usage example

Source: https://github.com/sixafter/graph/blob/main/_autodocs/api-reference/graph-interface.md

Example of streaming edges with a cursor and channel. The channel is closed by the implementation, so the range loop terminates. Prints each edge's source, target, and weight.

```go
cursor := simple.EmptyCursor()
ch := make(chan graph.Edge[int])
go func() {
	cursor, err = g.StreamEdgesWithContext(ctx, cursor, 10, ch)
}()
for edge := range ch { // channel is closed by the implementation
	fmt.Printf("Edge %v -> %v weight=%v\n", edge.Source(), edge.Target(), edge.Properties().Weight())
}
```

--------------------------------

### AddVertex usage example

Source: https://github.com/sixafter/graph/blob/main/_autodocs/api-reference/graph-interface.md

Creates a vertex with options and adds it to the graph. Logs fatal error on duplicate vertex.

```go
v := simple.NewVertexWithOptions("A", "A", graph.VertexWeight(4))
if err := g.AddVertex(v); err != nil {
	log.Fatal(err) // graph.ErrVertexAlreadyExists on duplicate
}
```

--------------------------------

### Clone the forked repository

Source: https://github.com/sixafter/graph/blob/main/CONTRIBUTING.md

Clones your forked repository to your local machine so you can start working on changes.

```bash
git clone https://github.com/your-username/graph.git
```

--------------------------------

### AddVertexWithOptions usage example

Source: https://github.com/sixafter/graph/blob/main/_autodocs/api-reference/graph-interface.md

Adds a vertex with weight and item options. Logs fatal error on failure.

```go
if err := g.AddVertexWithOptions("A", graph.VertexWeight(4), graph.VertexItem("type", "root")); err != nil {
	log.Fatal(err)
}
```

--------------------------------

### AveragePathLength usage example

Source: https://github.com/sixafter/graph/blob/main/_autodocs/api-reference/metrics.md

Example usage of metrics.AveragePathLength. Calls the function with a graph g, handles errors with log.Fatal, and prints the average path length formatted to three decimal places.

```go
apl, err := metrics.AveragePathLength(g)
if err != nil {
	log.Fatal(err)
}
fmt.Printf("average path length: %.3f\n", apl)
```

--------------------------------

### StreamVerticesWithContext usage example

Source: https://github.com/sixafter/graph/blob/main/_autodocs/api-reference/graph-interface.md

Example of streaming vertices with a timeout context. The channel is closed by the implementation, so ranging over it is safe. The cursor is updated to resume streaming.

```go
ctx, cancel := context.WithTimeout(context.Background(), time.Second)
defer cancel()

cursor := simple.EmptyCursor()
ch := make(chan []graph.Vertex[int, string])
go func() {
	cursor, err = g.StreamVerticesWithContext(ctx, cursor, 10, ch)
}()
for batch := range ch { // channel is closed by the implementation
	for _, vertex := range batch {
		fmt.Printf("%v\n", vertex.Value())
	}
}
```

--------------------------------

### PageRank function signature and usage example

Source: https://github.com/sixafter/graph/blob/main/_autodocs/api-reference/metrics.md

Computes PageRank scores for a directed (optionally weighted) graph, normalized to sum to 1.0. Requires a directed graph; dampingFactor must be in (0, 1), maxIterations and tol must be > 0. The example shows calling metrics.PageRank with typical parameters and printing results.

```go
func PageRank[K graph.Ordered, T any](
	g graph.Interface[K, T],
	dampingFactor float64,
	maxIterations int,
	tol float64,
) (map[K]float64, error)
```

```go
pr, err := metrics.PageRank(g, 0.85, 100, 1e-6)
if err != nil {
	fmt.Println("Error:", err)
	return
}
for v, score := range pr {
	fmt.Printf("vertex %v pagerank %.6f\n", v, score)
}
```

--------------------------------

### IntHash function signature and usage

Source: https://github.com/sixafter/graph/blob/main/_autodocs/api-reference/graph-hash.md

Identity function for integers. Example shows creating a directed graph and adding vertices and edges.

```go
func IntHash(v int) int
```

```go
g, _ := simple.New(graph.IntHash, graph.Directed())
_ = g.AddVertex(1)
_ = g.AddEdge(1, 2)
```

--------------------------------

### TopologicalSort usage example

Source: https://github.com/sixafter/graph/blob/main/_autodocs/api-reference/topology.md

Calls topology.TopologicalSort on a graph and handles the error, specifically checking for graph.ErrCyclicGraph to log a fatal message about a cycle. Prints the resulting order on success.

```go
order, err := topology.TopologicalSort(g)
if err != nil {
	if errors.Is(err, graph.ErrCyclicGraph) {
		log.Fatal("graph has a cycle; cannot sort")
	}
	log.Fatal(err)
}
fmt.Println(order)
```

--------------------------------

### TransitiveReduction usage example

Source: https://github.com/sixafter/graph/blob/main/_autodocs/api-reference/topology.md

Builds a small directed acyclic graph with a redundant edge (1->3) and calls `TransitiveReduction`. The resulting graph no longer contains that edge.

```go
g2, _ := simple.New(graph.IntHash, graph.Directed(), graph.Acyclic())
_ = g2.AddEdge(1, 2)
_ = g2.AddEdge(2, 3)
_ = g2.AddEdge(1, 3) // redundant
reduced, err := topology.TransitiveReduction(g2)
// reduced no longer contains edge 1 -> 3
```

--------------------------------

### TarjanFrom usage example

Source: https://github.com/sixafter/graph/blob/main/_autodocs/api-reference/topology.md

Calls topology.TarjanFrom on a graph and handles errors, specifically checking for graph.ErrSCCDetectionNotDirected to indicate that SCC detection requires a directed graph. Prints each SCC with its index and vertex hashes.

```go
components, err := topology.TarjanFrom(g)
if err != nil {
	if errors.Is(err, graph.ErrSCCDetectionNotDirected) {
		log.Fatal("SCCs need a directed graph")
	}
	log.Fatal(err)
}
for i, comp := range components {
	fmt.Printf("SCC %d: %v\n", i, comp)
}
```

--------------------------------

### Creating a directed, weighted, cycle-prevented graph

Source: https://github.com/sixafter/graph/blob/main/_autodocs/configuration.md

Example usage of simple.New with Directed, Weighted, and PreventCycles options. The error is checked and logged with log.Fatal. This graph is directed, edges carry weights, and AddEdge rejects cyclic additions with ErrEdgeCreatesCycle.

```go
// Directed, weighted, cycle-prevented graph:
g, err := simple.New(graph.StringHash, graph.Directed(), graph.Weighted(), graph.PreventCycles())
if err != nil {
	log.Fatal(err)
}
```

--------------------------------

### AdjacencyMap usage example

Source: https://github.com/sixafter/graph/blob/main/_autodocs/api-reference/graph-interface.md

Iterates over the adjacency map to print each source-target edge and its weight. Uses the returned map from AdjacencyMap.

```go
adj, err := g.AdjacencyMap()
for src, targets := range adj {
	for tgt, edge := range targets {
		fmt.Printf("%v -> %v (w=%v)\n", src, tgt, edge.Properties().Weight())
	}
}
```

--------------------------------

### Custom codec example (ListWriter)

Source: https://github.com/sixafter/graph/blob/main/_autodocs/api-reference/io.md

Shows how to satisfy the Writer contract with a trivial 'vertex-list' codec. The type implements WriteGraph by writing each vertex ID to the io.Writer. Includes a compile-time assertion that ListWriter satisfies graphio.Writer[string, string].

```go
import (
	"io"

	"github.com/sixafter/graph"
	graphio "github.com/sixafter/graph/io"
)

// A trivial "vertex-list" codec satisfying the Writer contract.
type ListWriter[K graph.Ordered, T any] struct{}

func (ListWriter[K, T]) WriteGraph(w io.Writer, g graph.Interface[K, T]) error {
	vertices, err := g.Vertices()
	if err != nil {
		return err
	}
	for _, v := range vertices {
		if _, err := io.WriteString(w, fmt.Sprintln(v.ID())); err != nil {
			return err
		}
	}
	return nil
}

var _ graphio.Writer[string, string] = ListWriter[string, string]{}
```

--------------------------------

### FNV1aHash64 function signature and usage

Source: https://github.com/sixafter/graph/blob/main/_autodocs/api-reference/graph-hash.md

Returns 64-bit FNV-1a hash. Example shows using it as a custom hash function for a graph.

```go
func FNV1aHash64(s string) uint64
```

```go
key := graph.FNV1aHash64("vertex-id")
g, _ := simple.New(func(s string) uint64 { return graph.FNV1aHash64(s) }, graph.Directed())
```

--------------------------------

### FindAllPaths function signature

Source: https://github.com/sixafter/graph/blob/main/_autodocs/api-reference/paths.md

Enumerates all simple paths from start to end using a non-recursive two-stack algorithm. Works on directed graphs; cycles are avoided. Returns an error if the adjacency map cannot be retrieved or on internal stack inconsistencies.

```go
func FindAllPaths[K graph.Ordered, T any](g graph.Interface[K, T], start, end K) ([][]K, error)
```

--------------------------------

### FindAllPaths

Source: https://github.com/sixafter/graph/blob/main/_autodocs/api-reference/paths.md

Enumerates all simple paths from a start vertex to an end vertex in a directed graph using a non-recursive two-stack algorithm. Returns a slice of paths, each path being a slice of vertex hashes.

```APIDOC
## FindAllPaths

### Description
Enumerates all simple paths (no repeated vertices) from `start` to `end` in a directed graph using a non-recursive two-stack algorithm. Returns a slice of paths, each path being a slice of vertex hashes.

### Function Signature
```go
func FindAllPaths[K graph.Ordered, T any](g graph.Interface[K, T], start, end K) ([][]K, error)
```

### Parameters
- `g` (graph.Interface[K, T]) - Required - The graph; adjacency map must be retrievable.
- `start` (K) - Required - Starting vertex hash.
- `end` (K) - Required - Ending vertex hash.

### Returns
- `[][]K` - Each element is one path `[]K` from `start` to `end`.

### Errors
- Returns an error if the adjacency map cannot be retrieved, or on internal stack inconsistencies.

### Example
```go
g, _ := simple.New(graph.IntHash, graph.Directed())
_ = g.AddEdge(1, 2)
_ = g.AddEdge(1, 3)
_ = g.AddEdge(2, 4)
_ = g.AddEdge(3, 4)

allPaths, err := paths.FindAllPaths(g, 1, 4) // [[1 2 4] [1 3 4]]
```
```

--------------------------------

### traverse.DFS

Source: https://github.com/sixafter/graph/blob/main/_autodocs/index.md

Performs a depth-first search traversal of the graph starting from a given vertex. It visits all vertices reachable from the start vertex.

```APIDOC
## DFS

### Description
Performs a depth-first search traversal of the graph starting from a given vertex. It visits all vertices reachable from the start vertex.

### Function Signature
`func DFS[K comparable, T any](g Interface[K,T], start K, visit func(Vertex[K,T]) error) error`

### Parameters
- `g` (Interface[K,T]) - Required - The graph to traverse.
- `start` (K) - Required - The ID of the starting vertex.
- `visit` (func(Vertex[K,T]) error) - Required - Callback invoked for each visited vertex.

### Returns
- `error` - An error if the traversal fails.

### Usage
Use to traverse a graph in depth-first order.
```

--------------------------------

### Make changes and commit

Source: https://github.com/sixafter/graph/blob/main/CONTRIBUTING.md

Make your changes and commit them with a descriptive message.

```bash
git add .
git commit -m "Describe your changes"
```

--------------------------------

### traverse.BFS

Source: https://github.com/sixafter/graph/blob/main/_autodocs/index.md

Performs a breadth-first search traversal of the graph starting from a given vertex. It visits all vertices reachable from the start vertex.

```APIDOC
## BFS

### Description
Performs a breadth-first search traversal of the graph starting from a given vertex. It visits all vertices reachable from the start vertex.

### Function Signature
`func BFS[K comparable, T any](g Interface[K,T], start K, visit func(Vertex[K,T]) error) error`

### Parameters
- `g` (Interface[K,T]) - Required - The graph to traverse.
- `start` (K) - Required - The ID of the starting vertex.
- `visit` (func(Vertex[K,T]) error) - Required - Callback invoked for each visited vertex.

### Returns
- `error` - An error if the traversal fails.

### Usage
Use to traverse a graph in breadth-first order.
```

--------------------------------

### BFSWithDepthTracking

Source: https://github.com/sixafter/graph/blob/main/_autodocs/api-reference/traverse.md

BFS that additionally passes the current depth (hops from start, starting at 0) as the second argument to the visit callback. Neighbors are visited in sorted order for deterministic traversal.

```APIDOC
## BFSWithDepthTracking

### Description
BFS that additionally passes the current depth (hops from `start`, starting at `0`) as the second argument to `visit`. Neighbors are visited in **sorted order** (`sort.Slice` with `neighbors[i] < neighbors[j]`) for deterministic traversal.

### Function Signature
```go
func BFSWithDepthTracking[K graph.Ordered, T any](g graph.Interface[K, T], start K, visit func(K, int) bool) error
```

### Parameters
- **g** (graph.Interface[K, T]) - Required - The graph; must not be nil.
- **start** (K) - Required - Starting vertex hash.
- **visit** (func(K, int) bool) - Required - Called per visited vertex with its depth; return `true` to stop.

### Returns
- **error** - `graph.ErrNilInputGraph` if `g == nil`; `"could not get adjacency map: %w"` on map failure; `"could not find start vertex with key %v"` if `start` is missing.

### Complexity
O(V + E) as documented in source.

### Example
```go
err := traverse.BFSWithDepthTracking(g, 1, func(v int, depth int) bool {
	fmt.Printf("depth %d: %d\n", depth, v)
	return depth > 3 // stop when depth exceeds 3
})
```
```

--------------------------------

### Open a Pull Request

Source: https://github.com/sixafter/graph/blob/main/CONTRIBUTING.md

Navigate to the original repository and open a pull request with a clear title and description.

```text
No code required for this step.
```

--------------------------------

### NewVertexWithOptions constructor

Source: https://github.com/sixafter/graph/blob/main/_autodocs/api-reference/simple.md

Builds a vertex, applying functional graph.VertexOptions to a fresh VertexProperties.

```go
func NewVertexWithOptions[K comparable, T any](id K, value T, options ...graph.VertexOption) graph.Vertex[K, T]
```

--------------------------------

### BFSWithDepthTracking function signature

Source: https://github.com/sixafter/graph/blob/main/_autodocs/api-reference/traverse.md

Signature for the BFSWithDepthTracking function. It performs BFS but also passes the current depth (hops from start, starting at 0) to the visit callback. Neighbors are visited in sorted order for deterministic traversal.

```go
func BFSWithDepthTracking[K graph.Ordered, T any](g graph.Interface[K, T], start K, visit func(K, int) bool) error
```

--------------------------------

### BFS function signature

Source: https://github.com/sixafter/graph/blob/main/_autodocs/api-reference/traverse.md

Signature for the BFS function. It performs a breadth-first search starting at the given vertex, calling the visit callback with each visited vertex hash. Returns graph.ErrNilInputGraph if g is nil, or an error if the start vertex is not found.

```go
func BFS[K graph.Ordered, T any](g graph.Interface[K, T], start K, visit func(K) bool) error
```

--------------------------------

### Modularity function signature and usage example

Source: https://github.com/sixafter/graph/blob/main/_autodocs/api-reference/metrics.md

Computes the modularity score of a community assignment in the nominal range [-0.5, 1]. Dispatches on Traits().IsDirected to directed or undirected calculation. The example shows building a communities map and calling metrics.Modularity.

```go
func Modularity[K graph.Ordered, T any](g graph.Interface[K, T], communities map[K]int) (float64, error)
```

```go
communities := map[int]int{1: 0, 2: 0, 3: 1, 4: 1} // vertex -> community
q, err := metrics.Modularity(g, communities)
```

--------------------------------

### NewVertexWithOptions

Source: https://github.com/sixafter/graph/blob/main/_autodocs/api-reference/simple.md

Builds a vertex, applying functional `graph.VertexOption`s to a fresh `VertexProperties`.

```APIDOC
## NewVertexWithOptions

### Description
Builds a vertex, applying functional `graph.VertexOption`s to a fresh `VertexProperties`.

### Signature
```go
func NewVertexWithOptions[K comparable, T any](id K, value T, options ...graph.VertexOption) graph.Vertex[K, T]
```

### Parameters
- **id** (K) - Required - The vertex identifier (hash)
- **value** (T) - Required - The vertex value
- **options** (...graph.VertexOption) - Optional - Property options (`VertexWeight`, `VertexItem`, `VertexItems`, `VertexMetadata`)
```

--------------------------------

### NewEdgeWithOptions function signature

Source: https://github.com/sixafter/graph/blob/main/_autodocs/api-reference/simple.md

Builds an edge by applying functional graph.EdgeOption to a fresh EdgeProperties. Each option type-asserts properties to *EdgeProperties; custom options that don't will panic.

```go
func NewEdgeWithOptions[T any](source, target T, options ...graph.EdgeOption) graph.Edge[T]
```

--------------------------------

### Fork the repository with git

Source: https://github.com/sixafter/graph/blob/main/CONTRIBUTING.md

Use this command to fork the repository to your GitHub account before making changes. Run it from your local machine after creating the fork on GitHub.

```bash
git fork
```

--------------------------------

### NewEdgeWithOptions

Source: https://github.com/sixafter/graph/blob/main/_autodocs/api-reference/simple.md

Builds an edge, applying functional graph.EdgeOptions to a fresh EdgeProperties.

```APIDOC
## NewEdgeWithOptions

### Description
Builds an edge, applying functional `graph.EdgeOption`s to a fresh `EdgeProperties`.

### Method
NewEdgeWithOptions

### Signature
`func NewEdgeWithOptions[T any](source, target T, options ...graph.EdgeOption) graph.Edge[T]`

### Parameters
- **source** (`T`) - Required - Source vertex.
- **target** (`T`) - Required - Target vertex.
- **options** (`...graph.EdgeOption`) - Optional - Property options (`EdgeWeight`, `EdgeItem`, `EdgeItems`, `EdgeData`).

### Returns
- `graph.Edge[T]` - The constructed edge.

### Panic Risk
Each provided option type-asserts the properties to `*EdgeProperties`; the built-in options are safe, a custom option that does not is not.

### Example
```go
edge := simple.NewEdgeWithOptions("A", "B", graph.EdgeWeight(10), graph.EdgeItem("color", "blue"))
err := g.AddEdge(edge) // g is graph.Interface[string, string]
```

```

--------------------------------

### VertexWeight function

Source: https://github.com/sixafter/graph/blob/main/_autodocs/api-reference/simple.md

Returns a graph.VertexOption that sets the vertex weight.

```go
func VertexWeight(weight float64) graph.VertexOption
```

--------------------------------

### NewVertex constructor

Source: https://github.com/sixafter/graph/blob/main/_autodocs/api-reference/simple.md

Builds a vertex from explicit id, value and properties.

```go
func NewVertex[K comparable, T any](id K, value T, properties graph.VertexProperties) graph.Vertex[K, T]
```

--------------------------------

### Verify release tarball and checksums with Cosign

Source: https://github.com/sixafter/graph/blob/main/README.md

Downloads the release tarball and checksums manifest along with their Sigstore bundles, then verifies each with `cosign verify-blob` using the published public key. Finally confirms local artifact integrity with `shasum -a 256 -c checksums.txt`. On success, Cosign outputs `Verified OK`.

```shell
# Fetch the latest release tag from GitHub API (e.g., "v0.13.0")
TAG=$(curl -s https://api.github.com/repos/sixafter/graph/releases/latest | jq -r .tag_name)

# Remove leading "v" for filenames (e.g., "v0.13.0" -> "0.13.0")
VERSION=${TAG#v}

# ---------------------------------------------------------------------
# Verify the source archive using Sigstore bundles
# ---------------------------------------------------------------------

# Download the release tarball and its signature bundle
curl -LO "https://github.com/sixafter/graph/releases/download/${TAG}/graph-${VERSION}.tar.gz"
curl -LO "https://github.com/sixafter/graph/releases/download/${TAG}/graph-${VERSION}.tar.gz.sigstore.json"

# Verify the tarball with Cosign using the published public key
cosign verify-blob \
  --key "https://raw.githubusercontent.com/sixafter/graph/main/cosign.pub" \
  --bundle "graph-${VERSION}.tar.gz.sigstore.json" \
  "graph-${VERSION}.tar.gz"

# ---------------------------------------------------------------------
# Verify the checksums manifest using Sigstore bundles
# ---------------------------------------------------------------------

curl -LO "https://github.com/sixafter/graph/releases/download/${TAG}/checksums.txt"
curl -LO "https://github.com/sixafter/graph/releases/download/${TAG}/checksums.txt.sigstore.json"

cosign verify-blob \
  --key "https://raw.githubusercontent.com/sixafter/graph/main/cosign.pub" \
  --bundle "checksums.txt.sigstore.json" \
  "checksums.txt"

# ---------------------------------------------------------------------
# Confirm local artifact integrity
# ---------------------------------------------------------------------

shasum -a 256 -c checksums.txt

```

--------------------------------

### RemoveVertex usage example

Source: https://github.com/sixafter/graph/blob/main/_autodocs/api-reference/graph-interface.md

Removes an edge first, then the vertex. Logs fatal error if the vertex still has edges.

```go
// Remove all edges first, then the vertex:
_ = g.RemoveEdge("A", "B")
if err := g.RemoveVertex("A"); errors.Is(err, graph.ErrVertexHasEdges) {
	log.Fatal("vertex still has edges")
}
```

--------------------------------

### VertexMetadata function

Source: https://github.com/sixafter/graph/blob/main/_autodocs/api-reference/simple.md

Returns a graph.VertexOption that sets custom metadata.

```go
func VertexMetadata(data any) graph.VertexOption
```

--------------------------------

### graph.Cursor interface

Source: https://github.com/sixafter/graph/blob/main/_autodocs/types.md

The Cursor interface represents a cursor for streaming graph vertices or edges. It provides methods to get and set the cursor state.

```APIDOC
## Cursor Interface

### Description
The `graph.Cursor` interface is used for streaming graph vertices or edges. It allows you to retrieve and update the cursor state.

### Methods

#### State
- **Signature:** `State() []byte`
- **Description:** Returns the current state of the cursor.

#### SetState
- **Signature:** `SetState(state []byte) error`
- **Description:** Sets the state of the cursor. Returns an error if the operation fails.

### Usage
- **Accepted by:** `Interface.StreamVerticesWithContext`, `Interface.StreamEdgesWithContext`.
- **Returned by:** the same two methods; `simple.EmptyCursor()`.
- **Implemented by:** `simple.Cursor`.
```

--------------------------------

### Edge.Properties

Source: https://github.com/sixafter/graph/blob/main/_autodocs/api-reference/simple.md

Returns the edge properties.

```APIDOC
## Edge.Properties

### Description
Returns the edge properties.

### Method
Properties

### Signature
`Properties() graph.EdgeProperties`

### Parameters
None

### Returns
- `graph.EdgeProperties` - The edge properties.

```

--------------------------------

### NewEdge function signature

Source: https://github.com/sixafter/graph/blob/main/_autodocs/api-reference/simple.md

Builds an edge from explicit source, target, and already-constructed properties.

```go
func NewEdge[T any](source, target T, properties graph.EdgeProperties) graph.Edge[T]
```

--------------------------------

### graph.Vertex[K comparable, T any] interface

Source: https://github.com/sixafter/graph/blob/main/_autodocs/types.md

The Vertex interface represents a vertex in the graph. It provides methods to clone, get the ID, value, and properties of the vertex.

```APIDOC
## Vertex Interface

### Description
The `graph.Vertex[K comparable, T any]` interface represents a vertex in the graph. It provides methods to clone the vertex, get its ID, value, and properties.

### Methods

#### Clone
- **Signature:** `Clone() Vertex[K, T]`
- **Description:** Returns a deep copy of the vertex.

#### ID
- **Signature:** `ID() K`
- **Description:** Returns the vertex identifier.

#### Value
- **Signature:** `Value() T`
- **Description:** Returns the vertex value.

#### Properties
- **Signature:** `Properties() VertexProperties`
- **Description:** Returns the vertex properties.

### Usage
- **Accepted by:** `Interface.AddVertex`, `Interface.AddVerticesFrom`.
- **Returned by:** `Interface.Vertex`, `Interface.Vertices`, `Interface.Neighbors`, `simple.NewVertex`, `simple.NewVertexWithOptions`, `simple.Vertex.Clone`.
```

--------------------------------

### Sha256Hash function signature and usage

Source: https://github.com/sixafter/graph/blob/main/_autodocs/api-reference/graph-hash.md

Returns cryptographically secure SHA-256 digest. Example shows using it as a custom hash function for a graph.

```go
func Sha256Hash(s string) [32]byte
```

```go
key := graph.Sha256Hash("vertex-id")
g, _ := simple.New(func(s string) [32]byte { return graph.Sha256Hash(s) }, graph.Directed())
```

--------------------------------

### NewEdge

Source: https://github.com/sixafter/graph/blob/main/_autodocs/api-reference/simple.md

Builds an edge from explicit source, target, and already-constructed properties.

```APIDOC
## NewEdge

### Description
Builds an edge from explicit source, target, and already-constructed properties.

### Method
NewEdge

### Signature
`func NewEdge[T any](source, target T, properties graph.EdgeProperties) graph.Edge[T]`

### Parameters
- **source** (`T`) - Required - Source vertex.
- **target** (`T`) - Required - Target vertex.
- **properties** (`graph.EdgeProperties`) - Required - Edge properties (e.g. `simple.NewEdgeProperties` result or a clone).

### Returns
- `graph.Edge[T]` - The constructed edge.

```

--------------------------------

### BFS

Source: https://github.com/sixafter/graph/blob/main/_autodocs/api-reference/traverse.md

Performs a breadth-first search starting at the given vertex. The visit callback is invoked for each visited vertex in BFS order, and returning true stops traversal early.

```APIDOC
## BFS

### Description
Performs a breadth-first search starting at `start`. `visit` is invoked with the hash of each visited vertex in BFS order. If `visit` returns `true`, traversal stops (early termination with `nil` error). In a disconnected graph, only the vertices reachable from `start` are visited.

### Function Signature
```go
func BFS[K graph.Ordered, T any](g graph.Interface[K, T], start K, visit func(K) bool) error
```

### Parameters
- **g** (graph.Interface[K, T]) - Required - The graph; must not be nil.
- **start** (K) - Required - Starting vertex hash.
- **visit** (func(K) bool) - Required - Called per visited vertex; return `true` to stop.

### Returns
- **error** - `graph.ErrNilInputGraph` if `g == nil`; wrapped error if the adjacency map cannot be retrieved; `"could not find start vertex with key %v"` if `start` is not in the graph.

### Example
```go
err := traverse.BFS(g, 1, func(v int) bool {
	fmt.Println(v)
	return v == 3 // stop traversal once 3 is visited
})
if err != nil {
	log.Fatal(err)
}
```
```

--------------------------------

### Import package in Go

Source: https://github.com/sixafter/graph/blob/main/README.md

Add this import statement to your Go source file to use the package.

```go
import "github.com/sixafter/graph"
```

--------------------------------

### NewVertex

Source: https://github.com/sixafter/graph/blob/main/_autodocs/api-reference/simple.md

Builds a vertex from explicit id, value and properties.

```APIDOC
## NewVertex

### Description
Builds a vertex from explicit id, value and properties.

### Signature
```go
func NewVertex[K comparable, T any](id K, value T, properties graph.VertexProperties) graph.Vertex[K, T]
```
```

--------------------------------

### EdgeWeight functional option

Source: https://github.com/sixafter/graph/blob/main/_autodocs/api-reference/simple.md

Functional option setting the edge weight.

```go
func EdgeWeight(weight float64) graph.EdgeOption
```

--------------------------------

### NewLike

Source: https://github.com/sixafter/graph/blob/main/_autodocs/api-reference/simple.md

Creates a new, independent graph that mirrors g: same key/value types, same hash function, and a deep copy of g's traits. The new graph is empty and uses the default in-memory ledger.

```APIDOC
## NewLike

### Description
Creates a new, independent graph that mirrors g: same key/value types, same hash function, and a deep copy of g's traits. The new graph is empty and uses the default in-memory ledger.

### Method
Constructor

### Signature
```go
func NewLike[K graph.Ordered, T any](g graph.Interface[K, T]) (graph.Interface[K, T], error)
```

### Parameters
- **g** (graph.Interface[K, T]) - Required - Model graph whose type/hash/traits are copied

### Returns
- **graph.Interface[K, T]** - a fresh empty graph
- **error** - only if the store cannot be created

### Used by
paths.MinimumSpanningTree/MaximumSpanningTree, sets.Union, sets.Intersection, sets.Complement

### Example
```go
h, err := simple.NewLike(g) // h is a new directed int graph, empty
```
```

--------------------------------

### DFS

Source: https://github.com/sixafter/graph/blob/main/_autodocs/api-reference/traverse.md

Performs a depth-first traversal starting at the given vertex, maintaining an explicit stack (non-recursive). The visit callback is invoked with each vertex hash; returning true breaks out of the traversal.

```APIDOC
## DFS

### Description
Performs a depth-first traversal starting at `start`, maintaining an explicit stack (non-recursive). `visit` is invoked with each vertex hash; returning `true` breaks out of the traversal (with `nil` error).

### Function Signature
```go
func DFS[K graph.Ordered, T any](g graph.Interface[K, T], start K, visit func(K) bool) error
```

### Parameters
- **g** (graph.Interface[K, T]) - Required - The graph.
- **start** (K) - Required - Starting vertex hash.
- **visit** (func(K) bool) - Required - Called per visited vertex; return `true` to stop.

### Returns
- **error** - `"could not get adjacency map: %w"` on failure; `"could not find start vertex with hash %v"` if `start` is not in the graph.

### Behavioral Notes
- Unlike `BFS`, `DFS` does **not** check for `g == nil`.
- It does not sort neighbors, so visit order depends on adjacency-map iteration order.
- Vertices are marked visited *after* being visited, and all neighbors are pushed unconditionally (visited ones are skipped when popped).

### Example
```go
err := traverse.DFS(g, 1, func(v int) bool {
	fmt.Println("visiting", v)
	return false // traverse everything reachable
})
```
```

--------------------------------

### EdgeData functional option

Source: https://github.com/sixafter/graph/blob/main/_autodocs/api-reference/simple.md

Functional option setting the metadata payload.

```go
func EdgeData(data any) graph.EdgeOption
```

--------------------------------

### Edge.Clone

Source: https://github.com/sixafter/graph/blob/main/_autodocs/api-reference/simple.md

Returns a deep copy of the edge. Requires non-nil properties.

```APIDOC
## Edge.Clone

### Description
Returns a deep copy of the edge. Requires non-nil properties.

### Method
Clone

### Signature
`Clone() graph.Edge[T]`

### Parameters
None

### Returns
- `graph.Edge[T]` - A deep copy of the edge.

```

--------------------------------

### EdgeItems functional option

Source: https://github.com/sixafter/graph/blob/main/_autodocs/api-reference/simple.md

Functional option setting the whole attribute map.

```go
func EdgeItems(items map[string]any) graph.EdgeOption
```

--------------------------------

### Handle graph errors with errors.Is and sentinel matching

Source: https://github.com/sixafter/graph/blob/main/_autodocs/errors.md

Use errors.Is to match sentinel errors from the graph library, including wrapped chains. The example checks for ErrVertexNotFound, ErrEdgeCreatesCycle, and ErrEdgeAlreadyExists after AddEdge. The library wraps sentinels with %w, so errors.Is works through wrapping chains like those from AddVerticesFrom.

```go
import (
	"errors"

	"github.com/sixafter/graph"
	"github.com/sixafter/graph/simple"
)

g, _ := simple.New(graph.StringHash, graph.Directed())
if err := g.AddEdge("A", "B"); err != nil {
	switch {
	case errors.Is(err, graph.ErrVertexNotFound):
		// one endpoint missing — add it first
	case errors.Is(err, graph.ErrEdgeCreatesCycle):
		// PreventCycles graph rejected the edge
	case errors.Is(err, graph.ErrEdgeAlreadyExists):
		// duplicate edge
	default:
		log.Fatal(err)
	}
}
```

--------------------------------

### simple.NewLike

Source: https://github.com/sixafter/graph/blob/main/_autodocs/configuration.md

Creates a new graph that copies the source graph's traits wholesale. It accepts no options.

```APIDOC
## simple.NewLike

### Description
Creates a new graph that copies the source graph's traits wholesale. It accepts no options.

### Signature
```go
func NewLike[K graph.Ordered, T any](g graph.Interface[K, T]) (graph.Interface[K, T], error)
```

### Parameters
- **g** (graph.Interface[K, T]) - Required - Source graph whose traits are copied.

### Return Value
- **graph.Interface[K, T]** - The new graph with copied traits.
- **error** - Error if construction fails.
```

--------------------------------

### EdgeItems

Source: https://github.com/sixafter/graph/blob/main/_autodocs/api-reference/simple.md

Functional option setting the whole attribute map.

```APIDOC
## EdgeItems

### Description
Functional option setting the whole attribute map.

### Signature
```go
func EdgeItems(items map[string]any) graph.EdgeOption
```
```

--------------------------------

### EdgeData

Source: https://github.com/sixafter/graph/blob/main/_autodocs/api-reference/simple.md

Functional option setting the metadata payload.

```APIDOC
## EdgeData

### Description
Functional option setting the metadata payload.

### Signature
```go
func EdgeData(data any) graph.EdgeOption
```
```

--------------------------------

### EdgeWeight

Source: https://github.com/sixafter/graph/blob/main/_autodocs/api-reference/simple.md

Functional option setting the edge weight.

```APIDOC
## EdgeWeight

### Description
Functional option setting the edge weight.

### Signature
```go
func EdgeWeight(weight float64) graph.EdgeOption
```
```

--------------------------------

### AddVerticesFrom method signature

Source: https://github.com/sixafter/graph/blob/main/_autodocs/api-reference/graph-interface.md

Imports all vertices from another graph. Stops at the first error.

```go
AddVerticesFrom(g Interface[K, T]) error
```

--------------------------------

### Create a feature branch

Source: https://github.com/sixafter/graph/blob/main/CONTRIBUTING.md

Creates a new branch for the contribution work.

```bash
git checkout -b feature/your-feature-name
```
Tokens:
Raw