use crate::builder::{Buildable, Builder};
use crate::traits::{Directed, DirectedEdge, FiniteDigraph, FiniteGraph, GraphIterator, GraphType, Undirected};
use crate::traits::{IndexGraph, Indexable};
use crate::num::iter::{range, range_step, Range, RangeStep};
use crate::num::traits::{PrimInt, Unsigned};
use std::fmt;
use std::hash::{Hash, Hasher};
use std::slice::Iter as SliceIter;
#[cfg(feature = "serialize")]
use serde_derive::{Deserialize, Serialize};
#[derive(PartialEq, Eq, Clone, Copy, Debug, Hash)]
pub struct Node<ID = u32>(ID)
where
ID: PrimInt + Unsigned;
impl<ID> fmt::Display for Node<ID>
where
ID: PrimInt + Unsigned + fmt::Display,
{
fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> {
write!(f, "{}", self.0)
}
}
impl<ID> Indexable for Node<ID>
where
ID: PrimInt + Unsigned,
{
fn index(&self) -> usize {
self.0.to_usize().unwrap()
}
}
#[derive(Eq, Clone, Copy, Debug)]
pub struct Edge<ID = u32>(ID)
where
ID: PrimInt + Unsigned;
impl<ID> PartialEq for Edge<ID>
where
ID: PrimInt + Unsigned,
{
fn eq(&self, other: &Self) -> bool {
(self.0 >> 1) == (other.0 >> 1)
}
}
impl<ID> fmt::Display for Edge<ID>
where
ID: PrimInt + Unsigned + fmt::Display,
{
fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> {
write!(
f,
"{}{}",
if (self.0 & ID::one()).is_zero() { "+" } else { "-" },
self.0 >> 1
)
}
}
impl<ID> Hash for Edge<ID>
where
ID: PrimInt + Unsigned + Hash,
{
fn hash<H: Hasher>(&self, state: &mut H) {
(self.0 >> 1).hash(state)
}
}
impl<ID> Indexable for Edge<ID>
where
ID: PrimInt + Unsigned,
{
fn index(&self) -> usize {
(self.0 >> 1).to_usize().unwrap()
}
}
impl<ID> DirectedEdge for Edge<ID>
where
ID: PrimInt + Unsigned,
{
type Edge = Self;
fn is_incoming(&self) -> bool {
!(self.0 & ID::one()).is_zero()
}
fn edge(&self) -> Self::Edge {
*self
}
}
#[cfg_attr(feature = "serialize", derive(Serialize, Deserialize))]
struct NodeData<ID> {
firstout: ID,
firstin: ID,
}
#[cfg_attr(feature = "serialize", derive(Serialize, Deserialize))]
struct EdgeData<ID> {
nodes: [ID; 2],
}
#[cfg_attr(feature = "serialize", derive(Serialize, Deserialize))]
pub struct VecGraph<ID = u32> {
nodes: Vec<NodeData<ID>>,
edges: Vec<EdgeData<ID>>,
adj: Vec<ID>,
}
#[derive(Clone)]
pub struct NodeIt<ID>(Range<ID>);
impl<'a, ID> GraphIterator<VecGraph<ID>> for NodeIt<ID>
where
ID: 'a + PrimInt + Unsigned,
{
type Item = Node<ID>;
fn next(&mut self, _g: &VecGraph<ID>) -> Option<Self::Item> {
Iterator::next(&mut self.0).map(Node)
}
fn size_hint(&self, _g: &VecGraph<ID>) -> (usize, Option<usize>) {
Iterator::size_hint(&self.0)
}
fn count(self, _g: &VecGraph<ID>) -> usize {
Iterator::count(self.0)
}
}
#[derive(Clone)]
pub struct EdgeIt<ID>(RangeStep<ID>);
impl<'a, ID> GraphIterator<VecGraph<ID>> for EdgeIt<ID>
where
ID: 'a + PrimInt + Unsigned,
{
type Item = Edge<ID>;
fn next(&mut self, _g: &VecGraph<ID>) -> Option<Self::Item> {
Iterator::next(&mut self.0).map(Edge)
}
fn size_hint(&self, _g: &VecGraph<ID>) -> (usize, Option<usize>) {
Iterator::size_hint(&self.0)
}
fn count(self, _g: &VecGraph<ID>) -> usize {
Iterator::count(self.0)
}
}
impl<ID> GraphType for VecGraph<ID>
where
ID: PrimInt + Unsigned,
{
type Node<'a> = Node<ID>;
type Edge<'a> = Edge<ID>;
}
impl<ID> FiniteGraph for VecGraph<ID>
where
ID: PrimInt + Unsigned,
{
type NodeIt<'a> = NodeIt<ID>
where
ID: 'a;
type EdgeIt<'a> = EdgeIt<ID>
where
ID: 'a;
fn num_nodes(&self) -> usize {
self.nodes.len()
}
fn num_edges(&self) -> usize {
self.edges.len()
}
fn nodes_iter(&self) -> Self::NodeIt<'_> {
NodeIt(range(ID::zero(), ID::from(self.num_nodes()).unwrap()))
}
fn edges_iter(&self) -> Self::EdgeIt<'_> {
EdgeIt(range_step(
ID::zero(),
ID::from(2 * self.edges.len()).unwrap(),
ID::from(2).unwrap(),
))
}
fn enodes(&self, e: Self::Edge<'_>) -> (Self::Node<'_>, Self::Node<'_>) {
let eid = e.index();
(Node(self.edges[eid].nodes[0]), Node(self.edges[eid].nodes[1]))
}
}
impl<ID> FiniteDigraph for VecGraph<ID>
where
ID: PrimInt + Unsigned,
{
fn src(&self, e: Self::Edge<'_>) -> Self::Node<'_> {
let eid = e.0.to_usize().unwrap();
Node(self.edges[eid >> 1].nodes[0])
}
fn snk(&self, e: Self::Edge<'_>) -> Self::Node<'_> {
let eid = e.0.to_usize().unwrap();
Node(self.edges[eid >> 1].nodes[1])
}
}
#[derive(Clone)]
pub struct NeighIt<'a, ID>(SliceIter<'a, ID>);
impl<'a, ID> GraphIterator<VecGraph<ID>> for NeighIt<'a, ID>
where
ID: PrimInt + Unsigned,
{
type Item = (Edge<ID>, Node<ID>);
fn next(&mut self, g: &VecGraph<ID>) -> Option<Self::Item> {
self.0.next().map(|&eid| {
let i = eid.to_usize().unwrap();
(Edge(eid), Node(g.edges[i >> 1].nodes[1 - (i & 1)]))
})
}
}
impl<ID> Undirected for VecGraph<ID>
where
ID: PrimInt + Unsigned + 'static,
{
type NeighIt<'a> = NeighIt<'a, ID>;
fn neigh_iter(&self, u: Self::Node<'_>) -> Self::NeighIt<'_> {
let uid = u.index();
let beg = self.nodes[uid].firstout.to_usize().unwrap();
let end = self
.nodes
.get(uid + 1)
.map(|n| n.firstout.to_usize().unwrap())
.unwrap_or_else(|| self.adj.len());
NeighIt(self.adj[beg..end].iter())
}
}
impl<ID> Directed for VecGraph<ID>
where
ID: PrimInt + Unsigned + 'static,
{
type OutIt<'a> = NeighIt<'a, ID>;
type InIt<'a> = NeighIt<'a, ID>;
type IncidentIt<'a> = NeighIt<'a, ID>;
type DirectedEdge<'a> = Self::Edge<'a>;
fn out_iter(&self, u: Self::Node<'_>) -> Self::OutIt<'_> {
let uid = u.index();
let beg = self.nodes[uid].firstout.to_usize().unwrap();
let end = self.nodes[uid].firstin.to_usize().unwrap();
NeighIt(self.adj[beg..end].iter())
}
fn in_iter(&self, u: Self::Node<'_>) -> Self::InIt<'_> {
let uid = u.index();
let beg = self.nodes[uid].firstin.to_usize().unwrap();
let end = self
.nodes
.get(uid + 1)
.map(|n| n.firstout.to_usize().unwrap())
.unwrap_or_else(|| self.adj.len());
NeighIt(self.adj[beg..end].iter())
}
fn incident_iter(&self, u: Self::Node<'_>) -> Self::IncidentIt<'_> {
self.neigh_iter(u)
}
}
impl<ID> IndexGraph for VecGraph<ID>
where
ID: PrimInt + Unsigned + 'static,
{
fn node_id(&self, u: Self::Node<'_>) -> usize {
u.index()
}
fn id2node(&self, id: usize) -> Self::Node<'_> {
debug_assert!(id < self.nodes.len(), "Invalid node id");
Node(ID::from(id).unwrap())
}
fn edge_id(&self, e: Self::Edge<'_>) -> usize {
e.index()
}
fn id2edge(&self, id: usize) -> Self::Edge<'_> {
debug_assert!(
id < self.edges.len(),
"Invalid edge id: {}({}), must be in 0..{}",
id,
id << 1,
self.edges.len()
);
Edge(ID::from(id << 1).unwrap())
}
}
pub struct VecGraphBuilder<ID> {
nodes: Vec<[Vec<ID>; 2]>,
edges: Vec<EdgeData<ID>>,
}
impl<ID> Builder for VecGraphBuilder<ID>
where
ID: PrimInt + Unsigned,
{
type Graph = VecGraph<ID>;
type Node = Node<ID>;
type Edge = Edge<ID>;
fn with_capacities(nnodes: usize, nedges: usize) -> Self {
VecGraphBuilder {
nodes: Vec::with_capacity(nnodes),
edges: Vec::with_capacity(nedges),
}
}
fn reserve(&mut self, nnodes: usize, nedges: usize) {
self.nodes.reserve(nnodes);
self.edges.reserve(nedges);
}
fn num_nodes(&self) -> usize {
self.nodes.len()
}
fn num_edges(&self) -> usize {
self.edges.len()
}
fn add_node(&mut self) -> Self::Node {
assert!(
self.nodes.len() + 1 < ID::max_value().to_usize().unwrap(),
"Node capacity exceeded"
);
let id = self.nodes.len();
self.nodes.push([vec![], vec![]]);
Node(ID::from(id).unwrap())
}
fn add_edge(&mut self, u: Self::Node, v: Self::Node) -> Self::Edge {
assert!(
self.edges.len() * 2 + 2 < ID::max_value().to_usize().unwrap(),
"Edge capacity exceeded"
);
let eid = ID::from(self.edges.len() << 1).unwrap();
self.edges.push(EdgeData { nodes: [u.0, v.0] });
self.nodes[u.index()][0].push(eid);
self.nodes[v.index()][1].push(eid | ID::one());
Edge(eid)
}
fn node2id(&self, u: Self::Node) -> usize {
u.index()
}
fn edge2id(&self, e: Self::Edge) -> usize {
e.index()
}
fn id2node(&self, uid: usize) -> Self::Node {
Node(ID::from(uid).unwrap())
}
fn id2edge(&self, eid: usize) -> Self::Edge {
Edge(ID::from(eid << 1).unwrap())
}
fn into_graph(self) -> VecGraph<ID> {
let mut nodes = Vec::with_capacity(self.nodes.len());
let mut adj = Vec::with_capacity(self.edges.len() * 2);
for [outs, ins] in self.nodes.into_iter() {
nodes.push(NodeData {
firstout: ID::from(adj.len()).unwrap(),
firstin: ID::from(adj.len() + outs.len()).unwrap(),
});
adj.extend(outs);
adj.extend(ins);
}
VecGraph {
nodes,
edges: self.edges,
adj,
}
}
}
impl<ID> Buildable for VecGraph<ID>
where
ID: PrimInt + Unsigned,
{
type Builder = VecGraphBuilder<ID>;
}
impl<ID> VecGraph<ID>
where
ID: PrimInt + Unsigned,
{
pub fn new() -> VecGraph<ID> {
VecGraph {
nodes: vec![],
edges: vec![],
adj: vec![],
}
}
}
impl<ID> Default for VecGraph<ID>
where
ID: PrimInt + Unsigned,
{
fn default() -> Self {
VecGraph::new()
}
}
#[cfg(test)]
mod tests {
use crate::classes::*;
use crate::traits::Indexable;
use crate::traits::*;
use crate::VecGraph;
use std::cmp::{max, min};
#[test]
fn test_graph() {
const N: usize = 7;
let g = cycle::<VecGraph>(N);
assert_eq!(g.num_nodes(), N);
assert_eq!(g.num_edges(), N);
let mut balances = vec![0; g.num_nodes()];
for u in g.nodes() {
balances[g.node_id(u)] = u.index();
}
for u in g.nodes() {
assert_eq!(balances[g.node_id(u)], u.index());
}
for u in g.nodes() {
let mut neighs: Vec<_> = g.neighs(u).collect();
for &(e, v) in &neighs {
eprintln!(
"{} {}->{} {}-{}",
e.index(),
u.index(),
v.index(),
g.enodes(e).0.index(),
g.enodes(e).1.index()
);
assert!((g.enodes(e) == (u, v)) || (g.enodes(e) == (v, u)));
}
neighs.sort_by_key(|&(_, u)| u.index());
let x = (u.index() + N - 1) % N;
let y = (u.index() + 1) % N;
assert_eq!(
neighs.iter().map(|&(_, v)| v).collect::<Vec<_>>(),
vec![g.id2node(min(x, y)), g.id2node(max(x, y))]
);
}
}
#[test]
fn test_edge_vec() {
let g = cycle::<VecGraph>(7);
let mut x = vec![0; g.num_edges()];
for (i, e) in g.edges().enumerate() {
x[g.edge_id(e)] = i;
}
for u in g.nodes() {
for (e, _) in g.neighs(u) {
assert_eq!(x[g.edge_id(e)], e.index());
}
}
}
#[test]
fn test_digraph() {
for g in [cycle::<VecGraph>(7), peterson(), hypercube(5)].iter() {
for u in g.nodes() {
for (e, v) in g.outedges(u) {
assert_eq!(u, g.src(e));
assert_eq!(v, g.snk(e));
}
for (e, v) in g.inedges(u) {
assert_eq!(v, g.src(e));
assert_eq!(u, g.snk(e));
}
for (e, v) in g.incident_edges(u) {
assert_eq!(
v,
if e.is_incoming() {
g.src(e.edge())
} else {
g.snk(e.edge())
}
);
}
}
}
}
#[cfg(feature = "serialize")]
mod serialize {
use super::VecGraph;
use crate::classes::peterson;
use crate::traits::{FiniteDigraph, FiniteGraph, IndexGraph};
use serde_json;
#[test]
fn test_serde() {
let g = peterson::<VecGraph>();
let serialized = serde_json::to_string(&g).unwrap();
println!("serialized = {}", serialized);
let h: VecGraph = serde_json::from_str(&serialized).unwrap();
assert_eq!(g.num_nodes(), h.num_nodes());
assert_eq!(g.num_edges(), h.num_edges());
for e in g.edges() {
let f = h.id2edge(g.edge_id(e));
assert_eq!(g.node_id(g.src(e)), h.node_id(h.src(f)));
assert_eq!(g.node_id(g.snk(e)), h.node_id(h.snk(f)));
}
}
#[test]
fn test_serialize() {
use crate::{Buildable, Builder};
let g = VecGraph::<u32>::new_with(|b| {
let nodes = b.add_nodes(5);
b.add_edge(nodes[0], nodes[1]);
b.add_edge(nodes[0], nodes[2]);
b.add_edge(nodes[1], nodes[4]);
b.add_edge(nodes[2], nodes[3]);
});
let serialized = serde_json::to_string(&g).unwrap();
let g2: VecGraph<u32> = serde_json::from_str(&serialized).unwrap();
assert_eq!(g.num_nodes(), g2.num_nodes());
let mut edges = g2
.edges()
.map(|e| {
let (u, v) = g2.enodes(e);
let (u, v) = (g2.node_id(u), g2.node_id(v));
(u.min(v), u.max(v))
})
.collect::<Vec<_>>();
edges.sort();
assert_eq!(edges, vec![(0, 1), (0, 2), (1, 4), (2, 3)]);
}
}
}