graph

package
v2.3.4 Latest Latest
Warning

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

 Go to latest Published: Sep 2, 2026 License: MIT Imports: 7 Imported by: 0

Documentation

Overview

Package graph provides graph analytics, clustering, and structural code intelligence algorithms inspired by Graphify, ported natively to Go with zero-CGO.

Package graph provides graph analytics, clustering, and structural code intelligence algorithms inspired by Graphify, ported natively to Go with zero-CGO.

Package graph provides business logic for managing relationships between observations in the knowledge graph.

The graph service enables semantic navigation through observations by creating, querying, and traversing edges (relationships) between them. This supports use cases like finding related knowledge, discovering contradiction chains, and understanding concept hierarchies.

Package graph provides graph analytics, clustering, and structural code intelligence algorithms inspired by Graphify, ported natively to Go with zero-CGO.

Index

Constants

View Source 
const (
	DefaultWeight     = 1.0
	MinWeight         = 0.0
	MaxWeight         = 10.0
	DefaultMaxDepth   = 5
	MaxTraversalDepth = 10 // Prevent infinite loops

	// DefaultMaxVisited is the default global admission budget for bounded
	// traversal; it counts the root plus every unique admitted node.
	DefaultMaxVisited = 1000
	// MaxVisitedCap bounds the user-supplied max_visited budget.
	MaxVisitedCap = 10000
	// DefaultMaxResults is the default emitted-row budget for bounded
	// traversal; it counts only emitted unique non-root observations.
	DefaultMaxResults = 100
	// MaxResultsCap bounds the user-supplied max_results budget.
	MaxResultsCap = 1000
)

Business rule constants

Variables

View Source 
var (
	ErrSelfReference = errors.New("cannot create edge from observation to itself")
	ErrInvalidWeight = errors.New("weight must be between 0 and 10")
	ErrInvalidDepth  = errors.New("depth must be between 1 and 10")
	ErrEdgeNotFound  = errors.New("edge not found")
	ErrDuplicateEdge = errors.New("edge already exists with same from_obs_id, to_obs_id, and relation_type")
	// ErrTraversalTruncated is the stable resource-limit error returned when
	// the max_visited budget is exhausted while eligible nodes remain and the
	// existence of a path has been neither proved nor disproved (GRAPH-01).
	// It is never returned for a proven no-path result.
	ErrTraversalTruncated = errors.New("graph: traversal truncated: max_visited budget exhausted")
)

Common errors

View Source 
var ValidRelationTypes = map[string]bool{
	domain.RelationReferences:  true,
	domain.RelationRelatesTo:   true,
	domain.RelationFollows:     true,
	domain.RelationSupersedes:  true,
	domain.RelationContradicts: true,
}

ValidRelationTypes contains all allowed relation types for edges.

Functions

func ComputePersonalizedPageRank added in v2.3.0 

func ComputePersonalizedPageRank(
	nodes []GraphAnalyticsNode,
	edges []GraphAnalyticsEdge,
	seeds map[string]float64,
	opts PPROptions,
) map[string]float64

ComputePersonalizedPageRank calculates the Personalized PageRank (PPR) distribution across the graph given an initial seed preference vector (HippoRAG activation).

In HippoRAG, the seeds represent the initial lexical/vector retrieval hits, and the PageRank power iteration propagates activation through structural associations in memory and code graphs in O(E * iterations) time without any external LLM calls.

func GetValidRelationTypes 

func GetValidRelationTypes() []string

GetValidRelationTypes returns a list of all valid relation types.

func ValidateRelationType 

func ValidateRelationType(relationType string) bool

ValidateRelationType checks if a relation type is valid.

Types

type BlastRadiusResult 

type BlastRadiusResult struct {
	RootNode       string   `json:"root_node"`
	DirectImpact   []string `json:"direct_impact"`
	TotalImpacted  []string `json:"total_impacted"`
	ImpactedFiles  []string `json:"impacted_files"`
	BlastRadiusPct float64  `json:"blast_radius_pct"`
}

BlastRadiusResult represents the impacted symbols and files when a node changes.

func CalculateBlastRadius 

func CalculateBlastRadius(rootNodeID string, nodes []GraphAnalyticsNode, edges []GraphAnalyticsEdge, maxHops int) *BlastRadiusResult

CalculateBlastRadius computes all downstream and upstream nodes impacted by changing a symbol.

type Community 

type Community struct {
	ID            int      `json:"id"`
	Label         string   `json:"label"`
	HubNodeID     string   `json:"hub_node_id"`
	Members       []string `json:"members"`
	Size          int      `json:"size"`
	CohesionScore float64  `json:"cohesion_score"`
}

Community represents a functional cluster of tightly-coupled nodes.

func DetectCommunities 

func DetectCommunities(nodes []GraphAnalyticsNode, edges []GraphAnalyticsEdge) []Community

DetectCommunities partitions nodes into clusters using connected components + Hub labeling.

type CommunitySummary added in v2.3.0 

type CommunitySummary struct {
	CommunityID     int      `json:"community_id"`
	Label           string   `json:"label"`
	HubNodeID       string   `json:"hub_node_id"`
	HubNodeLabel    string   `json:"hub_node_label"`
	MemberCount     int      `json:"member_count"`
	CohesionScore   float64  `json:"cohesion_score"`
	KeySymbols      []string `json:"key_symbols"`
	ExternalDeps    []string `json:"external_deps"`
	SummaryMarkdown string   `json:"summary_markdown"`
}

CommunitySummary encapsulates a high-level architectural summary of a functional cluster.

func GenerateCommunitySummaries added in v2.3.0 

func GenerateCommunitySummaries(
	communities []Community,
	nodes []GraphAnalyticsNode,
	edges []GraphAnalyticsEdge,
) []CommunitySummary

GenerateCommunitySummaries creates structured architectural summaries for each detected community (LightRAG).

type DependencyCycle 

type DependencyCycle struct {
	Length int      `json:"length"`
	Nodes  []string `json:"nodes"`
}

DependencyCycle represents a circular dependency chain.

func FindCycles 

func FindCycles(nodes []GraphAnalyticsNode, edges []GraphAnalyticsEdge) []DependencyCycle

FindCycles detects circular dependencies using Tarjan's strongly connected components algorithm.

type GodNode 

type GodNode struct {
	ID         string `json:"id"`
	Label      string `json:"label"`
	Degree     int    `json:"degree"`
	InDegree   int    `json:"in_degree"`
	OutDegree  int    `json:"out_degree"`
	SourceFile string `json:"source_file,omitempty"`
}

GodNode represents an architectural bottleneck with disproportionate connectivity.

func FindGodNodes 

func FindGodNodes(nodes []GraphAnalyticsNode, edges []GraphAnalyticsEdge, topN int) []GodNode

FindGodNodes identifies the most central, highly connected architectural entities.

type GraphAnalyticsEdge 

type GraphAnalyticsEdge struct {
	ID         string  `json:"id"`
	Source     string  `json:"source"`
	Target     string  `json:"target"`
	Type       string  `json:"type"`
	Weight     float64 `json:"weight"`
	Confidence float64 `json:"confidence"`
	Reasoning  string  `json:"reasoning,omitempty"`
}

GraphAnalyticsEdge represents an edge for graph analysis.

type GraphAnalyticsNode 

type GraphAnalyticsNode struct {
	ID         string         `json:"id"`
	Label      string         `json:"label"`
	Kind       string         `json:"kind"`
	Subtype    string         `json:"subtype,omitempty"`
	SourceFile string         `json:"source_file,omitempty"`
	Metadata   map[string]any `json:"metadata,omitempty"`
}

GraphAnalyticsNode represents a generic node for graph analysis.

type GraphAnalyticsReport 

type GraphAnalyticsReport struct {
	TotalNodes            int                    `json:"total_nodes"`
	TotalEdges            int                    `json:"total_edges"`
	Density               float64                `json:"density"`
	Communities           []Community            `json:"communities"`
	CommunitySummaries    []CommunitySummary     `json:"community_summaries,omitempty"`
	GodNodes              []GodNode              `json:"god_nodes"`
	SurprisingConnections []SurprisingConnection `json:"surprising_connections"`
	Cycles                []DependencyCycle      `json:"cycles"`
	PPRScores             map[string]float64     `json:"ppr_scores,omitempty"`
}

GraphAnalyticsReport is the aggregated health and structural intelligence report.

func AnalyzeGraph 

func AnalyzeGraph(nodes []GraphAnalyticsNode, edges []GraphAnalyticsEdge) *GraphAnalyticsReport

AnalyzeGraph performs full structural analysis and community detection.

type LevelNeighborBatcher 

type LevelNeighborBatcher interface {
	GetLevelNeighborObservations(ctx context.Context, frontier []int64) (map[int64][]*domain.Observation, error)
}

LevelNeighborBatcher is the optional repository capability (GRAPH-01) that resolves one-hop adjacency for an entire BFS frontier in a single lookup. Implementations MUST return hydrated neighbor observations for every requested frontier ID (missing IDs may map to an empty or absent entry) and SHOULD deduplicate and order each adjacency list by ascending observation ID; the service normalizes ordering defensively so shuffled rows cannot change traversal outcomes.

type PPROptions added in v2.3.0 

type PPROptions struct {
	// DampingFactor is the teleportation probability factor (typically 0.85).
	DampingFactor float64
	// MaxIterations is the maximum number of power iteration loops (typically 20).
	MaxIterations int
	// Tolerance is the convergence threshold (typically 1e-6).
	Tolerance float64
	// Directed determines if edges should be treated as strictly directed (Source -> Target).
	Directed bool
}

PPROptions configures the Personalized PageRank (HippoRAG) algorithm.

func DefaultPPROptions added in v2.3.0 

func DefaultPPROptions() PPROptions

DefaultPPROptions returns standard HippoRAG parameters.

type ScoredNode added in v2.3.0 

type ScoredNode struct {
	NodeID string  `json:"node_id"`
	Score  float64 `json:"score"`
}

ScoredNode represents a graph node scored by HippoRAG / Personalized PageRank.

func HippoRAGPropagate added in v2.3.0 

func HippoRAGPropagate(
	nodes []GraphAnalyticsNode,
	edges []GraphAnalyticsEdge,
	seeds map[string]float64,
	topK int,
) []ScoredNode

HippoRAGPropagate applies Personalized PageRank on graph nodes and returns top-K ranked nodes.

type Service 

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

Service provides graph operations for managing relationships between observations.

func NewService 

func NewService(repo domain.GraphRepository) *Service

NewService creates a new graph service with the given repository.

func (*Service) CreateEdge 

func (s *Service) CreateEdge(ctx context.Context, edge *domain.Edge) error

CreateEdge creates a relationship between two observations.

Business Rules:

  • Cannot create edge from observation to itself (self-reference)
  • Weight must be > 0 (defaults to 1.0)
  • Relation type must be valid
  • (from_obs_id, to_obs_id, relation_type) must be unique

func (*Service) DeleteEdge 

func (s *Service) DeleteEdge(ctx context.Context, id int64) error

DeleteEdge removes a relationship between observations. Returns ErrEdgeNotFound if the edge doesn't exist.

func (*Service) DetectConflicts 

func (s *Service) DetectConflicts(ctx context.Context, obsID int64) ([]*domain.Edge, error)

DetectConflicts finds edges where the observation is involved in a contradiction or has been superseded by newer knowledge.

func (*Service) FindPath 

func (s *Service) FindPath(ctx context.Context, fromID, toID int64, maxDepth int) ([]int64, error)

FindPath finds a path between two observations using Breadth-First Search (BFS). Returns the sequence of observation IDs from fromID to toID, or nil if no path exists.

The maxDepth parameter limits how far to search to prevent performance issues. If maxDepth is 0, DefaultMaxDepth (5) is used. FindPath uses the default max_visited budget; use FindPathBounded for an explicit budget.

func (*Service) FindPathBounded 

func (s *Service) FindPathBounded(ctx context.Context, fromID, toID int64, maxDepth, maxVisited int) ([]int64, error)

FindPathBounded finds the lexicographically smallest shortest path between two observations using level-batched BFS (GRAPH-01).

Each BFS frontier and every neighbor list is processed in ascending observation ID order, and at most one adjacency lookup is issued per expanded level through the optional LevelNeighborBatcher capability (repositories without it fall back to a bounded deterministic per-node lookup). maxDepth defaults to DefaultMaxDepth and is capped at MaxTraversalDepth. maxVisited defaults to DefaultMaxVisited, is capped at MaxVisitedCap, and counts the root plus every unique admitted node including the destination. When the budget is exhausted while eligible nodes remain and the path has been neither proved nor disproved, the call returns ErrTraversalTruncated instead of a false no-path result.

func (*Service) GetRelated 

func (s *Service) GetRelated(ctx context.Context, obsID int64, depth int) ([]*domain.Observation, error)

GetRelated retrieves all observations related to a given observation, traversing the graph up to the specified depth.

Depth meanings:

  • depth=1: Only directly connected observations
  • depth=2: Observations 1 or 2 hops away
  • depth=N: Observations up to N hops away

Returns observations in order of proximity (closer observations first).

func (*Service) GetRelatedBounded 

func (s *Service) GetRelatedBounded(ctx context.Context, obsID int64, opts domain.GraphTraversalOptions) (*domain.GraphTraversalResult, error)

GetRelatedBounded performs bounded local traversal (GRAPH-02) with independent max_visited and max_results budgets.

max_visited (default DefaultMaxVisited, cap MaxVisitedCap) counts the root plus unique admitted nodes; max_results (default DefaultMaxResults, cap MaxResultsCap) counts only emitted unique non-root observations. Rows are ordered by minimum hop ascending, then observation ID ascending, regardless of adjacency row order. The traversal probes one sentinel beyond each effective limit: truncated is reported (with reason max_visited, max_results, or both) ONLY when the sentinel proved eligible data was omitted. A result exactly equal to a limit is complete, not truncated. Legacy (non-v2) repositories obey the same semantics through the per-node fallback.

func (*Service) GetRelationships 

func (s *Service) GetRelationships(ctx context.Context, obsID int64) ([]*domain.Edge, error)

GetRelationships retrieves all edges for an observation (both outgoing and incoming). This is useful for displaying the full context of relationships for a given observation.

func (*Service) ResolveConflict 

func (s *Service) ResolveConflict(ctx context.Context, newObsID, obsoleteObsID int64, reason string) (*domain.Edge, error)

ResolveConflict resolves a knowledge contradiction by marking the new observation as superseding the obsolete one, documenting the reason, and creating a formal supersedes edge.

type SurprisingConnection 

type SurprisingConnection struct {
	SourceNode   string   `json:"source_node"`
	TargetNode   string   `json:"target_node"`
	RelationType string   `json:"relation_type"`
	Score        int      `json:"score"`
	Reasons      []string `json:"reasons"`
}

SurprisingConnection represents a non-obvious bridge across distinct domains or peripheral-to-hub coupling.

func FindSurprisingConnections 

func FindSurprisingConnections(nodes []GraphAnalyticsNode, edges []GraphAnalyticsEdge, topN int) []SurprisingConnection

FindSurprisingConnections scores and identifies unexpected cross-domain or peripheral-to-hub coupling.

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.