petgraph/graph_impl/stable_graph/

serialization.rs

use serde::de::Error;
use serde::{Deserialize, Deserializer, Serialize, Serializer};

#[cfg(feature = "std")]
use std::marker::PhantomData;

#[cfg(not(feature = "std"))]
use core::marker::PhantomData;

#[cfg(not(feature = "std"))]
use alloc::vec::Vec;

use crate::prelude::*;

use crate::graph::Node;
use crate::graph::{Edge, IndexType};
use crate::serde_utils::CollectSeqWithLength;
use crate::serde_utils::MappedSequenceVisitor;
use crate::serde_utils::{FromDeserialized, IntoSerializable};
use crate::stable_graph::StableGraph;
use crate::util::rev;
use crate::visit::NodeIndexable;
use crate::EdgeType;

use super::super::serialization::{invalid_length_err, invalid_node_err, EdgeProperty};

// Serialization representation for StableGraph
// Keep in sync with deserialization and Graph
#[derive(Serialize)]
#[serde(rename = "Graph")]
#[serde(bound(serialize = "N: Serialize, E: Serialize, Ix: IndexType + Serialize"))]
pub struct SerStableGraph<'a, N: 'a, E: 'a, Ix: 'a + IndexType> {
    nodes: Somes<&'a [Node<Option<N>, Ix>]>,
    node_holes: Holes<&'a [Node<Option<N>, Ix>]>,
    edge_property: EdgeProperty,
    #[serde(serialize_with = "ser_stable_graph_edges")]
    edges: &'a [Edge<Option<E>, Ix>],
}

// Deserialization representation for StableGraph
// Keep in sync with serialization and Graph
#[derive(Deserialize)]
#[serde(rename = "Graph")]
#[serde(bound(
    deserialize = "N: Deserialize<'de>, E: Deserialize<'de>, Ix: IndexType + Deserialize<'de>"
))]
pub struct DeserStableGraph<N, E, Ix> {
    #[serde(deserialize_with = "deser_stable_graph_nodes")]
    nodes: Vec<Node<Option<N>, Ix>>,
    #[serde(default = "Vec::new")]
    node_holes: Vec<NodeIndex<Ix>>,
    edge_property: EdgeProperty,
    #[serde(deserialize_with = "deser_stable_graph_edges")]
    edges: Vec<Edge<Option<E>, Ix>>,
}

/// `Somes` are the present node weights N, with known length.
struct Somes<T>(usize, T);

impl<'a, N, Ix> Serialize for Somes<&'a [Node<Option<N>, Ix>]>
where
    N: Serialize,
{
    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
    where
        S: Serializer,
    {
        serializer.collect_seq_with_length(
            self.0,
            self.1.iter().filter_map(|node| node.weight.as_ref()),
        )
    }
}

/// Holes are the node indices of vacancies, with known length
struct Holes<T>(usize, T);

impl<'a, N, Ix> Serialize for Holes<&'a [Node<Option<N>, Ix>]>
where
    Ix: Serialize + IndexType,
{
    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
    where
        S: Serializer,
    {
        serializer.collect_seq_with_length(
            self.0,
            self.1.iter().enumerate().filter_map(|(i, node)| {
                if node.weight.is_none() {
                    Some(NodeIndex::<Ix>::new(i))
                } else {
                    None
                }
            }),
        )
    }
}

fn ser_stable_graph_edges<S, E, Ix>(
    edges: &&[Edge<Option<E>, Ix>],
    serializer: S,
) -> Result<S::Ok, S::Error>
where
    S: Serializer,
    E: Serialize,
    Ix: Serialize + IndexType,
{
    serializer.collect_seq_exact(edges.iter().map(|edge| {
        edge.weight
            .as_ref()
            .map(|w| (edge.source(), edge.target(), w))
    }))
}

fn deser_stable_graph_nodes<'de, D, N, Ix>(
    deserializer: D,
) -> Result<Vec<Node<Option<N>, Ix>>, D::Error>
where
    D: Deserializer<'de>,
    N: Deserialize<'de>,
    Ix: IndexType + Deserialize<'de>,
{
    deserializer.deserialize_seq(MappedSequenceVisitor::new(|n| {
        Ok(Node {
            weight: Some(n),
            next: [EdgeIndex::end(); 2],
        })
    }))
}

fn deser_stable_graph_edges<'de, D, N, Ix>(
    deserializer: D,
) -> Result<Vec<Edge<Option<N>, Ix>>, D::Error>
where
    D: Deserializer<'de>,
    N: Deserialize<'de>,
    Ix: IndexType + Deserialize<'de>,
{
    deserializer.deserialize_seq(MappedSequenceVisitor::<
        Option<(NodeIndex<Ix>, NodeIndex<Ix>, N)>,
        _,
        _,
    >::new(|x| {
        if let Some((i, j, w)) = x {
            Ok(Edge {
                weight: Some(w),
                node: [i, j],
                next: [EdgeIndex::end(); 2],
            })
        } else {
            Ok(Edge {
                weight: None,
                node: [NodeIndex::end(); 2],
                next: [EdgeIndex::end(); 2],
            })
        }
    }))
}

impl<'a, N, E, Ty, Ix> IntoSerializable for &'a StableGraph<N, E, Ty, Ix>
where
    Ix: IndexType,
    Ty: EdgeType,
{
    type Output = SerStableGraph<'a, N, E, Ix>;
    fn into_serializable(self) -> Self::Output {
        let nodes = &self.raw_nodes()[..self.node_bound()];
        let node_count = self.node_count();
        let hole_count = nodes.len() - node_count;
        let edges = &self.raw_edges()[..self.edge_bound()];
        SerStableGraph {
            nodes: Somes(node_count, nodes),
            node_holes: Holes(hole_count, nodes),
            edges: edges,
            edge_property: EdgeProperty::from(PhantomData::<Ty>),
        }
    }
}

/// Requires crate feature `"serde-1"`
impl<N, E, Ty, Ix> Serialize for StableGraph<N, E, Ty, Ix>
where
    Ty: EdgeType,
    Ix: IndexType + Serialize,
    N: Serialize,
    E: Serialize,
{
    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
    where
        S: Serializer,
    {
        self.into_serializable().serialize(serializer)
    }
}

impl<'a, N, E, Ty, Ix> FromDeserialized for StableGraph<N, E, Ty, Ix>
where
    Ix: IndexType,
    Ty: EdgeType,
{
    type Input = DeserStableGraph<N, E, Ix>;
    fn from_deserialized<E2>(input: Self::Input) -> Result<Self, E2>
    where
        E2: Error,
    {
        let ty = PhantomData::<Ty>::from_deserialized(input.edge_property)?;
        let mut nodes = input.nodes;
        let node_holes = input.node_holes;
        let edges = input.edges;
        if edges.len() >= <Ix as IndexType>::max().index() {
            Err(invalid_length_err::<Ix, _>("edge", edges.len()))?
        }

        // insert Nones for each hole
        let mut offset = node_holes.len();
        let node_bound = node_holes.len() + nodes.len();
        for hole_pos in rev(node_holes) {
            offset -= 1;
            if hole_pos.index() >= node_bound {
                Err(invalid_node_err(hole_pos.index(), node_bound))?;
            }
            let insert_pos = hole_pos.index() - offset;
            nodes.insert(
                insert_pos,
                Node {
                    weight: None,
                    next: [EdgeIndex::end(); 2],
                },
            );
        }

        if nodes.len() >= <Ix as IndexType>::max().index() {
            Err(invalid_length_err::<Ix, _>("node", nodes.len()))?
        }

        let node_bound = nodes.len();
        let mut sgr = StableGraph {
            g: Graph {
                nodes: nodes,
                edges: edges,
                ty: ty,
            },
            node_count: 0,
            edge_count: 0,
            free_edge: EdgeIndex::end(),
            free_node: NodeIndex::end(),
        };
        sgr.link_edges()
            .map_err(|i| invalid_node_err(i.index(), node_bound))?;
        Ok(sgr)
    }
}

/// Requires crate feature `"serde-1"`
impl<'de, N, E, Ty, Ix> Deserialize<'de> for StableGraph<N, E, Ty, Ix>
where
    Ty: EdgeType,
    Ix: IndexType + Deserialize<'de>,
    N: Deserialize<'de>,
    E: Deserialize<'de>,
{
    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
    where
        D: Deserializer<'de>,
    {
        Self::from_deserialized(DeserStableGraph::deserialize(deserializer)?)
    }
}

#[test]
fn test_from_deserialized_with_holes() {
    use crate::graph::node_index;
    use crate::stable_graph::StableUnGraph;
    use itertools::assert_equal;
    use serde::de::value::Error as SerdeError;

    let input = DeserStableGraph::<_, (), u32> {
        nodes: vec![
            Node {
                weight: Some(1),
                next: [EdgeIndex::end(); 2],
            },
            Node {
                weight: Some(4),
                next: [EdgeIndex::end(); 2],
            },
            Node {
                weight: Some(5),
                next: [EdgeIndex::end(); 2],
            },
        ],
        node_holes: vec![node_index(0), node_index(2), node_index(3), node_index(6)],
        edges: vec![],
        edge_property: EdgeProperty::Undirected,
    };
    let graph = StableUnGraph::from_deserialized::<SerdeError>(input).unwrap();

    assert_eq!(graph.node_count(), 3);
    assert_equal(
        graph.raw_nodes().iter().map(|n| n.weight.as_ref().cloned()),
        vec![None, Some(1), None, None, Some(4), Some(5), None],
    );
}