pathrex 0.1.0

Library and CLI for benchmarking RPQ/CFL queries on edge-labeled graphs via SuiteSparse:GraphBLAS and LAGraph.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121

//! Regular Path Query (RPQ) evaluation over edge-labeled graphs.
//! ```rust,ignore
//! use pathrex::sparql::parse_rpq;
//! use pathrex::rpq::{RpqEvaluator, nfarpq::{NfaRpqEvaluator, NfaRpqResult}};
//!
//! let mut query = parse_rpq(
//!     "BASE <http://example.org/> SELECT ?x ?y WHERE { ?x <knows>/<likes>* ?y . }",
//! )?;
//! query.strip_base("http://example.org/");
//! let result: NfaRpqResult = NfaRpqEvaluator.evaluate(&query, &graph)?;
//! ```

pub mod nfarpq;
pub mod rpqmatrix;

use crate::eval::{Evaluator, PreparedEvaluator};
use crate::graph::{GraphDecomposition, GraphError};
use crate::sparql::ExtractError;
use spargebra::SparqlSyntaxError;
use thiserror::Error;

#[derive(Clone, Debug, PartialEq, Eq)]
pub enum Endpoint {
    Variable(String),
    Named(String),
}

#[derive(Clone, Debug, PartialEq, Eq)]
pub enum PathExpr {
    Label(String),
    Sequence(Box<PathExpr>, Box<PathExpr>),
    Alternative(Box<PathExpr>, Box<PathExpr>),
    ZeroOrMore(Box<PathExpr>),
    OneOrMore(Box<PathExpr>),
    ZeroOrOne(Box<PathExpr>),
}

#[derive(Clone, Debug, PartialEq, Eq)]
pub struct RpqQuery {
    pub subject: Endpoint,
    pub path: PathExpr,
    pub object: Endpoint,
}

impl RpqQuery {
    /// Strip a base IRI prefix from all IRIs in this query.
    pub fn strip_base(&mut self, base: &str) {
        strip_endpoint(&mut self.subject, base);
        strip_endpoint(&mut self.object, base);
        strip_path(&mut self.path, base);
    }
}

fn strip_endpoint(ep: &mut Endpoint, base: &str) {
    if let Endpoint::Named(s) = ep
        && s.starts_with(base)
    {
        *s = s[base.len()..].to_owned();
    }
}

fn strip_path(path: &mut PathExpr, base: &str) {
    match path {
        PathExpr::Label(s) => {
            if s.starts_with(base) {
                *s = s[base.len()..].to_owned();
            }
        }
        PathExpr::Sequence(l, r) | PathExpr::Alternative(l, r) => {
            strip_path(l, base);
            strip_path(r, base);
        }
        PathExpr::ZeroOrMore(inner) | PathExpr::OneOrMore(inner) | PathExpr::ZeroOrOne(inner) => {
            strip_path(inner, base);
        }
    }
}

#[derive(Debug, Error)]
pub enum RpqError {
    #[error("SPARQL syntax error: {0}")]
    Parse(#[from] SparqlSyntaxError),

    #[error("query extraction error: {0}")]
    Extract(#[from] ExtractError),

    #[error("unsupported path expression: {0}")]
    UnsupportedPath(String),

    #[error("vertex not found in graph: '{0}'")]
    VertexNotFound(String),

    #[error("graph error: {0}")]
    Graph(#[from] GraphError),
}

pub trait RpqEvaluator: Evaluator<Query = RpqQuery, Error = RpqError> {
    fn prepare<G: GraphDecomposition>(
        &self,
        query: &RpqQuery,
        graph: &G,
    ) -> Result<Self::Prepared, RpqError> {
        <Self as Evaluator>::prepare(self, query, graph)
    }

    fn evaluate<G: GraphDecomposition>(
        &self,
        query: &RpqQuery,
        graph: &G,
    ) -> Result<Self::Result, RpqError> {
        <Self as Evaluator>::evaluate(self, query, graph)
    }
}
impl<T> RpqEvaluator for T where T: Evaluator<Query = RpqQuery, Error = RpqError> {}

pub trait PreparedRpq: PreparedEvaluator<Error = RpqError> {
    fn execute(&mut self) -> Result<Self::Result, RpqError> {
        <Self as PreparedEvaluator>::execute(self)
    }
}
impl<T> PreparedRpq for T where T: PreparedEvaluator<Error = RpqError> {}