graph_io_gml/
lib.rs

1use asexp::atom::Atom;
2use asexp::token::{Token, Tokenizer};
3use asexp::Sexp;
4use petgraph::graph::NodeIndex;
5use petgraph::{Directed, Graph};
6use std::collections::BTreeMap;
7
8pub fn parse_gml<NodeWeightFn, EdgeWeightFn, N, E>(
9    s: &str,
10    node_weight_fn: &NodeWeightFn,
11    edge_weight_fn: &EdgeWeightFn,
12) -> Result<Graph<N, E, Directed>, &'static str>
13where
14    NodeWeightFn: Fn(Option<&Sexp>) -> Option<N>,
15    EdgeWeightFn: Fn(Option<&Sexp>) -> Option<E>,
16{
17    match parse_gml_to_sexp(s) {
18        Ok(sexp) => sexp_to_graph(sexp, node_weight_fn, edge_weight_fn),
19        Err(_) => Err("Invalid GML"),
20    }
21}
22
23fn parse_gml_to_sexp(s: &str) -> Result<Sexp, ()> {
24    let iter = Tokenizer::new(s, true).with_curly_around();
25    let iter = iter.map(|t| match t {
26        Token::OpenBracket => Token::OpenCurly,
27        Token::CloseBracket => Token::CloseCurly,
28        a => a,
29    });
30
31    Sexp::parse_iter(iter)
32}
33
34fn sexp_to_graph<NodeWeightFn, EdgeWeightFn, N, E>(
35    sexp: Sexp,
36    node_weight_fn: &NodeWeightFn,
37    edge_weight_fn: &EdgeWeightFn,
38) -> Result<Graph<N, E, Directed>, &'static str>
39where
40    NodeWeightFn: Fn(Option<&Sexp>) -> Option<N>,
41    EdgeWeightFn: Fn(Option<&Sexp>) -> Option<E>,
42{
43    let mut map = sexp.into_map()?;
44
45    if let Some(Sexp::Map(v)) = map.remove("graph") {
46        let mut node_map: BTreeMap<u64, NodeIndex> = BTreeMap::new();
47        let mut graph = Graph::new();
48        let mut edges = Vec::new();
49
50        for (k, v) in v {
51            match k.get_str() {
52                Some("directed") => match v.get_uint() {
53                    Some(1) => {}
54                    _ => {
55                        return Err("only directed graph supported");
56                    }
57                },
58                Some("node") => {
59                    let node_info = v.into_map()?;
60                    if let Some(&Sexp::Atom(Atom::UInt(node_id))) = node_info.get("id") {
61                        match node_weight_fn(node_info.get("weight")) {
62                            Some(weight) => {
63                                let idx = graph.add_node(weight);
64                                if node_map.insert(node_id, idx).is_some() {
65                                    return Err("duplicate node-id");
66                                }
67                            }
68                            None => {
69                                return Err("invalid node weight");
70                            }
71                        }
72                    } else {
73                        return Err("Invalid id");
74                    }
75                }
76                Some("edge") => {
77                    let edge_info = v.into_map()?;
78
79                    let source =
80                        if let Some(&Sexp::Atom(Atom::UInt(source))) = edge_info.get("source") {
81                            source
82                        } else {
83                            return Err("Invalid source id");
84                        };
85
86                    let target =
87                        if let Some(&Sexp::Atom(Atom::UInt(target))) = edge_info.get("target") {
88                            target
89                        } else {
90                            return Err("Invalid target id");
91                        };
92
93                    match edge_weight_fn(edge_info.get("weight")) {
94                        Some(weight) => {
95                            edges.push((source, target, weight));
96                        }
97                        None => {
98                            return Err("invalid edge weight");
99                        }
100                    }
101                }
102                _ => {
103                    return Err("invalid item");
104                }
105            }
106        }
107
108        for (source, target, weight) in edges {
109            let source_idx = node_map[&source];
110            let target_idx = node_map[&target];
111            graph.add_edge(source_idx, target_idx, weight);
112        }
113
114        Ok(graph)
115    } else {
116        Err("no graph given or invalid")
117    }
118}
119
120#[test]
121fn test_parse_gml() {
122    let gml = "
123    # comment
124    graph
125    [
126        directed 1
127        node
128        [
129          id 1
130          \
131               weight 1.0
132        ]
133        node
134        [
135          id 2
136        ]
137        edge
138        \
139               [
140           source 1
141           target 2
142           weight 1.1000
143        ]
144        \
145               edge
146        [
147           source 2
148           target 1
149        ]
150    ]
151    ";
152
153    let g = parse_gml(
154        gml,
155        &|s| -> Option<f64> { Some(s.and_then(Sexp::get_float).unwrap_or(0.0)) },
156        &|_| -> Option<()> { Some(()) },
157    );
158    assert!(g.is_ok());
159    let g = g.unwrap();
160    assert_eq!(true, g.is_directed());
161    assert_eq!(
162        true,
163        g.find_edge(NodeIndex::new(0), NodeIndex::new(1)).is_some()
164    );
165    assert_eq!(
166        true,
167        g.find_edge(NodeIndex::new(1), NodeIndex::new(0)).is_some()
168    );
169    assert_eq!(Some(&1.0), g.node_weight(NodeIndex::new(0)));
170    assert_eq!(Some(&0.0), g.node_weight(NodeIndex::new(1)));
171}
graph_io_gml/lib.rs

graph_io_gml/
lib.rs
