Crate uqa_graph 

Property graphs and their posting representation.

Defines GraphStore (trait + in-memory implementation), the GraphPostingList extension of uqa_core::PostingList, and the lossless Phi codec for carrying graph metadata through ordinary posting storage. Graph-result merges expose their subgraph collision policy separately from ordinary posting payload merges.

Re-exports

pub use adapters::GraphPostingCodec;

pub use adapters::PostingToGraphAdapter;

pub use adapters::TextTfScoreNormalizer;

Modules

adapters

Explicit adapters between posting representations.

age_names

Apache AGE graph and label name validation.

agtype

Canonical Apache AGE agtype value model and text rendering.

cypher

openCypher subset: lexer, AST, recursive-descent parser. The compiler that lowers AST onto graph operators lives in a separate slice; this module is the front-end only.

Structs

BetweennessCentrality

Betweenness centrality via Brandes algorithm.

CypherQueryOperator

CypherQueryOperator — execute a parsed openCypher query against a named graph and project the resulting (start, end) vertex pairs into a posting list for downstream operator composition.

Dfa

Document

A simple document representation for ToGraph / TextToGraph.

EdgePattern

(E_P) — an edge between two vertex variables, with an optional label and per-property constraints. negated == true flips it into a “must not exist” pattern, matched after positive edges resolve.

GMatch

GMatch_P (Definition 2.2.2 / 5.2.2): subgraph-isomorphism pattern matching via backtracking with arc-consistency candidate pruning, MRV (minimum remaining values) variable ordering, and a negated-edge post-filter. Each match maps each pattern variable to a vertex id; the result is a GraphPostingList keyed on a synthetic 1-based match id, with the assignment carried as payload fields.

GraphDelta

Records add / remove vertex / edge operations (Section 9.3, Paper 2).

GraphEmbedding

GraphLabelInfo

One ag_label catalog entry of a graph.

GraphLabelRegistry

Per-graph AGE label registry: label name -> label id plus the per-label id sequences. Serializable so engines can persist it in catalog metadata and restore deterministic id allocation.

GraphPattern

Subgraph pattern: P = (V_P, E_P, C_V, C_E).

GraphPayload

Auxiliary payload for graph posting list entries: the subgraph each matched entry refers to, plus a graph-name tag and a score override.

GraphPostingList

Posting list paired with a (doc_id -> GraphPayload) map. The invariants of the underlying PostingList (sorted, unique doc ids) hold here as well.

HITS

HITS centrality (hub / authority mutual reinforcement).

IncrementalPatternMatcher

LabelIndex

MemoryGraphStore

MessagePassing

Nfa

NfaTransition

NFA transition target. Some(label) is a labeled edge consumed by matching that label; None is an epsilon transition.

PageRank

PageRank centrality (power iteration with damping).

PathIndex

Pre-indexed reachable (start, end) pairs for fixed label sequences. Lookup is keyed by the slash-joined sequence so the RPQ operator can lift a Label / Label / ... expression into a direct hit without running NFA simulation.

RegularPathQuery

RPQ_R (Definition 5.1.2): evaluate a regular path expression over a graph. The expression is simplified, compiled to an NFA via Thompson’s construction, then converted to a DFA and simulated by a BFS over (vertex, dfa-state) configurations.

SQLiteGraphStore

SemanticGraphSearch

Traverse followed by a vector-similarity filter: keep only the vertices whose vector_field similarity to query_vector clears threshold. The retained entries’ scores are the cosine values.

SubgraphIndex

TemporalPatternMatch

Temporal-aware pattern matching (Section 10, Paper 2).

TemporalTraverse

BFS traversal that applies a TemporalFilter to every candidate edge before it is followed. Mirrors the structure of crate::Traverse but with the filter step inlined.

TextToGraph

Build a token co-occurrence graph from a document corpus.

ToGraph

Convert a document corpus into a fresh MemoryGraphStore.

Traverse

Traverse_{v,l,k} (Definition 2.2.1): BFS from start_vertex along edges with label (any label when None) up to max_hops hops. Each visited vertex becomes its own entry in the result.

VectorEnhancedMatch

GMatch followed by a per-match cosine filter against the vertex bound to score_variable. Matches with similarity below threshold are dropped; surviving entries take the cosine value as their score.

VersionedGraphStore

VertexAggregation

Aggregate a numeric property over the vertex set rolled up in a source operator’s GraphPayloads. Mirrors Definition 2.2.3.

VertexEmbedding

Per-vertex cosine similarity to a query embedding. Reads the named vector property and emits a standard PostingList keyed by vertex id, with the cosine score on the payload.

VertexMatch

Single-vertex Match: every vertex in graph whose label matches and whose predicates all hold. Useful as a Cypher-style anchor.

VertexPattern

(V_P) — a vertex variable in a pattern, with optional constraints.

VertexPropertyIndex

Immutable equality index over selected vertex properties in one named graph.

WeightedPathQuery

A bounded regular-path walk whose accumulated numeric edge weight must satisfy a caller-provided predicate.

WeightedPathQueryOperator

WeightedPathQueryOperator evaluates bounded DFA walks, sums a numeric edge property, and keeps endpoints for which the accumulated weight passes predicate. The selectivity value is retained solely for planning; it never substitutes for physical predicate evaluation.

Enums

AggFn

Aggregation function over a numeric vertex property.

AggregationKind

CrossParadigmError

DeltaOp

A single mutation operation in a GraphDelta.

Direction

Edge traversal direction relative to a vertex.

EdgePredicate

Predicate over an edge.

GraphPostingListError

GraphStoreError

LabelKind

AGE label kind: the ag_label.kind catalog value.

RPQBuildError

RPQParseError

RegularPathExpr

Regular path expression.

SubgraphMergePolicy

How graph metadata is combined when two graph results contain the same document. Ordinary posting payloads still follow PostingList::merge_union / PostingList::merge_intersection; this policy applies only to the graph name and subgraph vertex/edge sets.

TemporalFilter

Time-aware edge filter. Timestamp(t) accepts an edge if valid_from <= t <= valid_to; Range(a, b) accepts an edge whose validity interval overlaps [a, b]. An edge with neither valid_from nor valid_to is always accepted.

VertexPredicate

Predicate over a vertex.

Constants

DEFAULT_GRAPH_SCORE

Default score lifted into traversal and match payloads.

EDGE_DEFAULT_LABEL_ID

Reserved AGE label id for unlabeled edges (_ag_label_edge).

FIRST_USER_LABEL_ID

First label id available to user labels.

GRAPHID_LABEL_SHIFT

Number of bits reserved for the per-label sequence inside an AGE graphid. The label id occupies the remaining high 16 bits.

MAX_DFA_STATES

MAX_GRAPH_EMBEDDING_DIMENSIONS

MAX_GRAPH_EMBEDDING_LAYERS

MAX_MESSAGE_PASSING_LAYERS

Protects the public graph API from accidentally scheduling billions of full-graph propagation rounds from an unchecked u32 input.

MAX_NFA_STATES

MAX_RPQ_AST_DEPTH

Hard limits keep user-provided path expressions from turning NFA or DFA compilation into an unbounded memory allocation. They are deliberately independent: a compact NFA can still have an exponential DFA.

VERTEX_DEFAULT_LABEL_ID

Reserved AGE label id for unlabeled vertices (_ag_label_vertex).

Traits

GraphStore

Storage interface for named property graphs.

Functions

build_nfa

Build an NFA from a regular path expression via Thompson’s construction.

epsilon_closure

Epsilon closure of a state set: every state reachable by zero or more epsilon (label == None) transitions.

graphid_label_id

Label id component of an AGE graphid.

graphid_sequence

Sequence component of an AGE graphid.

implicated_vertices

Convenience helper: count vertices implicated by a delta, using the store to resolve removed edges back to their endpoints when those records are still around.

make_graphid

Compose an AGE graphid from a label id and per-label sequence.

parse_rpq

simplify

Algebraic simplification (Section 8.2, Paper 2): a|a -> a, (a*)* -> a*, a*|a -> a*, a*/a* -> a*, plus canonicalization of alternation operand order.

subset_construction

Convert an NFA to a DFA via the standard subset construction.

Type Aliases

CrossParadigmResult

DfaState

GraphPostingListResult

GraphStoreResult

StateId