graph

package
v0.9.7-patched74 Latest Latest
Warning

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

 Go to latest Published: Mar 12, 2026 License: Apache-2.0 Imports: 13 Imported by: 0

Documentation

Index

Constants

View Source 
const CycleCheckBudgetExceeded = "cycle-check-budget-exceeded" // informational tag only

CycleCheckBudgetExceeded is the sentinel returned when wouldCreateCycle exhausts its BFS budget without confirming a cycle. This is indistinguishable from a true cycle at the API level: AddEdge returns ErrCycleDetected and the HTTP handler surfaces a 409. Operators and callers should be aware that on large or dense graphs the default budget of DefaultCycleCheckLimit (512) visited nodes may be exceeded by a legitimate (non-cyclic) edge addition. The limit is configurable via FlatGraph.SetCycleCheckLimit or the OLU_GRAPH_CYCLE_CHECK_LIMIT environment variable. This behaviour is documented here and in GRAPH_API.md so that callers can reason about it.

Note: this constant is informational only — the code uses cycleCheckLimit directly. It is not returned as an error value; use ErrCycleDetected to detect both true cycles and budget-exhaustion rejections.

View Source 
const DefaultCycleCheckLimit = 512

DefaultCycleCheckLimit is the default BFS node-visit budget for wouldCreateCycle. It is exported so that callers (e.g. the startup diagnostic print) can display the effective default without hard-coding it. Override at runtime via FlatGraph.SetCycleCheckLimit or the OLU_GRAPH_CYCLE_CHECK_LIMIT environment variable.

View Source 
const NodeTypeVode = "__vode__"

NodeTypeVode is the synthetic type assigned to a graph node that was created implicitly by AddEdge as a forward-reference placeholder. A vode represents a node that has been pointed at by a REF field but whose entity data has not yet arrived (e.g. during streaming graph hydration where edges may be replayed before their target entities are written).

Vode lifecycle:

  1. AddEdge("a:1", "b:1", "R") is called when "b:1" does not exist yet. addEdgeLocked creates "b:1" with type NodeTypeVode as a placeholder. VodeCount increments.

  2. The entity for "b:1" is later written and UpdateFromEntity / AddNode is called with the real type. addNodeLocked detects the promotion from NodeTypeVode, removes the node from the vode type index, adds it to the real type index, and decrements VodeCount.

  3. At the end of successful hydration, VodeCount() should be zero. A non-zero count indicates dangling references — entity data that was referenced by a REF field but never written to the store.

The string value "__vode__" is intentionally non-colliding with any valid olu entity type name (which may not contain underscores by convention). "Vode" is a domain-specific term; it is not an acronym and should not be confused with REF, which is the *edge* pointing at a vode node.

Variables

View Source 
var (
	ErrCycleDetected   = errors.New("adding this edge would create a cycle")
	ErrCrossTenantEdge = errors.New("edge endpoints belong to different tenants")
	ErrMalformedNodeID = errors.New("node ID contains '@' but is not a valid XXXX@-prefixed ID")
	// ErrEdgeAlreadyExists is returned by AddEdge when an edge from→to already
	// exists with a *different* relationship label. The same pair with the same
	// label is a no-op (idempotent); only label conflicts trigger this.
	//
	// NOTE: this sentinel is also used internally by UpdateFromEntityForTenant
	// as a signal that an existing edge needs its label updated. External callers
	// should only see it when they call AddEdge directly. If the semantics of
	// this error ever change, UpdateFromEntityForTenant must be audited too.
	ErrEdgeAlreadyExists = errors.New("edge already exists with a different relationship name")

	// ErrNodeTypeMismatch is returned by AddNode when the node already exists
	// with an established non-vode type and the caller supplies a different type.
	// Silently retyping a node corrupts the type index and is almost certainly a
	// caller bug.
	//
	// Vode nodes (type NodeTypeVode, created implicitly by AddEdge as forward-
	// reference placeholders) are explicitly exempt: promoting a vode to a real
	// type via AddNode is the intended completion path and does not trigger this
	// error.
	ErrNodeTypeMismatch = errors.New("node already exists with a different type")
)

Sentinel errors. Previously re-exported from pkg/graph/state; now defined here directly after the removal of IndexedGraph and the state package.

Functions

This section is empty.

Types

type AdaptivePersister 

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

AdaptivePersister handles graph persistence with adaptive timing. Under high write load, saves are batched to reduce I/O. Under low load, changes persist quickly.

DEPRECATED: The JSON filestore backend is deprecated. The AdaptivePersister is only started when that backend is in use (storeHasEdgeTable == false in main.go). SQLite deployments — i.e. all production configurations — never start it; graph persistence is handled by the store's edge tables in that path. When the JSON filestore is removed, this entire type should be deleted along with it.

func NewAdaptivePersister 

func NewAdaptivePersister(g Graph, filename string, logger zerolog.Logger) *AdaptivePersister

NewAdaptivePersister creates a new adaptive persister

func (*AdaptivePersister) MarkDirty 

func (p *AdaptivePersister) MarkDirty()

MarkDirty signals that the graph has been modified and needs to be persisted. Call this after any mutation (AddEdge, RemoveNode, etc.).

func (*AdaptivePersister) Start 

func (p *AdaptivePersister) Start()

Start begins the background persistence loop. It is safe to call more than once — only the first call starts the loop. Calling Stop without a prior Start is safe and returns immediately.

func (*AdaptivePersister) Stats 

func (p *AdaptivePersister) Stats() map[string]interface{}

Stats returns current persister statistics

func (*AdaptivePersister) Stop 

func (p *AdaptivePersister) Stop()

Stop gracefully shuts down, ensuring a final save. If Start was never called, Stop is a no-op and returns immediately.

func (*AdaptivePersister) WriterEnter 

func (p *AdaptivePersister) WriterEnter()

WriterEnter increments active writer count. Call at the start of a write operation.

func (*AdaptivePersister) WriterExit 

func (p *AdaptivePersister) WriterExit()

WriterExit decrements active writer count. Call at the end of a write operation (defer recommended).

type Degree 

type Degree struct {
	In    int `json:"in"`
	Out   int `json:"out"`
	Total int `json:"total"`
}

type FlatGraph 

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

FlatGraph implements Graph with a single node map per instance.

func NewFlatGraph 

func NewFlatGraph() *FlatGraph

NewFlatGraph returns an empty FlatGraph with cycle detection disabled.

func NewFlatGraphWithCycleDetection 

func NewFlatGraphWithCycleDetection(mode string) *FlatGraph

NewFlatGraphWithCycleDetection returns a FlatGraph with the given cycle detection mode ("ignore", "warn", or "error"). An unrecognised mode prints a warning to stderr and falls back to "ignore".

func NewFlatGraphWithLogger 

func NewFlatGraphWithLogger(logger zerolog.Logger) *FlatGraph

NewFlatGraphWithLogger returns a FlatGraph that emits structured log events via the supplied zerolog.Logger. Use zerolog.Nop() (the default) to suppress all graph-layer logging.

func (*FlatGraph) AddEdge 

func (g *FlatGraph) AddEdge(from, to, relationship string) error

func (*FlatGraph) AddNode 

func (g *FlatGraph) AddNode(nodeID, nodeType string) error

func (*FlatGraph) CheckEdge 

func (g *FlatGraph) CheckEdge(from, to, relationship string) error

CheckEdge runs the same pre-flight checks as AddEdge without modifying the graph. It is safe to call concurrently. Returns nil if AddEdge would accept the edge, or the first error AddEdge would return.

Note: there is an inherent TOCTOU gap between CheckEdge and a subsequent AddEdge call — a concurrent write could change the graph state in between. CheckEdge is intended for use as a guard before an external storage write (e.g. SQLite); false rejections are possible under high concurrency but are safe (the write is simply refused). False acceptances are not possible for single-threaded or low-concurrency workloads.

func (*FlatGraph) Clear 

func (g *FlatGraph) Clear() error

func (*FlatGraph) EdgeCount 

func (g *FlatGraph) EdgeCount() int

func (*FlatGraph) EdgeCountForTenant 

func (g *FlatGraph) EdgeCountForTenant(tenantPrefix string) (int, error)

func (*FlatGraph) FindPath 

func (g *FlatGraph) FindPath(from, to string, maxDepth int) ([]string, error)

func (*FlatGraph) GetAllNodes 

func (g *FlatGraph) GetAllNodes() []string

func (*FlatGraph) GetAllNodesForTenant 

func (g *FlatGraph) GetAllNodesForTenant(tenantPrefix string) ([]string, error)

func (*FlatGraph) GetDegree 

func (g *FlatGraph) GetDegree(nodeID string) (Degree, error)

func (*FlatGraph) GetIncomingEdges 

func (g *FlatGraph) GetIncomingEdges(nodeID string) (map[string]string, error)

GetIncomingEdges returns a copy of the incoming-edge map for nodeID. If nodeID does not exist, an empty map is returned with a nil error (same silent-empty contract as GetNeighbors; see its comment).

func (*FlatGraph) GetNeighbors 

func (g *FlatGraph) GetNeighbors(nodeID string) (map[string]string, error)

GetNeighbors returns a copy of the outgoing-edge map for nodeID. If nodeID does not exist, an empty map is returned with a nil error — deliberately unlike GetNodeInfo / GetDegree which error on absent nodes. The server layer relies on this: it calls GetNeighbors before deciding whether to add/remove edges and treats "no neighbours" the same as "node not yet in graph".

func (*FlatGraph) GetNodeInfo 

func (g *FlatGraph) GetNodeInfo(nodeID string) (*NodeInfo, error)

func (*FlatGraph) GetNodesByType 

func (g *FlatGraph) GetNodesByType(entityType string) []string

func (*FlatGraph) GetNodesByTypeForTenant 

func (g *FlatGraph) GetNodesByTypeForTenant(tenantPrefix, entityType string) ([]string, error)

func (*FlatGraph) HasCycle 

func (g *FlatGraph) HasCycle() bool

func (*FlatGraph) HasCycleForTenant 

func (g *FlatGraph) HasCycleForTenant(tenantPrefix string) (bool, error)

HasCycleForTenant reports whether the tenant-scoped subgraph (nodes whose ID carries tenantPrefix) contains a directed cycle. Only nodes with that prefix are visited; edges to other tenants are not followed. Returns (false, ErrTenantRequired) when tenantPrefix is empty.

func (*FlatGraph) Load 

func (g *FlatGraph) Load(filename string) error

Load replaces the graph's in-memory state with the contents of filename. If the file was written by a current version of olu, the cycle-detection mode and limit are restored from the file. Files written by older versions that lack these fields leave the current runtime configuration unchanged, so existing deployments that configure the mode via NewFlatGraphWithCycleDetection continue to work without modification. Load is a no-op (returns nil) when filename does not exist.

func (*FlatGraph) NodeCount 

func (g *FlatGraph) NodeCount() int

func (*FlatGraph) NodeCountForTenant 

func (g *FlatGraph) NodeCountForTenant(tenantPrefix string) (int, error)

func (*FlatGraph) NodeExists 

func (g *FlatGraph) NodeExists(nodeID string) bool

func (*FlatGraph) PathExists 

func (g *FlatGraph) PathExists(from, to string, maxDepth int) (bool, int, error)

func (*FlatGraph) RemoveEdge 

func (g *FlatGraph) RemoveEdge(from, to string) error

func (*FlatGraph) RemoveNode 

func (g *FlatGraph) RemoveNode(nodeID string) error

func (*FlatGraph) Save 

func (g *FlatGraph) Save(filename string) error

Save serialises the graph to filename using an atomic write (write to .tmp then rename). The cycle-detection mode and limit are included in the file so that Load can restore them without additional caller configuration. The read lock is held only long enough to snapshot in-memory state; JSON marshalling and disk I/O happen outside the lock.

func (*FlatGraph) SetCycleCheckLimit 

func (g *FlatGraph) SetCycleCheckLimit(n int)

SetCycleCheckLimit sets the maximum number of unique nodes the BFS in wouldCreateCycle may visit before returning true conservatively. A value of 0 restores the package default (DefaultCycleCheckLimit = 512). Negative values are treated as 0 (i.e. the default is used). This method is safe to call concurrently; it acquires the write lock. It is the runtime counterpart of the OLU_GRAPH_CYCLE_CHECK_LIMIT config key.

func (*FlatGraph) SharedOutNeighbors 

func (g *FlatGraph) SharedOutNeighbors(nodeA, nodeB string) ([]string, error)

SharedOutNeighbors returns nodes reachable from both nodeA and nodeB via outgoing edges. Only the out-maps are consulted: a node C that points to nodeA or nodeB via an incoming edge is not included.

When nodeA == nodeB the method returns all outgoing neighbours of that single node — every neighbour trivially satisfies "reachable from both".

Returns a non-nil (possibly empty) slice. Callers may rely on this; they do not need to guard against nil before ranging or checking length.

Formerly named CommonNeighbors; renamed to SharedOutNeighbors to make the directed out-edge-only semantics explicit and avoid confusion with the graph-theory term "common neighbours" which is typically undirected.

func (*FlatGraph) UpdateFromEntity 

func (g *FlatGraph) UpdateFromEntity(entity string, id int, data map[string]interface{}) error

func (*FlatGraph) UpdateFromEntityForTenant 

func (g *FlatGraph) UpdateFromEntityForTenant(tenantID uint16, entity string, id int, data map[string]interface{}) error

func (*FlatGraph) VodeCount 

func (g *FlatGraph) VodeCount() int

func (*FlatGraph) VodeCountForTenant 

func (g *FlatGraph) VodeCountForTenant(tenantPrefix string) (int, error)

type Graph 

type Graph interface {
	// Mutation
	AddNode(nodeID string, nodeType string) error
	RemoveNode(nodeID string) error
	AddEdge(from, to, relationship string) error
	RemoveEdge(from, to string) error
	// CheckEdge runs the same pre-flight checks as AddEdge (cross-tenant guard,
	// cycle detection) without modifying the graph. Returns nil if the edge
	// would be accepted, or the same error that AddEdge would return.
	// Use this to validate edges before committing the owning entity to storage,
	// so that a cycle-detection rejection cannot leave the SQLite edge table and
	// the in-memory graph in disagreement.
	CheckEdge(from, to, relationship string) error
	UpdateFromEntityForTenant(tenantID uint16, entity string, id int, data map[string]interface{}) error
	UpdateFromEntity(entity string, id int, data map[string]interface{}) error

	// Traversal
	GetNeighbors(nodeID string) (map[string]string, error)
	GetIncomingEdges(nodeID string) (map[string]string, error)
	FindPath(from, to string, maxDepth int) ([]string, error)
	PathExists(from, to string, maxDepth int) (bool, int, error)
	// SharedOutNeighbors returns the nodes that both nodeA and nodeB point to
	// via outgoing edges — i.e. shared out-neighbours in a directed graph.
	// Nodes that point *to* nodeA or nodeB (incoming edges) are not
	// considered. Returns an empty (non-nil) slice when there is no overlap.
	// Previously named CommonNeighbors; renamed to match graph-theory convention
	// (shared directed out-neighbours, not undirected common neighbours).
	SharedOutNeighbors(nodeA, nodeB string) ([]string, error)

	// Node queries
	NodeExists(nodeID string) bool
	GetNodeInfo(nodeID string) (*NodeInfo, error)
	GetNodesByType(entityType string) []string
	GetAllNodes() []string
	GetDegree(nodeID string) (Degree, error)

	// Metrics
	NodeCount() int
	EdgeCount() int
	HasCycle() bool
	// HasCycleForTenant reports whether the subgraph for the given tenant
	// prefix contains a directed cycle. It performs a DFS scoped to nodes
	// carrying that prefix; nodes from other tenants are not visited.
	// Returns an error if tenantPrefix is empty (same guard as the other
	// *ForTenant methods).
	HasCycleForTenant(tenantPrefix string) (bool, error)

	// VodeCount returns the total number of vode (placeholder) nodes currently
	// in the graph across all tenants. Should be zero after successful hydration.
	VodeCount() int
	// VodeCountForTenant returns the vode count for a single tenant. Returns
	// ErrTenantRequired if tenantPrefix is empty.
	VodeCountForTenant(tenantPrefix string) (int, error)

	// Tenant-scoped queries
	NodeCountForTenant(tenantPrefix string) (int, error)
	EdgeCountForTenant(tenantPrefix string) (int, error)
	GetAllNodesForTenant(tenantPrefix string) ([]string, error)
	GetNodesByTypeForTenant(tenantPrefix, entityType string) ([]string, error)

	// Persistence
	Save(filename string) error
	Load(filename string) error
	Clear() error
}

Graph interface defines all graph operations. The interface is intentionally broad so that the server layer never needs to type-assert to a concrete implementation.

type NodeInfo 

type NodeInfo struct {
	ID       string            `json:"id"`
	Entity   string            `json:"entity"`
	EntityID int               `json:"entity_id"`
	Outgoing map[string]string `json:"outgoing"`
	Incoming map[string]string `json:"incoming"`
	Degree   Degree            `json:"degree"`
}

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.