Documentation
¶
Index ¶
- func DetectCycles(g *DependencyGraph) (bool, [][]string)
- func FindStronglyConnectedComponents(g *DependencyGraph) [][]string
- type CompressedEdge
- type CompressedGraph
- type CompressedNode
- type DependencyGraph
- func (g *DependencyGraph) AddEdge(from, to string, strategy string, bumpMap map[string]string) error
- func (g *DependencyGraph) AddNode(pkg config.Package) error
- func (g *DependencyGraph) GetAllNodes() []*GraphNode
- func (g *DependencyGraph) GetEdgeCount() int
- func (g *DependencyGraph) GetEdgesFrom(from string) []GraphEdge
- func (g *DependencyGraph) GetNode(name string) (*GraphNode, bool)
- func (g *DependencyGraph) GetNodeCount() int
- func (g *DependencyGraph) SetSCC(name string, sccID int) error
- type GraphCache
- type GraphEdge
- type GraphNode
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 (*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
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 (*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.