portgraph 0.16.1

//! Main definition of the port graph data structure.
//!
//! This module defines the [`PortGraph`] data structure and its associated
//! types. The port graph is a directed graph where each node has a pre-set
//! number of input and output ports, split between [`Direction::Incoming`] and
//! [`Direction::Outgoing`] . Each node has a global [`NodeIndex`] identifier
//! and each port has a global [`PortIndex`] identifier in addition to a local
//! port direction and offset.
//!
//! The number of ports of a node is set at creation time, but can be modified
//! at runtime using [`PortGraph::set_num_ports`].

mod iter;
mod node_entry;
mod port_entry;

use delegate::delegate;
use std::marker::PhantomData;
use std::mem::take;
use std::ops::Range;
use thiserror::Error;

use crate::index::{IndexBase, MaybeNodeIndex, MaybePortIndex};
use crate::view::{LinkMut, PortMut};
use crate::{Direction, LinkView, NodeIndex, PortIndex, PortOffset, PortView};
use node_entry::{FreeNodeEntry, NodeEntry, NodeMeta};
use port_entry::{PortEntry, PortMeta};

#[cfg(feature = "pyo3")]
use pyo3::prelude::*;

#[cfg(feature = "serde")]
use serde::{Deserialize, Serialize};

pub use crate::portgraph::iter::{
    Neighbours, NodeConnections, NodeLinks, NodePortOffsets, NodePorts, Nodes, Ports,
};

/// An unlabelled port graph.
///
/// A port graph consists of a collection of nodes identified by a [`NodeIndex`].
/// Each node has an ordered sequence of input and output ports, identified by a [`PortIndex`] that is unique within the graph.
/// To optimize for the most common use case, the number of input and output ports of a node must be specified when the node is created.
///
/// When a node and its associated ports are removed their indices will be reused on a best effort basis
/// when a new node is added.
/// The indices of unaffected nodes and ports remain stable.
/// [`PortGraph::compact_nodes`] and [`PortGraph::compact_ports`] to eliminate fragmentation in the index space.
///
/// # Generic parameters
/// - `N`: The unsigned integer type used for node indices.
/// - `P`: The unsigned integer type used for port indices.
/// - `PO`: The unsigned integer type used for port offsets.
#[cfg_attr(feature = "serde", derive(Deserialize, Serialize))]
#[derive(Clone, PartialEq)]
pub struct PortGraph<N: IndexBase = u32, P: IndexBase = u32, PO: IndexBase = u16> {
    /// Metadata for each node. Free slots form a linked list.
    node_meta: Vec<NodeEntry<N, P, PO>>,
    /// Links from ports to other ports. Free ports slabs (fixed-length lists of
    /// ports) form a linked list, with the next slab index stored in the first
    /// port.
    port_link: Vec<MaybePortIndex<P>>,
    /// Metadata for each port. Ports of a node are stored contiguously, with
    /// incoming ports first.
    port_meta: Vec<PortEntry<N>>,
    /// Index of the first free node slot in the free-node linked list embedded
    /// in `node_meta`.
    node_free: MaybeNodeIndex<N>,
    /// List of free slabs of ports. Each i-th item is the index of the first
    /// slab of size `i+1` in the free-port linked list embedded in `port_link`.
    port_free: Vec<MaybePortIndex<P>>,
    /// Number of nodes in the graph.
    node_count: usize,
    /// Number of ports in the graph.
    port_count: usize,
    /// Number of links in the graph.
    link_count: usize,
    /// Marker type for the port offset base type.
    _marker: PhantomData<PO>,
}

#[doc(hidden)]
#[cfg_attr(feature = "pyo3", pyclass(name = "PortGraph"))]
pub struct PyPortGraph(pub PortGraph<u32, u32, u16>);

impl<N: IndexBase, P: IndexBase, PO: IndexBase> PortGraph<N, P, PO> {
    /// Create a new empty [`PortGraph`].
    pub fn new() -> Self {
        Self {
            node_meta: Vec::new(),
            port_link: Vec::new(),
            port_meta: Vec::new(),
            node_free: None.into(),
            port_free: Vec::new(),
            node_count: 0,
            port_count: 0,
            link_count: 0,
            _marker: PhantomData,
        }
    }

    /// Create a new empty [`PortGraph`] with preallocated capacity.
    pub fn with_capacity(nodes: usize, ports: usize) -> Self {
        Self {
            node_meta: Vec::with_capacity(nodes),
            port_link: Vec::with_capacity(ports),
            port_meta: Vec::with_capacity(ports),
            node_free: None.into(),
            port_free: Vec::new(),
            node_count: 0,
            port_count: 0,
            link_count: 0,
            _marker: PhantomData,
        }
    }
}

impl<N: IndexBase, P: IndexBase, PO: IndexBase> PortGraph<N, P, PO> {
    #[inline]
    fn alloc_node(&mut self) -> NodeIndex<N> {
        match self.node_free.to_option() {
            Some(node) => {
                let free_entry = self.node_meta[node.index()].free_entry().unwrap();
                self.node_free = free_entry.next;
                if let Some(next) = free_entry.next.to_option() {
                    let next_entry = self.node_meta[next.index()].free_entry_mut().unwrap();
                    next_entry.prev = None.into();
                }
                node
            }
            None => {
                let index = self.node_meta.len();
                self.node_meta.push(NodeEntry::new_free(None, None));
                NodeIndex::new(index)
            }
        }
    }

    /// Allocates a slab of ports. Returns the index of the first port, and the
    /// number of ports in the slab.
    #[inline]
    fn alloc_ports(
        &mut self,
        node: NodeIndex<N>,
        incoming: usize,
        outgoing: usize,
        extra_capacity: usize,
    ) -> NodeMeta<P, PO> {
        let requested = incoming + outgoing + extra_capacity;
        if requested == 0 {
            return NodeMeta::default();
        }

        let meta_incoming = PortEntry::new(node, Direction::Incoming);
        let meta_outgoing = PortEntry::new(node, Direction::Outgoing);
        let meta_empty = PortEntry::new_free();
        match self
            .port_free
            .get(requested - 1)
            .and_then(|maybe_port| maybe_port.to_option())
        {
            Some(port) => {
                // TODO: Over-allocate if there are similarly-sized free slabs.
                let capacity = requested;

                let free_next = take(&mut self.port_link[port.index()]);
                self.port_free[requested - 1] = free_next;

                let node_meta = NodeMeta::try_new(
                    port,
                    PO::from_usize(incoming).expect("incoming port count exceeds maximum"),
                    PO::from_usize(outgoing).expect("outgoing port count exceeds maximum"),
                    PO::from_usize(capacity).expect("port capacity exceeds maximum"),
                )
                .unwrap_or_else(|e| panic!("Failed to allocate port: {e}"));
                self.port_meta[node_meta.incoming_ports()].fill(meta_incoming);
                self.port_meta[node_meta.outgoing_ports()].fill(meta_outgoing);
                self.port_meta[node_meta.unused_ports()].fill(meta_empty);

                self.port_link[port.index()..port.index() + capacity].fill(None.into());

                node_meta
            }
            None => {
                debug_assert_eq!(self.port_meta.len(), self.port_link.len());
                let old_len = self.port_meta.len();
                let port = PortIndex::new(old_len);
                let capacity = requested;

                self.port_meta.reserve(requested);
                self.port_meta.resize(old_len + incoming, meta_incoming);
                self.port_meta
                    .resize(old_len + incoming + outgoing, meta_outgoing);
                self.port_meta.resize(old_len + capacity, meta_empty);

                self.port_link.resize(old_len + capacity, None.into());

                NodeMeta::try_new(
                    port,
                    PO::from_usize(incoming).expect("incoming port count exceeds maximum"),
                    PO::from_usize(outgoing).expect("outgoing port count exceeds maximum"),
                    PO::from_usize(capacity).expect("port capacity exceeds maximum"),
                )
                .unwrap_or_else(|e| panic!("Failed to allocate port: {e}"))
            }
        }
    }

    #[inline]
    fn free_node(&mut self, node: NodeIndex<N>) {
        if let Some(node_free) = self.node_free.to_option() {
            let free_list = self.node_meta[node_free.index()].free_entry_mut().unwrap();
            free_list.prev = node.into();
        }
        self.node_meta[node.index()] = NodeEntry::new_free(None, self.node_free);
        self.node_free = node.into();
    }

    /// Free a slab of ports.
    ///
    /// Disconnects all links and adds the slab to the free port list.
    #[inline]
    fn free_ports(&mut self, ports: PortIndex<P>, size: usize) {
        if size > self.port_free.len() {
            self.port_free.resize(size, None.into());
        }
        if size == 0 {
            return;
        }

        let ports_free = &mut self.port_free[size - 1];

        for i in ports.index()..ports.index() + size {
            self.port_meta[i] = PortEntry::new_free();

            if let Some(link) = self.port_link[i].take().to_option() {
                self.port_link[link.index()] = None.into();
                self.link_count -= 1;
            }
        }

        // Add this slab to the free list.
        self.port_link[ports.index()] = ports_free.replace(ports);
    }

    #[inline]
    fn node_meta_valid(&self, node: NodeIndex<N>) -> Option<NodeMeta<P, PO>> {
        match self.node_meta.get(node.index()) {
            Some(NodeEntry::Node(node_meta)) => Some(*node_meta),
            _ => None,
        }
    }

    #[inline]
    #[must_use]
    fn port_meta_valid(&self, port: PortIndex<P>) -> Option<PortMeta<N>> {
        self.port_meta.get(port.index()).and_then(|pm| pm.as_meta())
    }

    /// Change the number of incoming and outgoing ports of a node, without
    /// altering the total.
    ///
    /// This operation avoids changing the number of incoming and outgoing ports
    /// without reallocating, but requires maintaining the total number of
    /// ports.
    ///
    /// Every time a port is moved, the `rekey` function will be called with its old and new index.
    /// If the port is removed, the new index will be `None`.
    ///
    /// # Panics
    ///
    /// If `incoming + outgoing` is more than the allocated port capacity.
    fn resize_ports_inplace<F>(
        &mut self,
        node: NodeIndex<N>,
        incoming: usize,
        outgoing: usize,
        mut rekey: F,
    ) where
        F: FnMut(PortIndex<P>, PortOperation<P>),
    {
        let node_meta = self.node_meta_valid(node).expect("Node must be valid");
        let new_meta = NodeMeta::try_new(
            node_meta.first_port(),
            PO::from_usize(incoming).expect("incoming port count exceeds maximum"),
            PO::from_usize(outgoing).expect("outgoing port count exceeds maximum"),
            PO::from_usize(node_meta.capacity()).expect("port capacity exceeds maximum"),
        )
        .unwrap_or_else(|e| panic!("Failed to allocate port: {e}"));

        // Disconnect any port to be removed.
        for port in self
            ._inputs(node)
            .skip(incoming)
            .chain(self._outputs(node).skip(outgoing))
        {
            let old_link = self.unlink_port(port);
            rekey(port, PortOperation::Removed { old_link });
        }

        let move_port = |(old, new)| {
            let old_index = PortIndex::new(old);
            let new_index = PortIndex::new(new);
            self.port_link[new] = self.port_link[old];
            self.port_meta[new] = self.port_meta[old];
            rekey(old_index, PortOperation::Moved { new_index });
            if let Some(link) = self.port_link[new].to_option() {
                self.port_link[link.index()] = new_index.into();
            }
        };

        // Choose whether to move the ports starting from the first or from the
        // last depending on the shift direction, to avoid overwriting valid
        // data.
        let pairs = node_meta.outgoing_ports().zip(new_meta.outgoing_ports());
        if node_meta.incoming() > incoming {
            pairs.for_each(move_port);
        } else {
            pairs.rev().for_each(move_port);
        };

        // Initialize the new ports
        for dir in Direction::BOTH {
            let existing = node_meta.num_ports(dir);
            for port in new_meta.ports(dir).skip(existing) {
                self.port_link[port] = None.into();
                self.port_meta[port] = PortEntry::new(node, dir);
            }
        }
        // Empty ports that are no longer used.
        for port_offset in new_meta.port_count()..node_meta.port_count() {
            let port = new_meta.first_port().index() + port_offset;
            self.port_link[port] = None.into();
            self.port_meta[port] = PortEntry::new_free();
        }

        self.node_meta[node.index()] = NodeEntry::Node(new_meta);

        self.port_count -= node_meta.incoming() + node_meta.outgoing();
        self.port_count += incoming + outgoing;
    }

    /// Returns the range of outgoing port indices for a given node.
    pub(crate) fn node_outgoing_ports(&self, node: NodeIndex<N>) -> Range<usize> {
        match self.node_meta_valid(node) {
            Some(node_meta) => node_meta.outgoing_ports(),
            None => 0..0,
        }
    }
}

impl<N: IndexBase, P: IndexBase, PO: IndexBase> PortView for PortGraph<N, P, PO> {
    type NodeIndexBase = N;
    type PortIndexBase = P;
    type PortOffsetBase = PO;

    #[inline]
    fn port_direction(&self, port: impl Into<PortIndex<P>>) -> Option<Direction> {
        self.port_meta_valid(port.into()).map(|pm| pm.direction)
    }

    #[inline]
    fn port_node(&self, port: impl Into<PortIndex<P>>) -> Option<NodeIndex<N>> {
        self.port_meta_valid(port.into()).map(|pm| pm.node)
    }

    fn port_offset(&self, port: impl Into<PortIndex<P>>) -> Option<PortOffset<PO>> {
        let port = port.into();
        let port_meta = self.port_meta_valid(port)?;

        let NodeEntry::Node(node_meta) = self.node_meta[port_meta.node.index()] else {
            unreachable!("ports are only attached to valid nodes");
        };

        let port_offset = port.index().wrapping_sub(node_meta.first_port().index());

        match port_meta.direction {
            Direction::Incoming => Some(PortOffset::new_incoming(port_offset)),
            Direction::Outgoing => {
                let port_offset = port_offset.saturating_sub(node_meta.incoming());
                Some(PortOffset::new_outgoing(port_offset))
            }
        }
    }

    fn port_index(&self, node: NodeIndex<N>, offset: PortOffset<PO>) -> Option<PortIndex<P>> {
        let node_meta = self.node_meta_valid(node)?;
        let direction = offset.direction();
        let offset = offset.index();
        node_meta.ports(direction).nth(offset).map(PortIndex::new)
    }

    #[inline]
    fn input(&self, node: NodeIndex<N>, offset: usize) -> Option<PortIndex<P>> {
        self.port_index(node, PortOffset::new_incoming(offset))
    }

    #[inline]
    fn output(&self, node: NodeIndex<N>, offset: usize) -> Option<PortIndex<P>> {
        self.port_index(node, PortOffset::new_outgoing(offset))
    }

    fn num_ports(&self, node: NodeIndex<N>, direction: Direction) -> usize {
        let Some(node_meta) = self.node_meta_valid(node) else {
            return 0;
        };
        if Direction::Incoming == direction {
            node_meta.incoming()
        } else {
            node_meta.outgoing()
        }
    }

    #[inline]
    fn contains_node(&self, node: NodeIndex<N>) -> bool {
        self.node_meta_valid(node).is_some()
    }

    #[inline]
    fn contains_port(&self, port: PortIndex<P>) -> bool {
        self.port_meta_valid(port).is_some()
    }

    #[inline]
    fn is_empty(&self) -> bool {
        self.node_count == 0 && self.port_count == 0
    }

    #[inline]
    fn node_count(&self) -> usize {
        self.node_count
    }

    #[inline]
    fn port_count(&self) -> usize {
        self.port_count
    }

    #[inline]
    fn node_capacity(&self) -> usize {
        self.node_meta.capacity()
    }

    #[inline]
    fn port_capacity(&self) -> usize {
        self.port_meta.capacity()
    }

    #[inline]
    fn node_port_capacity(&self, node: NodeIndex<N>) -> usize {
        self.node_meta_valid(node)
            .map_or(0, |node_meta| node_meta.capacity())
    }
    delegate! {
        to self {
            #[call(_ports)]
            fn ports(&self, node: NodeIndex<N>, direction: Direction) -> impl Iterator<Item = PortIndex<P>> + Clone;
            #[call(_all_ports)]
            fn all_ports(&self, node: NodeIndex<N>) -> impl Iterator<Item = PortIndex<P>> + Clone;
            #[call(_port_offsets)]
            fn port_offsets(&self, node: NodeIndex<N>, direction: Direction) -> impl Iterator<Item = PortOffset<PO>> + Clone;
            #[call(_all_port_offsets)]
            fn all_port_offsets(&self, node: NodeIndex<N>) -> impl Iterator<Item = PortOffset<PO>> + Clone;
            #[call(_nodes_iter)]
            fn nodes_iter(&self) -> impl Iterator<Item = NodeIndex<N>> + Clone;
            #[call(_ports_iter)]
            fn ports_iter(&self) -> impl Iterator<Item = PortIndex<P>> + Clone;
        }
    }
}

impl<N: IndexBase, P: IndexBase, PO: IndexBase> PortMut for PortGraph<N, P, PO> {
    fn add_node(&mut self, incoming: usize, outgoing: usize) -> NodeIndex<N> {
        assert!(
            incoming <= PortOffset::<PO>::max_offset(),
            "Incoming port count exceeds maximum."
        );
        assert!(
            outgoing <= PortOffset::<PO>::max_offset(),
            "Outgoing port count exceeds maximum."
        );

        let node = self.alloc_node();
        let node_meta = self.alloc_ports(node, incoming, outgoing, 0);
        self.node_meta[node.index()] = NodeEntry::Node(node_meta);

        self.node_count += 1;
        self.port_count += incoming + outgoing;

        node
    }

    fn remove_node(&mut self, node: NodeIndex<N>) {
        let Some(node_meta) = self.node_meta.get(node.index()).copied() else {
            return;
        };

        let NodeEntry::Node(node_meta) = node_meta else {
            return;
        };

        self.free_node(node);

        self.node_count -= 1;

        if node_meta.capacity() > 0 {
            let first_port = node_meta.first_port();
            let size = node_meta.capacity();
            self.port_count -= node_meta.port_count();

            assert!(first_port.index() + size <= self.port_link.len());
            assert!(first_port.index() + size <= self.port_meta.len());

            self.free_ports(first_port, size);
        }
    }

    fn clear(&mut self) {
        self.node_meta.clear();
        self.port_link.clear();
        self.port_meta.clear();
        self.node_free = None.into();
        self.port_free.clear();
        self.node_count = 0;
        self.port_count = 0;
        self.link_count = 0;
    }

    fn reserve(&mut self, nodes: usize, ports: usize) {
        self.node_meta.reserve(nodes);
        self.port_meta.reserve(ports);
        self.port_link.reserve(ports);
    }

    fn set_num_ports<F>(
        &mut self,
        node: NodeIndex<N>,
        incoming: usize,
        outgoing: usize,
        mut rekey: F,
    ) where
        F: FnMut(PortIndex<P>, PortOperation<P>),
    {
        assert!(
            incoming <= NodeMeta::<P, PO>::MAX_INCOMING,
            "Incoming port count exceeds maximum."
        );
        assert!(
            outgoing <= NodeMeta::<P, PO>::MAX_OUTGOING,
            "Outgoing port count exceeds maximum."
        );

        let new_total = incoming + outgoing;

        let Some(node_meta) = self.node_meta_valid(node) else {
            return;
        };
        let old_incoming = node_meta.incoming();
        let old_outgoing = node_meta.outgoing();
        let old_capacity = node_meta.capacity();
        let old_total = old_incoming + old_outgoing;
        let old_first_port = node_meta.first_port();
        if old_incoming == incoming && old_outgoing == outgoing {
            // Nothing to do
            return;
        } else if (1..old_capacity).contains(&new_total) {
            // Special case when we can avoid reallocations by shifting the
            // ports in the pre-allocated slab.
            self.resize_ports_inplace(node, incoming, outgoing, rekey);
            return;
        }

        // Disconnect any port to be removed.
        for port in self
            ._inputs(node)
            .skip(incoming)
            .chain(self._outputs(node).skip(outgoing))
        {
            let old_link = self.unlink_port(port);
            rekey(port, PortOperation::Removed { old_link });
        }
        // Allocate a new slab of ports. If `new_total` is 0, we just free the
        // old slab.
        //
        // TODO: Fine-tune overallocation factor
        let target_capacity = new_total.next_power_of_two();
        let new_meta = self.alloc_ports(node, incoming, outgoing, target_capacity - new_total);

        // Move the port data.
        for dir in Direction::BOTH {
            let rekeys = node_meta.ports(dir).zip(new_meta.ports(dir));
            for (old, new) in rekeys {
                if let Some(link) = self.port_link[old].to_option() {
                    self.port_link[link.index()] = PortIndex::new(new).into();
                }
                self.port_link[new] = self.port_link[old].take();
                self.port_meta[new] = self.port_meta[old];

                let new_index = PortIndex::new(new);
                rekey(PortIndex::new(old), PortOperation::Moved { new_index });
            }
        }

        self.node_meta[node.index()] = NodeEntry::Node(new_meta);
        self.free_ports(old_first_port, old_capacity);

        self.port_count = self.port_count - old_total + new_total;
    }

    fn compact_nodes<F>(&mut self, mut rekey: F)
    where
        F: FnMut(NodeIndex<N>, NodeIndex<N>),
    {
        let mut old_index = 0;
        let mut new_index = 0;
        self.node_meta.retain(|node_meta| {
            let old_node = NodeIndex::new(old_index);
            let new_node = NodeIndex::new(new_index);

            let NodeEntry::Node(node_meta) = node_meta else {
                old_index += 1;
                return false;
            };

            for dir in Direction::BOTH {
                for port in node_meta.ports(dir) {
                    self.port_meta[port] = PortEntry::new(new_node, dir);
                }
            }

            rekey(old_node, new_node);

            old_index += 1;
            new_index += 1;
            true
        });

        self.node_free = None.into();
    }

    fn swap_nodes(&mut self, a: NodeIndex<N>, b: NodeIndex<N>) {
        let meta_a = self.node_meta[a.index()];
        let meta_b = self.node_meta[b.index()];
        self.node_meta.swap(a.index(), b.index());
        // Update the node indices in the ports metadata.
        let mut update_ports = |new_node: NodeIndex<N>, entry: NodeEntry<N, P, PO>| {
            let NodeEntry::Node(node_meta) = entry else {
                return;
            };
            for dir in Direction::BOTH {
                for port in node_meta.ports(dir) {
                    self.port_meta[port] = PortEntry::new(new_node, dir);
                }
            }
        };
        update_ports(a, meta_b);
        update_ports(b, meta_a);
        // Update the free node linked list, only if we swapping empty and
        // non-empty spaces.
        let mut update_free_list = |new_node: NodeIndex<N>, entry: FreeNodeEntry<N>| {
            if let Some(prev) = entry.prev.to_option() {
                self.node_meta[prev.index()].free_entry_mut().unwrap().next = new_node.into();
            }
            if let Some(next) = entry.next.to_option() {
                self.node_meta[next.index()].free_entry_mut().unwrap().prev = new_node.into();
            }
        };
        match (meta_a, meta_b) {
            (NodeEntry::Free(meta_a), NodeEntry::Node(_)) => update_free_list(b, meta_a),
            (NodeEntry::Node(_), NodeEntry::Free(meta_b)) => update_free_list(a, meta_b),
            _ => (),
        }
    }

    fn compact_ports<F>(&mut self, mut rekey: F)
    where
        F: FnMut(PortIndex<P>, PortIndex<P>),
    {
        // Compact the links vector, ignoring free ports.
        let mut new_index = 0;
        for old_index in 0..self.port_link.len() {
            if self.port_meta[old_index].is_free() {
                continue;
            }
            if new_index == old_index {
                new_index += 1;
                continue;
            }

            // Invariant: The neighbour ports of visited ports always have
            // backlinks pointing to the correctly updated port indices.
            //
            // At the end of the loop, all port links have been updated.
            if let Some(link) = self.port_link[old_index].to_option() {
                self.port_link[link.index()] = PortIndex::new(new_index).into();
            }
            self.port_link.swap(new_index, old_index);
            new_index += 1;
        }
        self.port_link.truncate(new_index);

        // Compact the metadata vector
        let mut new_index = 0;
        let mut old_index = 0;
        self.port_meta.retain(|port_meta| {
            let old_port = PortIndex::<P>::new(old_index);
            let new_port = PortIndex::<P>::new(new_index);

            let Some(port_meta) = port_meta.as_meta() else {
                old_index += 1;
                return false;
            };

            // If we are moving the first port in a node's port list, we have to update the node.
            let node_entry = &mut self.node_meta[port_meta.node.index()];
            let NodeEntry::Node(node_meta) = *node_entry else {
                unreachable!("port must be attached to a valid node")
            };
            if node_meta.first_port() == old_port {
                // Update the node's port list, and reduce the capacity to match
                // the number of ports.
                *node_entry = NodeEntry::Node(
                    NodeMeta::<P, PO>::try_new(
                        new_port,
                        PO::from_usize(node_meta.incoming())
                            .expect("incoming port count exceeds maximum"),
                        PO::from_usize(node_meta.outgoing())
                            .expect("outgoing port count exceeds maximum"),
                        PO::from_usize(node_meta.port_count()).expect("port count exceeds maximum"),
                    )
                    .unwrap_or_else(|e| panic!("failed to create NodeMeta: {}", e)),
                );
            }

            rekey(old_port, new_port);

            old_index += 1;
            new_index += 1;
            true
        });

        self.port_free.clear();
    }

    fn shrink_to_fit(&mut self) {
        self.node_meta.shrink_to_fit();
        self.port_link.shrink_to_fit();
        self.port_meta.shrink_to_fit();
        self.port_free.shrink_to_fit();
    }
}

impl<N: IndexBase, P: IndexBase, PO: IndexBase> LinkView for PortGraph<N, P, PO> {
    type LinkEndpoint = PortIndex<P>;

    fn port_links(
        &self,
        port: PortIndex<P>,
    ) -> impl Iterator<Item = (PortIndex<P>, PortIndex<P>)> + Clone {
        self.port_meta_valid(port).unwrap();
        self.port_link[port.index()]
            .to_option()
            .map(|link| (port, link))
            .into_iter()
    }

    #[inline]
    fn link_count(&self) -> usize {
        self.link_count
    }

    delegate! {
        to self {
            #[call(_get_connections)]
            fn get_connections(&self, from: NodeIndex<N>, to: NodeIndex<N>) -> impl Iterator<Item = (Self::LinkEndpoint, Self::LinkEndpoint)> + Clone;
            #[call(_links)]
            fn links(&self, node: NodeIndex<N>, direction: Direction) -> impl Iterator<Item = (Self::LinkEndpoint, Self::LinkEndpoint)> + Clone;
            #[call(_all_links)]
            fn all_links(&self, node: NodeIndex<N>) -> impl Iterator<Item = (Self::LinkEndpoint, Self::LinkEndpoint)> + Clone;
            #[call(_neighbours)]
            fn neighbours(&self, node: NodeIndex<N>, direction: Direction) -> impl Iterator<Item = NodeIndex<N>> + Clone;
            #[call(_all_neighbours)]
            fn all_neighbours(&self, node: NodeIndex<N>) -> impl Iterator<Item = NodeIndex<N>> + Clone;
        }
    }
}

impl<N: IndexBase, P: IndexBase, PO: IndexBase> LinkMut for PortGraph<N, P, PO> {
    fn link_ports(
        &mut self,
        port_a: PortIndex<P>,
        port_b: PortIndex<P>,
    ) -> Result<(Self::LinkEndpoint, Self::LinkEndpoint), LinkError<N, P, PO>> {
        let Some(meta_a) = self.port_meta_valid(port_a) else {
            return Err(LinkError::UnknownPort { port: port_a });
        };

        let Some(meta_b) = self.port_meta_valid(port_b) else {
            return Err(LinkError::UnknownPort { port: port_a });
        };

        if meta_a.direction == meta_b.direction {
            return Err(LinkError::IncompatibleDirections {
                port_a,
                port_b,
                dir: meta_a.direction,
            });
        }

        if self.port_link[port_a.index()].is_some() {
            return Err(LinkError::AlreadyLinked { port: port_a });
        } else if self.port_link[port_b.index()].is_some() {
            return Err(LinkError::AlreadyLinked { port: port_b });
        }

        self.port_link[port_a.index()] = port_b.into();
        self.port_link[port_b.index()] = port_a.into();
        self.link_count += 1;
        Ok((port_a, port_b))
    }

    fn unlink_port(&mut self, port: PortIndex<P>) -> Option<PortIndex<P>> {
        self.port_meta_valid(port)?;
        let linked = self.port_link[port.index()].take().to_option()?;
        self.port_link[linked.index()] = None.into();
        self.link_count -= 1;
        Some(linked)
    }
}

impl<N: IndexBase, P: IndexBase, PO: IndexBase> Default for PortGraph<N, P, PO> {
    fn default() -> Self {
        Self::new()
    }
}

impl<N: IndexBase, P: IndexBase, PO: IndexBase> std::fmt::Debug for PortGraph<N, P, PO> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.debug_struct("PortGraph")
            .field("nodes", &debug::NodesDebug(self))
            .field("ports", &debug::PortsDebug(self))
            .finish()
    }
}

mod debug {
    use super::*;
    pub struct NodesDebug<'a, N: IndexBase, P: IndexBase, PO: IndexBase>(
        pub &'a PortGraph<N, P, PO>,
    );

    impl<N: IndexBase, P: IndexBase, PO: IndexBase> std::fmt::Debug for NodesDebug<'_, N, P, PO> {
        fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
            f.debug_map()
                .entries(
                    self.0
                        .nodes_iter()
                        .map(|node| (node, NodeDebug(self.0, node))),
                )
                .finish()
        }
    }

    pub struct NodeDebug<'a, N: IndexBase, P: IndexBase, PO: IndexBase>(
        pub &'a PortGraph<N, P, PO>,
        pub NodeIndex<N>,
    );

    impl<N: IndexBase, P: IndexBase, PO: IndexBase> std::fmt::Debug for NodeDebug<'_, N, P, PO> {
        fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
            let inputs = PortRangeDebug(self.0._inputs(self.1).as_range());
            let outputs = PortRangeDebug(self.0._outputs(self.1).as_range());

            f.debug_struct("Node")
                .field("inputs", &inputs)
                .field("outputs", &outputs)
                .finish()
        }
    }

    pub struct PortRangeDebug(pub Range<usize>);

    impl std::fmt::Debug for PortRangeDebug {
        fn fmt(&self, fmt: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
            if self.0.is_empty() {
                write!(fmt, "[]")?;
            } else if self.0.len() == 1 {
                write!(fmt, "[")?;
                PortIndex::<u32>::new(self.0.start).fmt(fmt)?;
                write!(fmt, "]")?;
            } else {
                PortIndex::<u32>::new(self.0.start).fmt(fmt)?;
                write!(fmt, "..")?;
                PortIndex::<u32>::new(self.0.end).fmt(fmt)?;
            }
            Ok(())
        }
    }

    pub struct PortsDebug<'a, N: IndexBase, P: IndexBase, PO: IndexBase>(
        pub &'a PortGraph<N, P, PO>,
    );

    impl<N: IndexBase, P: IndexBase, PO: IndexBase> std::fmt::Debug for PortsDebug<'_, N, P, PO> {
        fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
            f.debug_map()
                .entries(
                    self.0
                        .ports_iter()
                        .map(|port| (port, PortDebug(self.0, port))),
                )
                .finish()
        }
    }

    pub struct PortDebug<'a, N: IndexBase, P: IndexBase, PO: IndexBase>(
        pub &'a PortGraph<N, P, PO>,
        pub PortIndex<P>,
    );

    impl<N: IndexBase, P: IndexBase, PO: IndexBase> std::fmt::Debug for PortDebug<'_, N, P, PO> {
        fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
            let direction = self.0.port_direction(self.1).unwrap();
            let link = self.0.port_link(self.1);
            let node = self.0.port_node(self.1).unwrap();

            let mut fmt_struct = f.debug_struct("Port");
            fmt_struct.field("node", &node);
            fmt_struct.field("direction", &direction);

            if let Some(link) = link {
                fmt_struct.field("link", &link);
            }

            fmt_struct.finish()
        }
    }
}

/// Error generated when linking ports.
#[derive(Debug, Clone, Error, PartialEq, Eq)]
#[allow(missing_docs)]
pub enum LinkError<N: IndexBase = u32, P: IndexBase = u32, PO: IndexBase = u16> {
    /// The port is already linked.
    #[error("port {port:?} is already linked")]
    AlreadyLinked { port: PortIndex<P> },
    /// The port does not exist.
    #[error("unknown port '{port:?}''")]
    UnknownPort { port: PortIndex<P> },
    /// The port offset is invalid.
    #[error("unknown port offset {} in node {node:?} in direction {:?}", offset.index(), offset.direction())]
    UnknownOffset {
        node: NodeIndex<N>,
        offset: PortOffset<PO>,
    },
    /// The ports have the same direction so they cannot be linked.
    #[error("Cannot link two ports with direction {dir:?}. In ports {port_a:?} and {port_b:?}")]
    IncompatibleDirections {
        port_a: PortIndex<P>,
        port_b: PortIndex<P>,
        dir: Direction,
    },
}

#[cfg(feature = "pyo3")]
impl<N: IndexBase, P: IndexBase, PO: IndexBase> From<LinkError<N, P, PO>> for PyErr {
    fn from(s: LinkError<N, P, PO>) -> Self {
        pyo3::exceptions::PyRuntimeError::new_err(s.to_string())
    }
}

/// Operations applied to a port, used by the callback in [`PortGraph::set_num_ports`].
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum PortOperation<P: IndexBase = u32> {
    /// The port was moved to a new position.
    Moved {
        /// New index for the port
        new_index: PortIndex<P>,
    },
    /// The port was removed.
    Removed {
        /// The old link from the port, if any.
        old_link: Option<PortIndex<P>>,
    },
}

impl<P: IndexBase> PortOperation<P> {
    /// Return the new index of the port, if it was moved
    pub fn new_index(&self) -> Option<PortIndex<P>> {
        match self {
            PortOperation::Moved { new_index } => Some(*new_index),
            _ => None,
        }
    }
}

#[cfg(test)]
pub(crate) mod test {
    #[cfg(feature = "serde")]
    #[cfg(feature = "proptest")]
    use crate::proptest::gen_portgraph;
    use itertools::Itertools;
    #[cfg(feature = "proptest")]
    use proptest::prelude::*;

    use std::collections::HashMap;

    use super::*;
    use crate::NodeIndex;
    use crate::PortIndex;

    #[test]
    fn create_graph() {
        let graph: PortGraph = PortGraph::new();

        assert_eq!(graph.node_count(), 0);
        assert_eq!(graph.port_count(), 0);
        assert_eq!(graph.link_count(), 0);
        assert_eq!(graph.nodes_iter().count(), 0);
        assert_eq!(graph.ports_iter().count(), 0);
    }

    #[test]
    fn add_nodes() {
        let mut graph: PortGraph = PortGraph::with_capacity(5, 10);
        assert_eq!(graph.node_count(), 0);
        assert_eq!(graph.node_capacity(), 5);
        assert_eq!(graph.port_count(), 0);
        assert_eq!(graph.port_capacity(), 10);

        let lengths = [(0, 1), (0, 0), (1, 0), (2, 1), (1, 6)];
        let node_count = lengths.len();
        let port_count = lengths
            .iter()
            .map(|(incoming, outgoing)| incoming + outgoing)
            .sum();

        for (incoming, outgoing) in lengths.iter().copied() {
            let node = graph.add_node(incoming, outgoing);
            assert!(graph.contains_node(node));

            assert_eq!(graph.inputs(node).count(), incoming);
            assert_eq!(graph.outputs(node).count(), outgoing);
            assert_eq!(graph.num_ports(node, Direction::Incoming), incoming);
            assert_eq!(graph.num_ports(node, Direction::Outgoing), outgoing);
            assert_eq!(graph.all_ports(node).count(), incoming + outgoing);
            assert_eq!(graph.all_port_offsets(node).count(), incoming + outgoing);

            let inputs = graph
                .inputs(node)
                .enumerate()
                .map(|(i, port)| (i, port, Direction::Incoming));
            let outputs = graph
                .outputs(node)
                .enumerate()
                .map(|(i, port)| (i, port, Direction::Outgoing));
            for (i, port, dir) in inputs.chain(outputs) {
                let offset = PortOffset::new(dir, i);
                assert_eq!(graph.port_direction(port), Some(dir));
                assert_eq!(graph.port_offset(port), Some(offset));
                assert_eq!(graph.port_node(port), Some(node));
                assert_eq!(graph.port_index(node, offset), Some(port));
                assert_eq!(graph.port_link(port), None);
            }
        }

        // Global iterators
        let nodes = graph.nodes_iter().take(2);
        let nodes = nodes.chain(graph.nodes_iter().skip(2));
        let nodes = nodes.collect::<Vec<_>>();
        assert_eq!(
            nodes,
            (0..node_count).map(NodeIndex::new).collect::<Vec<_>>()
        );

        let ports = graph.ports_iter().take(2);
        let ports = ports.chain(graph.ports_iter().skip(2));
        let ports = ports.collect::<Vec<_>>();
        assert_eq!(ports.len(), port_count);
        assert_eq!(
            ports,
            (0..port_count).map(PortIndex::new).collect::<Vec<_>>()
        );
    }

    #[test]
    fn link_ports() {
        let mut g: PortGraph = PortGraph::new();
        let node0 = g.add_node(2, 1);
        let node1 = g.add_node(1, 2);
        let node0_input = g.input(node0, 0).unwrap();
        let node0_input2 = g.input(node0, 1).unwrap();
        let node0_output = g.output(node0, 0).unwrap();
        let node1_input = g.input(node1, 0).unwrap();
        let node1_output = g.output(node1, 0).unwrap();
        let node1_output2 = g.output(node1, 1).unwrap();
        assert_eq!(g.link_count(), 0);
        assert!(!g.connected(node0, node1));
        assert!(!g.connected(node1, node0));

        g.link_ports(node0_output, node1_input).unwrap();
        assert_eq!(g.link_count(), 1);
        assert_eq!(
            g.get_connections(node0, node1).collect::<Vec<_>>(),
            vec![(node0_output, node1_input)]
        );
        assert!(!g.connected(node1, node0));

        g.link_nodes(node1, 0, node0, 0).unwrap();
        assert_eq!(g.link_count(), 2);
        assert_eq!(
            g.get_connections(node0, node1).collect::<Vec<_>>(),
            vec![(node0_output, node1_input)]
        );
        assert_eq!(
            g.get_connections(node1, node0).collect::<Vec<_>>(),
            vec![(node1_output, node0_input)]
        );

        g.unlink_port(node0_output);
        assert_eq!(g.link_count(), 1);
        assert!(!g.connected(node0, node1));
        assert_eq!(
            g.get_connections(node1, node0).collect::<Vec<_>>(),
            vec![(node1_output, node0_input)]
        );

        g.link_nodes(node1, 1, node0, 1).unwrap();
        assert_eq!(g.link_count(), 2);
        assert!(!g.connected(node0, node1));
        assert_eq!(
            g.get_connections(node1, node0).collect::<Vec<_>>(),
            vec![(node1_output, node0_input), (node1_output2, node0_input2)]
        );
        assert_eq!(
            g._get_connections(node1, node0).rev().collect::<Vec<_>>(),
            vec![(node1_output2, node0_input2), (node1_output, node0_input)]
        );
    }

    #[test]
    fn link_ports_errors() {
        let mut g: PortGraph = PortGraph::new();
        let node0 = g.add_node(1, 1);
        let node1 = g.add_node(1, 1);
        let node0_input = g.input(node0, 0).unwrap();
        let node0_output = g.output(node0, 0).unwrap();
        let node1_input = g.input(node1, 0).unwrap();
        let node1_output = g.output(node1, 0).unwrap();
        assert!(g.link_ports(node0_input, node1_input).is_err());
        assert!(g.link_ports(node0_output, node1_output).is_err());
        g.link_ports(node0_output, node0_input).unwrap();
        assert!(g.link_ports(node0_output, node1_input).is_err());
        g.unlink_port(node0_output);
        g.remove_node(node1);
        assert!(g.link_ports(node1_output, node0_input).is_err());
    }

    #[test]
    fn link_iterators() {
        let mut g: PortGraph = PortGraph::new();
        let node0 = g.add_node(1, 3);
        let node1 = g.add_node(2, 1);
        let node0_input0 = g.input(node0, 0).unwrap();
        let node0_output0 = g.output(node0, 0).unwrap();
        let node0_output1 = g.output(node0, 1).unwrap();
        let node0_output2 = g.output(node0, 2).unwrap();
        let node1_input0 = g.input(node1, 0).unwrap();
        let node1_input1 = g.input(node1, 1).unwrap();

        assert!(g.input_links(node0).eq([]));
        assert!(g.output_links(node0).eq([]));
        assert!(g.all_links(node0).eq([]));
        assert!(g.input_neighbours(node0).eq([]));
        assert!(g.output_neighbours(node0).eq([]));
        assert!(g.all_neighbours(node0).eq([]));

        g.link_nodes(node0, 0, node1, 0).unwrap();

        assert!(g.input_links(node0).eq([]));
        assert!(g.output_links(node0).eq([(node0_output0, node1_input0)]));
        assert!(g.all_links(node0).eq([(node0_output0, node1_input0)]));
        assert!(g.input_neighbours(node0).eq([]));
        assert!(g.output_neighbours(node0).eq([node1]));
        assert!(g.all_neighbours(node0).eq([node1]));

        g.link_nodes(node0, 1, node1, 1).unwrap();

        assert!(g.input_links(node0).eq([]));
        assert!(g
            .output_links(node0)
            .eq([(node0_output0, node1_input0), (node0_output1, node1_input1)]));
        assert!(g
            .all_links(node0)
            .eq([(node0_output0, node1_input0), (node0_output1, node1_input1)]));
        assert!(g.input_neighbours(node0).eq([]));
        assert!(g.output_neighbours(node0).eq([node1, node1]));
        assert!(g.all_neighbours(node0).eq([node1, node1]));

        // Self-link
        g.link_nodes(node0, 2, node0, 0).unwrap();

        assert!(g.input_links(node0).eq([(node0_input0, node0_output2)]));
        assert!(g.output_links(node0).eq([
            (node0_output0, node1_input0),
            (node0_output1, node1_input1),
            (node0_output2, node0_input0)
        ]));
        // The self-link should only appear once in the all_links iterator
        assert!(g.all_links(node0).eq([
            (node0_output0, node1_input0),
            (node0_output1, node1_input1),
            (node0_output2, node0_input0)
        ]));
        assert!(g.input_neighbours(node0).eq([node0]));
        assert!(g.output_neighbours(node0).eq([node1, node1, node0]));
        assert!(g.all_neighbours(node0).eq([node1, node1, node0]));
    }

    #[test]
    fn compact_operations() {
        let mut g: PortGraph = PortGraph::new();
        let x = g.add_node(3, 2);
        let a = g.add_node(1, 1);
        let b = g.add_node(2, 2);
        let c = g.add_node(1, 1);
        g.link_nodes(a, 0, b, 0).unwrap();
        g.link_nodes(b, 0, b, 1).unwrap();
        g.link_nodes(b, 1, c, 0).unwrap();
        g.link_nodes(c, 0, a, 0).unwrap();
        let a_input = g.input(a, 0).unwrap();
        let a_output = g.input(a, 0).unwrap();

        assert_eq!(g.link_count(), 4);
        assert_eq!(g.node_count(), 4);
        assert_eq!(g.port_count(), 13);

        g.remove_node(x);

        assert_eq!(g.link_count(), 4);
        assert_eq!(g.node_count(), 3);
        assert_eq!(g.port_count(), 8);
        assert!(g.connected(a, b));
        assert!(g.connected(b, b));
        assert!(g.connected(b, c));
        assert!(g.connected(c, a));

        let mut new_nodes = HashMap::new();
        g.compact_nodes(|old, new| {
            new_nodes.insert(old, new);
        });

        assert_eq!(
            g.nodes_iter().collect::<Vec<_>>(),
            (0..3).map(NodeIndex::new).collect::<Vec<_>>()
        );
        assert_eq!(new_nodes.len(), 3);
        assert_eq!(g.port_node(a_input), Some(new_nodes[&a]));
        assert_eq!(g.port_node(a_output), Some(new_nodes[&a]));

        let a = new_nodes[&a];
        let b = new_nodes[&b];
        let c = new_nodes[&c];

        assert_eq!(g.link_count(), 4);
        assert_eq!(g.node_count(), 3);
        assert_eq!(g.port_count(), 8);
        assert!(g.connected(a, b));
        assert!(g.connected(b, b));
        assert!(g.connected(b, c));
        assert!(g.connected(c, a));

        let mut new_ports = HashMap::new();
        g.compact_ports(|old, new| {
            new_ports.insert(old, new);
        });

        assert_eq!(
            g.ports_iter().collect::<Vec<_>>(),
            (0..8).map(PortIndex::new).collect::<Vec<_>>()
        );
        assert_eq!(new_ports.len(), 8);
        assert_eq!(g.port_node(new_ports[&a_input]), Some(a));
        assert_eq!(g.port_node(new_ports[&a_output]), Some(a));

        assert_eq!(g.link_count(), 4);
        assert_eq!(g.node_count(), 3);
        assert_eq!(g.port_count(), 8);
        assert!(g.connected(a, b));
        assert!(g.connected(b, b));
        assert!(g.connected(b, c));
        assert!(g.connected(c, a));
    }

    #[test]
    fn resize_ports() {
        let mut g: PortGraph = PortGraph::new();
        let x = g.add_node(3, 2);
        let a = g.add_node(1, 1);
        let b = g.add_node(2, 2);
        let c = g.add_node(1, 1);
        g.link_nodes(a, 0, b, 0).unwrap();
        g.link_nodes(b, 0, b, 1).unwrap();
        g.link_nodes(b, 1, c, 0).unwrap();
        g.link_nodes(c, 0, a, 0).unwrap();

        assert_eq!(g.link_count(), 4);
        assert_eq!(g.node_count(), 4);
        assert_eq!(g.port_count(), 13);

        g.set_num_ports(x, 0, 3, |_, _| {});

        assert_eq!(g.link_count(), 4);
        assert_eq!(g.node_count(), 4);
        assert_eq!(g.port_count(), 11);
        assert!(g.connected(a, b));
        assert!(g.connected(b, b));
        assert!(g.connected(b, c));
        assert!(g.connected(c, a));

        g.set_num_ports(x, 0, 0, |_, _| {});

        assert_eq!(g.link_count(), 4);
        assert_eq!(g.node_count(), 4);
        assert_eq!(g.port_count(), 8);
        assert!(g.connected(a, b));
        assert!(g.connected(b, b));
        assert!(g.connected(b, c));
        assert!(g.connected(c, a));

        g.set_num_ports(a, 2, 3, |_, _| {});

        assert_eq!(g.link_count(), 4);
        assert_eq!(g.node_count(), 4);
        assert_eq!(g.port_count(), 11);
        assert!(g.connected(a, b));
        assert!(g.connected(b, b));
        assert!(g.connected(b, c));
        assert!(g.connected(c, a));

        g.set_num_ports(b, 2, 3, |_, _| {});

        assert_eq!(g.link_count(), 4);
        assert_eq!(g.node_count(), 4);
        assert_eq!(g.port_count(), 12);
        assert!(g.connected(a, b));
        assert!(g.connected(b, b));
        assert!(g.connected(b, c));
        assert!(g.connected(c, a));

        g.set_num_ports(b, 3, 2, |_, _| {});

        assert_eq!(g.link_count(), 4);
        assert_eq!(g.node_count(), 4);
        assert_eq!(g.port_count(), 12);
        assert!(g.connected(a, b));
        assert!(g.connected(b, b));
        assert!(g.connected(b, c));
        assert!(g.connected(c, a));

        g.set_num_ports(b, 2, 3, |_, _| {});

        assert_eq!(g.link_count(), 4);
        assert_eq!(g.node_count(), 4);
        assert_eq!(g.port_count(), 12);
        assert!(g.connected(a, b));
        assert!(g.connected(b, b));
        assert!(g.connected(b, c));
        assert!(g.connected(c, a));

        // Grow an empty node
        let d = g.add_node(0, 0);
        g.set_num_ports(d, 2, 3, |_, _| {});
        assert_eq!(g.port_count(), 17);
        g.set_num_ports(d, 0, 0, |_, _| {});
        assert_eq!(g.port_count(), 12);

        // Check links after resizing
        g.clear();
        let n0 = g.add_node(0, 2);
        let n1 = g.add_node(2, 1);
        g.link_nodes(n0, 0, n1, 0).unwrap();

        g.set_num_ports(n1, 1, 1, |_, _| {});

        let o = g.output(n0, 0).unwrap();
        let i = g.port_link(o).unwrap();
        assert!(g.port_node(i).is_some());
    }

    #[test]
    fn insert_graph() -> Result<(), Box<dyn std::error::Error>> {
        let mut g: PortGraph = PortGraph::new();
        // Add dummy nodes to produce different node ids than in the other graph.
        g.add_node(0, 0);
        g.add_node(0, 0);
        let node0g = g.add_node(1, 1);
        let node1g = g.add_node(1, 1);
        g.link_nodes(node0g, 0, node1g, 0)?;

        let mut h: PortGraph = PortGraph::new();
        let node0h = h.add_node(2, 2);
        let node1h = h.add_node(1, 1);
        h.link_nodes(node0h, 0, node1h, 0)?;
        h.link_nodes(node0h, 1, node0h, 0)?;
        h.link_nodes(node1h, 0, node0h, 1)?;

        let map = g.insert_graph(&h)?;
        assert_eq!(map.len(), 2);

        assert_eq!(g.node_count(), 6);
        assert_eq!(g.link_count(), 4);
        assert!(g.contains_node(map[&node0h]));
        assert!(g.contains_node(map[&node1h]));
        assert_eq!(
            g.input_neighbours(map[&node0h]).collect_vec(),
            [map[&node0h], map[&node1h]]
        );
        assert_eq!(
            g.output_neighbours(map[&node0h]).collect_vec(),
            [map[&node1h], map[&node0h]]
        );
        assert_eq!(
            g.all_neighbours(map[&node0h]).collect_vec(),
            [map[&node1h], map[&node1h], map[&node0h]]
        );

        Ok(())
    }

    #[cfg(feature = "serde")]
    pub(crate) fn ser_roundtrip<T: Serialize + serde::de::DeserializeOwned>(g: &T) -> T {
        let v = rmp_serde::to_vec_named(g).unwrap();
        rmp_serde::from_slice(&v[..]).unwrap()
    }
    #[cfg(feature = "serde")]
    #[cfg(feature = "proptest")]
    proptest! {
        #[test]
        fn prop_serialization(graph in gen_portgraph(100, 50, 1000)) {
            prop_assert_eq!(ser_roundtrip(&graph), graph);
        }
    }

    #[cfg(feature = "serde")]
    #[test]
    fn empty_portgraph_serialize() {
        let g: PortGraph = PortGraph::new();
        assert_eq!(ser_roundtrip(&g), g);
    }
}