use crate::adjacencies::{InEdges, Neighbors, OutEdges};
pub mod refs;
pub trait GraphIterator<G: ?Sized>: Clone {
type Item;
fn next(&mut self, g: &G) -> Option<Self::Item>;
fn size_hint(&self, _g: &G) -> (usize, Option<usize>) {
(0, None)
}
fn count(mut self, g: &G) -> usize {
let mut c = 0;
while self.next(g).is_some() {
c += 1
}
c
}
fn iter<'a>(self, g: &'a G) -> GraphIter<'a, G, Self>
where
G: Sized,
{
GraphIter(self, g)
}
}
pub struct GraphIter<'a, G, I>(pub(crate) I, pub(crate) &'a G);
impl<'a, G, I> Clone for GraphIter<'a, G, I>
where
I: Clone,
{
fn clone(&self) -> Self {
GraphIter(self.0.clone(), self.1)
}
}
impl<'a, G, I> Iterator for GraphIter<'a, G, I>
where
I: GraphIterator<G>,
{
type Item = I::Item;
fn next(&mut self) -> Option<Self::Item> {
self.0.next(self.1)
}
fn size_hint(&self) -> (usize, Option<usize>) {
self.0.size_hint(self.1)
}
fn count(self) -> usize {
self.0.count(self.1)
}
}
pub trait GraphType<'a> {
type Node: 'a + Copy + Eq;
type Edge: 'a + Copy + Eq;
}
pub type NodeIterator<'a, G> = GraphIter<'a, G, <G as GraphSize<'a>>::NodeIt>;
pub type EdgeIterator<'a, G> = GraphIter<'a, G, <G as GraphSize<'a>>::EdgeIt>;
pub trait GraphSize<'a>: GraphType<'a> {
type NodeIt: GraphIterator<Self, Item = Self::Node>;
type EdgeIt: GraphIterator<Self, Item = Self::Edge>;
fn num_nodes(&self) -> usize;
fn num_edges(&self) -> usize;
fn nodes_iter(&'a self) -> Self::NodeIt;
fn nodes(&'a self) -> NodeIterator<'a, Self>
where
Self: Sized,
{
GraphIter(self.nodes_iter(), self)
}
fn edges_iter(&'a self) -> Self::EdgeIt;
fn edges(&'a self) -> EdgeIterator<'a, Self>
where
Self: Sized,
{
GraphIter(self.edges_iter(), self)
}
}
type NeighIterator<'a, G> = GraphIter<'a, G, <G as Undirected<'a>>::NeighIt>;
pub trait Undirected<'a>: GraphSize<'a> {
type NeighIt: GraphIterator<Self, Item = (Self::Edge, Self::Node)>;
fn enodes(&'a self, e: Self::Edge) -> (Self::Node, Self::Node);
fn neigh_iter(&'a self, u: Self::Node) -> Self::NeighIt;
fn neighs(&'a self, u: Self::Node) -> NeighIterator<'a, Self>
where
Self: Sized,
{
self.neigh_iter(u).iter(self)
}
fn neighbors(&'a self) -> Neighbors<'a, Self>
where
Self: Sized,
{
Neighbors(self)
}
}
pub trait DirectedEdge {
type Edge;
fn is_incoming(&self) -> bool;
fn is_outgoing(&self) -> bool {
!self.is_incoming()
}
fn edge(&self) -> Self::Edge;
}
type OutIterator<'a, G> = GraphIter<'a, G, <G as Directed<'a>>::OutIt>;
type InIterator<'a, G> = GraphIter<'a, G, <G as Directed<'a>>::InIt>;
type IncidentIterator<'a, G> = GraphIter<'a, G, <G as Directed<'a>>::IncidentIt>;
pub trait Directed<'a>: Undirected<'a> {
type OutIt: GraphIterator<Self, Item = (Self::Edge, Self::Node)>;
type InIt: GraphIterator<Self, Item = (Self::Edge, Self::Node)>;
type IncidentIt: GraphIterator<Self, Item = (Self::DirectedEdge, Self::Node)>;
type DirectedEdge: 'a + DirectedEdge<Edge = Self::Edge> + Copy + Eq;
fn src(&'a self, e: Self::Edge) -> Self::Node;
fn snk(&'a self, e: Self::Edge) -> Self::Node;
fn out_iter(&'a self, u: Self::Node) -> Self::OutIt;
fn outedges(&'a self, u: Self::Node) -> OutIterator<'a, Self>
where
Self: Sized,
{
GraphIter(self.out_iter(u), self)
}
fn outgoing(&'a self) -> OutEdges<'a, Self>
where
Self: Sized,
{
OutEdges(self)
}
fn in_iter(&'a self, u: Self::Node) -> Self::InIt;
fn inedges(&'a self, u: Self::Node) -> InIterator<'a, Self>
where
Self: Sized,
{
GraphIter(self.in_iter(u), self)
}
fn incoming(&'a self) -> InEdges<'a, Self>
where
Self: Sized,
{
InEdges(self)
}
fn incident_iter(&'a self, u: Self::Node) -> Self::IncidentIt;
fn incident_edges(&'a self, u: Self::Node) -> IncidentIterator<'a, Self>
where
Self: Sized,
{
GraphIter(self.incident_iter(u), self)
}
}
pub trait Graph<'a>: GraphSize<'a> + Undirected<'a> {}
impl<'a, G> Graph<'a> for G where G: GraphSize<'a> + Undirected<'a> {}
pub trait Digraph<'a>: Graph<'a> + Directed<'a> {}
impl<'a, G> Digraph<'a> for G where G: GraphSize<'a> + Directed<'a> {}
pub trait Indexable {
fn index(&self) -> usize;
}
pub trait IndexGraph<'a>: Graph<'a> {
fn node_id(&self, u: Self::Node) -> usize;
fn id2node(&'a self, id: usize) -> Self::Node;
fn edge_id(&self, e: Self::Edge) -> usize;
fn id2edge(&'a self, id: usize) -> Self::Edge;
}
pub trait IndexDigraph<'a>: IndexGraph<'a> + Digraph<'a> {}
impl<'a, T> IndexDigraph<'a> for T where T: IndexGraph<'a> + Digraph<'a> {}
pub trait NumberedGraph<'a>: Graph<'a>
where
<Self as GraphType<'a>>::Node: Indexable,
<Self as GraphType<'a>>::Edge: Indexable,
{
}
impl<'a, G> NumberedGraph<'a> for G
where
G: Graph<'a>,
G::Node: Indexable,
G::Edge: Indexable,
{
}
pub trait NumberedDigraph<'a>: NumberedGraph<'a> + Digraph<'a>
where
<Self as GraphType<'a>>::Node: Indexable,
<Self as GraphType<'a>>::Edge: Indexable,
{
}
impl<'a, G> NumberedDigraph<'a> for G
where
G: Digraph<'a> + NumberedGraph<'a>,
G::Node: Indexable,
G::Edge: Indexable,
{
}
impl<'a, 'g: 'a, G> GraphType<'a> for &'g G
where
G: GraphType<'g>,
{
type Node = G::Node;
type Edge = G::Edge;
}
#[derive(Clone)]
pub struct WrapIt<I>(pub I);
impl<'a, G, I> GraphIterator<&'a G> for WrapIt<I>
where
I: GraphIterator<G>,
{
type Item = I::Item;
fn next(&mut self, g: &&'a G) -> Option<Self::Item> {
self.0.next(*g)
}
fn size_hint(&self, g: &&'a G) -> (usize, Option<usize>) {
self.0.size_hint(*g)
}
fn count(self, g: &&'a G) -> usize {
self.0.count(*g)
}
}
impl<I> From<I> for WrapIt<I> {
fn from(it: I) -> WrapIt<I> {
WrapIt(it)
}
}
impl<'a, 'g: 'a, G> GraphSize<'a> for &'g G
where
G: GraphSize<'g>,
{
type NodeIt = WrapIt<G::NodeIt>;
type EdgeIt = WrapIt<G::EdgeIt>;
fn num_nodes(&self) -> usize {
(*self).num_nodes()
}
fn num_edges(&self) -> usize {
(*self).num_edges()
}
fn nodes_iter(&'a self) -> Self::NodeIt {
(*self).nodes_iter().into()
}
fn edges_iter(&self) -> Self::EdgeIt {
(*self).edges_iter().into()
}
}
impl<'a, 'g: 'a, G> Undirected<'a> for &'g G
where
G: Undirected<'g>,
{
type NeighIt = WrapIt<G::NeighIt>;
fn enodes(&'a self, e: Self::Edge) -> (Self::Node, Self::Node) {
(*self).enodes(e)
}
fn neigh_iter(&'a self, u: Self::Node) -> Self::NeighIt {
(*self).neigh_iter(u).into()
}
}
impl<'a, 'g: 'a, G> IndexGraph<'a> for &'g G
where
G: IndexGraph<'g>,
{
fn node_id(&self, u: Self::Node) -> usize {
(*self).node_id(u)
}
fn id2node(&'a self, id: usize) -> Self::Node {
(*self).id2node(id)
}
fn edge_id(&self, e: Self::Edge) -> usize {
(*self).edge_id(e)
}
fn id2edge(&'a self, id: usize) -> Self::Edge {
(*self).id2edge(id)
}
}
impl<'a, 'g: 'a, G> Directed<'a> for &'g G
where
G: Directed<'g>,
{
type OutIt = WrapIt<G::OutIt>;
type InIt = WrapIt<G::InIt>;
type IncidentIt = WrapIt<G::IncidentIt>;
type DirectedEdge = G::DirectedEdge;
fn src(&'a self, e: Self::Edge) -> Self::Node {
(*self).src(e)
}
fn snk(&'a self, e: Self::Edge) -> Self::Node {
(*self).snk(e)
}
fn out_iter(&'a self, u: Self::Node) -> Self::OutIt {
(*self).out_iter(u).into()
}
fn in_iter(&'a self, u: Self::Node) -> Self::InIt {
(*self).in_iter(u).into()
}
fn incident_iter(&'a self, u: Self::Node) -> Self::IncidentIt {
(*self).incident_iter(u).into()
}
}
impl<'a, G> refs::GraphSizeRef<'a> for &'a G
where
G: GraphSize<'a>,
{
fn nodes_iter(&self) -> Self::NodeIt {
(*self).nodes_iter().into()
}
fn edges_iter(&self) -> Self::EdgeIt {
(*self).edges_iter().into()
}
}
impl<'a, G> refs::UndirectedRef<'a> for &'a G
where
G: Undirected<'a>,
{
fn enodes(&self, e: Self::Edge) -> (Self::Node, Self::Node) {
(*self).enodes(e)
}
fn neigh_iter(&self, u: Self::Node) -> Self::NeighIt {
(*self).neigh_iter(u).into()
}
}
impl<'a, G> refs::DirectedRef<'a> for &'a G
where
G: Directed<'a>,
{
fn src(&self, u: Self::Edge) -> Self::Node {
(*self).src(u)
}
fn snk(&self, u: Self::Edge) -> Self::Node {
(*self).snk(u)
}
fn out_iter(&self, u: Self::Node) -> Self::OutIt {
(*self).out_iter(u).into()
}
fn in_iter(&self, u: Self::Node) -> Self::InIt {
(*self).in_iter(u).into()
}
fn incident_iter(&self, u: Self::Node) -> Self::IncidentIt {
(*self).incident_iter(u).into()
}
}
impl<'a, G> refs::IndexGraphRef<'a> for &'a G
where
G: IndexGraph<'a>,
{
fn id2node(&self, id: usize) -> Self::Node {
(*self).id2node(id)
}
fn id2edge(&self, id: usize) -> Self::Edge {
(*self).id2edge(id)
}
}