graph

package
v0.2.0 Latest Latest
Warning

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

Go to latest
Published: Feb 3, 2026 License: MIT Imports: 7 Imported by: 0

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func DetectCycles

func DetectCycles(g *DependencyGraph) (bool, [][]string)

DetectCycles identifies cycles in the dependency graph using Tarjan's algorithm. Returns:

  • hasCycles: true if any cycles exist in the graph
  • cycles: slice of cycles, where each cycle is a slice of package names

A cycle is defined as an SCC with more than one node, or a single node with a self-loop.

func FindStronglyConnectedComponents

func FindStronglyConnectedComponents(g *DependencyGraph) [][]string

FindStronglyConnectedComponents uses Tarjan's algorithm to identify strongly connected components (SCCs) in the dependency graph. Returns a slice of SCCs, where each SCC is a slice of package names. Also sets the SCC field on each node to its component ID.

Types

type CompressedEdge

type CompressedEdge struct {
	From     string
	To       string
	Strategy string            // Inherited from original edge
	BumpMap  map[string]string // Inherited from original edge
}

CompressedEdge represents an edge in the compressed graph

type CompressedGraph

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

CompressedGraph represents a dependency graph where SCCs are compressed into meta-nodes

func CompressGraph

func CompressGraph(g *DependencyGraph) *CompressedGraph

CompressGraph converts a dependency graph into a compressed graph where each SCC becomes a single meta-node. Prerequisites: FindStronglyConnectedComponents must be called first to set SCC IDs

func NewCompressedGraph

func NewCompressedGraph() *CompressedGraph

NewCompressedGraph creates a new empty compressed graph

func (*CompressedGraph) GetAllNodes

func (cg *CompressedGraph) GetAllNodes() []*CompressedNode

GetAllNodes returns all nodes in the compressed graph

func (*CompressedGraph) GetEdgeCount

func (cg *CompressedGraph) GetEdgeCount() int

GetEdgeCount returns the total number of edges in the compressed graph

func (*CompressedGraph) GetEdgesFrom

func (cg *CompressedGraph) GetEdgesFrom(from string) []CompressedEdge

GetEdgesFrom returns all edges originating from the given node

func (*CompressedGraph) GetNode

func (cg *CompressedGraph) GetNode(name string) (*CompressedNode, bool)

GetNode returns the compressed node with the given name

func (*CompressedGraph) GetNodeCount

func (cg *CompressedGraph) GetNodeCount() int

GetNodeCount returns the number of nodes in the compressed graph

type CompressedNode

type CompressedNode struct {
	Name    string   // Meta-node name (for cycles: "scc_N", for singles: original name)
	Members []string // Package names in this node (1 for singles, multiple for cycles)
	SCC     int      // Original SCC ID
}

CompressedNode represents a node in the compressed graph It may represent a single package or a strongly connected component (cycle)

func TopologicalSort

func TopologicalSort(cg *CompressedGraph) ([]*CompressedNode, error)

TopologicalSort performs a topological sort on a compressed graph using Kahn's algorithm. Returns nodes in dependency order (dependencies before dependents). The compressed graph must be a DAG (cycles should be compressed first). Returns an error if a cycle is detected (should not happen with properly compressed graph).

func (*CompressedNode) IsCycle

func (cn *CompressedNode) IsCycle() bool

IsCycle returns true if the node represents a cycle (has multiple members)

func (*CompressedNode) String

func (cn *CompressedNode) String() string

String returns a human-readable representation of the compressed node

type DependencyGraph

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

DependencyGraph represents a directed graph of package dependencies

func BuildGraph

func BuildGraph(cfg *config.Config) (*DependencyGraph, error)

BuildGraph constructs a dependency graph from package configurations Returns an error if any dependency references a non-existent package

func BuildGraphFromPackages

func BuildGraphFromPackages(packages []config.Package) (*DependencyGraph, error)

BuildGraphFromPackages is a convenience function for building a graph from a slice of packages It creates a temporary config and calls BuildGraph

func NewGraph

func NewGraph() *DependencyGraph

NewGraph creates a new empty dependency graph

func (*DependencyGraph) AddEdge

func (g *DependencyGraph) AddEdge(from, to string, strategy string, bumpMap map[string]string) error

AddEdge adds a directed edge from one package to another Returns an error if either node doesn't exist

func (*DependencyGraph) AddNode

func (g *DependencyGraph) AddNode(pkg config.Package) error

AddNode adds a package node to the graph Returns an error if a node with the same name already exists

func (*DependencyGraph) GetAllNodes

func (g *DependencyGraph) GetAllNodes() []*GraphNode

GetAllNodes returns all nodes in the graph

func (*DependencyGraph) GetEdgeCount

func (g *DependencyGraph) GetEdgeCount() int

GetEdgeCount returns the total number of edges in the graph

func (*DependencyGraph) GetEdgesFrom

func (g *DependencyGraph) GetEdgesFrom(from string) []GraphEdge

GetEdgesFrom returns all edges originating from the given node

func (*DependencyGraph) GetNode

func (g *DependencyGraph) GetNode(name string) (*GraphNode, bool)

GetNode returns the node with the given name, or nil if not found

func (*DependencyGraph) GetNodeCount

func (g *DependencyGraph) GetNodeCount() int

GetNodeCount returns the number of nodes in the graph

func (*DependencyGraph) SetSCC

func (g *DependencyGraph) SetSCC(name string, sccID int) error

SetSCC sets the Strongly Connected Component ID for a node

type GraphCache

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

GraphCache provides caching for dependency graphs to avoid rebuilding on every operation. Thread-safe for concurrent access.

func NewGraphCache

func NewGraphCache() *GraphCache

NewGraphCache creates a new graph cache.

func (*GraphCache) Clear

func (gc *GraphCache) Clear()

Clear removes all entries from the cache.

func (*GraphCache) GetOrBuild

func (gc *GraphCache) GetOrBuild(cfg *config.Config) (*DependencyGraph, error)

GetOrBuild returns a cached graph if available, otherwise builds and caches it. Errors are not cached - failed builds will retry on next call.

func (*GraphCache) Invalidate

func (gc *GraphCache) Invalidate(cfg *config.Config)

Invalidate removes the cache entry for a specific config.

type GraphEdge

type GraphEdge struct {
	From     string
	To       string
	Strategy string            // "fixed" or "linked"
	BumpMap  map[string]string // changeType -> changeType mapping
}

GraphEdge represents a directed edge in the dependency graph

type GraphNode

type GraphNode struct {
	Package config.Package
	SCC     int // Strongly Connected Component ID (0 if not in cycle)
}

GraphNode represents a node in the dependency graph

Jump to

Keyboard shortcuts

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