graphmodel

package
v0.0.1 Latest Latest
Warning

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

 Go to latest Published: Jun 10, 2026 License: Apache-2.0 Imports: 9 Imported by: 0

Documentation

Overview

Package graphmodel holds the pure-domain graph model and analyses: the directed reference graph over documents and sections, the hierarchy tree, and the orphan/component/HITS/gap analyses defined on the document projection (see ADR 0007). It depends only on the standard library and the sibling corpus/identity/reference packages — never on a third-party graph library, application, or infrastructure (ADR 0004). All algorithms are hand-rolled with sorted iteration so output is fully deterministic.

Index

Constants

View Source 
const (
	// FMKeyMatlatl is the front-matter key (in FrontMatter.Extra) carrying
	// matlatl directives.
	FMKeyMatlatl = "matlatl"
	// FMValOrphanIntentional marks a document as an intentional orphan, excluding
	// it from Orphan/Unreachable findings.
	FMValOrphanIntentional = "orphan-intentional"
	// FMTypeIndex is the front-matter `type: index` value that marks a root.
	FMTypeIndex = "index"
)

Front-matter keys/values that affect analysis (ADR 0007).

View Source 
const DefaultInboundThreshold = 3

DefaultInboundThreshold is the under-linked discoverability floor: a document with fewer than this many inbound navigational links (but at least one outbound link, so it is not a dead-end) is reported as under-linked. The default of 3 follows Wikipedia's "discoverable" heuristic. A configured threshold of <=0 is normalized up to this value (Analyze does the floor).

View Source 
const DefaultMinSharedNeighbours = 2

DefaultMinSharedNeighbours is the floor on how many neighbours two documents must share before they are suggested as a link. A single shared neighbour is weak evidence (two docs both linked from one index page); requiring at least two keeps the signal conservative, mirroring how GapOptions.MinComponentSize defaults to 2 to avoid a blow-up of trivial singleton pairs. The zero value of LinkPredictionOptions.MinSharedNeighbours is normalized up to this default.

View Source 
const DefaultPageRankDamping = 0.85

DefaultPageRankDamping is the standard damping factor d (Brin & Page 1998): the probability the random surfer follows a link rather than teleporting.

View Source 
const DefaultPageRankEpsilon = 1e-6

DefaultPageRankEpsilon is the per-document L1 convergence threshold: iteration stops when the total absolute change Σ|newPR-pr| drops below N*epsilon.

View Source 
const DefaultPageRankMaxIterations = 100

DefaultPageRankMaxIterations bounds the power iteration so a pathological graph cannot spin forever (matching HitsOptions' cap).

View Source 
const LowScentThreshold = 0.20

LowScentThreshold is the Jaccard-similarity floor below which a navigational link's anchor text is flagged as low-scent (ADR 0016). A link whose label shares fewer than 20% of its meaningful tokens with the target's title gives a reader (or agent) almost no preview of where it leads — Pirolli & Card's "information scent" (1999): a weak scent makes a corpus hard to forage. Below this the anchor is reported; at or above it the link is considered to carry enough scent. Not a hard cutoff for any gating — the finding is always Info.

View Source 
const MaxGaps = 1000

MaxGaps is the hard defensive cap on the number of gaps DetectGaps will produce in a single pass. Gap detection is inherently O(k^2) in the number of kept components, so on pathological input (e.g. thousands of disconnected clusters) the pair count explodes. We stop at MaxGaps and surface truncation (GapResult.Truncated) rather than allocate millions of structs — mirroring how the scanner caps discovery at MaxFiles and surfaces a truncation notice (ADR 0003). No silent cap: the truncation is always reported.

View Source 
const MaxNeighbourFanout = 256

MaxNeighbourFanout bounds the degree of a common neighbour used as a pair-GENERATOR. A hub of degree d contributes O(d^2) candidate pairs; an index page linking hundreds of docs would otherwise dominate the candidate space and produce low-signal suggestions (everything "shares" the index). We skip any neighbour whose undirected degree exceeds this as a generator and set LinkSuggestionResult.Truncated / HubsSkipped, so the cost is bounded at O(Σ deg(c)^2) over non-hub neighbours. The threshold is the Adamic/Adar intuition made operational: very high-degree common neighbours carry little signal (their 1/log(deg) weight is already tiny), so skipping them as generators loses almost no ranking information while bounding the work.

View Source 
const MaxSuggestedLinks = 1000

MaxSuggestedLinks is the hard defensive cap on the number of suggested links PredictLinks will produce in a single pass. Like MaxGaps, the candidate space is super-linear (every shared neighbour generates O(deg^2) pairs), so on a densely-connected corpus the pair count can blow up. We stop at this cap and surface truncation (LinkSuggestionResult.Truncated) rather than allocate an unbounded slice — mirroring MaxGaps and the scanner's MaxFiles cap (ADR 0003). No silent cap: truncation is always reported.

Variables

View Source 
var DefaultNavigationalTypes = []reference.LinkType{
	reference.RelativeLink,
	reference.Wikilink,
	reference.Anchor,
	reference.ImageEmbed,
	reference.Transclusion,
	reference.FrontmatterRelated,
}

DefaultNavigationalTypes is the set of LinkTypes that count as navigational in the document projection (ADR 0007). External is deliberately absent: an external link neither reaches nor is reached.

Functions

func IntentionalOrphans 

func IntentionalOrphans(c *corpus.Corpus) []identity.DocumentID

IntentionalOrphans returns the sorted set of documents marked orphan-intentional.

Types

type AnalyzeOptions 

type AnalyzeOptions struct {
	// RootGlobs are configured root globs (in addition to conventions).
	RootGlobs []string
	// Hits tunes the HITS power iteration.
	Hits HitsOptions
	// PageRank tunes the PageRank power iteration (ADR 0016). Zero values are
	// normalized to the documented defaults inside ComputePageRank.
	PageRank PageRankOptions
	// Gaps tunes knowledge-gap detection.
	Gaps GapOptions
	// LinkPrediction tunes topology-based link prediction (ADR 0013). Zero values
	// are normalized to the documented defaults inside PredictLinks.
	LinkPrediction LinkPredictionOptions
	// InboundThreshold is the under-linked discoverability floor (ADR 0012).
	// Analyze normalizes a <=0 value up to DefaultInboundThreshold.
	InboundThreshold int
}

AnalyzeOptions bundles the tunables for a full analysis pass. The navigational-type set is fixed at graph-build time (BuildOptions), so it is not repeated here.

type Betweenness 

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

Betweenness holds per-document betweenness-centrality scores (ADR 0015). It is pure DATA, exactly like HitsScores: betweenness measures how often a document lies on shortest paths between OTHER documents — a high score marks a load-bearing connector whose removal lengthens or severs navigation. It produces no finding and never gates the check exit code; it is surfaced per-node and as a top-N block in graph.json, the human reports, and over MCP.

Concurrency / freeze boundary: the score map is built once by ComputeBetweenness and frozen thereafter. It is unexported and reached only through the read accessors (Score, TopBetweenness), so a downstream consumer cannot mutate the shared map; after construction the value is safe for concurrent reads (the P6 fan-out boundary), mirroring HitsScores.

func (Betweenness) Score 

func (b Betweenness) Score(id identity.DocumentID) float64

Score returns the betweenness score for id (0 if unknown). Read-only.

func (Betweenness) TopBetweenness 

func (b Betweenness) TopBetweenness(n int) []RankedDocument

TopBetweenness returns documents ranked by betweenness score descending, ties broken by DocumentID ascending (deterministic). n<=0 returns all. It reuses the hits.go rankDesc total order (direct float compare, no epsilon).

type BowtieBucket 

type BowtieBucket int

BowtieBucket classifies each document relative to the corpus's giant strongly connected component (the "core") in the bow-tie structure model (ADR 0012). It is pure classification DATA — it produces no per-document finding; it is surfaced in graph.json, the report summary, and over MCP so an agent can read the macro-shape of the corpus. 

const (
	// BucketDisconnected is the zero value: the document is in a weak component
	// that does NOT contain the giant SCC.
	BucketDisconnected BowtieBucket = iota
	// BucketCore documents are members of the giant SCC.
	BucketCore
	// BucketIn documents can reach the core but are not reachable from it.
	BucketIn
	// BucketOut documents are reachable from the core but cannot reach it.
	BucketOut
	// BucketTendril documents are in the same weak component as the core but
	// neither reach it nor are reached from it.
	BucketTendril
)

func (BowtieBucket) String 

func (b BowtieBucket) String() string

String returns the canonical bucket name used in artifacts.

type BowtieReport 

type BowtieReport struct {
	// Bucket maps each document to its bow-tie bucket.
	Bucket map[identity.DocumentID]BowtieBucket
	// GiantSCC is the ID (sorted-min member) of the chosen giant SCC, or "" when
	// the corpus is empty.
	GiantSCC identity.DocumentID
	// GiantSCCSize is the member count of the giant SCC. A size of 1 means the
	// corpus has no cyclic core (every SCC is a singleton); the human report
	// labels this "no cyclic core" but the buckets are still populated
	// deterministically.
	GiantSCCSize int
	// Counts tallies the documents per bucket.
	Counts map[BowtieBucket]int
}

BowtieReport is the bow-tie classification of every document relative to the giant SCC. It is deterministic: GiantSCC is chosen by most-members, tie-broken by the smallest sorted-min ID, and every traversal iterates sorted slices.

func (BowtieReport) BucketOf 

func (r BowtieReport) BucketOf(id identity.DocumentID) BowtieBucket

BucketOf returns the bow-tie bucket of id (BucketDisconnected when unknown or when no report was computed).

type Bridge 

type Bridge struct {
	A identity.DocumentID
	B identity.DocumentID
}

Bridge is an undirected edge whose removal disconnects the document graph (a single point of failure between two clusters). A and B are stored canonically with A < B by DocumentID so the pair is order-independent and deterministic.

type BuildOptions 

type BuildOptions struct {
	// NavigationalTypes overrides the default navigational LinkType set. Empty
	// means DefaultNavigationalTypes.
	NavigationalTypes []reference.LinkType
	// StrictDirectoryLinks controls how a directory link (TargetDirectory)
	// confers reachability (ADR 0008). When false (default, the lenient "vouch"
	// policy) a directory link adds navigational edges Origin → each direct-child
	// document, so the folder's contents are reachable. When true (the
	// documentation-hygiene hardline, wired to --strict) a directory link adds
	// only the primary Origin → index edge (when an index exists) and does NOT
	// vouch for the directory's other contents.
	StrictDirectoryLinks bool
}

BuildOptions tunes graph construction.

type Component 

type Component struct {
	ID      identity.DocumentID
	Members []identity.DocumentID
}

Component is a connected component: an ID (the sorted-minimum member, for determinism) and its sorted member documents.

type Components 

type Components []Component

Components is a sorted list of components (ordered by ID).

type CriticalStructure 

type CriticalStructure struct {
	// ArticulationPoints are the cut vertices, sorted by DocumentID.
	ArticulationPoints []identity.DocumentID
	// Bridges are the cut edges (A<B canonical), sorted by (A, B).
	Bridges []Bridge
}

CriticalStructure is the corpus' critical-path structure (ADR 0015): the articulation points (cut VERTICES) and bridges (cut EDGES) of the UNDIRECTED link closure. An articulation point is a document whose removal fragments the corpus into more pieces; a bridge is the only link connecting two parts. Both are surfaced as non-gating Info findings AND as graph.json data. Slices are sorted for determinism.

func (CriticalStructure) IsArticulation 

func (cs CriticalStructure) IsArticulation(id identity.DocumentID) bool

IsArticulation reports whether id is a cut vertex. Linear scan over the (typically small) sorted articulation-point set; used by the emitters to set the per-node isArticulation flag.

type Degree 

type Degree struct {
	In  int
	Out int
}

Degree holds the in/out navigational degree of a document in the projection.

type DegreeIndex 

type DegreeIndex map[identity.DocumentID]Degree

DegreeIndex maps each document to its projection in/out degree.

Freeze boundary: a DegreeIndex is built once by BuildDegreeIndex and is treated as immutable thereafter (it is embedded by value in the shared *GraphMetrics). Read it through the Degree accessor rather than mutating the map; after construction it is safe for concurrent reads (the P6 fan-out boundary).

func (DegreeIndex) Degree 

func (d DegreeIndex) Degree(id identity.DocumentID) Degree

Degree returns the in/out projection degree of id (the zero Degree if id is unknown). Read-only accessor over the frozen index.

type Edge 

type Edge struct {
	From NodeID
	To   NodeID
	Kind EdgeKind
	Type reference.LinkType
	// AnchorText is the human-facing display text of the link (ADR 0016), carried
	// from the resolved reference so the information-scent analysis can score the
	// label against the target's title. Meaningful only for EdgeReference edges;
	// empty for EdgeContains and for reference edges with no display text.
	AnchorText string
	// Line is the 1-based source line of the reference in its origin document
	// (ADR 0016), so a scent finding can be pinned to the link. Meaningful only
	// for EdgeReference edges; 0 for EdgeContains.
	Line int
}

Edge is a directed, typed edge. Type is meaningful only for EdgeReference edges; for EdgeContains it is left at the zero LinkType and ignored.

type EdgeKind 

type EdgeKind int

EdgeKind distinguishes structural containment edges from navigational reference edges (ADR 0007). 

const (
	// EdgeContains is a structural edge (Document→Section, Section→Section).
	EdgeContains EdgeKind = iota
	// EdgeReference is a navigational edge (a resolved in-corpus link).
	EdgeReference
)

func (EdgeKind) String 

func (k EdgeKind) String() string

String returns the canonical name of the edge kind.

type Gap 

type Gap struct {
	ComponentA identity.DocumentID
	ComponentB identity.DocumentID
	// RepresentativeA/B are the (sorted-min) member of each component, useful as
	// a concrete bridge suggestion.
	RepresentativeA identity.DocumentID
	RepresentativeB identity.DocumentID
}

Gap is a candidate bridge between two distinct weakly-connected components, identified by their IDs (the smaller ID first) and a representative document from each side. Because the two components are distinct WCCs, they have no navigational links between them by construction.

type GapOptions 

type GapOptions struct {
	// MinComponentSize ignores trivial components smaller than this on either
	// side. The pipeline sets it to 2: isolated singletons are already reported
	// as orphans (ADR 0007), so they must NOT also generate a combinatorial
	// blow-up of singleton-vs-singleton gaps. The zero value is normalized to 2
	// to keep that safe default even for a zero-value GapOptions.
	MinComponentSize int
}

GapOptions tunes knowledge-gap detection: finding pairs of weakly-connected components that could plausibly be bridged — candidate "knowledge gaps" where two clusters of documentation likely should reference each other but do not.

Gap detection is EXPERIMENTAL and intentionally conservative (ADR 0007). By construction, two DISTINCT weakly-connected components have ZERO navigational links between them — that disconnection is exactly what makes them separate weak components. So a "gap" is simply a pair of distinct WCCs (each at or above MinComponentSize): two disconnected clusters that may warrant a bridge. Callers label gaps Info severity, so they never fail a build. The signal is a heuristic, not a correctness claim: linking the two clusters merges them into one component and removes the pair.

type GapResult 

type GapResult struct {
	Gaps      []Gap
	Truncated bool
}

GapResult is the outcome of gap detection: the (sorted) candidate gaps plus whether the list was truncated at MaxGaps. Truncated is surfaced as a notice by the caller, exactly like the scanner's MaxFiles truncation.

func DetectGaps 

func DetectGaps(wccs Components, opts GapOptions) GapResult

DetectGaps reports candidate gaps between pairs of distinct weakly-connected components. It takes the ALREADY-COMPUTED WCC components (one traversal, in metrics.go) rather than recomputing them, so data flow is explicit and there is no duplicate union-find pass. Distinct WCCs have zero cross-links by construction (ADR 0007), so every pair of kept components is a gap; the only tuning knob is MinComponentSize, which drops trivial/singleton clusters.

Results are deterministic: wccs is sorted by ID (see WeaklyConnectedComponents), so the nested pair loop yields gaps in (ComponentA, ComponentB) sorted order. The total is hard-capped at MaxGaps; on hitting the cap, detection stops and GapResult.Truncated is set (no silent truncation).

type GraphMetrics 

type GraphMetrics struct {
	// Graph is the built reference graph (vertices + edges + projection), for
	// emitters that render the graph itself (graph.json, DOT/Mermaid).
	Graph *ReferenceGraph
	// Hierarchy is the folder/front-matter parent tree (breadcrumbs/index).
	Hierarchy *HierarchyTree
	// RootSet is the resolved reachability root set (may be Indeterminate).
	RootSet RootSet
	// Reachability holds the BFS reachability result (empty if Indeterminate).
	Reachability Reachability
	// Degrees is the per-document in/out navigational degree.
	Degrees DegreeIndex
	// Orphans holds isolated-orphan and unreachable classification.
	Orphans OrphanReport
	// WCC / SCC are the weak and strong components (sorted, deterministic IDs).
	WCC Components
	// SCC are the strongly-connected components (cycles collapse to one).
	SCC Components
	// Bowtie is the bow-tie classification of every document relative to the
	// giant SCC (core/in/out/tendril/disconnected). Pure data, not findings.
	Bowtie BowtieReport
	// HITS holds hub/authority scores.
	HITS HitsScores
	// Gaps are experimental knowledge-gap bridge candidates.
	Gaps []Gap
	// GapsTruncated reports that the gap list was capped at MaxGaps (the corpus
	// has pathologically many disconnected clusters); surfaced as a notice.
	GapsTruncated bool
	// SuggestedLinks are topology-based link-prediction suggestions: UNLINKED but
	// structurally-close document pairs (ADR 0013). An ADDITIVE signal alongside
	// Gaps; ranked by Adamic/Adar, capped at MaxSuggestedLinks.
	SuggestedLinks []LinkSuggestion
	// SuggestedLinksTruncated reports the suggestion list was capped (MaxSuggestedLinks)
	// or a hub neighbour was skipped as a generator (MaxNeighbourFanout); surfaced
	// as a notice.
	SuggestedLinksTruncated bool
	// Navigability holds the corpus-level navigability / structural-health scalars
	// (ADR 0014): compactness, stratum, characteristic/median path length,
	// clustering coefficient, diameter. Pure data — never a finding, never gates
	// the check exit code.
	Navigability Navigability
	// Betweenness holds per-document betweenness centrality over the DIRECTED
	// projection (ADR 0015): how often a document lies on shortest paths between
	// others (a load-bearing connector). Pure data, like HITS — never a finding,
	// never gates the exit code.
	Betweenness Betweenness
	// Critical holds the corpus' critical-path structure (ADR 0015): articulation
	// points (cut vertices) and bridges (cut edges) of the UNDIRECTED closure. It
	// is surfaced BOTH as non-gating Info findings (articulation-point / bridge)
	// AND as graph.json data.
	Critical CriticalStructure
	// PageRank holds per-document PageRank scores (ADR 0016): global importance via
	// the random-surfer stationary distribution. Pure data, like HITS/Betweenness —
	// never a finding, never gates the exit code. It also ranks the reading-order
	// Trails.
	PageRank PageRankScores
	// Trails are the per-weak-component suggested reading orders (ADR 0016): a
	// topologically-valid order that prefers higher-PageRank docs among the
	// available frontier. Pure data; surfaced in the emit bundle (trails.json +
	// the llms.txt reading-order block).
	Trails []Trail
	// Scent holds the low-scent navigational links (ADR 0016): links whose anchor
	// text shares too few tokens with the target's title to preview where they
	// lead. Surfaced as non-gating Info low-scent-anchor findings.
	Scent []ScentFinding
	// contains filtered or unexported fields
}

GraphMetrics is the frozen carrier of all P3 graph analysis results. It is the single struct later phases (P4 human emitters, P5 graph.json/llms.txt) read from, alongside the AnalysisReport. Every field is computed deterministically and treated as immutable after construction.

func Analyze 

func Analyze(g *ReferenceGraph, c *corpus.Corpus, opts AnalyzeOptions) *GraphMetrics

Analyze runs the full P3 analysis over a pre-built graph and the corpus, returning the frozen metrics carrier. The graph must already be built from the corpus + resolved references. This is the single entry point the pipeline calls. All sub-results are deterministic.

func (*GraphMetrics) ComponentOf 

func (m *GraphMetrics) ComponentOf(id identity.DocumentID) identity.DocumentID

ComponentOf returns the WCC ID of a document (the sorted-min member of its weak component), or "" if unknown.

type HierarchyNode 

type HierarchyNode struct {
	ID       identity.DocumentID
	Children []identity.DocumentID // sorted
}

HierarchyNode is a node in the document hierarchy: a document plus its children (documents whose folder-or-front-matter parent is this document).

type HierarchyTree 

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

HierarchyTree is the folder / front-matter-parent hierarchy over documents, for later breadcrumb/index emitters (P4). It does not drive analysis. The parent of a document is, in precedence order: its front-matter `parent` (if it resolves to a known document), else the README.md/index.md of its directory (if one exists and is not itself), else none (a top-level entry).

func BuildHierarchyTree 

func BuildHierarchyTree(c *corpus.Corpus) *HierarchyTree

BuildHierarchyTree constructs the hierarchy from the corpus. Deterministic: children and roots are sorted.

func (*HierarchyTree) Children 

func (t *HierarchyTree) Children(id identity.DocumentID) []identity.DocumentID

Children returns the sorted children of a document.

func (*HierarchyTree) Roots 

func (t *HierarchyTree) Roots() []identity.DocumentID

Roots returns the sorted top-level documents.

type HitsOptions 

type HitsOptions struct {
	MaxIterations int     // default 100
	Epsilon       float64 // L2-delta convergence threshold; default 1e-8
}

HitsOptions tunes the HITS power iteration.

type HitsScores 

type HitsScores struct {
	Iterations int
	Converged  bool
	// contains filtered or unexported fields
}

HitsScores holds per-document hub and authority scores plus the iteration metadata, for determinism auditing.

Concurrency / freeze boundary: the hub and authority maps are built once by ComputeHITS and frozen thereafter. They are unexported and reached only through the read accessors (HubScore/AuthorityScore/Score, TopHubs/ TopAuthorities) so a downstream consumer cannot mutate the shared maps. After construction the value is safe for concurrent reads (the P6 fan-out boundary).

func (HitsScores) AuthorityScore 

func (h HitsScores) AuthorityScore(id identity.DocumentID) float64

AuthorityScore returns the authority score for id (0 if unknown). Read-only.

func (HitsScores) HubScore 

func (h HitsScores) HubScore(id identity.DocumentID) float64

HubScore returns the hub score for id (0 if unknown). Read-only.

func (HitsScores) Score 

func (h HitsScores) Score(id identity.DocumentID) (hub, authority float64)

Score returns both the hub and authority scores for id (0 if unknown).

func (HitsScores) TopAuthorities 

func (h HitsScores) TopAuthorities(n int) []RankedDocument

TopAuthorities returns documents ranked by authority score descending, ties broken by DocumentID ascending (deterministic). n<=0 returns all.

func (HitsScores) TopHubs 

func (h HitsScores) TopHubs(n int) []RankedDocument

TopHubs returns documents ranked by hub score descending, ties broken by DocumentID ascending. n<=0 returns all.

type LinkPredictionOptions 

type LinkPredictionOptions struct {
	// MinSharedNeighbours is the minimum |N(A)∩N(B)| an unlinked pair must have
	// to be suggested. <=0 is normalized to DefaultMinSharedNeighbours (2).
	MinSharedNeighbours int
	// MaxFanout is the undirected-degree ceiling above which a common neighbour is
	// skipped as a pair-generator (the hub guard). <=0 is normalized to
	// MaxNeighbourFanout.
	MaxFanout int
}

LinkPredictionOptions tunes topology-based link prediction (the suggested-link signal). Zero values are normalized to the documented defaults, like GapOptions.MinComponentSize.

type LinkSuggestion 

type LinkSuggestion struct {
	DocA identity.DocumentID
	DocB identity.DocumentID
	// SharedNeighbours is |N(A)∩N(B)| over the undirected closure.
	SharedNeighbours int
	// Coupling is bibliographic coupling: |out(A)∩out(B)| (both link to the same
	// docs).
	Coupling int
	// CoCitation is |in(A)∩in(B)| (the same docs link to both).
	CoCitation int
	// AdamicAdar is the primary similarity score: Σ over common neighbours c (with
	// |N(c)|>1) of 1/log(|N(c)|). Rare shared neighbours weigh more than hubs.
	AdamicAdar float64
}

LinkSuggestion is a topology-based suggestion that two UNLINKED documents (neither links to the other) may warrant a navigational link, because they are structurally close: they share neighbours in the undirected closure N(x)=out(x)∪in(x). It reports the primary Adamic/Adar score plus the directed components (bibliographic coupling and co-citation) so a consumer can see WHY. DocA < DocB by DocumentID string (the pair is unordered, stored canonically).

type LinkSuggestionResult 

type LinkSuggestionResult struct {
	Suggestions []LinkSuggestion
	Truncated   bool
	// HubsSkipped reports that at least one common neighbour exceeded MaxFanout and
	// was skipped as a pair-generator (so some structurally-close pairs may be
	// absent). It implies Truncated.
	HubsSkipped bool
}

LinkSuggestionResult is the outcome of link prediction: the ranked, capped suggestions plus whether the list was truncated. Truncated is set when EITHER the MaxSuggestedLinks cap was hit OR a hub above MaxFanout was skipped as a generator (HubsSkipped) — in both cases the list is not exhaustive and the caller surfaces a notice, exactly like GapResult.Truncated. 

type Navigability struct {
	// Compactness (Cp) is the directed reachability-weighted compactness in [0,1]
	// over the document projection: 1 means every ordered pair reaches the other
	// in one hop (fully connected), 0 means nothing reaches anything. Unreachable
	// ordered pairs are charged the maximum sub-distance K=N (the doc count), so a
	// disconnected corpus scores low.
	Compactness float64
	// Stratum measures how linear/hierarchical the directed reachability is, in
	// [0,1]: 1 is a pure chain (a strict status order), 0 is a pure cycle / fully
	// symmetric structure (no net flow direction). Computed from per-node status
	// = inStatus - outStatus over FINITE sub-distances.
	Stratum float64
	// CharacteristicPathLength is the MEAN shortest-path distance over all finite
	// (reachable) ordered pairs in the UNDIRECTED closure. 0 when there are no
	// finite pairs.
	CharacteristicPathLength float64
	// MedianPathLength is the MEDIAN of the same finite-pair distance distribution
	// (computed from the histogram, no float sort). 0 when there are no finite
	// pairs.
	MedianPathLength float64
	// ClusteringCoefficient is the Watts-Strogatz global clustering coefficient in
	// [0,1] over the undirected closure: the mean local clustering over nodes with
	// undirected degree >= 2 (degree-<2 nodes are EXCLUDED, not counted as 0).
	ClusteringCoefficient float64
	// Diameter is the longest finite shortest-path distance in the undirected
	// closure (the eccentricity bound). 0 when there are no finite pairs.
	Diameter int
	// ReachablePairs is the number of ordered (i!=j) pairs with a FINITE
	// undirected-closure distance — the count behind CPL/median/diameter.
	ReachablePairs int
	// Documents is N, the document count the metrics were computed over.
	Documents int
}

Navigability holds the corpus-level navigability / structural-health scalars (P9). It is pure DATA, like BowtieReport: it produces no finding and never gates the check exit code; it is surfaced in graph.json (summary.navigability), the human reports, and over MCP so an agent can read how navigable the corpus is. Floats are plain float64 here in the domain; the fixed-precision wire Float lives only in the graphjson layer (exactly like HITS scores).

type Node 

type Node struct {
	ID   NodeID
	Kind NodeKind
	// Document is the owning document identity (the document itself for a
	// document vertex, or the section's document for a section vertex).
	Document identity.DocumentID
	// Slug is the section slug for a section vertex; empty for a document vertex.
	Slug string
}

Node is a graph vertex.

type NodeID 

type NodeID string

NodeID identifies a vertex. A Document vertex's NodeID is exactly the DocumentID string; a Section vertex's NodeID is "<DocumentID>#<slug>" (ADR 0007).

func NodeIDForDocument 

func NodeIDForDocument(id identity.DocumentID) NodeID

NodeIDForDocument returns the NodeID of a document vertex (the DocumentID's string), so a Document-kind NodeID round-trips to its DocumentID.

func NodeIDForSection 

func NodeIDForSection(id identity.DocumentID, slug string) NodeID

NodeIDForSection returns the NodeID of a section vertex: "<DocumentID>#<slug>".

func (NodeID) String 

func (n NodeID) String() string

String returns the identifier as a plain string.

type NodeKind 

type NodeKind int

NodeKind distinguishes document vertices from section vertices. 

const (
	// NodeKindDocument is a whole-file vertex.
	NodeKindDocument NodeKind = iota
	// NodeKindSection is a heading-scoped vertex.
	NodeKindSection
)

func (NodeKind) String 

func (k NodeKind) String() string

String returns the canonical name of the node kind.

func (NodeKind) Valid 

func (k NodeKind) Valid() bool

Valid reports whether k is a defined NodeKind.

type OrphanOptions 

type OrphanOptions struct {
	// InboundThreshold is the under-linked discoverability floor: a non-exempt
	// document with outbound links but fewer than this many inbound links is
	// under-linked. Callers should pass a normalized (>=1) value; DetectOrphans
	// floors a <=0 value up to DefaultInboundThreshold defensively.
	InboundThreshold int
}

OrphanOptions tunes the structure-ladder classification.

type OrphanReport 

type OrphanReport struct {
	// Isolated documents have in-degree 0 AND out-degree 0 in the projection
	// (the most-severe orphan tier).
	Isolated []identity.DocumentID
	// DeadEnd documents have inbound links but link to nothing onward (in>0 &&
	// out==0). Mutually exclusive with Isolated and UnderLinked (single bucket).
	DeadEnd []identity.DocumentID
	// UnderLinked documents have outbound links but fewer inbound links than the
	// discoverability threshold (out>0 && 0<=in<threshold, excluding the in==0
	// dead-of-isolated case which is Isolated). Mutually exclusive with the other
	// tiers.
	UnderLinked []identity.DocumentID
	// Unreachable documents are not reached from the root set (excluding those
	// already reported as Isolated, to avoid double-reporting the same doc).
	// Orthogonal to Dead-end/Under-linked: only a fully-isolated Orphan suppresses
	// it (ADR 0012).
	Unreachable []identity.DocumentID
	// Indeterminate mirrors Reachability.Indeterminate: when true, Unreachable is
	// empty (reachability was not computed) but the structure tiers are still
	// populated.
	Indeterminate bool
}

OrphanReport classifies documents into a single-bucket structure ladder (isolated orphan, dead-end, under-linked) plus the orthogonal unreachable set, with intentional orphans and roots suppressed (ADR 0007, ADR 0012).

type PageRankOptions 

type PageRankOptions struct {
	// Damping is the teleport-vs-follow factor d. <=0 (or >=1) is normalized to
	// DefaultPageRankDamping.
	Damping float64
	// Epsilon is the L1 convergence threshold per document. <=0 normalized to
	// DefaultPageRankEpsilon.
	Epsilon float64
	// MaxIterations bounds the power iteration. <=0 normalized to
	// DefaultPageRankMaxIterations.
	MaxIterations int
}

PageRankOptions tunes the PageRank power iteration. Zero values are normalized to the documented defaults (Damping 0.85, Epsilon 1e-6, MaxIterations 100).

type PageRankScores 

type PageRankScores struct {
	Iterations int
	Converged  bool
	// contains filtered or unexported fields
}

PageRankScores holds per-document PageRank scores plus iteration metadata, for determinism auditing. PageRank is the stationary distribution of a random surfer over the directed document projection (Brin & Page 1998): the probability mass that accumulates at a document is its global importance. It is pure DATA, exactly like HitsScores and Betweenness — it produces no finding and never gates the check exit code; it is surfaced per-node and as a top-N block in graph.json and the human reports, and it drives the reading-order trails (ADR 0016).

Unlike HITS (which sums RAW neighbour scores and L2-normalizes each round), PageRank divides each contributing neighbour's score by that neighbour's out-degree and conserves total mass (Σ PR = 1), so there is NO normalization step: dangling nodes (no out-links) have their mass redistributed uniformly (Langville & Meyer 2006; the NetworkX dangling convention).

Concurrency / freeze boundary: the score map is built once by ComputePageRank and frozen thereafter. It is unexported and reached only through the read accessors (Score, Top), so a downstream consumer cannot mutate the shared map; after construction the value is safe for concurrent reads (the P6 fan-out boundary), mirroring HitsScores and Betweenness.

func (PageRankScores) Score 

func (p PageRankScores) Score(id identity.DocumentID) float64

Score returns the PageRank score for id (0 if unknown). Read-only.

func (PageRankScores) Top 

func (p PageRankScores) Top(n int) []RankedDocument

Top returns documents ranked by PageRank score descending, ties broken by DocumentID ascending (deterministic). n<=0 returns all. It reuses the hits.go rankDesc total order (direct float compare, no epsilon).

type RankedDocument 

type RankedDocument struct {
	ID    identity.DocumentID
	Score float64
}

RankedDocument pairs a document with a score, for deterministic top-N output.

type Reachability 

type Reachability struct {
	// Indeterminate is true when the root set was empty (ADR 0007): reachability
	// was not computed and Reached/Unreachable are empty.
	Indeterminate bool
	// Reached is the sorted set of documents reachable from the root set
	// (includes the roots themselves).
	Reached []identity.DocumentID
	// Unreachable is the sorted set of in-corpus documents not reached.
	Unreachable []identity.DocumentID
}

Reachability is the BFS reachability result over the document projection.

type ReferenceGraph 

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

ReferenceGraph is the mixed-granularity graph: document and section vertices with CONTAINS and REFERENCE edges. It exposes the document projection that all analyses run on. Built once and treated as immutable.

func BuildReferenceGraph 

func BuildReferenceGraph(c *corpus.Corpus, refs []reference.Reference, opts BuildOptions) *ReferenceGraph

BuildReferenceGraph assembles the graph from a frozen corpus and the resolved references over it. The corpus supplies vertices (documents + sections) and the CONTAINS tree; refs supply REFERENCE edges (only Health==Valid, in-corpus targets). Origin is attributed to the containing section when the ref line falls in a section span, else the document (ADR 0007).

func (*ReferenceGraph) BuildDegreeIndex 

func (g *ReferenceGraph) BuildDegreeIndex() DegreeIndex

BuildDegreeIndex computes in/out degree for every document from the projection.

func (*ReferenceGraph) ClassifyBowtie 

func (g *ReferenceGraph) ClassifyBowtie(scc, wcc Components) BowtieReport

ClassifyBowtie computes the bow-tie report relative to the giant SCC. It reuses the already-computed SCC and WCC component lists (Analyze passes them in) so it does no redundant traversal of the component decomposition; it only runs two forward/reverse BFS passes over the document projection from the core.

Determinism: the giant SCC is picked by descending member count, tie-broken by the smallest component ID; BFS uses sorted projAdj / projRev neighbor lists and a sorted seed order, so the report is identical regardless of map order.

func (*ReferenceGraph) ComputeBetweenness 

func (g *ReferenceGraph) ComputeBetweenness() Betweenness

ComputeBetweenness computes directed betweenness centrality over the document projection (projAdj) with Brandes' algorithm (ADR 0015). Scores are normalized by (n-1)(n-2) — the number of ordered (s,t) pairs excluding a given vertex v — so they land in [0,1]; there is NO halving (the graph is directed). A corpus with n<3 documents has no vertex that can lie strictly between two others, so every score is 0.

Determinism: the per-source forward pass runs in sorted source order with sorted neighbour expansion (ForEachSourceBFS), the predecessor lists it yields are sorted, and the dependency back-accumulation walks the BFS order in reverse — so every float division and sum runs in a fixed order and the result is byte-stable regardless of map iteration order (ADR 0007). Cost: O(V·(V+E)) time, O(V+E) transient memory (no V² matrix), matching the streaming SSSP shape of ForEachSourceDistances.

func (*ReferenceGraph) ComputeCriticalStructure 

func (g *ReferenceGraph) ComputeCriticalStructure() CriticalStructure

ComputeCriticalStructure finds the articulation points and bridges of the UNDIRECTED link closure (N(x)=out(x)∪in(x)) with Tarjan's low-link algorithm, driven iteratively over an explicit stack — NO recursion — so an arbitrarily long link chain cannot overflow the goroutine stack (the components.go stack-safety contract, ADR 0015). Betweenness, by contrast, runs over the DIRECTED projection (centrality.go); the directed/undirected split mirrors ADR 0014's navigability metrics.

Determinism: the closure neighbour lists are sorted/deduped/self-loop-free (undirectedClosure), the DFS is driven from every undiscovered document in sorted g.documents order (a forest over disconnected components), neighbours are visited in sorted order, and both output slices are sorted — so the result is byte-stable regardless of map iteration order (ADR 0007).

Edge cases: empty/single-node → none; a 2-node A-B → one bridge, no articulation; a cycle → none/none; a path A-B-C-D → {B,C} articulation and every edge a bridge. The DFS root is an articulation point IFF it has >=2 DFS-tree children.

func (*ReferenceGraph) ComputeHITS 

func (g *ReferenceGraph) ComputeHITS(opts HitsOptions) HitsScores

ComputeHITS runs the HITS hub/authority algorithm over the directed document projection. Iteration order is sorted (documents and neighbors) and scores are L2-normalized each round, so output is deterministic across runs and input orderings (ADR 0007). Authority(p) = sum of Hub(q) over q→p; Hub(p) = sum of Authority(q) over p→q.

func (*ReferenceGraph) ComputeNavigability 

func (g *ReferenceGraph) ComputeNavigability() Navigability

ComputeNavigability computes the corpus navigability scalars over the document projection (ADR 0014). Compactness and stratum use the DIRECTED projection; characteristic/median path length, diameter and clustering use the UNDIRECTED closure N(x)=out(x)∪in(x). It is deterministic: all iteration is over the sorted g.documents and sorted neighbour lists, float sums are accumulated in that fixed order, and the median is read from a histogram (no float sort).

Edge cases: N<=1 yields a zero-valued struct (Documents=N) — there are no ordered pairs, so every metric is 0 with no division by zero.

func (*ReferenceGraph) ComputePageRank 

func (g *ReferenceGraph) ComputePageRank(opts PageRankOptions) PageRankScores

ComputePageRank runs the PageRank power iteration over the directed document projection (ADR 0016). Per node v: 

newPR[v] = (1-d)/N + d*( Σ_{u → v} pr[u]/outdeg(u) + danglingSum/N )

where d is the damping factor, N the document count, and danglingSum the total score of dangling nodes (no out-links), redistributed uniformly so total mass is conserved (Σ PR = 1). There is NO L2 normalization (unlike HITS).

Determinism (CLAUDE.md): every float SUM runs in a fixed order — the per-node neighbour contribution iterates g.projRev[v] (already sorted), and danglingSum accumulates over g.documents (sorted) — so the float addition order is byte-stable regardless of map iteration order. Convergence is the L1 delta Σ_{v}|newPR[v]-pr[v]| < N*epsilon; on convergence the completed iteration is counted (matching hits.go). An empty graph returns early (Converged); a single-document corpus scores 1.0.

func (*ReferenceGraph) ComputeReachability 

func (g *ReferenceGraph) ComputeReachability(rs RootSet) Reachability

ComputeReachability runs BFS from the root set over projection out-edges. When the root set is indeterminate, it returns Indeterminate=true and computes nothing (callers must not mark everything unreachable, ADR 0005/0007). Iteration is sorted for determinism.

func (*ReferenceGraph) ComputeScent 

func (g *ReferenceGraph) ComputeScent(c *corpus.Corpus) []ScentFinding

ComputeScent scores every navigational, in-corpus REFERENCE edge's anchor text against its target document's title and returns the low-scent links (ADR 0016). It runs on the GRAPH (the resolved reference edges carry the anchor text and source line), not on a refs parameter, so the analysis stays a method on the graph. The corpus supplies target titles (corpus.Document.Title, the same resolution the emit layer uses, so they cannot drift).

Per navigational reference edge with an in-corpus document target:

  • Normalize the anchor (lowercase, collapse whitespace, trim). If it is in scentFreePhrases → score 0.0 (flagged). If the RAW anchor is wholly backtick-wrapped (a code identifier like `Foo`) → SKIP (no finding; code identifiers are legitimate labels).
  • Tokenize anchor and title (lowercase, split on non-letter/digit, drop stopwords and length-1 tokens, sort+dedup). An empty anchor token set (bare URL / numeric) → score 0.0. If the title yields no tokens, fall back to the union of the target's heading texts.
  • score = Jaccard(anchorTokens, titleTokens) = |∩| / |∪| (sorted merge-walk; the single division is the only float). A finding is emitted when score < LowScentThreshold.

Two edges are never flagged, regardless of score:

  • Synthetic directory-expansion edges (ADR 0008): a directory link expands into one anchor-less, line-0 "vouch" edge per directory member. A finding must point at an authored link with a source line, so edges with Line <= 0 are skipped (this removes the phantom empty-anchor findings).
  • Stable-identifier anchors (ADR 0016): an anchor naming the target's stable identifier (e.g. "ADR 0010" → 0010-*.md) points the reader at the exact doc and is exempt via namesTargetIdentifier — but a bare path-/filename-like anchor (e.g. "docs/dev-guide.md") is NOT exempt and stays flagged.

Determinism (CLAUDE.md): edges are iterated in sorted order, token sets are sorted, the Jaccard intersection/union are sorted merge-walks (never map ranging), and findings are returned sorted by (Source, Line, Target, AnchorText). There is NO count cap on scent findings (bounded by the link count); like the no-silent-cap convention, this is a deliberate decision stated in ADR 0016.

func (*ReferenceGraph) Condensation 

func (g *ReferenceGraph) Condensation(scc Components) (repOf map[identity.DocumentID]identity.DocumentID, adj map[identity.DocumentID][]identity.DocumentID)

Condensation collapses each strongly-connected component to a single representative node (its sorted-min member = the existing Component.ID) and returns the condensation DAG over those representatives (ADR 0016). repOf maps every document to its SCC representative; adj is the condensation out-edge adjacency between DISTINCT representatives, built from the sorted document projection (g.projAdj) so neighbour lists are sorted and de-duplicated and the result is fully deterministic. A self-edge within an SCC (sv == sw) is skipped so the condensation stays acyclic. It takes the SCC list as a parameter (rather than recomputing) so the caller's single Tarjan pass is reused.

func (*ReferenceGraph) DetectOrphans 

func (g *ReferenceGraph) DetectOrphans(c *corpus.Corpus, rootSet RootSet, deg DegreeIndex, reach Reachability, opts OrphanOptions) OrphanReport

DetectOrphans computes the structure-ladder + unreachable classification (ADR 0007, ADR 0012). Each non-exempt document falls into AT MOST ONE structure bucket, in priority order:

  1. in==0 && out==0 → Isolated (fully-isolated orphan, most severe).
  2. else out==0 (in>0) → DeadEnd.
  3. else in<threshold (out>0) → UnderLinked.

Unreachable is computed independently (only when reachability is determinate) and is suppressed ONLY by a fully-isolated Orphan — dead-end/under-linked do NOT suppress it. Two kinds of node are exempt from ALL structure tiers: intentional orphans (front-matter `matlatl: orphan-intentional`) and root-set members (configured OR convention) — a declared entry point is its purpose, not a defect (ADR 0007). Results are sorted (g.documents is sorted and we append in that order).

func (*ReferenceGraph) Documents 

func (g *ReferenceGraph) Documents() []identity.DocumentID

Documents returns the sorted document identities (vertices of kind document).

func (*ReferenceGraph) Edges 

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

Edges returns all edges sorted (From, To, Kind, Type), for representation.

func (*ReferenceGraph) ForEachSourceBFS 

func (g *ReferenceGraph) ForEachSourceBFS(
	adj map[identity.DocumentID][]identity.DocumentID,
	visit func(
		src identity.DocumentID,
		order []identity.DocumentID,
		preds map[identity.DocumentID][]identity.DocumentID,
		sigma map[identity.DocumentID]float64,
	),
)

ForEachSourceBFS streams the per-source Brandes forward pass for betweenness centrality over the given adjacency — the sibling primitive ForEachSourceDistances promises in its reuse contract (ADR 0014/0015). For every source s (in sorted g.documents order) it runs one BFS and invokes visit with, in addition to the distances ForEachSourceDistances would give, the two extra quantities Brandes' back-pass needs:

  • order: the BFS discovery (push) order — Brandes' stack S. The dependency back-accumulation walks this in REVERSE.
  • preds: shortest-path predecessors. preds[w] lists every v with an edge v→w on a shortest path s→…→w (i.e. dist[w]==dist[v]+1). Because neighbours are expanded in sorted order, each preds[w] is appended in sorted order, so the float divisions/sums the caller performs over it run in a fixed order and are byte-stable (ADR 0007).
  • sigma: the number of shortest paths from s to each node (float64, as Brandes specifies, to match the dependency arithmetic).

Reuse contract: the dist/sigma/preds maps and the order/queue slices are OWNED by this helper and REUSED across sources (dist/sigma cleared, preds' slices re-sliced to empty, order/queue re-sliced per source). They are valid ONLY for the duration of the visit call; the callback MUST NOT retain them (copy what it needs). preds may carry leftover keys with EMPTY slices from earlier sources — read preds[w] only for w that appear in order (every such w had its predecessor list rebuilt this source). The explicit queue head index avoids the reslice-reallocation pitfall ForEachSourceDistances documents, and reusing the predecessor backing arrays keeps the V·(V+E) pass at O(V+E) transient memory with no per-source slice churn and no V² state.

func (*ReferenceGraph) ForEachSourceDistances 

func (g *ReferenceGraph) ForEachSourceDistances(
	adj map[identity.DocumentID][]identity.DocumentID,
	visit func(src identity.DocumentID, dist map[identity.DocumentID]int),
)

ForEachSourceDistances streams an all-pairs-shortest-path (APSP) computation over the given adjacency without ever materializing a V² distance matrix: it runs one breadth-first search per source document (in sorted g.documents order) and invokes visit with the source and its single-source shortest-path distance map. Edges are unweighted, so BFS yields the exact shortest-path distances (hop counts).

The dist map passed to visit is REUSED across sources (cleared between sources via the builtin clear) — it is owned by this helper and valid ONLY for the duration of the visit call; a caller that needs to retain distances must copy them. dist[src] == 0 (the self-distance) is included; a destination absent from dist is UNREACHABLE from src. Neighbour lists are iterated in the sorted order buildProjection guarantees, so the traversal — and therefore any reduction a caller computes over it — is fully deterministic regardless of map iteration order (ADR 0004).

Cost: O(V·(V+E)) time and O(V) transient memory (one reused dist map plus one BFS queue), since no per-source result is stored.

Reuse contract (P10 betweenness): this is deliberately the minimal streaming SSSP primitive. A sibling helper for betweenness will need, in addition to the distances, the BFS discovery ORDER (for the dependency-accumulation back-pass) and the shortest-path PREDECESSOR counts (sigma). Those are intentionally NOT computed here so unweighted distance consumers (navigability) pay nothing for them; the sibling should follow this same per-source streaming shape (sorted source order, sorted neighbour expansion, no stored V² state) rather than generalizing this function with extra out-parameters.

func (*ReferenceGraph) HasDocument 

func (g *ReferenceGraph) HasDocument(id identity.DocumentID) bool

HasDocument reports whether id is a document vertex.

func (*ReferenceGraph) Nodes 

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

Nodes returns all vertices sorted by NodeID (documents and sections), for representation/emitters. 

func (g *ReferenceGraph) PredictLinks(opts LinkPredictionOptions) LinkSuggestionResult

PredictLinks suggests navigational links between UNLINKED but structurally close documents over the document projection (ADR 0013). It AUGMENTS the WCC-pair knowledge-gap signal (DetectGaps): gaps flag wholly-disconnected clusters, whereas this flags concrete unlinked PAIRS within or across clusters that already share neighbours.

Algorithm (deterministic, stdlib+math only, ADR 0004): for each potential common neighbour c with undirected degree deg(c) in [2, MaxFanout], every unordered pair (A,B) within N(c) accumulates shared++ and adamicAdar += 1/log(deg(c)). Iterating c's neighbour list in SORTED order fixes the float addition order, so the Adamic/Adar sum is byte-stable. A neighbour with deg(c) > MaxFanout is skipped as a generator (HubsSkipped). After accumulation, pairs with shared < MinSharedNeighbours or that are already linked are dropped; coupling/co-citation are computed via sorted-list merge-intersection. Results are sorted by AdamicAdar DESC, then SharedNeighbours DESC, then DocA ASC, then DocB ASC (the hits.go rankDesc float-compare pattern, no epsilon), and capped at MaxSuggestedLinks (Truncated).

func (*ReferenceGraph) ProjectionIn 

func (g *ReferenceGraph) ProjectionIn(id identity.DocumentID) []identity.DocumentID

ProjectionIn returns the document-projection in-neighbors of id (sorted).

func (*ReferenceGraph) ProjectionOut 

func (g *ReferenceGraph) ProjectionOut(id identity.DocumentID) []identity.DocumentID

ProjectionOut returns the document-projection out-neighbors of id (sorted).

func (*ReferenceGraph) StronglyConnectedComponents 

func (g *ReferenceGraph) StronglyConnectedComponents() Components

StronglyConnectedComponents computes SCCs over the DIRECTED projection using Tarjan's algorithm with sorted neighbor iteration and a sorted document driver order, then assigns each SCC the sorted-min-member ID and sorts the component list by ID — fully deterministic.

func (*ReferenceGraph) WeaklyConnectedComponents 

func (g *ReferenceGraph) WeaklyConnectedComponents() Components

WeaklyConnectedComponents computes WCCs over the UNDIRECTED projection using union-find with path compression and union-by-size. Component IDs are the lexicographically smallest member, and the component list is sorted by ID, so the result is fully deterministic regardless of map order (ADR 0007).

type RootSet 

type RootSet struct {
	Roots         []identity.DocumentID // sorted
	Indeterminate bool
	// BadGlobs holds configured globs that are malformed (path.Match reported
	// ErrBadPattern). They matched nothing and are surfaced as a notice by the
	// caller rather than silently ignored.
	BadGlobs []string
}

RootSet is the resolved set of reachability roots plus whether it is indeterminate (empty). When Indeterminate is true, reachability analysis is skipped and a notice is emitted (ADR 0005/0007); orphan detection still runs.

func ResolveRootSet 

func ResolveRootSet(c *corpus.Corpus, configuredGlobs []string) RootSet

ResolveRootSet computes the root set from configured globs plus conventions (ADR 0007): any README.md/index.md/SKILL.md at any depth (filename conventions, case-insensitive), and any doc with front matter `type: index`. configuredGlobs are matched against DocumentIDs with path.Match (slash paths; the single-`*` wildcard does NOT cross `/`, and `**` is not supported). A malformed glob is collected in BadGlobs (it matches nothing) rather than silently discarded. The result is sorted and de-duplicated.

type ScentFinding 

type ScentFinding struct {
	Source     identity.DocumentID
	Target     identity.DocumentID
	Line       int
	AnchorText string
	Score      float64
	Suggestion string
}

ScentFinding is one low-scent navigational link (ADR 0016): the source document and line, the anchor text as written, the target it points at, the computed Jaccard score against the target's title, and the suggested replacement (the target's title). Pure data; the application layer turns it into a non-gating Info finding.

type Trail 

type Trail struct {
	// Root is the component's most-important document: its highest-PageRank member
	// (ties broken by smallest DocumentID). It is NOT necessarily the first element
	// of Order — a high-importance sink is topologically late.
	Root identity.DocumentID
	// Order is the full topological reading sequence of the component's documents,
	// PageRank-preferred among the available frontier. Root may appear anywhere in
	// it (not necessarily first).
	Order []identity.DocumentID
}

Trail is a suggested reading order for one weakly-connected component of the corpus (ADR 0016): a topologically-valid sequence that, among the documents currently AVAILABLE to read (their prerequisites already placed), prefers higher-authority docs by PageRank.

This is the modern realization of Vannevar Bush's associative "trails" (Bush, "As We May Think", 1945): a curated path through linked documents. The order is topological over the SCC condensation, so a doc never appears before something it depends on; the PageRank tie-break makes the path prefer globally-important docs at each step. NOTE: a high-PageRank SINK is topologically LATE and will appear near the end — that is correct ("prefer authority among the available frontier", not literal "hubs first"). The Root is an IMPORTANCE pointer, not the head of Order: it may appear anywhere in the sequence.

func ComputeTrails 

func ComputeTrails(pr PageRankScores, wcc Components, scc Components, cond func() (map[identity.DocumentID]identity.DocumentID, map[identity.DocumentID][]identity.DocumentID)) []Trail

ComputeTrails builds one Trail per weakly-connected component (ADR 0016), sorted by Root. Within each component it runs a priority Kahn topological sort over the SCC CONDENSATION (so cycles cannot deadlock the ordering): the frontier is the set of zero-in-degree SCC representatives; at each step it pops the representative whose maximum-member PageRank is highest (ties broken by representative DocumentID ascending), appends that SCC's members (a multi-node SCC emits its members by PageRank DESC, then DocumentID ASC), and decrements the in-degree of its condensation successors.

Determinism (CLAUDE.md): the frontier is a re-sorted slice (no heap, no map ranging for output); WCCs are iterated in sorted order; the condensation adjacency and member lists are sorted upstream. The Root of a component is its highest-PageRank document (tie min-ID). A singleton component yields [root].

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.