algorithms

package
v0.4.1 Latest Latest
Warning

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

 Go to latest Published: Jun 4, 2026 License: MIT Imports: 6 Imported by: 0

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func AllShortestPaths 

func AllShortestPaths(graph storage.Storage, sourceID uint64) (map[uint64]int, error)

AllShortestPaths finds all shortest paths from a source node using BFS

func AverageClusteringCoefficient 

func AverageClusteringCoefficient(graph *storage.GraphStorage) (float64, error)

AverageClusteringCoefficient computes the average clustering coefficient

func BetweennessCentrality 

func BetweennessCentrality(graph *storage.GraphStorage) (map[uint64]float64, error)

BetweennessCentrality computes betweenness centrality for all nodes (tenant-blind). Measures how often a node appears on shortest paths.

func BetweennessCentralityForTenant 

func BetweennessCentralityForTenant(graph *storage.GraphStorage, tenantID string) (map[uint64]float64, error)

BetweennessCentralityForTenant restricts computation to the caller's tenant subgraph. Audit A6c-algorithms.

func CalculateModularity 

func CalculateModularity(graph *storage.GraphStorage, nodeCommunity map[uint64]int) float64

CalculateModularity computes the modularity score for a community partition. Modularity measures the quality of a partition: values > 0.3 indicate significant community structure, values > 0.7 indicate strong structure. Range: [-0.5, 1.0]

Formula: Q = Σ_c [(l_c / m) - (d_c / 2m)²] Where:

  • m = total number of edges
  • l_c = number of edges within community c
  • d_c = sum of degrees of nodes in community c

func ClosenessCentrality 

func ClosenessCentrality(graph *storage.GraphStorage) (map[uint64]float64, error)

ClosenessCentrality computes closeness centrality for all nodes. Measures average distance from a node to all other nodes.

func ClusteringCoefficient 

func ClusteringCoefficient(graph *storage.GraphStorage) (map[uint64]float64, error)

ClusteringCoefficient computes local clustering coefficient for all nodes Measures how close a node's neighbors are to being a complete graph.

Enumerates nodes via GetAllNodeIDs rather than scanning IDs 1..NodeCount+buffer. The previous scan-based approach was both fragile (relied on stats.NodeCount being accurate at call time) and slow (one GetNode call per scanned ID).

func DegreeCentrality 

func DegreeCentrality(graph *storage.GraphStorage) (map[uint64]float64, error)

DegreeCentrality computes degree centrality for all nodes. Simple count of connections (in-degree + out-degree).

func HasCycle 

func HasCycle(graph storage.Storage) (bool, error)

HasCycle checks if the graph contains any cycles (tenant-blind, faster than detecting all cycles).

func HasCycleForTenant 

func HasCycleForTenant(graph storage.Storage, tenantID string) (bool, error)

HasCycleForTenant checks if the caller's tenant subgraph contains any cycles. Audit A6c-algorithms.

func IsBipartite 

func IsBipartite(graph *storage.GraphStorage) (bool, []uint64, []uint64, error)

IsBipartite checks if the graph can be colored with two colors such that no two adjacent nodes have the same color Returns (is_bipartite, partition1, partition2, error)

func IsConnected 

func IsConnected(graph *storage.GraphStorage) (bool, error)

IsConnected checks if all nodes in the graph are reachable from any starting node For directed graphs, this checks weak connectivity (treating edges as undirected)

func IsDAG 

func IsDAG(graph *storage.GraphStorage) (bool, error)

IsDAG checks if the graph is a Directed Acyclic Graph Returns true if the graph contains no cycles

func IsTree 

func IsTree(graph *storage.GraphStorage) (bool, error)

IsTree checks if the graph forms a valid tree structure A tree must: - Be connected - Have exactly n-1 edges for n nodes - Contain no cycles - Have a single root (node with in-degree 0)

func NodeSimilarityPair 

func NodeSimilarityPair(graph storage.Storage, nodeA, nodeB uint64, opts NodeSimilarityOptions) (float64, error)

NodeSimilarityPair computes similarity between two nodes (tenant-blind).

func NodeSimilarityPairForTenant 

func NodeSimilarityPairForTenant(graph storage.Storage, nodeA, nodeB uint64, opts NodeSimilarityOptions, tenantID string) (float64, error)

NodeSimilarityPairForTenant computes similarity restricted to the caller's tenant. Audit A6c-algorithms.

func PredictLinkScore 

func PredictLinkScore(graph storage.Storage, fromNodeID, toNodeID uint64, opts LinkPredictionOptions) (float64, error)

PredictLinkScore computes the link prediction score between two specific nodes (tenant-blind).

func PredictLinkScoreForTenant 

func PredictLinkScoreForTenant(graph storage.Storage, fromNodeID, toNodeID uint64, opts LinkPredictionOptions, tenantID string) (float64, error)

PredictLinkScoreForTenant restricts to the caller's tenant. Audit A6c-algorithms.

func ShortestPath 

func ShortestPath(graph storage.Storage, startID, endID uint64) ([]uint64, error)

ShortestPath finds the shortest path between two nodes using bidirectional BFS This is 2x faster than unidirectional BFS for large graphs

func ShortestPathForTenant 

func ShortestPathForTenant(graph storage.Storage, startID, endID uint64, tenantID string) ([]uint64, error)

ShortestPathForTenant finds the shortest path between two nodes using bidirectional BFS, restricted to edges owned by the given tenant. Audit A6b (2026-05-08).

Critical: do not post-filter the path returned by ShortestPath — the bidirectional BFS may pick a shorter cross-tenant route, and rejecting it after the fact would deny paths that *do* exist within the caller's subgraph. The filter must happen at edge expansion.

Tenant-strict guarantee: as of the A6a follow-up, CreateEdgeWithTenant refuses cross-tenant from/to node references, so a tenant-stamped edge cannot point at a foreign-tenant node. That means the edge-tenant filter is sufficient — no per-neighbor GetNodeForTenant in the BFS hot loop.

func TopologicalSort 

func TopologicalSort(graph *storage.GraphStorage) ([]uint64, error)

TopologicalSort returns nodes in topological order using Kahn's algorithm Returns error if graph contains a cycle (not a DAG) The ordering ensures that for every directed edge u->v, u comes before v

func WeightedShortestPath 

func WeightedShortestPath(graph storage.Storage, startID, endID uint64) ([]uint64, float64, error)

WeightedShortestPath finds shortest path with edge weights using Dijkstra's algorithm

Types

type CentralityResult 

type CentralityResult struct {
	Betweenness          map[uint64]float64
	Closeness            map[uint64]float64
	Degree               map[uint64]float64
	EdgeBetweenness      *EdgeBetweennessResult
	TopByBetweenness     []RankedNode
	TopByCloseness       []RankedNode
	TopByDegree          []RankedNode
	TopByEdgeBetweenness []RankedEdge
}

CentralityResult contains centrality measures for all nodes and edges.

func ComputeAllCentrality 

func ComputeAllCentrality(graph *storage.GraphStorage) (*CentralityResult, error)

ComputeAllCentrality computes all centrality measures in a single pass where possible. Node and edge betweenness share one Brandes traversal.

type Community 

type Community struct {
	ID      int
	Nodes   []uint64
	Size    int
	Density float64 // Edge density within community
}

Community represents a detected community

type CommunityDetectionResult 

type CommunityDetectionResult struct {
	Communities   []*Community
	Modularity    float64        // Quality measure of the partitioning
	NodeCommunity map[uint64]int // Node ID -> Community ID
}

CommunityDetectionResult contains detected communities

func ConnectedComponents 

func ConnectedComponents(graph *storage.GraphStorage) (*CommunityDetectionResult, error)

ConnectedComponents finds all connected components in the graph

func LabelPropagation 

func LabelPropagation(graph *storage.GraphStorage, maxIterations int) (*CommunityDetectionResult, error)

LabelPropagation performs label propagation for community detection Fast, scalable algorithm for large graphs

type CondensationEdge 

type CondensationEdge struct {
	FromSCCID int
	ToSCCID   int
	EdgeCount int
}

CondensationEdge represents a directed edge in the condensation DAG, where each SCC has been contracted to a single node.

func Condensation 

func Condensation(graph storage.Storage, scc *SCCResult) ([]CondensationEdge, error)

Condensation builds the condensation DAG from an SCC result. Each SCC becomes a single node; edges between SCCs are aggregated with their count. Runs in O(E) time over all original edges.

type Cycle 

type Cycle []uint64

Cycle represents a detected cycle as a sequence of node IDs

func DetectCycles 

func DetectCycles(graph storage.Storage) ([]Cycle, error)

DetectCycles finds all cycles in the graph using DFS with three-color marking. Tenant-blind. Multi-tenant API callers must use DetectCyclesForTenant.

Algorithm: depth-first search with three colors:

  • WHITE (0): Unvisited node
  • GRAY (1): Currently visiting (in recursion stack)
  • BLACK (2): Finished visiting (all descendants explored)

A GRAY node found during DFS is a back edge, indicating a cycle.

func DetectCyclesForTenant 

func DetectCyclesForTenant(graph storage.Storage, tenantID string) ([]Cycle, error)

DetectCyclesForTenant finds cycles within the caller's tenant subgraph. Audit A6c-algorithms (2026-05-08).

func DetectCyclesWithOptions 

func DetectCyclesWithOptions(graph storage.Storage, opts CycleDetectionOptions) ([]Cycle, error)

DetectCyclesWithOptions finds cycles matching the given criteria (tenant-blind).

func DetectCyclesWithOptionsForTenant 

func DetectCyclesWithOptionsForTenant(graph storage.Storage, opts CycleDetectionOptions, tenantID string) ([]Cycle, error)

DetectCyclesWithOptionsForTenant restricts the cycle search and filtering to the caller's tenant. Audit A6c-algorithms.

type CycleDetectionOptions 

type CycleDetectionOptions struct {
	MinCycleLength int                      // Minimum cycle length to report (0 = all)
	MaxCycleLength int                      // Maximum cycle length to report (0 = unlimited)
	NodePredicate  func(*storage.Node) bool // Only include cycles with nodes matching predicate
	EdgeTypes      []string                 // Only follow edges of these types (empty = all types)
}

CycleDetectionOptions configures cycle detection behavior

type CycleStats 

type CycleStats struct {
	TotalCycles   int
	ShortestCycle int
	LongestCycle  int
	AverageLength float64
	SelfLoops     int // Number of self-referencing nodes
}

CycleStats provides statistics about detected cycles

func AnalyzeCycles 

func AnalyzeCycles(cycles []Cycle) CycleStats

AnalyzeCycles computes statistics about detected cycles

type EdgeBetweennessResult 

type EdgeBetweennessResult struct {
	// ByEdgeID maps each directed edge ID to its BC score.
	ByEdgeID map[uint64]float64 `json:"by_edge_id"`
	// ByNodePair maps [fromNodeID, toNodeID] to the directed edge's BC score.
	ByNodePair map[[2]uint64]float64 `json:"by_node_pair"`
	// TopEdges lists the top edges ranked by BC score (descending).
	TopEdges []RankedEdge `json:"top_edges"`
}

EdgeBetweennessResult contains edge betweenness centrality in multiple representations for different access patterns.

func EdgeBetweennessCentrality 

func EdgeBetweennessCentrality(graph *storage.GraphStorage) (*EdgeBetweennessResult, error)

EdgeBetweennessCentrality computes betweenness centrality for all edges (tenant-blind). Measures how often an edge appears on shortest paths between all node pairs.

func EdgeBetweennessCentralityForTenant 

func EdgeBetweennessCentralityForTenant(graph *storage.GraphStorage, tenantID string) (*EdgeBetweennessResult, error)

EdgeBetweennessCentralityForTenant restricts computation to the caller's tenant subgraph. Audit A6c-algorithms.

type KHopOptions 

type KHopOptions struct {
	MaxHops    int // must be >= 1
	Direction  NeighborDirection
	EdgeTypes  []string // nil means all edge types
	MaxResults int      // 0 = unlimited; BFS order gives closer nodes priority
}

KHopOptions configures the k-hop neighbourhood traversal.

func DefaultKHopOptions 

func DefaultKHopOptions() KHopOptions

DefaultKHopOptions returns sensible defaults.

type KHopResult 

type KHopResult struct {
	SourceNodeID   uint64
	ByHop          map[int][]uint64 // hop distance → node IDs at that distance
	Distances      map[uint64]int   // node ID → shortest hop count
	TotalReachable int
}

KHopResult holds the BFS neighbourhood of a source node.

func KHopNeighbours 

func KHopNeighbours(graph storage.Storage, sourceNodeID uint64, opts KHopOptions) (*KHopResult, error)

KHopNeighbours performs a BFS from sourceNodeID up to MaxHops levels, returning all discovered nodes grouped by distance. Tenant-blind — runs across every tenant. Multi-tenant API callers must use KHopNeighboursForTenant. The source node is never included in results.

func KHopNeighboursForTenant 

func KHopNeighboursForTenant(graph storage.Storage, sourceNodeID uint64, opts KHopOptions, tenantID string) (*KHopResult, error)

KHopNeighboursForTenant performs the same BFS as KHopNeighbours but restricted to the caller's tenant subgraph. Audit A6c-algorithms: expansion uses the tenant-scoped *ForTenant edge accessors, so foreign-tenant node IDs never appear in ByHop / Distances. Pairs with the tenant-strict fix to the /algorithms khop handler.

type LinkPrediction 

type LinkPrediction struct {
	FromNodeID uint64
	ToNodeID   uint64
	Score      float64
}

LinkPrediction holds a predicted link score between two nodes.

type LinkPredictionMethod 

type LinkPredictionMethod int

LinkPredictionMethod selects the scoring formula for link prediction. 

const (
	// LinkPredCommonNeighbours scores by |N(u) ∩ N(v)| — integer counts.
	LinkPredCommonNeighbours LinkPredictionMethod = iota

	// LinkPredAdamicAdar scores by Σ_{w ∈ N(u)∩N(v)} 1/log(|N(w)|) — weighted sum
	// giving higher weight to common neighbors with fewer connections.
	LinkPredAdamicAdar

	// LinkPredPreferentialAttachment scores by |N(u)| × |N(v)| — degree product.
	// Requires no intersection computation.
	LinkPredPreferentialAttachment
)

type LinkPredictionOptions 

type LinkPredictionOptions struct {
	Method          LinkPredictionMethod
	Direction       NeighborDirection
	EdgeTypes       []string
	ExcludeExisting bool // default true — skip pairs that already share an edge
	TopK            int  // default 10, 0 = all
}

LinkPredictionOptions configures link prediction.

Scores across different methods are not comparable. Common Neighbours returns integer counts, Adamic-Adar returns weighted sums, and Preferential Attachment returns degree products.

func DefaultLinkPredictionOptions 

func DefaultLinkPredictionOptions() LinkPredictionOptions

DefaultLinkPredictionOptions returns sensible defaults.

type LinkPredictionResult 

type LinkPredictionResult struct {
	SourceNodeID uint64
	Predictions  []LinkPrediction // sorted desc by Score
}

LinkPredictionResult holds predictions for a single source node.

func PredictLinksFor 

func PredictLinksFor(graph storage.Storage, sourceNodeID uint64, opts LinkPredictionOptions) (*LinkPredictionResult, error)

PredictLinksFor predicts links for a source node against all other nodes (tenant-blind).

func PredictLinksForForTenant 

func PredictLinksForForTenant(graph storage.Storage, sourceNodeID uint64, opts LinkPredictionOptions, tenantID string) (*LinkPredictionResult, error)

PredictLinksForForTenant restricts to caller's tenant. Audit A6c-algorithms.

type NeighborDirection 

type NeighborDirection int

NeighborDirection controls which edges to follow when building neighbor sets. 

const (
	DirectionOut  NeighborDirection = iota // outgoing edges only
	DirectionIn                            // incoming edges only
	DirectionBoth                          // union of both
)

type NodeSimilarityOptions 

type NodeSimilarityOptions struct {
	Metric    SimilarityMetric
	Direction NeighborDirection
	EdgeTypes []string // nil means all edge types
	TopK      int      // max results per node (0 = all)
}

NodeSimilarityOptions configures the node similarity computation.

func DefaultNodeSimilarityOptions 

func DefaultNodeSimilarityOptions() NodeSimilarityOptions

DefaultNodeSimilarityOptions returns sensible defaults.

type NodeSimilarityResult 

type NodeSimilarityResult struct {
	SourceNodeID uint64
	Similar      []NodeSimilarityScore // sorted desc by Score, zeros excluded
}

NodeSimilarityResult holds similarity results for a single source node.

func NodeSimilarityAll 

func NodeSimilarityAll(graph storage.Storage, opts NodeSimilarityOptions) ([]NodeSimilarityResult, error)

NodeSimilarityAll computes similarity for every node against every other node (tenant-blind).

func NodeSimilarityAllForTenant 

func NodeSimilarityAllForTenant(graph storage.Storage, opts NodeSimilarityOptions, tenantID string) ([]NodeSimilarityResult, error)

NodeSimilarityAllForTenant restricts to caller's tenant. Audit A6c-algorithms.

func NodeSimilarityFor 

func NodeSimilarityFor(graph storage.Storage, sourceNodeID uint64, opts NodeSimilarityOptions) (*NodeSimilarityResult, error)

NodeSimilarityFor computes similarity of sourceNodeID against all other nodes (tenant-blind). Multi-tenant API callers must use NodeSimilarityForTenant.

func NodeSimilarityForForTenant 

func NodeSimilarityForForTenant(graph storage.Storage, sourceNodeID uint64, opts NodeSimilarityOptions, tenantID string) (*NodeSimilarityResult, error)

NodeSimilarityForForTenant restricts to caller's tenant. Audit A6c-algorithms.

type NodeSimilarityScore 

type NodeSimilarityScore struct {
	NodeA uint64
	NodeB uint64
	Score float64
}

NodeSimilarityScore holds a similarity score between two nodes.

type PageRankOptions 

type PageRankOptions struct {
	DampingFactor float64 // Usually 0.85
	MaxIterations int
	Tolerance     float64 // Convergence threshold
}

PageRankOptions configures PageRank algorithm

func DefaultPageRankOptions 

func DefaultPageRankOptions() PageRankOptions

DefaultPageRankOptions returns default PageRank configuration

type PageRankResult 

type PageRankResult struct {
	Scores     map[uint64]float64 // Node ID -> PageRank score
	Iterations int                // Number of iterations performed
	Converged  bool               // Whether algorithm converged
	TopNodes   []RankedNode       // Top N nodes by score
}

PageRankResult contains PageRank scores for all nodes

func PageRank 

func PageRank(graph storage.Storage, opts PageRankOptions) (*PageRankResult, error)

PageRank computes PageRank scores for all nodes in the graph (tenant-blind — runs across every tenant). Used by CLI, demos, and single-tenant deployments. Multi-tenant API callers must use PageRankForTenant.

func PageRankForTenant 

func PageRankForTenant(graph storage.Storage, opts PageRankOptions, tenantID string) (*PageRankResult, error)

PageRankForTenant computes PageRank scores for nodes owned by the given tenant. Audit A6c-algorithms (2026-05-08): same algorithm body as PageRank, but the underlying graph access is restricted to the tenant — foreign-tenant nodes are excluded from the scoring graph and edges to foreign-tenant nodes are dropped at expansion.

func (*PageRankResult) GetNodeRank 

func (pr *PageRankResult) GetNodeRank(nodeID uint64) float64

GetNodeRank returns the PageRank score for a specific node

func (*PageRankResult) GetTopNodesByPageRank 

func (pr *PageRankResult) GetTopNodesByPageRank(n int) []RankedNode

GetTopNodesByPageRank returns top N nodes by PageRank score

type RankedEdge 

type RankedEdge struct {
	EdgeID     uint64  `json:"edge_id"`
	FromNodeID uint64  `json:"from_node_id"`
	ToNodeID   uint64  `json:"to_node_id"`
	Score      float64 `json:"score"`
}

RankedEdge holds a ranked edge with its betweenness centrality score.

type RankedNode 

type RankedNode struct {
	NodeID uint64
	Score  float64
	Node   *storage.Node
}

RankedNode represents a node with its rank

type SCCResult 

type SCCResult struct {
	*CommunityDetectionResult
	LargestSCC     *Community
	SingletonCount int
}

SCCResult holds the result of Tarjan's strongly connected components algorithm. It embeds CommunityDetectionResult for compatibility with the existing community infrastructure. Modularity is always 0.0 since SCCs are structural, not quality-optimized.

func StronglyConnectedComponents 

func StronglyConnectedComponents(graph storage.Storage) (*SCCResult, error)

StronglyConnectedComponents finds all SCCs using Tarjan's algorithm in O(V+E) time, tenant-blind. Only outgoing edges are followed (directed graph semantics). Multi-tenant API callers must use StronglyConnectedComponentsForTenant.

func StronglyConnectedComponentsForTenant 

func StronglyConnectedComponentsForTenant(graph storage.Storage, tenantID string) (*SCCResult, error)

StronglyConnectedComponentsForTenant computes SCCs within the caller's tenant subgraph. Audit A6c-algorithms (2026-05-08).

type SimilarityMetric 

type SimilarityMetric int

SimilarityMetric selects which similarity formula to use. 

const (
	SimilarityJaccard SimilarityMetric = iota // |A∩B| / |A∪B|
	SimilarityOverlap                         // |A∩B| / min(|A|,|B|)
	SimilarityCosine                          // |A∩B| / sqrt(|A|×|B|)
)

type TriangleCountResult 

type TriangleCountResult struct {
	PerNode                map[uint64]int
	GlobalCount            int
	ClusteringCoefficients map[uint64]float64
	TopNodes               []RankedNode
}

TriangleCountResult holds triangle counting results including per-node counts, global count, clustering coefficients, and top nodes by triangle participation.

func CountTriangles 

func CountTriangles(graph storage.Storage) (*TriangleCountResult, error)

CountTriangles counts triangles in the graph, treating all edges as undirected (tenant-blind). Multi-tenant API callers must use CountTrianglesForTenant.

func CountTrianglesForTenant 

func CountTrianglesForTenant(graph storage.Storage, tenantID string) (*TriangleCountResult, error)

CountTrianglesForTenant counts triangles within the caller's tenant subgraph. Audit A6c-algorithms (2026-05-08).

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.