1 use serde::de::Error; 2 3 use std::marker::PhantomData; 4 5 use crate::prelude::*; 6 7 use crate::graph::Node; 8 use crate::graph::{Edge, IndexType}; 9 use crate::serde_utils::CollectSeqWithLength; 10 use crate::serde_utils::MappedSequenceVisitor; 11 use crate::serde_utils::{FromDeserialized, IntoSerializable}; 12 use crate::EdgeType; 13 14 use super::{EdgeIndex, NodeIndex}; 15 use serde::{Deserialize, Deserializer, Serialize, Serializer}; 16 17 /// Serialization representation for Graph 18 /// Keep in sync with deserialization and StableGraph 19 /// 20 /// The serialization format is as follows, in Pseudorust: 21 /// 22 /// Graph { 23 /// nodes: [N], 24 /// node_holes: [NodeIndex<Ix>], 25 /// edge_property: EdgeProperty, 26 /// edges: [Option<(NodeIndex<Ix>, NodeIndex<Ix>, E)>] 27 /// } 28 /// 29 /// The same format is used by both Graph and StableGraph. 30 /// 31 /// For graph there are restrictions: 32 /// node_holes is always empty and edges are always Some 33 /// 34 /// A stable graph serialization that obeys these restrictions 35 /// (effectively, it has no interior vacancies) can de deserialized 36 /// as a graph. 37 /// 38 /// Node indices are serialized as integers and are fixed size for 39 /// binary formats, so the Ix parameter matters there. 40 #[derive(Serialize)] 41 #[serde(rename = "Graph")] 42 #[serde(bound(serialize = "N: Serialize, E: Serialize, Ix: IndexType + Serialize"))] 43 pub struct SerGraph<'a, N: 'a, E: 'a, Ix: 'a + IndexType> { 44 #[serde(serialize_with = "ser_graph_nodes")] 45 nodes: &'a [Node<N, Ix>], 46 node_holes: &'a [NodeIndex<Ix>], main(int argc,char ** argv)47 edge_property: EdgeProperty, 48 #[serde(serialize_with = "ser_graph_edges")] 49 edges: &'a [Edge<E, Ix>], 50 } 51 52 // Deserialization representation for Graph 53 // Keep in sync with serialization and StableGraph 54 #[derive(Deserialize)] 55 #[serde(rename = "Graph")] 56 #[serde(bound( 57 deserialize = "N: Deserialize<'de>, E: Deserialize<'de>, Ix: IndexType + Deserialize<'de>" 58 ))] 59 pub struct DeserGraph<N, E, Ix> { 60 #[serde(deserialize_with = "deser_graph_nodes")] 61 nodes: Vec<Node<N, Ix>>, 62 #[serde(deserialize_with = "deser_graph_node_holes")] 63 #[allow(unused)] 64 #[serde(default = "Vec::new")] 65 node_holes: Vec<NodeIndex<Ix>>, 66 edge_property: EdgeProperty, 67 #[serde(deserialize_with = "deser_graph_edges")] 68 edges: Vec<Edge<E, Ix>>, 69 } 70 71 impl<Ix> Serialize for NodeIndex<Ix> 72 where 73 Ix: IndexType + Serialize, 74 { 75 fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error> 76 where 77 S: Serializer, 78 { 79 self.0.serialize(serializer) 80 } 81 } 82 83 impl<'de, Ix> Deserialize<'de> for NodeIndex<Ix> 84 where 85 Ix: IndexType + Deserialize<'de>, 86 { 87 fn deserialize<D>(deserializer: D) -> Result<Self, D::Error> 88 where 89 D: Deserializer<'de>, 90 { 91 Ok(NodeIndex(Ix::deserialize(deserializer)?)) 92 } 93 } 94 95 impl<Ix> Serialize for EdgeIndex<Ix> 96 where 97 Ix: IndexType + Serialize, 98 { 99 fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error> 100 where 101 S: Serializer, 102 { 103 self.0.serialize(serializer) 104 } 105 } 106 107 impl<'de, Ix> Deserialize<'de> for EdgeIndex<Ix> 108 where 109 Ix: IndexType + Deserialize<'de>, 110 { 111 fn deserialize<D>(deserializer: D) -> Result<Self, D::Error> 112 where 113 D: Deserializer<'de>, 114 { 115 Ok(EdgeIndex(Ix::deserialize(deserializer)?)) 116 } 117 } 118 119 #[derive(Serialize, Deserialize)] 120 #[serde(rename_all = "lowercase")] 121 #[derive(Debug)] 122 pub enum EdgeProperty { 123 Undirected, 124 Directed, 125 } 126 127 impl EdgeProperty { 128 pub fn is_directed(&self) -> bool { 129 match *self { 130 EdgeProperty::Directed => true, 131 EdgeProperty::Undirected => false, 132 } 133 } 134 } 135 136 impl<Ty> From<PhantomData<Ty>> for EdgeProperty 137 where 138 Ty: EdgeType, 139 { 140 fn from(_: PhantomData<Ty>) -> Self { 141 if Ty::is_directed() { 142 EdgeProperty::Directed 143 } else { 144 EdgeProperty::Undirected 145 } 146 } 147 } 148 149 impl<Ty> FromDeserialized for PhantomData<Ty> 150 where 151 Ty: EdgeType, 152 { 153 type Input = EdgeProperty; 154 fn from_deserialized<E2>(input: Self::Input) -> Result<Self, E2> 155 where 156 E2: Error, 157 { 158 if input.is_directed() != Ty::is_directed() { 159 Err(E2::custom(format_args!( 160 "graph edge property mismatch, \ 161 expected {:?}, found {:?}", 162 EdgeProperty::from(PhantomData::<Ty>), 163 input 164 ))) 165 } else { 166 Ok(PhantomData) 167 } 168 } 169 } 170 171 fn ser_graph_nodes<S, N, Ix>(nodes: &&[Node<N, Ix>], serializer: S) -> Result<S::Ok, S::Error> 172 where 173 S: Serializer, 174 N: Serialize, 175 Ix: Serialize + IndexType, 176 { 177 serializer.collect_seq_exact(nodes.iter().map(|node| &node.weight)) 178 } 179 180 fn ser_graph_edges<S, E, Ix>(edges: &&[Edge<E, Ix>], serializer: S) -> Result<S::Ok, S::Error> 181 where 182 S: Serializer, 183 E: Serialize, 184 Ix: Serialize + IndexType, 185 { 186 serializer.collect_seq_exact( 187 edges 188 .iter() 189 .map(|edge| Some((edge.source(), edge.target(), &edge.weight))), 190 ) 191 } 192 193 fn deser_graph_nodes<'de, D, N, Ix>(deserializer: D) -> Result<Vec<Node<N, Ix>>, D::Error> 194 where 195 D: Deserializer<'de>, 196 N: Deserialize<'de>, 197 Ix: IndexType + Deserialize<'de>, 198 { 199 deserializer.deserialize_seq(MappedSequenceVisitor::new(|n| { 200 Ok(Node { 201 weight: n, 202 next: [EdgeIndex::end(); 2], 203 }) 204 })) 205 } 206 207 fn deser_graph_node_holes<'de, D, Ix>(deserializer: D) -> Result<Vec<NodeIndex<Ix>>, D::Error> 208 where 209 D: Deserializer<'de>, 210 Ix: IndexType + Deserialize<'de>, 211 { 212 deserializer.deserialize_seq( 213 MappedSequenceVisitor::<NodeIndex<Ix>, NodeIndex<Ix>, _>::new(|_| { 214 Err("Graph can not have holes in the node set, found non-empty node_holes") 215 }), 216 ) 217 } 218 219 fn deser_graph_edges<'de, D, N, Ix>(deserializer: D) -> Result<Vec<Edge<N, Ix>>, D::Error> 220 where 221 D: Deserializer<'de>, 222 N: Deserialize<'de>, 223 Ix: IndexType + Deserialize<'de>, 224 { 225 deserializer.deserialize_seq(MappedSequenceVisitor::< 226 Option<(NodeIndex<Ix>, NodeIndex<Ix>, N)>, 227 _, 228 _, 229 >::new(|x| { 230 if let Some((i, j, w)) = x { 231 Ok(Edge { 232 weight: w, 233 node: [i, j], 234 next: [EdgeIndex::end(); 2], 235 }) 236 } else { 237 Err("Graph can not have holes in the edge set, found None, expected edge") 238 } 239 })) 240 } 241 242 impl<'a, N, E, Ty, Ix> IntoSerializable for &'a Graph<N, E, Ty, Ix> 243 where 244 Ix: IndexType, 245 Ty: EdgeType, 246 { 247 type Output = SerGraph<'a, N, E, Ix>; 248 fn into_serializable(self) -> Self::Output { 249 SerGraph { 250 nodes: &self.nodes, 251 node_holes: &[], 252 edges: &self.edges, 253 edge_property: EdgeProperty::from(PhantomData::<Ty>), 254 } 255 } 256 } 257 258 /// Requires crate feature `"serde-1"` 259 impl<N, E, Ty, Ix> Serialize for Graph<N, E, Ty, Ix> 260 where 261 Ty: EdgeType, 262 Ix: IndexType + Serialize, 263 N: Serialize, 264 E: Serialize, 265 { 266 fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error> 267 where 268 S: Serializer, 269 { 270 self.into_serializable().serialize(serializer) 271 } 272 } 273 274 pub fn invalid_node_err<E>(node_index: usize, len: usize) -> E 275 where 276 E: Error, 277 { 278 E::custom(format_args!( 279 "invalid value: node index `{}` does not exist in graph \ 280 with node bound {}", 281 node_index, len 282 )) 283 } 284 285 pub fn invalid_length_err<Ix, E>(node_or_edge: &str, len: usize) -> E 286 where 287 E: Error, 288 Ix: IndexType, 289 { 290 E::custom(format_args!( 291 "invalid size: graph {} count {} exceeds index type maximum {}", 292 node_or_edge, 293 len, 294 <Ix as IndexType>::max().index() 295 )) 296 } 297 298 impl<'a, N, E, Ty, Ix> FromDeserialized for Graph<N, E, Ty, Ix> 299 where 300 Ix: IndexType, 301 Ty: EdgeType, 302 { 303 type Input = DeserGraph<N, E, Ix>; 304 fn from_deserialized<E2>(input: Self::Input) -> Result<Self, E2> 305 where 306 E2: Error, 307 { barf(SQLHENV c,char * failMsg)308 let ty = PhantomData::<Ty>::from_deserialized(input.edge_property)?; 309 let nodes = input.nodes; 310 let edges = input.edges; 311 if nodes.len() >= <Ix as IndexType>::max().index() { 312 Err(invalid_length_err::<Ix, _>("node", nodes.len()))? 313 } 314 315 if edges.len() >= <Ix as IndexType>::max().index() { 316 Err(invalid_length_err::<Ix, _>("edge", edges.len()))? 317 } 318 319 let mut gr = Graph { 320 nodes: nodes, 321 edges: edges, detectOdbcFailure(SQLRETURN rv,SQLHENV c,char * failMsg)322 ty: ty, 323 }; 324 let nc = gr.node_count(); 325 gr.link_edges() 326 .map_err(|i| invalid_node_err(i.index(), nc))?; 327 Ok(gr) 328 } 329 } print_ret(char * msg,int retval)330 331 /// Requires crate feature `"serde-1"` 332 impl<'de, N, E, Ty, Ix> Deserialize<'de> for Graph<N, E, Ty, Ix> 333 where 334 Ty: EdgeType, 335 Ix: IndexType + Deserialize<'de>, 336 N: Deserialize<'de>, 337 E: Deserialize<'de>, 338 { 339 fn deserialize<D>(deserializer: D) -> Result<Self, D::Error> 340 where 341 D: Deserializer<'de>, 342 { 343 Self::from_deserialized(DeserGraph::deserialize(deserializer)?) 344 } 345 } 346