Documentation
¶
Index ¶
- func IsAcyclic(edgeType string) bool
- func IsValidEdgeType(t string) bool
- func Modularity(communities []Community, edges []*storage.Edge) float64
- type Community
- type CommunityDetector
- type CommunitySearcher
- func (cs *CommunitySearcher) CommunitySummaryForContext(communities []Community, tokenBudget int) string
- func (cs *CommunitySearcher) ExpandCommunity(communityID string, communities []Community) []*storage.Node
- func (cs *CommunitySearcher) RankCommunitiesByRelevance(query string, communities []Community) []Community
- func (cs *CommunitySearcher) SearchByCommunity(query string, communities []Community) []Community
- type DriftSearcher
- type Graph
- type Subgraph
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func IsValidEdgeType ¶
IsValidEdgeType reports whether t is a recognized edge type.
func Modularity ¶
Modularity computes Newman-Girvan modularity Q for the given partition. Q = (1/2m) * sum_ij [ A_ij - ki*kj/(2m) ] * delta(ci, cj) where m = total edge weight, A_ij = adjacency weight, ki = degree of i. The sum is over all ordered pairs (i,j), not just existing edges.
Types ¶
type Community ¶
type Community struct {
ID string
Level int
NodeIDs []string
Summary string
Keywords []string
Strength float64 // internal edge density relative to expected
}
Community represents a detected group of densely-connected nodes in the memory graph. Level 0 = finest granularity; higher levels = coarser groupings.
type CommunityDetector ¶
type CommunityDetector struct {
// MinCommunitySize excludes communities smaller than this from results.
MinCommunitySize int
}
CommunityDetector implements Louvain-style modularity-optimizing community detection. It operates on in-memory node/edge slices — no database access required.
func NewCommunityDetector ¶
func NewCommunityDetector() *CommunityDetector
NewCommunityDetector creates a detector with sensible defaults.
func (*CommunityDetector) Detect ¶
Detect partitions nodes into communities using Louvain modularity optimization. It treats edges as undirected (both directions count) and uses edge Weight as the connection strength. Returns a flat slice of Level-0 communities.
func (*CommunityDetector) HierarchicalCommunities ¶
func (cd *CommunityDetector) HierarchicalCommunities(nodes []*storage.Node, edges []*storage.Edge, levels int) [][]Community
HierarchicalCommunities produces multi-level community hierarchy by repeatedly merging communities from finer levels. Level 0 = Detect() output. Level 1 merges Level 0 communities that share edges, and so on up to the requested depth.
type CommunitySearcher ¶
type CommunitySearcher struct {
// NodeLookup maps node IDs to their full Node data for expansion.
NodeLookup map[string]*storage.Node
}
CommunitySearcher provides search operations over detected communities. It implements keyword-based ranking (BM25) and token-budgeted context building, inspired by GraphRAG's global search over community summaries.
func NewCommunitySearcher ¶
func NewCommunitySearcher(nodes []*storage.Node) *CommunitySearcher
NewCommunitySearcher creates a searcher with the given node lookup table.
func (*CommunitySearcher) CommunitySummaryForContext ¶
func (cs *CommunitySearcher) CommunitySummaryForContext(communities []Community, tokenBudget int) string
CommunitySummaryForContext formats the top communities into a context string that fits within the given token budget. Each token is approximated as 4 characters.
func (*CommunitySearcher) ExpandCommunity ¶
func (cs *CommunitySearcher) ExpandCommunity(communityID string, communities []Community) []*storage.Node
ExpandCommunity returns all nodes belonging to the given community ID.
func (*CommunitySearcher) RankCommunitiesByRelevance ¶
func (cs *CommunitySearcher) RankCommunitiesByRelevance(query string, communities []Community) []Community
RankCommunitiesByRelevance ranks communities using BM25-style scoring on their summaries and keywords. Returns a new slice sorted by descending relevance score.
func (*CommunitySearcher) SearchByCommunity ¶
func (cs *CommunitySearcher) SearchByCommunity(query string, communities []Community) []Community
SearchByCommunity finds communities whose summaries or keywords match the query. Returns communities sorted by relevance (descending).
type DriftSearcher ¶
type DriftSearcher struct {
// Searcher is used for BM25 ranking at each level.
Searcher *CommunitySearcher
// MaxResults caps the number of returned nodes.
MaxResults int
}
DriftSearcher implements GraphRAG's "drift search" pattern: start at a high-level community, drill down based on relevance to the query, and return the most relevant nodes. This hierarchical approach is more effective than flat search for structured knowledge because it leverages the community topology to narrow focus quickly.
func NewDriftSearcher ¶
func NewDriftSearcher(nodes []*storage.Node, maxResults int) *DriftSearcher
NewDriftSearcher creates a drift searcher with the given node data.
func (*DriftSearcher) DriftSearch ¶
func (ds *DriftSearcher) DriftSearch(query string, hierarchy [][]Community) []*storage.Node
DriftSearch performs hierarchical community-guided search.
Algorithm (inspired by GraphRAG DRIFT):
- Start at the highest (coarsest) level of the community hierarchy.
- Rank communities at that level by relevance to the query.
- Select the top-k most relevant communities.
- Drill down: for each selected community, find its sub-communities at the next level.
- Repeat until reaching Level 0 (finest granularity).
- Expand the final communities into individual nodes, ranked by relevance.
This is fundamentally different from flat vector search: it uses the graph's community structure as a "table of contents" to navigate to relevant regions without scoring every node individually.
type Graph ¶
type Graph interface {
AddNode(ctx context.Context, n *storage.Node) error
AddEdge(ctx context.Context, e *storage.Edge) error
RemoveNode(ctx context.Context, id string) error
RemoveEdge(ctx context.Context, id string) error
ExtractSubgraph(ctx context.Context, startID string, maxDepth int) (*Subgraph, error)
BFS(ctx context.Context, startID string, maxDepth int) ([]string, error)
IntentBFS(ctx context.Context, startID string, maxDepth int, queryIntent intent.Intent) ([]string, error)
Impact(ctx context.Context, filePath string, maxDepth int) ([]string, error)
Ancestors(ctx context.Context, id string) ([]string, error)
Descendants(ctx context.Context, id string) ([]string, error)
}
Graph is the interface for all graph operations used by Engine.
Source Files