Documentation
¶
Overview ¶
Package label provides a Roaring-bitmap-backed inverted index from label identifiers to the NodeIDs that carry them.
The index is the substrate for label-filtered queries such as "find every node with label Person and label Active": each label is represented by a 64-bit Roaring bitmap, and compound queries are answered via bitmap intersection / union, which Roaring implements with run-length and array-bitmap hybrids.
Index is safe for concurrent use.
Index ¶
- type Index
- func (i *Index) Add(label uint32, node graph.NodeID)
- func (i *Index) AddRange(label uint32, fromNode, toNode graph.NodeID)
- func (i *Index) Apply(c index.Change)
- func (i *Index) Count(label uint32) uint64
- func (i *Index) Deserialize(r io.Reader) error
- func (i *Index) Has(label uint32, node graph.NodeID) bool
- func (i *Index) Intersect(labels ...uint32) *roaring64.Bitmap
- func (*Index) Kind() string
- func (i *Index) Remove(label uint32, node graph.NodeID)
- func (i *Index) RemoveRange(label uint32, fromNode, toNode graph.NodeID)
- func (i *Index) Scan(label uint32) []graph.NodeID
- func (i *Index) Scope() Scope
- func (i *Index) Serialize(w io.Writer) error
- func (i *Index) Union(labels ...uint32) *roaring64.Bitmap
- type Scope
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Index ¶
type Index struct {
// contains filtered or unexported fields
}
Index maps label identifiers (uint32) to the set of NodeIDs that carry them. Different LabelID namespaces (vertices, edges) should use distinct Index instances.
Example ¶
ExampleIndex shows membership queries on the label bitmap index: add NodeIDs under a label, test single-node membership with Has, count the carriers, and Scan the full member set in ascending NodeID order.
package main
import (
"fmt"
"github.com/FlavioCFOliveira/GoGraph/graph"
"github.com/FlavioCFOliveira/GoGraph/graph/index/label"
)
// Interned label identifiers used by the examples below. A real graph
// obtains these from its lpg.LabelID registry; here they are constants.
const labelPerson = uint32(1)
func main() {
idx := label.NewNodeIndex()
idx.Add(labelPerson, graph.NodeID(1))
idx.Add(labelPerson, graph.NodeID(2))
idx.Add(labelPerson, graph.NodeID(3))
fmt.Println("node 2 is Person:", idx.Has(labelPerson, graph.NodeID(2)))
fmt.Println("node 9 is Person:", idx.Has(labelPerson, graph.NodeID(9)))
fmt.Println("Person count:", idx.Count(labelPerson))
fmt.Println("Person members:", idx.Scan(labelPerson))
}
Output: node 2 is Person: true node 9 is Person: false Person count: 3 Person members: [1 2 3]
func NewEdgeIndex ¶
func NewEdgeIndex() *Index
NewEdgeIndex returns an empty index that listens for edge-label changes when registered with a index.Manager.
func NewIndex ¶
func NewIndex() *Index
NewIndex returns an empty index in ScopeNode — equivalent to NewNodeIndex. Existing callers that pre-date the scope field keep this constructor as the default.
func NewNodeIndex ¶
func NewNodeIndex() *Index
NewNodeIndex returns an empty index that listens for node-label changes when registered with a index.Manager.
func (*Index) AddRange ¶
AddRange records that all nodes in [fromNode, toNode] (inclusive) carry label. It uses roaring64.Bitmap.AddRange which represents dense ranges in O(1) space, making bulk ingestion of contiguous NodeID bands efficient.
func (*Index) Apply ¶
Apply dispatches the change to the underlying bitmaps when the change kind matches the index's Scope. Other ops are ignored (the manager fans every change to every subscriber; per-subscriber filtering is the subscriber's responsibility).
func (*Index) Deserialize ¶
Deserialize replaces the receiver's state with the contents of r. On any structural problem, truncated payload, or CRC mismatch the function returns a wrapped index.ErrIndexCorrupted and the receiver is restored to the pre-call state.
The implementation reads the whole payload into a buffer, validates the trailing CRC32C against the prefix, then re-parses the prefix to populate the bitmaps. This costs one extra pass over the data but keeps the corruption-detection contract simple and lets the reader reject malformed inputs before any state mutation.
func (*Index) Intersect ¶
Intersect returns a fresh Roaring bitmap containing the NodeIDs that carry every supplied label. Calling with no labels returns the empty bitmap.
Example ¶
ExampleIndex_Intersect shows compound label queries via bitmap set operations. Intersect answers "every node carrying all of these labels"; Union answers "every node carrying any of them".
package main
import (
"fmt"
"github.com/FlavioCFOliveira/GoGraph/graph"
"github.com/FlavioCFOliveira/GoGraph/graph/index/label"
)
// Interned label identifiers used by the examples below. A real graph
// obtains these from its lpg.LabelID registry; here they are constants.
const (
labelPerson = uint32(1)
labelActive = uint32(2)
)
func main() {
idx := label.NewNodeIndex()
for _, n := range []graph.NodeID{1, 2, 3} {
idx.Add(labelPerson, n)
}
for _, n := range []graph.NodeID{2, 3, 4} {
idx.Add(labelActive, n)
}
both := idx.Intersect(labelPerson, labelActive)
either := idx.Union(labelPerson, labelActive)
fmt.Println("Person AND Active:", both.ToArray())
fmt.Println("Person OR Active:", either.ToArray())
}
Output: Person AND Active: [2 3] Person OR Active: [1 2 3 4]
func (*Index) RemoveRange ¶
RemoveRange records that all nodes in [fromNode, toNode] (inclusive) no longer carry label. Empty bitmaps are deleted so the map does not grow unboundedly after bulk-remove operations.
func (*Index) Scan ¶
Scan returns the sorted slice of NodeIDs that carry label. Returns nil when label has no entries.
func (*Index) Scope ¶
Scope reports which label-event kind the index observes via Index.Apply.
func (*Index) Serialize ¶
Serialize writes the index's per-label bitmaps to w in the format documented in docs/persistence.md. The on-disk layout is:
uint32 magic ('SLBI')
uint32 formatVersion
uint32 labelCount
repeat labelCount times:
uint32 labelID
uint64 bitmapLen
[bitmapLen]byte bitmap (Roaring native binary format)
uint32 crc32c (covers every byte above, little-endian)
Serialize takes the index's RLock for the whole emission so a concurrent writer cannot observe a partially serialised state. The returned error wraps the underlying I/O failure verbatim; the caller treats short writes the same as any other I/O error.
type Scope ¶
type Scope uint8
Scope tags whether the index observes node-label or edge-label changes when registered with index.Manager. The two scopes share a common bitmap shape so the on-disk format is identical.
const ( // ScopeNode listens for [index.OpAddNodeLabel] / [index.OpRemoveNodeLabel] // when the index is registered with a [index.Manager]. It is the // default; callers building an unregistered index can ignore the // scope entirely. ScopeNode Scope = iota + 1 // ScopeEdge listens for [index.OpAddEdgeLabel] / [index.OpRemoveEdgeLabel]. // Edge bitmaps are keyed by the source NodeID, mirroring the LPG // convention exposed by [lpg.Graph.EdgeIndex]. ScopeEdge )
Scope values for NewNodeIndex / NewEdgeIndex.
Source Files