causal_hub/io/gml/
parser.rs

1#![allow(missing_docs)]
2
3use std::collections::HashMap;
4
5use pest::{Parser, iterators::Pair};
6use pest_derive::Parser;
7
8use crate::types::{Error, Result, Set};
9
10/// A GML parser built on top of `pest`.
11///
12/// The parsed representation is graph-agnostic: it stores the graph direction
13/// (`graph_type`), the (sorted) vertex labels, and the list of directed edges
14/// as label pairs. Converting to a concrete graph type (`DiGraph` / `UnGraph`)
15/// validates the directionality.
16#[allow(missing_docs)]
17#[derive(Parser)]
18#[grammar = "src/io/gml/grammar.pest"]
19pub struct GMLParser;
20
21/// A graph-agnostic GML representation.
22#[derive(Clone, Debug, Default, PartialEq, Eq)]
23pub struct GML {
24    /// The graph direction (`"graph"` for undirected, `"digraph"` for directed).
25    pub graph_type: String,
26    /// The set of vertex labels (sorted).
27    pub vertices: Set<String>,
28    /// The list of directed edges as label pairs.
29    pub edges: Vec<(String, String)>,
30}
31
32impl GML {
33    /// Parse a GML string into the graph-agnostic representation.
34    ///
35    /// # Arguments
36    ///
37    /// * `string` - The GML content.
38    ///
39    /// # Returns
40    ///
41    /// The parsed [`GML`] representation.
42    ///
43    /// # Errors
44    ///
45    /// Returns an error if the string is not valid GML.
46    ///
47    pub fn from_string(string: &str) -> Result<Self> {
48        let mut pairs = GMLParser::parse(Rule::file, string.trim())
49            .map_err(|evidence| Error::Parsing(&evidence.to_string()))?;
50        let pair = pairs
51            .next()
52            .ok_or_else(|| Error::Parsing("empty GML document"))?;
53        Self::from_pair(pair)
54    }
55
56    /// Build a [`GML`] from a parsed `graph` pair.
57    fn from_pair(pair: Pair<Rule>) -> Result<Self> {
58        if pair.as_rule() != Rule::graph {
59            return Err(Error::Parsing("expected a GML graph"));
60        }
61
62        let mut inner = pair.into_inner();
63        let list = inner
64            .next()
65            .ok_or_else(|| Error::Parsing("missing graph list"))?;
66        if list.as_rule() != Rule::list {
67            return Err(Error::Parsing("expected a GML list"));
68        }
69
70        let mut graph_type = "graph".to_string();
71        let mut vertices_map: HashMap<usize, String> = HashMap::new();
72        let mut edges: Vec<(usize, usize)> = Vec::new();
73
74        for item in list.into_inner() {
75            if item.as_rule() != Rule::item {
76                return Err(Error::Parsing("expected a GML item"));
77            }
78            let mut inner = item.into_inner();
79            let key = inner
80                .next()
81                .ok_or_else(|| Error::Parsing("missing item key"))?;
82            if key.as_rule() != Rule::key {
83                return Err(Error::Parsing("expected a GML key"));
84            }
85            let value = inner
86                .next()
87                .ok_or_else(|| Error::Parsing("missing item value"))?;
88
89            match key.as_str() {
90                "directed" => {
91                    graph_type = "digraph".to_string();
92                }
93                "graphType" => {
94                    graph_type = value.as_str().trim_matches('"').to_string();
95                }
96                "node" => {
97                    if value.as_rule() != Rule::list {
98                        return Err(Error::Parsing("node must be a list"));
99                    }
100                    let mut id: Option<usize> = None;
101                    let mut label: Option<String> = None;
102                    for attr in value.into_inner() {
103                        if attr.as_rule() != Rule::item {
104                            continue;
105                        }
106                        let mut ai = attr.into_inner();
107                        let k = ai
108                            .next()
109                            .ok_or_else(|| Error::Parsing("missing attribute key"))?;
110                        let v = ai
111                            .next()
112                            .ok_or_else(|| Error::Parsing("missing attribute value"))?;
113                        match k.as_str() {
114                            "id" => {
115                                id = Some(
116                                    v.as_str()
117                                        .trim()
118                                        .parse()
119                                        .map_err(|_| Error::Parsing("invalid node id"))?,
120                                )
121                            }
122                            "label" => {
123                                label = Some(v.as_str().trim_matches('"').to_string());
124                            }
125                            _ => {}
126                        }
127                    }
128                    let id = id.ok_or_else(|| Error::Parsing("node without id"))?;
129                    let label = label.unwrap_or_else(|| id.to_string());
130                    vertices_map.insert(id, label);
131                }
132                "edge" => {
133                    if value.as_rule() != Rule::list {
134                        return Err(Error::Parsing("edge must be a list"));
135                    }
136                    let mut source: Option<usize> = None;
137                    let mut target: Option<usize> = None;
138                    for attr in value.into_inner() {
139                        if attr.as_rule() != Rule::item {
140                            continue;
141                        }
142                        let mut ai = attr.into_inner();
143                        let k = ai
144                            .next()
145                            .ok_or_else(|| Error::Parsing("missing attribute key"))?;
146                        let v = ai
147                            .next()
148                            .ok_or_else(|| Error::Parsing("missing attribute value"))?;
149                        match k.as_str() {
150                            "source" => {
151                                source = Some(
152                                    v.as_str()
153                                        .trim()
154                                        .parse()
155                                        .map_err(|_| Error::Parsing("invalid edge source"))?,
156                                )
157                            }
158                            "target" => {
159                                target = Some(
160                                    v.as_str()
161                                        .trim()
162                                        .parse()
163                                        .map_err(|_| Error::Parsing("invalid edge target"))?,
164                                )
165                            }
166                            _ => {}
167                        }
168                    }
169                    let source = source.ok_or_else(|| Error::Parsing("edge without source"))?;
170                    let target = target.ok_or_else(|| Error::Parsing("edge without target"))?;
171                    edges.push((source, target));
172                }
173                _ => {}
174            }
175        }
176
177        // Resolve edge endpoints to labels.
178        let edges: Vec<(String, String)> = edges
179            .into_iter()
180            .map(|(stats, t)| {
181                let stats = vertices_map
182                    .get(&stats)
183                    .cloned()
184                    .ok_or_else(|| Error::Parsing("edge references unknown node"))?;
185                let t = vertices_map
186                    .get(&t)
187                    .cloned()
188                    .ok_or_else(|| Error::Parsing("edge references unknown node"))?;
189                Ok((stats, t))
190            })
191            .collect::<Result<Vec<_>>>()?;
192
193        // Collect and sort the vertex labels for deterministic output.
194        let mut vlist: Vec<String> = vertices_map.into_values().collect();
195        vlist.sort();
196        let vertices: Set<String> = Set::from_iter(vlist);
197
198        Ok(Self {
199            graph_type,
200            vertices,
201            edges,
202        })
203    }
204}
205
206/// Serialize a [`GML`] representation into a GML string.
207pub(crate) fn serialize(gml: &GML) -> Result<String> {
208    let mut string = String::new();
209    string.push_str("graph [\n");
210
211    // Print directionality.
212    match gml.graph_type.as_ref() {
213        "digraph" => string.push_str("\tdirected 1\n"),
214        graph_type => string.push_str(&format!("\tgraphType \"{}\"\n", graph_type)),
215    }
216
217    // Print vertices (id is the sorted position).
218    for (id, label) in gml.vertices.iter().enumerate() {
219        string.push_str("\tnode [\n");
220        string.push_str(&format!("\t\tid {}\n", id));
221        string.push_str(&format!("\t\tlabel \"{}\"\n", label));
222        string.push_str("\t]\n");
223    }
224
225    // Print edges.
226    for (source, target) in &gml.edges {
227        let sid = gml
228            .vertices
229            .get_index_of(source)
230            .ok_or_else(|| Error::Parsing("edge references unknown node"))?;
231        let tid = gml
232            .vertices
233            .get_index_of(target)
234            .ok_or_else(|| Error::Parsing("edge references unknown node"))?;
235        string.push_str("\tedge [\n");
236        string.push_str(&format!("\t\tsource {}\n", sid));
237        string.push_str(&format!("\t\ttarget {}\n", tid));
238        string.push_str("\t]\n");
239    }
240
241    string.push_str("]\n");
242    Ok(string)
243}
244
245/// A trait for reading and writing GML files / strings.
246pub trait GmlIO: Sized {
247    /// Create an instance of the type from a GML string.
248    ///
249    /// # Arguments
250    ///
251    /// * `gml` - A string slice that holds the GML data.
252    ///
253    /// # Returns
254    ///
255    /// A new instance of the type.
256    ///
257    fn from_gml_string(gml: &str) -> Result<Self>;
258
259    /// Convert the instance to a GML string.
260    ///
261    /// # Returns
262    ///
263    /// A string that holds the GML data.
264    ///
265    fn to_gml_string(&self) -> Result<String>;
266
267    /// Read a GML file and create an instance of the type.
268    ///
269    /// # Arguments
270    ///
271    /// * `path` - A string slice that holds the path to the GML file.
272    ///
273    /// # Returns
274    ///
275    /// A new instance of the type.
276    ///
277    fn from_gml_file(path: &str) -> Result<Self>;
278
279    /// Write the instance to a GML file.
280    ///
281    /// # Arguments
282    ///
283    /// * `path` - A string slice that holds the path to the GML file.
284    ///
285    /// # Returns
286    ///
287    /// `Ok(())` if the write succeeds.
288    ///
289    fn to_gml_file(&self, path: &str) -> Result<()>;
290}
causal_hub/io/gml/parser.rs

causal_hub/io/gml/
parser.rs
