graph

package
v1.22.78 Latest Latest
Warning

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

 Go to latest Published: Jan 1, 2026 License: BSD-3-Clause Imports: 8 Imported by: 0

Documentation

Index

Constants

View Source 
const (
	GasCreateNode          = 20000
	GasDeleteNode          = 15000
	GasCreateEdge          = 25000
	GasDeleteEdge          = 15000
	GasUpdateNode          = 10000
	GasUpdateEdge          = 10000
	GasGetNode             = 2000
	GasGetEdge             = 2000
	GasQueryBase           = 5000
	GasQueryPerItem        = 1000
	GasBFSBase             = 10000
	GasBFSPerNode          = 500
	GasDFSBase             = 10000
	GasDFSPerNode          = 500
	GasShortestPath        = 15000
	GasHasCycle            = 20000
	GasSubgraphMatch       = 50000
	GasTriangleCount       = 100000
	GasConnectedComponents = 50000
	GasGetCount            = 1000
)

Gas costs for operations.

Variables

View Source 
var (
	// Mutations
	SelectorCreateNode = [4]byte{0x01, 0x00, 0x00, 0x01} // createNode(bytes32,string,bytes)
	SelectorDeleteNode = [4]byte{0x01, 0x00, 0x00, 0x02} // deleteNode(bytes32)
	SelectorCreateEdge = [4]byte{0x01, 0x00, 0x00, 0x03} // createEdge(bytes32,bytes32,bytes32,string,bytes)
	SelectorDeleteEdge = [4]byte{0x01, 0x00, 0x00, 0x04} // deleteEdge(bytes32)
	SelectorUpdateNode = [4]byte{0x01, 0x00, 0x00, 0x05} // updateNode(bytes32,bytes)
	SelectorUpdateEdge = [4]byte{0x01, 0x00, 0x00, 0x06} // updateEdge(bytes32,bytes)

	// Queries
	SelectorGetNode           = [4]byte{0x02, 0x00, 0x00, 0x01} // getNode(bytes32)
	SelectorGetEdge           = [4]byte{0x02, 0x00, 0x00, 0x02} // getEdge(bytes32)
	SelectorQueryNodesByLabel = [4]byte{0x02, 0x00, 0x00, 0x03} // queryNodesByLabel(string)
	SelectorQueryEdgesByLabel = [4]byte{0x02, 0x00, 0x00, 0x04} // queryEdgesByLabel(string)
	SelectorGetOutgoingEdges  = [4]byte{0x02, 0x00, 0x00, 0x05} // getOutgoingEdges(bytes32)
	SelectorGetIncomingEdges  = [4]byte{0x02, 0x00, 0x00, 0x06} // getIncomingEdges(bytes32)

	// Traversal
	SelectorBFS          = [4]byte{0x03, 0x00, 0x00, 0x01} // bfs(bytes32,uint8,uint32,uint32,string)
	SelectorDFS          = [4]byte{0x03, 0x00, 0x00, 0x02} // dfs(bytes32,uint8,uint32,uint32,string)
	SelectorShortestPath = [4]byte{0x03, 0x00, 0x00, 0x03} // shortestPath(bytes32,bytes32,uint8,uint32,string)
	SelectorHasCycle     = [4]byte{0x03, 0x00, 0x00, 0x04} // hasCycle(bytes32)

	// Pattern Matching
	SelectorSubgraphMatch       = [4]byte{0x04, 0x00, 0x00, 0x01} // subgraphMatch(bytes,uint32)
	SelectorTriangleCount       = [4]byte{0x04, 0x00, 0x00, 0x02} // triangleCount()
	SelectorConnectedComponents = [4]byte{0x04, 0x00, 0x00, 0x03} // connectedComponents()

	// Stats
	SelectorGetNodeCount = [4]byte{0x05, 0x00, 0x00, 0x01} // getNodeCount()
	SelectorGetEdgeCount = [4]byte{0x05, 0x00, 0x00, 0x02} // getEdgeCount()
)

Function selectors (first 4 bytes of keccak256 of function signature).

View Source 
var (
	ErrNodeNotFound   = errors.New("node not found")
	ErrEdgeNotFound   = errors.New("edge not found")
	ErrInvalidInput   = errors.New("invalid input")
	ErrDuplicateNode  = errors.New("duplicate node")
	ErrDuplicateEdge  = errors.New("duplicate edge")
	ErrCyclicGraph    = errors.New("cyclic graph detected where not allowed")
	ErrPatternInvalid = errors.New("invalid pattern")
)
View Source 
var GraphPrecompileAddress = [20]byte{0x03, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0x10}

Precompile address for Graph operations. Address: 0x0300000000000000000000000000000000000010

Functions

func BytesToUint64 

func BytesToUint64(b []byte) uint64

BytesToUint64 converts bytes to uint64 (big-endian).

func Uint64ToBytes 

func Uint64ToBytes(n uint64) []byte

Uint64ToBytes converts uint64 to bytes (big-endian).

Types

type Edge 

type Edge struct {
	ID         EdgeID            `json:"id"`
	From       NodeID            `json:"from"`
	To         NodeID            `json:"to"`
	Label      string            `json:"label"`
	Properties map[string][]byte `json:"properties"`
}

Edge represents a directed edge between two nodes.

func DeserializeEdge 

func DeserializeEdge(data []byte) (*Edge, error)

DeserializeEdge deserializes bytes to an Edge.

func (*Edge) Serialize 

func (e *Edge) Serialize() ([]byte, error)

Serialize serializes an Edge to bytes.

type EdgeID 

type EdgeID [32]byte

EdgeID is a 32-byte identifier for an edge.

func GenerateEdgeID 

func GenerateEdgeID(from, to NodeID, label string) EdgeID

GenerateEdgeID creates a deterministic EdgeID from input data.

func ParseEdgeID 

func ParseEdgeID(data []byte) (EdgeID, error)

ParseEdgeID parses an EdgeID from bytes.

type GraphContract 

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

GraphContract implements the graph database precompile.

func NewGraphContract 

func NewGraphContract(db database.Database) *GraphContract

NewGraphContract creates a new graph contract instance.

func (*GraphContract) RequiredGas 

func (c *GraphContract) RequiredGas(input []byte) uint64

RequiredGas returns the gas required for the operation.

func (*GraphContract) Run 

func (c *GraphContract) Run(input []byte) ([]byte, error)

Run executes the graph precompile operation.

type GraphStorage 

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

GraphStorage provides persistent storage for graph data.

func NewGraphStorage 

func NewGraphStorage(db database.Database) *GraphStorage

NewGraphStorage creates a new graph storage instance.

func (*GraphStorage) BFS 

func (s *GraphStorage) BFS(startID NodeID, opts TraversalOptions) ([]TraversalResult, error)

BFS performs breadth-first search starting from the given node. Returns all visited nodes in BFS order with their depths.

func (*GraphStorage) ConnectedComponents 

func (s *GraphStorage) ConnectedComponents() (int, error)

ConnectedComponents returns the number of connected components. Uses union-find algorithm.

func (*GraphStorage) CreateEdge 

func (s *GraphStorage) CreateEdge(edge *Edge) error

CreateEdge stores a new edge in the graph.

func (*GraphStorage) CreateNode 

func (s *GraphStorage) CreateNode(node *Node) error

CreateNode stores a new node in the graph.

func (*GraphStorage) DFS 

func (s *GraphStorage) DFS(startID NodeID, opts TraversalOptions) ([]TraversalResult, error)

DFS performs depth-first search starting from the given node. Returns all visited nodes in DFS order with their depths.

func (*GraphStorage) DeleteEdge 

func (s *GraphStorage) DeleteEdge(id EdgeID) error

DeleteEdge removes an edge.

func (*GraphStorage) DeleteNode 

func (s *GraphStorage) DeleteNode(id NodeID) error

DeleteNode removes a node and all its edges.

func (*GraphStorage) GetEdge 

func (s *GraphStorage) GetEdge(id EdgeID) (*Edge, error)

GetEdge retrieves an edge by ID.

func (*GraphStorage) GetEdgeCount 

func (s *GraphStorage) GetEdgeCount() (uint64, error)

GetEdgeCount returns the total number of edges.

func (*GraphStorage) GetIncomingEdges 

func (s *GraphStorage) GetIncomingEdges(nodeID NodeID) ([]*Edge, error)

GetIncomingEdges returns all edges ending at a node.

func (*GraphStorage) GetNode 

func (s *GraphStorage) GetNode(id NodeID) (*Node, error)

GetNode retrieves a node by ID.

func (*GraphStorage) GetNodeCount 

func (s *GraphStorage) GetNodeCount() (uint64, error)

GetNodeCount returns the total number of nodes.

func (*GraphStorage) GetOutgoingEdges 

func (s *GraphStorage) GetOutgoingEdges(nodeID NodeID) ([]*Edge, error)

GetOutgoingEdges returns all edges starting from a node.

func (*GraphStorage) HasCycle 

func (s *GraphStorage) HasCycle(startID NodeID) (bool, error)

HasCycle checks if there is a cycle in the graph starting from the given node.

func (*GraphStorage) QueryEdgesByLabel 

func (s *GraphStorage) QueryEdgesByLabel(label string) ([]*Edge, error)

QueryEdgesByLabel returns all edges with the given label.

func (*GraphStorage) QueryNodesByLabel 

func (s *GraphStorage) QueryNodesByLabel(label string) ([]*Node, error)

QueryNodesByLabel returns all nodes with the given label.

func (*GraphStorage) ReachableNodes 

func (s *GraphStorage) ReachableNodes(startID NodeID, opts TraversalOptions) ([]NodeID, error)

ReachableNodes returns all nodes reachable from the start node within maxDepth.

func (*GraphStorage) ShortestPath 

func (s *GraphStorage) ShortestPath(fromID, toID NodeID, opts TraversalOptions) ([]NodeID, error)

ShortestPath finds the shortest path between two nodes using BFS. Returns the path and an error if no path exists.

func (*GraphStorage) SubgraphMatch 

func (s *GraphStorage) SubgraphMatch(pattern SubgraphPattern, maxResults int) ([]MatchResult, error)

SubgraphMatch finds all subgraphs matching the given pattern. Uses backtracking with constraint satisfaction.

func (*GraphStorage) TriangleCount 

func (s *GraphStorage) TriangleCount() (uint64, error)

TriangleCount counts the number of triangles in the graph. A triangle is a cycle of exactly 3 nodes.

type MatchResult 

type MatchResult struct {
	Bindings map[string]NodeID `json:"bindings"` // var name -> matched node
}

MatchResult represents a single match from subgraph matching.

type Node 

type Node struct {
	ID         NodeID            `json:"id"`
	Label      string            `json:"label"`
	Properties map[string][]byte `json:"properties"`
}

Node represents a vertex in the graph.

func DeserializeNode 

func DeserializeNode(data []byte) (*Node, error)

DeserializeNode deserializes bytes to a Node.

func (*Node) Serialize 

func (n *Node) Serialize() ([]byte, error)

Serialize serializes a Node to bytes.

type NodeID 

type NodeID [32]byte

NodeID is a 32-byte identifier for a node.

func GenerateNodeID 

func GenerateNodeID(data []byte) NodeID

GenerateNodeID creates a deterministic NodeID from input data.

func ParseNodeID 

func ParseNodeID(data []byte) (NodeID, error)

ParseNodeID parses a NodeID from bytes.

type PatternEdge 

type PatternEdge struct {
	FromVar    string            `json:"from_var"`
	ToVar      string            `json:"to_var"`
	Label      string            `json:"label"`
	Properties map[string][]byte `json:"properties"`
}

PatternEdge represents an edge constraint in a subgraph pattern.

type PatternNode 

type PatternNode struct {
	Var        string            `json:"var"`        // Variable name for binding
	Label      string            `json:"label"`      // Required label (empty = any)
	Properties map[string][]byte `json:"properties"` // Required properties
}

PatternNode represents a node constraint in a subgraph pattern.

type SubgraphPattern 

type SubgraphPattern struct {
	Nodes []PatternNode `json:"nodes"`
	Edges []PatternEdge `json:"edges"`
}

SubgraphPattern represents a pattern for matching subgraphs.

type TraversalDirection 

type TraversalDirection int

TraversalDirection specifies the direction of edge traversal. 

const (
	DirectionOutgoing TraversalDirection = iota
	DirectionIncoming
	DirectionBoth
)

type TraversalOptions 

type TraversalOptions struct {
	Direction TraversalDirection
	MaxDepth  int
	MaxNodes  int
	EdgeLabel string // Filter by edge label (empty = all)
}

TraversalOptions configures graph traversal behavior.

func DefaultTraversalOptions 

func DefaultTraversalOptions() TraversalOptions

DefaultTraversalOptions returns sensible defaults.

type TraversalResult 

type TraversalResult struct {
	Path  []NodeID `json:"path"`
	Depth int      `json:"depth"`
}

TraversalResult represents a path found during traversal.

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.