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<G>(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
}
}
}
#[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(),
}
}
}
impl<'a, G> Network<G>
where
G: Digraph<'a>,
{
pub fn new(g: G) -> Self {
Network(g)
}
pub fn as_graph(&self) -> &G {
&self.0
}
pub fn into_graph(self) -> G {
self.0
}
pub fn from_edge(&self, e: G::Edge) -> NetworkEdge<G::Edge> {
NetworkEdge::Forward(e)
}
}
impl<'a, G> GraphType<'a> for Network<G>
where
G: Digraph<'a>,
{
type Node = G::Node;
type Edge = NetworkEdge<G::Edge>;
}
impl<'a, G> GraphSize<'a> for Network<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(&'a self) -> Self::NodeIter {
self.0.nodes()
}
fn edges(&'a self) -> Self::EdgeIter {
NetworkEdgeIter(self.0.edges(), None)
}
}
type NetworkNeigh<Neigh> = NetworkEdge<Neigh>;
impl<'a, G> Undirected<'a> for Network<G>
where
G: Digraph<'a>,
{
type Neigh = NetworkNeigh<G::Neigh>;
fn enodes(&'a self, e: Self::Edge) -> (Self::Node, Self::Node) {
match e {
NetworkEdge::Forward(e) | NetworkEdge::Backward(e) => self.0.enodes(e),
}
}
fn first_neigh(&'a self, u: Self::Node) -> Option<Self::Neigh> {
self.0.first_neigh(u).map(NetworkNeigh::Forward)
}
fn next_neigh(&'a self, it: Self::Neigh) -> Option<Self::Neigh> {
match it {
NetworkEdge::Forward(it) => Some(NetworkEdge::Backward(it)),
NetworkEdge::Backward(it) => self.0.next_neigh(it).map(NetworkEdge::Forward),
}
}
fn get_neigh(&'a self, it: &Self::Neigh) -> (Self::Edge, Self::Node) {
match it {
NetworkEdge::Forward(it) => {
let (e, v) = self.0.get_neigh(it);
(NetworkEdge::Forward(e), v)
}
NetworkEdge::Backward(it) => {
let (e, v) = self.0.get_neigh(it);
(NetworkEdge::Backward(e), v)
}
}
}
}
#[derive(Clone)]
pub struct NetworkOutEdge<Neigh>(Neigh);
#[derive(Clone)]
pub struct NetworkInEdge<Neigh>(Neigh);
#[derive(Clone)]
pub struct NetworkIncidentEdge<Neigh>(NetworkEdge<Neigh>);
impl<'a, G> Directed<'a> for Network<G>
where
G: Digraph<'a>,
{
type OutEdge = NetworkOutEdge<G::IncidentEdge>;
type InEdge = NetworkInEdge<G::IncidentEdge>;
type IncidentEdge = NetworkIncidentEdge<G::IncidentEdge>;
type DirectedEdge = NetworkDirectedEdge<Self::Edge>;
fn src(&'a self, e: Self::Edge) -> Self::Node {
match e {
NetworkEdge::Forward(e) => self.0.src(e),
NetworkEdge::Backward(e) => self.0.snk(e),
}
}
fn snk(&'a self, e: Self::Edge) -> Self::Node {
match e {
NetworkEdge::Forward(e) => self.0.snk(e),
NetworkEdge::Backward(e) => self.0.src(e),
}
}
fn first_out(&'a self, u: Self::Node) -> Option<Self::OutEdge> {
self.0.first_incident(u).map(NetworkOutEdge)
}
fn next_out(&'a self, it: Self::OutEdge) -> Option<Self::OutEdge> {
self.0.next_incident(it.0).map(NetworkOutEdge)
}
fn get_out(&'a self, it: &Self::OutEdge) -> (Self::Edge, Self::Node) {
let (e, v) = self.0.get_incident(&it.0);
if e.is_outgoing() {
(NetworkEdge::Forward(e.edge()), v)
} else {
(NetworkEdge::Backward(e.edge()), v)
}
}
fn first_in(&'a self, u: Self::Node) -> Option<Self::InEdge> {
self.0.first_incident(u).map(NetworkInEdge)
}
fn next_in(&'a self, it: Self::InEdge) -> Option<Self::InEdge> {
self.0.next_incident(it.0).map(NetworkInEdge)
}
fn get_in(&'a self, it: &Self::InEdge) -> (Self::Edge, Self::Node) {
let (e, v) = self.0.get_incident(&it.0);
if e.is_outgoing() {
(NetworkEdge::Backward(e.edge()), v)
} else {
(NetworkEdge::Forward(e.edge()), v)
}
}
fn first_incident(&'a self, u: Self::Node) -> Option<Self::IncidentEdge> {
self.0
.first_incident(u)
.map(NetworkEdge::Forward)
.map(NetworkIncidentEdge)
}
fn next_incident(&'a self, it: Self::IncidentEdge) -> Option<Self::IncidentEdge> {
match it.0 {
NetworkEdge::Forward(it) => Some(NetworkIncidentEdge(NetworkEdge::Backward(it))),
NetworkEdge::Backward(it) => self
.0
.next_incident(it)
.map(NetworkEdge::Forward)
.map(NetworkIncidentEdge),
}
}
fn get_incident(&'a self, it: &Self::IncidentEdge) -> (Self::DirectedEdge, Self::Node) {
match it.0 {
NetworkEdge::Forward(ref it) => {
let (e, v) = self.0.get_incident(it);
if e.is_outgoing() {
(NetworkDirectedEdge::Outgoing(NetworkEdge::Forward(e.edge())), v)
} else {
(NetworkDirectedEdge::Incoming(NetworkEdge::Forward(e.edge())), v)
}
}
NetworkEdge::Backward(ref it) => {
let (e, v) = self.0.get_incident(it);
if e.is_incoming() {
(NetworkDirectedEdge::Outgoing(NetworkEdge::Backward(e.edge())), v)
} else {
(NetworkDirectedEdge::Incoming(NetworkEdge::Backward(e.edge())), v)
}
}
}
}
}
impl<'a, G> IndexGraph<'a> for Network<G>
where
G: Digraph<'a> + 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.edge())) << 1 | (e.is_backward() as usize)
}
fn id2edge(&'a 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 first_neigh(&self, u: Self::Node) -> Option<Self::Neigh> {
Undirected::first_neigh(self, u)
}
fn next_neigh(&self, it: Self::Neigh) -> Option<Self::Neigh> {
Undirected::next_neigh(self, it)
}
fn get_neigh(&self, it: &Self::Neigh) -> (Self::Edge, Self::Node) {
Undirected::get_neigh(self, it)
}
}
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 first_out(&self, u: Self::Node) -> Option<Self::OutEdge> {
Directed::first_out(self, u)
}
fn next_out(&self, it: Self::OutEdge) -> Option<Self::OutEdge> {
Directed::next_out(self, it)
}
fn get_out(&self, it: &Self::OutEdge) -> (Self::Edge, Self::Node) {
Directed::get_out(self, it)
}
fn first_in(&self, u: Self::Node) -> Option<Self::InEdge> {
Directed::first_in(self, u)
}
fn next_in(&self, it: Self::InEdge) -> Option<Self::InEdge> {
Directed::next_in(self, it)
}
fn get_in(&self, it: &Self::InEdge) -> (Self::Edge, Self::Node) {
Directed::get_in(self, it)
}
fn first_incident(&self, u: Self::Node) -> Option<Self::IncidentEdge> {
Directed::first_incident(self, u)
}
fn next_incident(&self, it: Self::IncidentEdge) -> Option<Self::IncidentEdge> {
Directed::next_incident(self, it)
}
fn get_incident(&self, it: &Self::IncidentEdge) -> (Self::DirectedEdge, Self::Node) {
Directed::get_incident(self, it)
}
}
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));
}
}
}
}