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.
Each label's node set is held as an index.NodeSet: a sparse label carried by one or a handful of nodes stays in the inline small-set tier (no per-label roaring overhead), while a dense label — one built via Index.AddRange over a contiguous NodeID band, or grown past the small-set threshold — is a roaring64.Bitmap with its run-container optimality intact. Promotion to the bitmap tier is one-way, so a dense label can never be mis-tiered as a small set (sprint 206, #1585).
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