petgraph/graph_impl/stable_graph/
serialization.rs

1use serde::de::Error;
2use serde::{Deserialize, Deserializer, Serialize, Serializer};
3
4use std::marker::PhantomData;
5
6use crate::prelude::*;
7
8use crate::graph::Node;
9use crate::graph::{Edge, IndexType};
10use crate::serde_utils::CollectSeqWithLength;
11use crate::serde_utils::MappedSequenceVisitor;
12use crate::serde_utils::{FromDeserialized, IntoSerializable};
13use crate::stable_graph::StableGraph;
14use crate::visit::{EdgeIndexable, NodeIndexable};
15use crate::EdgeType;
16
17use super::super::serialization::{
18    invalid_hole_err, invalid_length_err, invalid_node_err, EdgeProperty,
19};
20
21// Serialization representation for StableGraph
22// Keep in sync with deserialization and Graph
23#[derive(Serialize)]
24#[serde(rename = "Graph")]
25#[serde(bound(serialize = "N: Serialize, E: Serialize, Ix: IndexType + Serialize"))]
26pub struct SerStableGraph<'a, N: 'a, E: 'a, Ix: 'a + IndexType> {
27    nodes: Somes<&'a [Node<Option<N>, Ix>]>,
28    node_holes: Holes<&'a [Node<Option<N>, Ix>]>,
29    edge_property: EdgeProperty,
30    #[serde(serialize_with = "ser_stable_graph_edges")]
31    edges: &'a [Edge<Option<E>, Ix>],
32}
33
34// Deserialization representation for StableGraph
35// Keep in sync with serialization and Graph
36#[derive(Deserialize)]
37#[serde(rename = "Graph")]
38#[serde(bound(
39    deserialize = "N: Deserialize<'de>, E: Deserialize<'de>, Ix: IndexType + Deserialize<'de>"
40))]
41pub struct DeserStableGraph<N, E, Ix> {
42    #[serde(deserialize_with = "deser_stable_graph_nodes")]
43    nodes: Vec<Node<Option<N>, Ix>>,
44    #[serde(default = "Vec::new")]
45    node_holes: Vec<NodeIndex<Ix>>,
46    edge_property: EdgeProperty,
47    #[serde(deserialize_with = "deser_stable_graph_edges")]
48    edges: Vec<Edge<Option<E>, Ix>>,
49}
50
51/// `Somes` are the present node weights N, with known length.
52struct Somes<T>(usize, T);
53
54impl<'a, N, Ix> Serialize for Somes<&'a [Node<Option<N>, Ix>]>
55where
56    N: Serialize,
57{
58    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
59    where
60        S: Serializer,
61    {
62        serializer.collect_seq_with_length(
63            self.0,
64            self.1.iter().filter_map(|node| node.weight.as_ref()),
65        )
66    }
67}
68
69/// Holes are the node indices of vacancies, with known length
70struct Holes<T>(usize, T);
71
72impl<'a, N, Ix> Serialize for Holes<&'a [Node<Option<N>, Ix>]>
73where
74    Ix: Serialize + IndexType,
75{
76    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
77    where
78        S: Serializer,
79    {
80        serializer.collect_seq_with_length(
81            self.0,
82            self.1.iter().enumerate().filter_map(|(i, node)| {
83                if node.weight.is_none() {
84                    Some(NodeIndex::<Ix>::new(i))
85                } else {
86                    None
87                }
88            }),
89        )
90    }
91}
92
93fn ser_stable_graph_edges<S, E, Ix>(
94    edges: &&[Edge<Option<E>, Ix>],
95    serializer: S,
96) -> Result<S::Ok, S::Error>
97where
98    S: Serializer,
99    E: Serialize,
100    Ix: Serialize + IndexType,
101{
102    serializer.collect_seq_exact(edges.iter().map(|edge| {
103        edge.weight
104            .as_ref()
105            .map(|w| (edge.source(), edge.target(), w))
106    }))
107}
108
109fn deser_stable_graph_nodes<'de, D, N, Ix>(
110    deserializer: D,
111) -> Result<Vec<Node<Option<N>, Ix>>, D::Error>
112where
113    D: Deserializer<'de>,
114    N: Deserialize<'de>,
115    Ix: IndexType + Deserialize<'de>,
116{
117    deserializer.deserialize_seq(MappedSequenceVisitor::new(|n| {
118        Ok(Node {
119            weight: Some(n),
120            next: [EdgeIndex::end(); 2],
121        })
122    }))
123}
124
125fn deser_stable_graph_edges<'de, D, N, Ix>(
126    deserializer: D,
127) -> Result<Vec<Edge<Option<N>, Ix>>, D::Error>
128where
129    D: Deserializer<'de>,
130    N: Deserialize<'de>,
131    Ix: IndexType + Deserialize<'de>,
132{
133    deserializer.deserialize_seq(MappedSequenceVisitor::<
134        Option<(NodeIndex<Ix>, NodeIndex<Ix>, N)>,
135        _,
136        _,
137    >::new(|x| {
138        if let Some((i, j, w)) = x {
139            Ok(Edge {
140                weight: Some(w),
141                node: [i, j],
142                next: [EdgeIndex::end(); 2],
143            })
144        } else {
145            Ok(Edge {
146                weight: None,
147                node: [NodeIndex::end(); 2],
148                next: [EdgeIndex::end(); 2],
149            })
150        }
151    }))
152}
153
154impl<'a, N, E, Ty, Ix> IntoSerializable for &'a StableGraph<N, E, Ty, Ix>
155where
156    Ix: IndexType,
157    Ty: EdgeType,
158{
159    type Output = SerStableGraph<'a, N, E, Ix>;
160    fn into_serializable(self) -> Self::Output {
161        let nodes = &self.raw_nodes()[..self.node_bound()];
162        let node_count = self.node_count();
163        let hole_count = nodes.len() - node_count;
164        let edges = &self.raw_edges()[..self.edge_bound()];
165        SerStableGraph {
166            nodes: Somes(node_count, nodes),
167            node_holes: Holes(hole_count, nodes),
168            edges: edges,
169            edge_property: EdgeProperty::from(PhantomData::<Ty>),
170        }
171    }
172}
173
174/// Requires crate feature `"serde-1"`
175impl<N, E, Ty, Ix> Serialize for StableGraph<N, E, Ty, Ix>
176where
177    Ty: EdgeType,
178    Ix: IndexType + Serialize,
179    N: Serialize,
180    E: Serialize,
181{
182    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
183    where
184        S: Serializer,
185    {
186        self.into_serializable().serialize(serializer)
187    }
188}
189
190impl<'a, N, E, Ty, Ix> FromDeserialized for StableGraph<N, E, Ty, Ix>
191where
192    Ix: IndexType,
193    Ty: EdgeType,
194{
195    type Input = DeserStableGraph<N, E, Ix>;
196    fn from_deserialized<E2>(input: Self::Input) -> Result<Self, E2>
197    where
198        E2: Error,
199    {
200        let ty = PhantomData::<Ty>::from_deserialized(input.edge_property)?;
201        let node_holes = input.node_holes;
202        let edges = input.edges;
203        if edges.len() >= <Ix as IndexType>::max().index() {
204            Err(invalid_length_err::<Ix, _>("edge", edges.len()))?
205        }
206
207        let total_nodes = input.nodes.len() + node_holes.len();
208        let mut nodes = Vec::with_capacity(total_nodes);
209
210        let mut compact_nodes = input.nodes.into_iter();
211        let mut node_pos = 0;
212        for hole_pos in node_holes.iter() {
213            let hole_pos = hole_pos.index();
214            if !(node_pos..total_nodes).contains(&hole_pos) {
215                return Err(invalid_hole_err(hole_pos));
216            }
217            nodes.extend(compact_nodes.by_ref().take(hole_pos - node_pos));
218            nodes.push(Node {
219                weight: None,
220                next: [EdgeIndex::end(); 2],
221            });
222            node_pos = hole_pos + 1;
223            debug_assert_eq!(nodes.len(), node_pos);
224        }
225        nodes.extend(compact_nodes);
226
227        if nodes.len() >= <Ix as IndexType>::max().index() {
228            Err(invalid_length_err::<Ix, _>("node", nodes.len()))?
229        }
230
231        let node_bound = nodes.len();
232        let mut sgr = StableGraph {
233            g: Graph {
234                nodes: nodes,
235                edges: edges,
236                ty: ty,
237            },
238            node_count: 0,
239            edge_count: 0,
240            free_edge: EdgeIndex::end(),
241            free_node: NodeIndex::end(),
242        };
243        sgr.link_edges()
244            .map_err(|i| invalid_node_err(i.index(), node_bound))?;
245        Ok(sgr)
246    }
247}
248
249/// Requires crate feature `"serde-1"`
250impl<'de, N, E, Ty, Ix> Deserialize<'de> for StableGraph<N, E, Ty, Ix>
251where
252    Ty: EdgeType,
253    Ix: IndexType + Deserialize<'de>,
254    N: Deserialize<'de>,
255    E: Deserialize<'de>,
256{
257    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
258    where
259        D: Deserializer<'de>,
260    {
261        Self::from_deserialized(DeserStableGraph::deserialize(deserializer)?)
262    }
263}
264
265#[test]
266fn test_from_deserialized_with_holes() {
267    use crate::graph::node_index;
268    use crate::stable_graph::StableUnGraph;
269    use itertools::assert_equal;
270    use serde::de::value::Error as SerdeError;
271
272    let input = DeserStableGraph::<_, (), u32> {
273        nodes: vec![
274            Node {
275                weight: Some(1),
276                next: [EdgeIndex::end(); 2],
277            },
278            Node {
279                weight: Some(4),
280                next: [EdgeIndex::end(); 2],
281            },
282            Node {
283                weight: Some(5),
284                next: [EdgeIndex::end(); 2],
285            },
286        ],
287        node_holes: vec![node_index(0), node_index(2), node_index(3), node_index(6)],
288        edges: vec![],
289        edge_property: EdgeProperty::Undirected,
290    };
291    let graph = StableUnGraph::from_deserialized::<SerdeError>(input).unwrap();
292
293    assert_eq!(graph.node_count(), 3);
294    assert_equal(
295        graph.raw_nodes().iter().map(|n| n.weight.as_ref().cloned()),
296        vec![None, Some(1), None, None, Some(4), Some(5), None],
297    );
298}
petgraph/graph_impl/stable_graph/serialization.rs

petgraph/graph_impl/stable_graph/
serialization.rs
