uqa-graph 0.3.8

//
// Unified Query Algebra
//
// Copyright (c) 2023-2026 Cognica, Inc.
//

//! Specialized graph indexes for accelerating traversal and RPQ
//! evaluation (Section 6.4, Paper 2).
//!
//! `LabelIndex` exposes label cardinality and label-to-vertex sets on
//! top of what the underlying [`GraphStore`] already tracks.
//! `PathIndex` pre-computes the `(start, end)` reachability set for a
//! list of label sequences so the RPQ operator can short-circuit when
//! the input expression is a pure label-concatenation.

use std::collections::{BTreeMap, BTreeSet};

use uqa_core::{EdgeId, Value, VertexId};

use crate::store::{GraphStore, GraphStoreError, GraphStoreResult};

#[derive(Debug, Clone, Default)]
pub struct LabelIndex {
    label_to_edges: BTreeMap<String, Vec<EdgeId>>,
    label_to_vertices: BTreeMap<String, BTreeSet<VertexId>>,
}

impl LabelIndex {
    pub fn build<G: GraphStore>(store: &G, graph: &str) -> GraphStoreResult<Self> {
        let mut idx = Self::default();
        for vid in store.vertex_ids_in_graph(graph)? {
            for eid in store.out_edge_ids(vid, graph)? {
                let edge = store.get_edge(eid)?.ok_or_else(|| {
                    GraphStoreError::CorruptGraph(format!("missing indexed edge {eid}"))
                })?;
                idx.label_to_edges
                    .entry(edge.label.clone())
                    .or_default()
                    .push(eid);
                let vset = idx.label_to_vertices.entry(edge.label.clone()).or_default();
                vset.insert(edge.source_id);
                vset.insert(edge.target_id);
            }
        }
        for edges in idx.label_to_edges.values_mut() {
            edges.sort_unstable();
            edges.dedup();
        }
        Ok(idx)
    }

    pub fn edges_by_label(&self, label: &str) -> &[EdgeId] {
        self.label_to_edges.get(label).map_or(&[], Vec::as_slice)
    }

    pub fn vertices_by_label(&self, label: &str) -> Option<&BTreeSet<VertexId>> {
        self.label_to_vertices.get(label)
    }

    pub fn labels(&self) -> Vec<String> {
        self.label_to_edges.keys().cloned().collect()
    }

    pub fn label_count(&self, label: &str) -> usize {
        self.label_to_edges.get(label).map_or(0, Vec::len)
    }
}

/// Immutable equality index over selected vertex properties in one named graph.
///
/// Missing properties are not indexed, while an explicitly stored
/// [`Value::Null`] remains queryable. Value equality follows [`Value`]'s total
/// ordering, including its cross-numeric equality rules, so indexed lookup and
/// relational equality agree.
#[derive(Debug, Clone, Default)]
pub struct VertexPropertyIndex {
    property_values: BTreeMap<String, BTreeMap<Value, BTreeSet<VertexId>>>,
}

impl VertexPropertyIndex {
    pub fn build<G: GraphStore>(
        store: &G,
        graph: &str,
        properties: &[&str],
    ) -> GraphStoreResult<Self> {
        let property_names: BTreeSet<String> = properties
            .iter()
            .map(|property| (*property).to_owned())
            .collect();
        let mut property_values: BTreeMap<String, BTreeMap<Value, BTreeSet<VertexId>>> =
            property_names
                .iter()
                .map(|property| (property.clone(), BTreeMap::new()))
                .collect();

        for vertex_id in store.vertex_ids_in_graph(graph)? {
            let vertex = store.get_vertex(vertex_id)?.ok_or_else(|| {
                GraphStoreError::CorruptGraph(format!(
                    "graph {graph:?} references missing indexed vertex {vertex_id}"
                ))
            })?;
            for property in &property_names {
                let Some(value) = vertex.properties.get(property) else {
                    continue;
                };
                property_values
                    .get_mut(property)
                    .expect("requested property was initialized")
                    .entry(value.clone())
                    .or_default()
                    .insert(vertex_id);
            }
        }

        Ok(Self { property_values })
    }

    pub fn has_property(&self, property: &str) -> bool {
        self.property_values.contains_key(property)
    }

    pub fn lookup_eq(&self, property: &str, value: &Value) -> Option<&BTreeSet<VertexId>> {
        self.property_values.get(property)?.get(value)
    }

    pub fn property_names(&self) -> impl Iterator<Item = &str> {
        self.property_values.keys().map(String::as_str)
    }
}

// Path-index handles retain only definitions for durable stores.
mod path_index;
pub use path_index::PathIndex;

#[cfg(test)]
mod tests {
    use uqa_core::{Value, Vertex};

    use super::VertexPropertyIndex;
    use crate::{GraphStore, MemoryGraphStore};

    #[test]
    fn vertex_property_index_tracks_selected_values_and_missing_fields() {
        let mut store = MemoryGraphStore::new();
        store.create_graph("g");
        let mut first = Vertex::new(1, "node");
        first.properties.insert("val".into(), Value::Int(7));
        first.properties.insert("nullable".into(), Value::Null);
        store.add_vertex(first, "g").unwrap();
        let mut second = Vertex::new(2, "node");
        second.properties.insert("val".into(), Value::Float(7.0));
        store.add_vertex(second, "g").unwrap();

        let index =
            VertexPropertyIndex::build(&store, "g", &["val", "nullable", "missing"]).unwrap();

        assert!(index.has_property("val"));
        assert!(index.has_property("missing"));
        assert_eq!(
            index.lookup_eq("val", &Value::Int(7)).unwrap(),
            &std::collections::BTreeSet::from([1, 2])
        );
        assert_eq!(
            index.lookup_eq("nullable", &Value::Null).unwrap(),
            &std::collections::BTreeSet::from([1])
        );
        assert!(index.lookup_eq("missing", &Value::Null).is_none());
        assert!(index.lookup_eq("not-indexed", &Value::Int(7)).is_none());
    }

    #[test]
    fn vertex_property_index_rejects_unknown_graph() {
        let store = MemoryGraphStore::new();
        let error = VertexPropertyIndex::build(&store, "missing", &["val"]).unwrap_err();
        assert!(error.to_string().contains("missing"));
    }
}