use crate::builder::Builder;
use crate::traits::refs::{DirectedRef, GraphSizeRef, IndexGraphRef, UndirectedRef};
use crate::traits::{Directed, DirectedEdge, GraphSize, GraphType, IndexGraph, Undirected};
#[derive(Clone, Copy)]
pub struct ReverseDigraph<G>(G);
#[derive(Clone, Copy, PartialEq, Eq)]
pub struct ReverseDirectedEdge<E>(E);
impl<E> DirectedEdge for ReverseDirectedEdge<E>
where
E: DirectedEdge,
{
type Edge = E::Edge;
fn is_incoming(&self) -> bool {
self.0.is_outgoing()
}
fn is_outgoing(&self) -> bool {
self.0.is_incoming()
}
fn edge(&self) -> Self::Edge {
self.0.edge()
}
}
impl<'a, G> GraphType<'a> for ReverseDigraph<G>
where
G: GraphType<'a>,
{
type Node = G::Node;
type Edge = G::Edge;
}
impl<'a, G> GraphSize<'a> for ReverseDigraph<G>
where
G: GraphSize<'a>,
{
type NodeIter = G::NodeIter;
type EdgeIter = G::EdgeIter;
fn num_nodes(&self) -> usize {
self.0.num_nodes()
}
fn num_edges(&self) -> usize {
self.0.num_edges()
}
fn nodes(&'a self) -> Self::NodeIter {
self.0.nodes()
}
fn edges(&'a self) -> Self::EdgeIter {
self.0.edges()
}
}
impl<'a, G> Undirected<'a> for ReverseDigraph<G>
where
G: Undirected<'a>,
{
type Neigh = G::Neigh;
fn enodes(&'a self, e: Self::Edge) -> (Self::Node, Self::Node) {
self.0.enodes(e)
}
fn first_neigh(&'a self, u: Self::Node) -> Option<Self::Neigh> {
self.0.first_neigh(u)
}
fn next_neigh(&'a self, it: Self::Neigh) -> Option<Self::Neigh> {
self.0.next_neigh(it)
}
fn get_neigh(&'a self, it: &Self::Neigh) -> (Self::Edge, Self::Node) {
self.0.get_neigh(it)
}
}
impl<'a, G> IndexGraph<'a> for ReverseDigraph<G>
where
G: IndexGraph<'a>,
{
fn node_id(&self, u: Self::Node) -> usize {
self.0.node_id(u)
}
fn id2node(&'a self, id: usize) -> Self::Node {
self.0.id2node(id)
}
fn edge_id(&self, e: Self::Edge) -> usize {
self.0.edge_id(e)
}
fn id2edge(&'a self, id: usize) -> Self::Edge {
self.0.id2edge(id)
}
}
impl<'a, G> Directed<'a> for ReverseDigraph<G>
where
G: Directed<'a>,
{
type OutEdge = G::InEdge;
type InEdge = G::OutEdge;
type IncidentEdge = G::IncidentEdge;
type DirectedEdge = ReverseDirectedEdge<G::DirectedEdge>;
fn src(&'a self, e: Self::Edge) -> Self::Node {
self.0.snk(e)
}
fn snk(&'a self, e: Self::Edge) -> Self::Node {
self.0.src(e)
}
fn first_out(&'a self, u: Self::Node) -> Option<Self::OutEdge> {
self.0.first_in(u)
}
fn next_out(&'a self, it: Self::OutEdge) -> Option<Self::OutEdge> {
self.0.next_in(it)
}
fn get_out(&'a self, it: &Self::OutEdge) -> (Self::Edge, Self::Node) {
self.0.get_in(it)
}
fn first_in(&'a self, u: Self::Node) -> Option<Self::InEdge> {
self.0.first_out(u)
}
fn next_in(&'a self, it: Self::InEdge) -> Option<Self::InEdge> {
self.0.next_out(it)
}
fn get_in(&'a self, it: &Self::InEdge) -> (Self::Edge, Self::Node) {
self.0.get_out(it)
}
fn first_incident(&'a self, u: Self::Node) -> Option<Self::IncidentEdge> {
self.0.first_incident(u)
}
fn next_incident(&'a self, it: Self::IncidentEdge) -> Option<Self::IncidentEdge> {
self.0.next_incident(it)
}
fn get_incident(&'a self, it: &Self::IncidentEdge) -> (Self::DirectedEdge, Self::Node) {
let (e, v) = self.0.get_incident(it);
(ReverseDirectedEdge(e), v)
}
}
pub struct ReverseDigraphBuilder<B>(B);
impl<B> Builder for ReverseDigraphBuilder<B>
where
B: Builder,
{
type Graph = ReverseDigraph<B::Graph>;
type Node = B::Node;
type Edge = B::Edge;
fn new() -> Self {
ReverseDigraphBuilder(B::new())
}
fn with_capacities(nnodes: usize, nedges: usize) -> Self {
ReverseDigraphBuilder(B::with_capacities(nnodes, nedges))
}
fn reserve(&mut self, nnodes: usize, nedges: usize) {
self.0.reserve(nnodes, nedges)
}
fn num_nodes(&self) -> usize {
self.0.num_nodes()
}
fn num_edges(&self) -> usize {
self.0.num_edges()
}
fn add_node(&mut self) -> Self::Node {
self.0.add_node()
}
fn add_nodes(&mut self, n: usize) -> Vec<Self::Node> {
self.0.add_nodes(n)
}
fn add_edge(&mut self, u: Self::Node, v: Self::Node) -> Self::Edge {
self.0.add_edge(u, v)
}
fn node2id(&self, u: Self::Node) -> usize {
self.0.node2id(u)
}
fn edge2id(&self, e: Self::Edge) -> usize {
self.0.edge2id(e)
}
fn to_graph(self) -> Self::Graph {
ReverseDigraph(self.0.to_graph())
}
}
impl<G> From<G> for ReverseDigraph<G> {
fn from(g: G) -> Self {
ReverseDigraph(g)
}
}
pub fn reverse<'a, G: Directed<'a>>(g: G) -> ReverseDigraph<G> {
ReverseDigraph(g)
}
impl<'a, G> GraphSizeRef<'a> for ReverseDigraph<G>
where
G: GraphSizeRef<'a>,
{
fn nodes(&self) -> Self::NodeIter {
GraphSizeRef::nodes(&self.0)
}
fn edges(&self) -> Self::EdgeIter {
GraphSizeRef::edges(&self.0)
}
}
impl<'a, G> UndirectedRef<'a> for ReverseDigraph<G>
where
G: UndirectedRef<'a>,
{
fn enodes(&self, e: Self::Edge) -> (Self::Node, Self::Node) {
UndirectedRef::enodes(&self.0, e)
}
fn first_neigh(&self, u: Self::Node) -> Option<Self::Neigh> {
UndirectedRef::first_neigh(&self.0, u)
}
fn next_neigh(&self, it: Self::Neigh) -> Option<Self::Neigh> {
UndirectedRef::next_neigh(&self.0, it)
}
fn get_neigh(&self, it: &Self::Neigh) -> (Self::Edge, Self::Node) {
UndirectedRef::get_neigh(&self.0, it)
}
}
impl<'a, G> DirectedRef<'a> for ReverseDigraph<G>
where
G: DirectedRef<'a>,
{
fn src(&self, u: Self::Edge) -> Self::Node {
DirectedRef::snk(&self.0, u)
}
fn snk(&self, u: Self::Edge) -> Self::Node {
DirectedRef::src(&self.0, u)
}
fn first_out(&self, u: Self::Node) -> Option<Self::OutEdge> {
DirectedRef::first_in(&self.0, u)
}
fn next_out(&self, it: Self::OutEdge) -> Option<Self::OutEdge> {
DirectedRef::next_in(&self.0, it)
}
fn get_out(&self, it: &Self::OutEdge) -> (Self::Edge, Self::Node) {
DirectedRef::get_in(&self.0, it)
}
fn first_in(&self, u: Self::Node) -> Option<Self::InEdge> {
DirectedRef::first_out(&self.0, u)
}
fn next_in(&self, it: Self::InEdge) -> Option<Self::InEdge> {
DirectedRef::next_out(&self.0, it)
}
fn get_in(&self, it: &Self::InEdge) -> (Self::Edge, Self::Node) {
DirectedRef::get_out(&self.0, it)
}
fn first_incident(&self, u: Self::Node) -> Option<Self::IncidentEdge> {
DirectedRef::first_incident(&self.0, u)
}
fn next_incident(&self, it: Self::IncidentEdge) -> Option<Self::IncidentEdge> {
DirectedRef::next_incident(&self.0, it)
}
fn get_incident(&self, it: &Self::IncidentEdge) -> (Self::DirectedEdge, Self::Node) {
let (e, v) = DirectedRef::get_incident(&self.0, it);
(ReverseDirectedEdge(e), v)
}
}
impl<'a, G> IndexGraphRef<'a> for ReverseDigraph<G>
where
G: IndexGraphRef<'a>,
{
fn id2node(&self, id: usize) -> Self::Node {
IndexGraphRef::id2node(&self.0, id)
}
fn id2edge(&self, id: usize) -> Self::Edge {
IndexGraphRef::id2edge(&self.0, id)
}
}
#[cfg(test)]
mod tests {
use super::reverse;
use crate::classes;
use crate::traits::GraphSize;
use crate::vec::EdgeVec;
use crate::LinkedListGraph;
#[test]
fn test_vec() {
let g = classes::peterson::<LinkedListGraph>();
let r = reverse(&g);
let weights = EdgeVec::new(r, 42);
for e in r.edges() {
assert_eq!(weights[e], 42);
}
}
}