portgraph 0.16.1

//! Petgraph's trait implementations for portgraphs.

use std::iter::FusedIterator;

use bitvec::vec::BitVec;

use crate::index::IndexBase;
use crate::multiportgraph::MultiPortGraph;
use crate::view::filter::{LinkFilter, NodeFilter};
use crate::view::flat_region::FlatRegion;
use crate::view::region::Region;
use crate::view::subgraph::Subgraph;
use crate::{LinkView, NodeIndex, PortGraph, PortIndex, PortView, SecondaryMap};

use super::FilteredGraph;

impl From<petgraph::Direction> for crate::Direction {
    fn from(d: petgraph::Direction) -> Self {
        match d {
            petgraph::Direction::Incoming => crate::Direction::Incoming,
            petgraph::Direction::Outgoing => crate::Direction::Outgoing,
        }
    }
}

impl From<crate::Direction> for petgraph::Direction {
    fn from(d: crate::Direction) -> Self {
        match d {
            crate::Direction::Incoming => petgraph::Direction::Incoming,
            crate::Direction::Outgoing => petgraph::Direction::Outgoing,
        }
    }
}

impl<N: IndexBase> petgraph::visit::NodeRef for NodeIndex<N> {
    type NodeId = NodeIndex<N>;
    type Weight = ();

    fn id(&self) -> Self::NodeId {
        *self
    }

    fn weight(&self) -> &Self::Weight {
        &()
    }
}

/// Implement petgraph traits for a portgraph type or wrapper.
///
/// Can be called simply as `impl_petgraph_traits!(MyGraph)` for non-generic
/// graphs, or
/// ```ignore
/// impl_petgraph_traits!(MyGraph<T, G>, [T, G] where T: Bound, G: OtherBound);
/// ```
/// for generic types with bounds.
macro_rules! impl_petgraph_traits {
    ($graph:ty) => {impl_petgraph_traits!($graph, []);};
    ($graph:ty, [$($args:tt)*]) => {impl_petgraph_traits!($graph, [$($args)*] where );};
    ($graph:ty, [$($args:tt)*] where $($where:tt)*) => {
        impl<$($args)*> petgraph::visit::GraphBase for $graph where $($where)* {
            type NodeId = NodeIndex<<$graph as PortView>::NodeIndexBase>;
            type EdgeId = (
                <$graph as LinkView>::LinkEndpoint,
                <$graph as LinkView>::LinkEndpoint,
            );
        }

        impl<$($args)*> petgraph::visit::GraphProp for $graph where $($where)* {
            type EdgeType = petgraph::Directed;
        }

        impl<$($args)*> petgraph::visit::NodeCount for $graph where $($where)* {
            fn node_count(&self) -> usize {
                PortView::node_count(self)
            }
        }

        impl<$($args)*> petgraph::visit::NodeIndexable for $graph where $($where)* {
            fn node_bound(&self) -> usize {
                PortView::node_count(self)
            }

            fn to_index(&self, ix: Self::NodeId) -> usize {
                ix.index()
            }

            fn from_index(&self, ix: usize) -> Self::NodeId {
                NodeIndex::new(ix)
            }
        }

        impl<$($args)*> petgraph::visit::EdgeCount for $graph where $($where)* {
            fn edge_count(&self) -> usize {
                LinkView::link_count(self)
            }
        }

        impl<$($args)*> petgraph::visit::Data for $graph where $($where)* {
            type NodeWeight = ();
            type EdgeWeight = ();
        }

        impl<'g, $($args)*> petgraph::visit::IntoNodeIdentifiers for &'g $graph where $($where)* {
            type NodeIdentifiers = Box<dyn Iterator<Item = NodeIndex<<$graph as PortView>::NodeIndexBase>> + 'g>;

            fn node_identifiers(self) -> Self::NodeIdentifiers {
                Box::new(self.nodes_iter())
            }
        }

        impl<'g, $($args)*> petgraph::visit::IntoNodeReferences for &'g $graph where $($where)* {
            type NodeRef = NodeIndex<<$graph as PortView>::NodeIndexBase>;
            type NodeReferences = Box<dyn Iterator<Item = NodeIndex<<$graph as PortView>::NodeIndexBase>> + 'g>;

            fn node_references(self) -> Self::NodeReferences {
                Box::new(self.nodes_iter())
            }
        }

        impl<'g, $($args)*> petgraph::visit::IntoNeighbors for &'g $graph where $($where)* {
            type Neighbors = Box<dyn Iterator<Item = NodeIndex<<$graph as PortView>::NodeIndexBase>> + 'g>;

            fn neighbors(self, n: Self::NodeId) -> Self::Neighbors {
                Box::new(self.output_neighbours(n))
            }
        }

        impl<'g, $($args)*> petgraph::visit::IntoNeighborsDirected for &'g $graph where $($where)* {
            type NeighborsDirected = Box<dyn Iterator<Item = NodeIndex<<$graph as PortView>::NodeIndexBase>> + 'g>;

            fn neighbors_directed(
                self,
                n: Self::NodeId,
                d: petgraph::Direction,
            ) -> Self::NeighborsDirected {
                Box::new(self.neighbours(n, d.into()))
            }
        }

        impl<'g, $($args)*> petgraph::visit::IntoEdgeReferences for &'g $graph where $($where)* {
            type EdgeRef = EdgeRef<<$graph as PortView>::NodeIndexBase, <$graph as LinkView>::LinkEndpoint>;
            type EdgeReferences = EdgeRefs<'g, $graph>;

            fn edge_references(self) -> Self::EdgeReferences {
                EdgeRefs::new(self)
            }
        }

        impl<'g, $($args)*> petgraph::visit::IntoEdges for &'g $graph where $($where)* {
            type Edges = NodeEdgeRefs<'g, $graph>;

            fn edges(self, n: Self::NodeId) -> Self::Edges {
                NodeEdgeRefs::new(self, n)
            }
        }

        impl<'g, $($args)*> petgraph::visit::IntoEdgesDirected for &'g $graph where $($where)* {
            type EdgesDirected = NodeEdgeRefs<'g, $graph>;

            fn edges_directed(
                self,
                n: Self::NodeId,
                d: petgraph::Direction,
            ) -> Self::EdgesDirected {
                NodeEdgeRefs::new_directed(self, n, d.into())
            }
        }
    };
}

/// Implement petgraph's `Visitable` and `GetAdjacencyMatrix` traits for a portgraph type or wrapper.
///
/// Assumes that the node indices are dense and start at 0, and uses internal containers that consume O(#nodes) memory.
macro_rules! impl_visit_dense {
    ($graph:ty) => {impl_visit_dense!($graph, []);};
    ($graph:ty, [$($args:tt)*]) => {impl_visit_dense!($graph, [$($args)*] where );};
    ($graph:ty, [$($args:tt)*] where $($where:tt)*) => {
        impl<$($args)*> petgraph::visit::Visitable for $graph $($where)* {
            type Map = bitvec::vec::BitVec;

            fn visit_map(&self) -> Self::Map {
                BitVec::with_capacity(self.node_capacity())
            }

            fn reset_map(&self, map: &mut Self::Map) {
                map.clear();
            }
        }

        impl<$($args)*> petgraph::visit::GetAdjacencyMatrix for $graph $($where)* {
            type AdjMatrix = (bitvec::vec::BitVec, usize);

            fn adjacency_matrix(&self) -> Self::AdjMatrix {
                let row_size = self.node_capacity();
                let mut matrix = bitvec::bitvec![0; row_size * row_size];
                for node in self.nodes_iter() {
                    for neighbour in self.output_neighbours(node) {
                        let row = node.index();
                        let column = neighbour.index();
                        matrix.set(row * row_size + column, true);
                    }
                }
                (matrix, row_size)
            }

            fn is_adjacent(
                &self,
                matrix: &Self::AdjMatrix,
                a: Self::NodeId,
                b: Self::NodeId,
            ) -> bool {
                let (matrix, row_size) = matrix;
                let row = a.index();
                let column = b.index();
                matrix[row * row_size + column]
            }
        }
    };
}

/// Implement petgraph's `Visitable` and `GetAdjacencyMatrix` traits for a sparse portgraph type or wrapper.
///
/// Uses sparse containers to keep track of visited nodes.
macro_rules! impl_visit_sparse {
    ($graph:ty) => {impl_visit_sparse!($graph, []);};
    ($graph:ty, [$($args:tt)*]) => {impl_visit_sparse!($graph, [$($args)*] where );};
    ($graph:ty, [$($args:tt)*] where $($where:tt)*) => {
        impl<$($args)*> petgraph::visit::Visitable for $graph where $($where)* {
            type Map = std::collections::HashSet<Self::NodeId>;

            fn visit_map(&self) -> Self::Map {
                std::collections::HashSet::new()
            }

            fn reset_map(&self, map: &mut Self::Map) {
                map.clear();
            }
        }

        impl<$($args)*> petgraph::visit::GetAdjacencyMatrix for $graph where $($where)* {
            type AdjMatrix = std::collections::HashSet<(Self::NodeId, Self::NodeId)>;

            fn adjacency_matrix(&self) -> Self::AdjMatrix {
                let mut matrix = std::collections::HashSet::new();
                for node in self.nodes_iter() {
                    for neighbour in self.output_neighbours(node) {
                        matrix.insert((node, neighbour));
                    }
                }
                matrix
            }

            fn is_adjacent(
                &self,
                matrix: &Self::AdjMatrix,
                a: Self::NodeId,
                b: Self::NodeId,
            ) -> bool {
                matrix.contains(&(a, b))
            }
        }
    };
}

impl_petgraph_traits!(PortGraph<N, P, PO>, [N: IndexBase, P: IndexBase, PO: IndexBase]);
impl_petgraph_traits!(MultiPortGraph<N, P, PO>, [N: IndexBase, P: IndexBase, PO: IndexBase]);
impl_petgraph_traits!(FilteredGraph<G, NodeFilter<Ctx, G::NodeIndexBase>, LinkFilter<Ctx, G::PortIndexBase>, Ctx>, [G, Ctx]
    where
        G: LinkView + Clone,
        <G as LinkView>::LinkEndpoint: Eq
);
impl_petgraph_traits!(Region<'graph, G>, ['graph, G]
    where
        G: LinkView + Clone,
        <G as LinkView>::LinkEndpoint: Eq
);
impl_petgraph_traits!(FlatRegion<'graph, G>, ['graph, G]
    where
        G: LinkView + Clone,
        <G as LinkView>::LinkEndpoint: Eq
);
impl_petgraph_traits!(Subgraph<G>, [G]
    where
        G: LinkView + Clone,
        <G as LinkView>::LinkEndpoint: Eq
);

impl_visit_dense!(PortGraph<N, P, PO>, [N: IndexBase, P: IndexBase, PO: IndexBase]);
impl_visit_dense!(MultiPortGraph<N, P, PO>, [N: IndexBase, P: IndexBase, PO: IndexBase]);
impl_visit_sparse!(FilteredGraph<G, NodeFilter<Ctx, G::NodeIndexBase>, LinkFilter<Ctx, G::PortIndexBase>, Ctx>, [G, Ctx]
    where
        G: LinkView + Clone,
        <G as LinkView>::LinkEndpoint: Eq
);
impl_visit_sparse!(Region<'graph, G>, ['graph, G]
    where
        G: LinkView + Clone,
        <G as LinkView>::LinkEndpoint: Eq
);
impl_visit_sparse!(FlatRegion<'graph, G>, ['graph, G]
    where
        G: LinkView + Clone,
        <G as LinkView>::LinkEndpoint: Eq
);
impl_visit_sparse!(Subgraph<G>, [G]
    where
        G: LinkView + Clone,
        <G as LinkView>::LinkEndpoint: Eq
);

impl<N: IndexBase> petgraph::visit::VisitMap<NodeIndex<N>> for BitVec {
    fn visit(&mut self, a: NodeIndex<N>) -> bool {
        let is_visited = self.is_visited(&a);
        <Self as SecondaryMap<NodeIndex<N>, bool>>::set(self, a, true);
        is_visited
    }

    fn is_visited(&self, a: &NodeIndex<N>) -> bool {
        *<Self as SecondaryMap<NodeIndex<N>, bool>>::get(self, *a)
    }

    fn unvisit(&mut self, a: NodeIndex<N>) -> bool {
        let is_visited = self.is_visited(&a);
        <Self as SecondaryMap<NodeIndex<N>, bool>>::set(self, a, false);
        is_visited
    }
}

/// A reference to an edge in a portgraph, with information about the nodes it
/// connects.
///
/// Used to implement petgraph's `EdgeRef` trait.
#[derive(Debug, Clone, Copy)]
pub struct EdgeRef<N: IndexBase, P> {
    from_node: NodeIndex<N>,
    to_node: NodeIndex<N>,
    edge: (P, P),
}

impl<N: IndexBase, P> petgraph::visit::EdgeRef for EdgeRef<N, P>
where
    P: Copy,
{
    type NodeId = NodeIndex<N>;
    type EdgeId = (P, P);
    type Weight = ();

    fn source(&self) -> Self::NodeId {
        self.from_node
    }

    fn target(&self) -> Self::NodeId {
        self.to_node
    }

    fn weight(&self) -> &Self::Weight {
        &()
    }

    fn id(&self) -> Self::EdgeId {
        self.edge
    }
}

/// Iterator over the edges of a portgraph.
///
/// Used for compatibility with petgraph.
#[allow(clippy::type_complexity)]
pub struct EdgeRefs<'g, G: LinkView> {
    graph: &'g G,
    ports: Box<dyn Iterator<Item = PortIndex<G::PortIndexBase>> + 'g>,
    links: Option<Box<dyn Iterator<Item = (G::LinkEndpoint, G::LinkEndpoint)> + 'g>>,
    count: usize,
}

impl<'g, G> EdgeRefs<'g, G>
where
    G: LinkView,
{
    /// Create a new iterator over the edges of a portgraph.
    pub fn new(graph: &'g G) -> Self {
        Self {
            graph,
            ports: Box::new(graph.ports_iter()),
            links: None,
            count: graph.link_count(),
        }
    }
}

impl<G> Iterator for EdgeRefs<'_, G>
where
    G: LinkView,
{
    type Item = EdgeRef<G::NodeIndexBase, G::LinkEndpoint>;

    fn next(&mut self) -> Option<Self::Item> {
        loop {
            if let Some((from, to)) = self.links.as_mut().and_then(|links| links.next()) {
                return Some(EdgeRef {
                    from_node: self.graph.port_node(from).unwrap(),
                    to_node: self.graph.port_node(to).unwrap(),
                    edge: (from, to),
                });
            }

            let port = self.ports.next()?;
            self.links = Some(Box::new(self.graph.port_links(port)));
        }
    }

    #[inline]
    fn count(self) -> usize
    where
        Self: Sized,
    {
        self.count
    }

    #[inline]
    fn size_hint(&self) -> (usize, Option<usize>) {
        (self.count, Some(self.count))
    }
}

impl<G: LinkView> ExactSizeIterator for EdgeRefs<'_, G> {
    #[inline]
    fn len(&self) -> usize {
        self.count
    }
}

impl<G: LinkView> FusedIterator for EdgeRefs<'_, G> {}

/// Iterator over the edges of a node.
///
/// Used for compatibility with petgraph.
pub struct NodeEdgeRefs<'g, G: LinkView> {
    graph: &'g G,
    links: Box<dyn Iterator<Item = (G::LinkEndpoint, G::LinkEndpoint)> + 'g>,
}

impl<'g, G> NodeEdgeRefs<'g, G>
where
    G: LinkView,
{
    /// Create a new iterator over the edges of a portgraph.
    pub fn new(graph: &'g G, node: NodeIndex<G::NodeIndexBase>) -> Self {
        Self {
            graph,
            links: Box::new(graph.all_links(node)),
        }
    }

    /// Create a new iterator over the edges of a portgraph.
    pub fn new_directed(
        graph: &'g G,
        node: NodeIndex<G::NodeIndexBase>,
        dir: crate::Direction,
    ) -> Self {
        Self {
            graph,
            links: Box::new(graph.links(node, dir)),
        }
    }
}

impl<G> Iterator for NodeEdgeRefs<'_, G>
where
    G: LinkView,
{
    type Item = EdgeRef<G::NodeIndexBase, G::LinkEndpoint>;

    fn next(&mut self) -> Option<Self::Item> {
        let (from, to) = self.links.next()?;
        Some(EdgeRef {
            from_node: self.graph.port_node(from).unwrap(),
            to_node: self.graph.port_node(to).unwrap(),
            edge: (from, to),
        })
    }

    #[inline]
    fn count(self) -> usize
    where
        Self: Sized,
    {
        self.links.count()
    }

    #[inline]
    fn size_hint(&self) -> (usize, Option<usize>) {
        self.links.size_hint()
    }
}