graph

package
v0.0.0-...-083b4a2 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: May 12, 2026 License: MIT Imports: 6 Imported by: 0

Documentation

Index

Constants

This section is empty.

Variables

View Source
var (
	ErrDuplicateNode = errors.New("graph: duplicate node")
	ErrUnknownNode   = errors.New("graph: unknown node")
	ErrUnknownEdge   = errors.New("graph: unknown edge")
	ErrSelfLoop      = errors.New("graph: self-loop not allowed")
)

Functions

func BFS

func BFS(g *Graph, roots []NodeID, maxDepth int, visit func(NodeID, int) bool)

BFS performs a breadth-first traversal starting from each node in roots, following forward edges. It visits each reachable node at most once and calls visit(node, depth) for each. Returns early if visit returns false. maxDepth of -1 means unlimited.

Types

type Builder

type Builder struct {
	// contains filtered or unexported fields
}

Builder accumulates nodes and edges, then produces an immutable Graph. Builder is not safe for concurrent use.

func NewBuilder

func NewBuilder() *Builder

NewBuilder returns an empty Builder.

func (*Builder) AddEdge

func (b *Builder) AddEdge(e Edge) error

AddEdge registers a directed edge. Returns ErrUnknownNode if either endpoint is not already registered. Returns ErrSelfLoop if From == To.

func (*Builder) AddNode

func (b *Builder) AddNode(n Node) error

AddNode registers a node. Returns ErrDuplicateNode if the ID already exists.

func (*Builder) Build

func (b *Builder) Build() (*Graph, error)

Build constructs an immutable Graph from the accumulated nodes and edges. It computes adjacency lists, reverse adjacency, max depth, and cycle detection.

type Edge

type Edge struct {
	From     NodeID
	To       NodeID
	Kind     EdgeKind
	Metadata map[string]any
}

Edge is an immutable directed relationship between two nodes.

func (Edge) Copy

func (e Edge) Copy() Edge

Copy returns a copy that callers cannot mutate.

type EdgeKind

type EdgeKind string

EdgeKind classifies the relationship between two nodes.

const (
	EdgeKindDependsOn EdgeKind = "depends_on"
	EdgeKindReplaces  EdgeKind = "replaces"
)

type FilterOptions

type FilterOptions struct {
	// MaxDepth limits traversal depth from root nodes. -1 means unlimited.
	MaxDepth int

	// IncludePatterns are regular expressions; a node is kept only if its Name
	// matches at least one pattern. Empty means keep all.
	IncludePatterns []*regexp.Regexp

	// ExcludePatterns are regular expressions; a node is removed if its Name
	// matches any pattern.
	ExcludePatterns []*regexp.Regexp

	// NoIndirect removes nodes that are only reachable as indirect dependencies.
	NoIndirect bool
}

FilterOptions controls which nodes and edges are included in a filtered graph.

type Graph

type Graph struct {
	// contains filtered or unexported fields
}

Graph is an immutable view of a dependency graph. All accessor methods return copies so callers cannot mutate internal state.

func Filter

func Filter(g *Graph, opts FilterOptions) (*Graph, error)

Filter returns a new Graph containing only the nodes (and their connecting edges) that satisfy opts. The original graph is not modified.

func (*Graph) Ancestors

func (g *Graph) Ancestors(id NodeID) []NodeID

Ancestors returns a copy of the slice of node IDs that depend on id (reverse edges).

func (*Graph) EdgeCount

func (g *Graph) EdgeCount() int

EdgeCount returns the number of edges in the graph.

func (*Graph) Edges

func (g *Graph) Edges() []Edge

Edges returns a copy of all edges, sorted by (From, To) for determinism.

func (*Graph) Neighbors

func (g *Graph) Neighbors(id NodeID) []NodeID

Neighbors returns a copy of the slice of node IDs that id directly depends on.

func (*Graph) Node

func (g *Graph) Node(id NodeID) (Node, bool)

Node returns a copy of the node with the given ID, and whether it was found.

func (*Graph) NodeCount

func (g *Graph) NodeCount() int

NodeCount returns the number of nodes in the graph.

func (*Graph) Nodes

func (g *Graph) Nodes() []Node

Nodes returns a copy of all nodes, sorted by ID for determinism.

func (*Graph) Stats

func (g *Graph) Stats() Stats

Stats returns aggregate metrics about the graph.

type Node

type Node struct {
	ID         NodeID
	Name       string
	Version    string
	Kind       NodeKind
	Indirect   bool
	Dev        bool
	ReplacedBy *Replacement
	Metadata   map[string]any
}

Node is an immutable value representing a single module in the graph.

func (Node) Copy

func (n Node) Copy() Node

Copy returns a deep-enough copy that callers cannot mutate this Node.

type NodeID

type NodeID string

NodeID is the canonical identifier for a node: "<module-path>@<version>". The main module uses an empty version: "example.com/myapp@".

func Ancestors

func Ancestors(g *Graph, id NodeID) []NodeID

Ancestors returns all node IDs that can reach id via forward edges (reverse BFS).

func Descendants

func Descendants(g *Graph, id NodeID, maxDepth int) []NodeID

Descendants returns all node IDs reachable from id via forward edges, excluding id itself. Honors maxDepth (-1 = unlimited).

func NewNodeID

func NewNodeID(path, version string) NodeID

NewNodeID constructs a NodeID from a module path and version.

type NodeKind

type NodeKind string

NodeKind classifies a node within the dependency graph.

const (
	NodeKindMain    NodeKind = "main"
	NodeKindModule  NodeKind = "module"
	NodeKindReplace NodeKind = "replace"
)

type Replacement

type Replacement struct {
	Path    string
	Version string
}

Replacement describes a module that stands in for another.

type Stats

type Stats struct {
	NodeCount int
	EdgeCount int
	MaxDepth  int
	HasCycles bool
}

Stats holds aggregate metrics about a graph.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL