use crate::traits::refs::{DirectedRef, GraphSizeRef, IndexGraphRef, UndirectedRef};
use crate::traits::{Digraph, Directed, DirectedEdge, GraphSize, GraphType, IndexGraph, Indexable, Undirected};
#[derive(Clone, Copy)]
pub struct Network<'a, G>(&'a G);
#[derive(Clone, Copy, PartialEq, Eq)]
pub enum NetworkEdge<E> {
Forward(E),
Backward(E),
}
impl<E> NetworkEdge<E>
where
E: Clone + Eq,
{
pub fn new(e: E) -> Self {
NetworkEdge::Forward(e)
}
pub fn is_forward(&self) -> bool {
match self {
NetworkEdge::Forward(_) => true,
NetworkEdge::Backward(_) => false,
}
}
pub fn is_backward(&self) -> bool {
!self.is_forward()
}
pub fn is_reverse(&self, e: Self) -> bool {
use NetworkEdge::*;
match (self, &e) {
(Forward(a), Backward(b)) | (Backward(a), Forward(b)) => a == b,
_ => false,
}
}
pub fn reverse(&self) -> Self {
match self {
NetworkEdge::Forward(e) => NetworkEdge::Backward(e.clone()),
NetworkEdge::Backward(e) => NetworkEdge::Forward(e.clone()),
}
}
pub fn forward(&self) -> Self {
NetworkEdge::Forward(self.edge())
}
pub fn backward(&self) -> Self {
NetworkEdge::Backward(self.edge())
}
pub fn edge(&self) -> E {
match self {
NetworkEdge::Forward(e) | NetworkEdge::Backward(e) => e.clone(),
}
}
}
pub struct NetworkEdgeIter<I>(I, Option<I::Item>)
where
I: Iterator;
impl<I> Iterator for NetworkEdgeIter<I>
where
I: Iterator,
I::Item: Clone,
{
type Item = NetworkEdge<I::Item>;
fn next(&mut self) -> Option<Self::Item> {
if let Some(cur) = self.1.take() {
Some(NetworkEdge::Backward(cur))
} else if let Some(nxt) = self.0.next() {
self.1 = Some(nxt.clone());
Some(NetworkEdge::Forward(nxt))
} else {
None
}
}
}
pub struct NetworkNeighIter<I, N, E>(I, Option<(E, N)>)
where
I: Iterator;
impl<I, N, E> Iterator for NetworkNeighIter<I, N, E>
where
I: Iterator<Item = (E, N)>,
N: Clone,
E: Clone,
{
type Item = (NetworkEdge<E>, N);
fn next(&mut self) -> Option<Self::Item> {
if let Some(cur) = self.1.take() {
Some((NetworkEdge::Backward(cur.0), cur.1))
} else if let Some(nxt) = self.0.next() {
self.1 = Some(nxt.clone());
Some((NetworkEdge::Forward(nxt.0), nxt.1))
} else {
None
}
}
}
pub struct NetworkOutIter<'a, G>(G::IncidentIter)
where
G: Directed<'a>;
impl<'a, G> Iterator for NetworkOutIter<'a, G>
where
G: Directed<'a>,
{
type Item = (NetworkEdge<G::Edge>, G::Node);
fn next(&mut self) -> Option<Self::Item> {
self.0.next().map(|(e, v)| {
if e.is_outgoing() {
(NetworkEdge::Forward(e.edge()), v)
} else {
(NetworkEdge::Backward(e.edge()), v)
}
})
}
}
pub struct NetworkInIter<'a, G>(G::IncidentIter)
where
G: Directed<'a>;
impl<'a, G> Iterator for NetworkInIter<'a, G>
where
G: Directed<'a>,
{
type Item = (NetworkEdge<G::Edge>, G::Node);
fn next(&mut self) -> Option<Self::Item> {
self.0.next().map(|(e, v)| {
if e.is_incoming() {
(NetworkEdge::Forward(e.edge()), v)
} else {
(NetworkEdge::Backward(e.edge()), v)
}
})
}
}
#[derive(Clone, Copy, PartialEq, Eq)]
pub enum NetworkDirectedEdge<E> {
Outgoing(E),
Incoming(E),
}
impl<E> DirectedEdge for NetworkDirectedEdge<E>
where
E: Clone,
{
type Edge = E;
fn is_incoming(&self) -> bool {
match self {
NetworkDirectedEdge::Incoming(..) => true,
_ => false,
}
}
fn edge(&self) -> E {
match self {
NetworkDirectedEdge::Incoming(e) | NetworkDirectedEdge::Outgoing(e) => e.clone(),
}
}
}
pub struct NetworkIncidentIter<'a, G>
where
G: Directed<'a>,
{
forward: NetworkOutIter<'a, G>,
backward: NetworkInIter<'a, G>,
forward_dir: bool,
}
impl<'a, G> NetworkIncidentIter<'a, G>
where
G: Directed<'a>,
{
fn new(forward: NetworkOutIter<'a, G>, backward: NetworkInIter<'a, G>) -> Self {
NetworkIncidentIter {
forward,
backward,
forward_dir: true,
}
}
}
impl<'a, G> Iterator for NetworkIncidentIter<'a, G>
where
G: Directed<'a>,
{
type Item = (NetworkDirectedEdge<NetworkEdge<G::Edge>>, G::Node);
fn next(&mut self) -> Option<Self::Item> {
use NetworkDirectedEdge::*;
if self.forward_dir {
if let Some((e, v)) = self.forward.next() {
Some((Outgoing(e), v))
} else if let Some((e, v)) = self.backward.next() {
self.forward_dir = false;
Some((Incoming(e), v))
} else {
None
}
} else if let Some((e, v)) = self.backward.next() {
Some((Incoming(e), v))
} else {
None
}
}
}
impl<'a, G> Network<'a, G>
where
G: Digraph<'a>,
{
pub fn new(g: &'a G) -> Self {
Network(g)
}
pub fn as_graph(&self) -> &'a G {
self.0
}
pub fn from_edge(&self, e: G::Edge) -> NetworkEdge<G::Edge> {
NetworkEdge::Forward(e)
}
}
impl<'s, 'a: 's, G> GraphType<'s> for Network<'a, G>
where
G: Digraph<'a>,
{
type Node = G::Node;
type Edge = NetworkEdge<G::Edge>;
}
impl<'s, 'a: 's, G> GraphSize<'s> for Network<'a, G>
where
G: Digraph<'a>,
{
type NodeIter = G::NodeIter;
type EdgeIter = NetworkEdgeIter<G::EdgeIter>;
fn num_nodes(&self) -> usize {
self.0.num_nodes()
}
fn num_edges(&self) -> usize {
self.0.num_edges() * 2
}
fn nodes(&self) -> Self::NodeIter {
self.0.nodes()
}
fn edges(&'s self) -> Self::EdgeIter {
NetworkEdgeIter(self.0.edges(), None)
}
}
impl<'s, 'a: 's, G> Undirected<'s> for Network<'a, G>
where
G: Digraph<'a>,
{
type NeighIter = NetworkNeighIter<G::NeighIter, G::Node, G::Edge>;
fn enodes(&'s self, e: Self::Edge) -> (Self::Node, Self::Node) {
match e {
NetworkEdge::Forward(e) | NetworkEdge::Backward(e) => self.0.enodes(e),
}
}
fn neighs(&'s self, u: Self::Node) -> Self::NeighIter {
NetworkNeighIter(self.0.neighs(u), None)
}
}
impl<'s, 'a: 's, G> Directed<'s> for Network<'a, G>
where
G: 'a + Digraph<'a>,
{
type OutEdgeIter = NetworkOutIter<'a, &'a G>;
type InEdgeIter = NetworkInIter<'a, &'a G>;
type IncidentIter = NetworkIncidentIter<'a, &'a G>;
type DirectedEdge = NetworkDirectedEdge<Self::Edge>;
fn src(&'s self, e: Self::Edge) -> Self::Node {
match e {
NetworkEdge::Forward(e) => self.0.src(e),
NetworkEdge::Backward(e) => self.0.snk(e),
}
}
fn snk(&'s self, e: Self::Edge) -> Self::Node {
match e {
NetworkEdge::Forward(e) => self.0.snk(e),
NetworkEdge::Backward(e) => self.0.src(e),
}
}
fn outedges(&'s self, u: Self::Node) -> Self::OutEdgeIter {
NetworkOutIter(self.0.incident_edges(u))
}
fn inedges(&'s self, u: Self::Node) -> Self::InEdgeIter {
NetworkInIter(self.0.incident_edges(u))
}
fn incident_edges(&'s self, u: Self::Node) -> Self::IncidentIter {
NetworkIncidentIter::new(Directed::outedges(self, u), Directed::inedges(self, u))
}
}
impl<'s, 'a: 's, G> IndexGraph<'s> for Network<'a, G>
where
G: Digraph<'a> + IndexGraph<'a>,
{
fn node_id(&self, u: Self::Node) -> usize {
self.0.node_id(u)
}
fn id2node(&'s self, id: usize) -> Self::Node {
self.0.id2node(id)
}
fn edge_id(&self, e: Self::Edge) -> usize {
(self.0.edge_id(e.edge())) << 1 | (e.is_backward() as usize)
}
fn id2edge(&'s self, id: usize) -> Self::Edge {
match id & 1 {
0 => NetworkEdge::Forward(self.0.id2edge(id >> 1)),
_ => NetworkEdge::Backward(self.0.id2edge(id >> 1)),
}
}
}
impl<E> Indexable for NetworkEdge<E>
where
E: Indexable,
{
fn index(&self) -> usize {
match self {
NetworkEdge::Forward(e) => e.index() << 1,
NetworkEdge::Backward(e) => (e.index() << 1) | 1,
}
}
}
impl<'a, G> GraphSizeRef<'a> for Network<'a, G>
where
G: Directed<'a>,
{
fn nodes(&self) -> Self::NodeIter {
GraphSize::nodes(self)
}
fn edges(&self) -> Self::EdgeIter {
GraphSize::edges(self)
}
}
impl<'a, G> UndirectedRef<'a> for Network<'a, G>
where
G: Directed<'a>,
{
fn enodes(&self, e: Self::Edge) -> (Self::Node, Self::Node) {
Undirected::enodes(self, e)
}
fn neighs(&self, u: Self::Node) -> Self::NeighIter {
Undirected::neighs(self, u)
}
}
impl<'a, G> DirectedRef<'a> for Network<'a, G>
where
G: 'a + Directed<'a>,
{
fn src(&self, u: Self::Edge) -> Self::Node {
Directed::src(self, u)
}
fn snk(&self, u: Self::Edge) -> Self::Node {
Directed::snk(self, u)
}
fn outedges(&self, u: Self::Node) -> Self::OutEdgeIter {
Directed::outedges(self, u)
}
fn inedges(&self, u: Self::Node) -> Self::InEdgeIter {
Directed::inedges(self, u)
}
fn incident_edges(&self, u: Self::Node) -> Self::IncidentIter {
Directed::incident_edges(self, u)
}
}
impl<'a, G> IndexGraphRef<'a> for Network<'a, G>
where
G: Directed<'a> + IndexGraph<'a>,
{
fn id2node(&self, id: usize) -> Self::Node {
IndexGraph::id2node(self, id)
}
fn id2edge(&self, id: usize) -> Self::Edge {
IndexGraph::id2edge(self, id)
}
}
#[cfg(test)]
mod tests {
use super::Network;
use crate::classes::*;
use crate::traits::{Directed, DirectedEdge, GraphSize, Undirected};
use crate::LinkedListGraph;
use std::collections::HashMap;
#[test]
fn test_network() {
for g in [cycle::<LinkedListGraph>(7), peterson(), hypercube(5)].iter() {
let n = Network(g);
assert_eq!(2 * g.num_edges(), n.num_edges());
for u in g.nodes() {
assert_eq!(g.neighs(u).count(), n.outedges(u).count());
assert_eq!(g.neighs(u).count(), n.inedges(u).count());
assert_eq!(2 * g.neighs(u).count(), n.neighs(u).count());
assert_eq!(2 * g.incident_edges(u).count(), n.incident_edges(u).count());
{
let mut fwds = g.outedges(u).map(|e| (e, false)).collect::<HashMap<_, _>>();
let mut bwds = g.inedges(u).map(|e| (e, false)).collect::<HashMap<_, _>>();
for (e, v) in n.outedges(u) {
assert!(!e.is_forward() || !fwds.insert((e.edge(), v), true).unwrap_or(true));
assert!(!e.is_backward() || !bwds.insert((e.edge(), v), true).unwrap_or(true));
}
assert!(fwds.values().all(|x| *x));
assert!(bwds.values().all(|x| *x));
}
{
let mut fwds = g.inedges(u).map(|e| (e, false)).collect::<HashMap<_, _>>();
let mut bwds = g.outedges(u).map(|e| (e, false)).collect::<HashMap<_, _>>();
for (e, v) in n.inedges(u) {
assert!(!e.is_forward() || !fwds.insert((e.edge(), v), true).unwrap_or(true));
assert!(!e.is_backward() || !bwds.insert((e.edge(), v), true).unwrap_or(true));
}
assert!(fwds.values().all(|x| *x));
assert!(bwds.values().all(|x| *x));
}
{
let mut fwds = g.neighs(u).map(|e| (e, false)).collect::<HashMap<_, _>>();
let mut bwds = g.neighs(u).map(|e| (e, false)).collect::<HashMap<_, _>>();
for (e, v) in n.neighs(u) {
assert!(!e.is_forward() || !fwds.insert((e.edge(), v), true).unwrap_or(true));
assert!(!e.is_backward() || !bwds.insert((e.edge(), v), true).unwrap_or(true));
}
assert!(fwds.values().all(|x| *x));
assert!(bwds.values().all(|x| *x));
}
{
let mut out_fwds = g.outedges(u).map(|e| (e, false)).collect::<HashMap<_, _>>();
let mut out_bwds = g.inedges(u).map(|e| (e, false)).collect::<HashMap<_, _>>();
let mut in_fwds = g.inedges(u).map(|e| (e, false)).collect::<HashMap<_, _>>();
let mut in_bwds = g.outedges(u).map(|e| (e, false)).collect::<HashMap<_, _>>();
for (e, v) in n.incident_edges(u) {
if e.is_outgoing() {
let e = e.edge();
assert!(!e.is_forward() || !out_fwds.insert((e.edge(), v), true).unwrap_or(true));
assert!(!e.is_backward() || !out_bwds.insert((e.edge(), v), true).unwrap_or(true));
} else {
let e = e.edge();
assert!(!e.is_forward() || !in_fwds.insert((e.edge(), v), true).unwrap_or(true));
assert!(!e.is_backward() || !in_bwds.insert((e.edge(), v), true).unwrap_or(true));
}
}
assert!(out_fwds.values().all(|x| *x));
assert!(out_bwds.values().all(|x| *x));
assert!(in_fwds.values().all(|x| *x));
assert!(in_bwds.values().all(|x| *x));
}
}
{
let mut fwds = g.edges().map(|e| (e, false)).collect::<HashMap<_, _>>();
let mut bwds = g.edges().map(|e| (e, false)).collect::<HashMap<_, _>>();
for e in n.edges() {
assert!(!e.is_forward() || !fwds.insert(e.edge(), true).unwrap_or(true));
assert!(!e.is_backward() || !bwds.insert(e.edge(), true).unwrap_or(true));
assert!(e.is_reverse(e.reverse()));
assert!(e.is_forward() || e.reverse().is_forward());
assert!(e.is_backward() || e.reverse().is_backward());
assert!(!e.is_forward() || e.forward() == e);
assert!(!e.is_backward() || e.backward() == e);
}
assert!(fwds.values().all(|x| *x));
assert!(bwds.values().all(|x| *x));
}
}
}
}