graph

package
v0.30.38 Latest Latest
Warning

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

 Go to latest Published: Sep 7, 2026 License: Apache-2.0 Imports: 10 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 XOLU_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 XOLU_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 xolu 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 Degree 

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

type EdgeRef 

type EdgeRef struct {
	Rel string
	ID  int
}

EdgeRef identifies an outgoing edge from a traversal result. Rel is the relationship label (always present). ID is the surrogate edge ID assigned when the edge has a property row in t<X>_edges or t<X>_edata_<label>; zero means no properties are stored.

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) AddEdgeWithID 

func (g *FlatGraph) AddEdgeWithID(from, to, relationship string, edgeID int) error

AddEdgeWithID adds the edge and sets EdgeRef.ID in the adjacency map. Used during graph hydration to restore surrogate edge IDs from the topology table so that relationship variables in Sulpher queries can trigger property fetch via preHydrateEnvs.

func (*FlatGraph) AddEdgeWithProps 

func (g *FlatGraph) AddEdgeWithProps(from, to, relationship string, props map[string]interface{}) error

AddEdgeWithProps records the edge topology. The props argument is accepted for interface compatibility but is not stored in the in-memory graph — property persistence is handled by the storage layer (SQLiteStore), which assigns surrogate IDs and writes to t<X>_edges. A nil or empty props map makes this call identical to AddEdge.

func (*FlatGraph) AddNode 

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

func (*FlatGraph) AllShortestPaths 

func (g *FlatGraph) AllShortestPaths(from, to string, maxDepth int, dir PathDirection) ([][]string, error)

AllShortestPaths returns all paths of minimum length from from to to, using the given traversal direction. Uses a two-phase BFS:

  1. Find the minimum path length.
  2. Enumerate all paths of exactly that length.

Returns an empty slice (not an error) when no path exists.

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) FindPathDirected 

func (g *FlatGraph) FindPathDirected(from, to string, maxDepth int, dir PathDirection) ([]string, error)

FindPathDirected finds the shortest path between two nodes, respecting the given traversal direction. PathDirOutgoing behaves identically to FindPath. PathDirIncoming follows edges in reverse (target→source direction). PathDirAny follows edges in either direction (undirected BFS).

Returns the path as an ordered slice of node IDs from source to destination.

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]EdgeRef, 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]EdgeRef, 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) 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) 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 XOLU_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 tenant.TenantID, 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
	// AddEdgeWithProps is like AddEdge but signals that the edge carries
	// property data. The graph layer records the edge; the storage layer
	// assigns a surrogate edge ID and writes the property blob. A nil or
	// empty props map is equivalent to calling AddEdge.
	AddEdgeWithProps(from, to, relationship string, props map[string]interface{}) error
	// AddEdgeWithID is used during graph hydration to restore a previously
	// assigned surrogate edge ID into the in-memory adjacency map. It is
	// equivalent to AddEdge but sets EdgeRef.ID so that relationship variable
	// binding in Sulpher queries can surface the stored edge properties.
	// edgeID = 0 means the edge has no property row (same semantics as AddEdge).
	AddEdgeWithID(from, to, relationship string, edgeID int) 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 tenant.TenantID, entity string, id int, data map[string]interface{}) error
	UpdateFromEntity(entity string, id int, data map[string]interface{}) error

	// Traversal
	// GetNeighbors returns the outgoing edges from nodeID as a map from
	// neighbour node ID to EdgeRef. EdgeRef.Rel is the relationship label;
	// EdgeRef.ID is the surrogate edge ID (0 when no property row exists).
	GetNeighbors(nodeID string) (map[string]EdgeRef, error)
	// GetIncomingEdges returns the incoming edges to nodeID as a map from
	// source node ID to EdgeRef.
	GetIncomingEdges(nodeID string) (map[string]EdgeRef, error)
	FindPath(from, to string, maxDepth int) ([]string, error)
	// FindPathDirected finds the shortest path respecting the given traversal
	// direction. PathDirOutgoing follows outgoing edges (same as FindPath),
	// PathDirIncoming follows incoming edges, PathDirAny follows both.
	// Returns the path as ordered node IDs from source to destination.
	FindPathDirected(from, to string, maxDepth int, dir PathDirection) ([]string, error)
	// AllShortestPaths returns all paths of minimum length from from to to.
	// Uses the same direction semantics as FindPathDirected.
	AllShortestPaths(from, to string, maxDepth int, dir PathDirection) ([][]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
	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"`
}

type PathDirection 

type PathDirection int

PathDirection controls which edges are followed during path traversal. 

const (
	PathDirOutgoing PathDirection = iota // follow outgoing edges only (default)
	PathDirIncoming                      // follow incoming edges only
	PathDirAny                           // follow edges in either direction (undirected)
)

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.