graph

type ChainFinder ¶ added in v0.2.2

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

ChainFinder answers longest-dependency-chain queries over a directed graph.

Finding the longest simple path in a graph that may contain cycles is NP-hard, so a ChainFinder walks the condensation instead: strongly connected components are collapsed to single vertices and the heaviest path through the resulting DAG is memoized in one linear pass, weighting each component by how many nodes it holds. Each query then expands that component path into a concrete route through the members of every component it crosses, so every chain returned is a real simple path in the graph.

The chain is maximal in dependency layers: no other simple path crosses more strongly connected components. Within a component the route is not guaranteed maximal — the final component is walked greedily through as many members as it can reach, while components the chain passes through are crossed by the shortest route between the edges that enter and leave them. Recovering the longest route through a cycle is the NP-hard problem again.

Ties are resolved by traversal order, which is derived from the graph's node ordering, so repeated queries over the same graph return the same chain.

func NewChainFinder(g DirectedGraph) *ChainFinder

func (f *ChainFinder) LongestChain() []string

func (f *ChainFinder) LongestChainFrom(nodeID string) []string

type CouplingConfig ¶

type CouplingConfig struct {
	// AbstractnessFunc computes the abstractness (0.0–1.0) for a given node.
	// pyscn: ratio of public names matching abstract patterns.
	// jscan: export ratio.
	// If nil, Abstractness defaults to 0.0 for all nodes.
	AbstractnessFunc func(nodeID string) (float64, error)
}

CouplingConfig configures coupling metric computation.

type CouplingMetrics ¶

type CouplingMetrics struct {
	NodeID       string
	Ca           int     // Afferent coupling (incoming edges)
	Ce           int     // Efferent coupling (outgoing edges)
	Instability  float64 // Ce / (Ca + Ce), 0 = maximally stable
	Abstractness float64 // Provided by language-specific callback
	Distance     float64 // |Abstractness + Instability - 1|
}

CouplingMetrics holds Robert Martin's package coupling metrics for a node.

type CycleDetector ¶

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

CycleDetector finds strongly connected components using Tarjan's algorithm.

func NewCycleDetector() *CycleDetector

func (d *CycleDetector) DetectCycles(g DirectedGraph) *CycleResult

type CycleResult ¶

type CycleResult struct {
	// Cycles contains all strongly connected components with more than one node.
	Cycles [][]string
	// HasCycles is true if any cycle was found.
	HasCycles bool
	// AffectedNodes contains all nodes that participate in at least one cycle.
	AffectedNodes map[string]bool
}

CycleResult holds the result of cycle detection via Tarjan's SCC algorithm.

type DirectedGraph ¶

type DirectedGraph interface {
	// NodeIDs returns all node identifiers in the graph.
	NodeIDs() []string
	// Successors returns the IDs of nodes that this node has edges to.
	Successors(nodeID string) []string
	// Predecessors returns the IDs of nodes that have edges to this node.
	Predecessors(nodeID string) []string
	// NodeCount returns the number of nodes in the graph.
	NodeCount() int
	// HasNode returns true if the node exists in the graph.
	HasNode(nodeID string) bool
}

DirectedGraph provides read-only access to a directed graph. pyscn's DependencyGraph (map[string]*ModuleNode) and jscan's domain.DependencyGraph (method-based) can both implement this.

type MapGraph ¶

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

MapGraph is a simple directed graph implementation backed by maps. Useful for testing and as a default implementation.

func NewMapGraph() *MapGraph

func (g *MapGraph) AddEdge(from, to string)

func (g *MapGraph) AddNode(id string)

func (g *MapGraph) HasNode(nodeID string) bool

func (g *MapGraph) NodeCount() int

func (g *MapGraph) NodeIDs() []string

func (g *MapGraph) Predecessors(nodeID string) []string

func (g *MapGraph) Successors(nodeID string) []string