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 chains through the resulting DAG are memoized in one linear pass, weighting each component by how many nodes it holds. Each query then expands a component chain into a concrete route through the members of every component it crosses, so every chain returned is a real simple path in the graph.

A 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.

Chains are ranked by weight (the node count of the components they cross) and, between equally heavy chains, by the lexicographic order of the components they cross, each component named by its smallest member. That order depends only on the graph, not on traversal, so repeated queries over the same graph return the same chains.

func NewChainFinder(ctx context.Context, g DirectedGraph) (*ChainFinder, error)

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

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

func (f *ChainFinder) LongestChains(ctx context.Context, limit int) ([][]string, error)

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