simple_graph/
tgf.rs

1use std::collections::HashMap;
2use std::fmt::{self, Debug, Display, Formatter};
3use std::hash::Hash;
4use std::str::FromStr;
5
6use super::{Graph, ParseGraphError, VertexId};
7
8/// Trait used for serialization and deserialization of the Trivial Graph Format
9pub trait Label: Ord + Hash + Clone + Default + Debug + FromStr + Display {}
10
11impl<T: Ord + Hash + Clone + Default + Debug + FromStr + Display> Label for T {}
12
13impl<V: Label, E: Label> Display for Graph<V, E> {
14    /// Formats graph as string in Trivial Graph Format
15    ///
16    /// ```
17    /// use simple_graph::Graph;
18    ///
19    /// let mut graph = Graph::<String, String>::new();
20    ///
21    /// let first_node_id = graph.add_vertex("First node".into()).unwrap();
22    /// let second_node_id = graph.add_vertex("Second node".into()).unwrap();
23    ///
24    /// graph.add_edge(first_node_id, second_node_id, "Edge between the two".into()).unwrap();
25    ///
26    /// let s = concat!(
27    ///     "1 First node\n",
28    ///     "2 Second node\n",
29    ///     "#\n",
30    ///     "1 2 Edge between the two\n",
31    /// );
32    /// assert_eq!(graph.to_string(), s);
33    /// ```
34    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
35        let mut vertices = HashMap::<VertexId, usize>::with_capacity(self.vertices_count());
36
37        for (n, (&vertex_id, _)) in (1_usize..).zip(self.vertices.iter()) {
38            if let Ok(vertex_data) = self.get_vertex(vertex_id) {
39                vertices.insert(vertex_id, n);
40                writeln!(f, "{n} {vertex_data}")?;
41            }
42        }
43
44        writeln!(f, "#")?;
45
46        for ([from, to], edge) in self.edges().expect("failed to get edges") {
47            let from_id = self.get_vertex_id(from);
48            let to_id = self.get_vertex_id(to);
49            if let Some((from, to)) = vertices.get(&from_id).zip(vertices.get(&to_id)) {
50                writeln!(f, "{from} {to} {edge}")?;
51            }
52        }
53
54        Ok(())
55    }
56}
57
58/// Trivial Graph Format has two types of definitions which is separated by `#` char
59#[derive(Ord, PartialOrd, Eq, PartialEq)]
60enum ParserMode {
61    /// `1 vertex label`, `<id: usize> <label: &str>`
62    VertexDefinitions,
63    /// `1 2 edge label`, `<from: usize> <to: usize> <label: &str>`
64    EdgeDefinitions,
65}
66
67fn parse_index(s: &str, line: usize) -> Result<usize, ParseGraphError> {
68    s.parse().map_err(|_| ParseGraphError::ParseInt(line))
69}
70
71fn parse_label<T: FromStr>(s: &str, line: usize) -> Result<T, ParseGraphError> {
72    s.parse::<T>()
73        .map_err(|_| ParseGraphError::ParseLabel(line))
74}
75
76impl<V: Label, E: Label> FromStr for Graph<V, E> {
77    type Err = ParseGraphError;
78
79    /// Parses [`crate::Graph<V, E>`] from [`&str`] in Trivial Graph Format
80    ///
81    /// ```
82    /// use simple_graph::{Graph, VertexId};
83    /// use std::str::FromStr;
84    ///
85    /// let s = concat!(
86    ///     "1 First node\n",
87    ///     "2 Second node\n",
88    ///     "#\n",
89    ///     "1 2 Edge between the two\n",
90    /// );
91    /// let mut graph = Graph::<String, String>::from_str(s).unwrap();
92    ///
93    /// let first_node_id = graph.get_vertex_id(&"First node".into());
94    /// let second_node_id = graph.get_vertex_id(&"Second node".into());
95    ///
96    /// let ([from, to], edge) = graph.get_edge(first_node_id, second_node_id).unwrap();
97    /// assert!(*from == first_node_id && *to == second_node_id && edge == "Edge between the two");
98    /// ```
99    fn from_str(s: &str) -> Result<Self, Self::Err> {
100        let mut graph = Self::new();
101        let mut vertices = HashMap::<usize, VertexId>::new();
102
103        let mut mode = ParserMode::VertexDefinitions;
104        for (n, line) in (1_usize..).zip(s.lines()) {
105            if line.starts_with('#') {
106                mode = ParserMode::EdgeDefinitions;
107                continue;
108            }
109
110            let mut it = line.split_whitespace();
111            match mode {
112                ParserMode::VertexDefinitions => {
113                    let s = it.next().ok_or(ParseGraphError::VertexDefinition(n))?;
114                    let index = parse_index(s, n)?;
115                    let label: V = parse_label(it.remainder().unwrap_or(""), n)?;
116
117                    let vertex_id = graph
118                        .add_vertex(label)
119                        .map_err(|err| ParseGraphError::GraphError(err, n))?;
120
121                    if vertices.insert(index, vertex_id).is_some() {
122                        return Err(ParseGraphError::VertexAlreadyDefined(index, n));
123                    }
124                }
125                ParserMode::EdgeDefinitions => {
126                    let (from, to) = it
127                        .next()
128                        .zip(it.next())
129                        .ok_or(ParseGraphError::EdgeDefinition(n))?;
130
131                    let from = parse_index(from, n)?;
132                    let to = parse_index(to, n)?;
133                    let label: E = parse_label(it.remainder().unwrap_or(""), n)?;
134
135                    let (&from, &to) = vertices
136                        .get(&from)
137                        .zip(vertices.get(&to))
138                        .ok_or(ParseGraphError::VerticesNotDefined(from, to, n))?;
139
140                    graph
141                        .add_edge(from, to, label)
142                        .map_err(|err| ParseGraphError::GraphError(err, n))?;
143                }
144            }
145        }
146
147        Ok(graph)
148    }
149}
simple_graph/tgf.rs

simple_graph/
tgf.rs
