use crate::attributes::{EdgeAttributes, NodeAttributes};
use crate::builder::{Buildable, Builder};
use crate::traits::{Directed, DirectedEdge, GraphSize, 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};
#[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))]
pub struct LinkedListGraph<ID = u32, N = (), E = ()> {
nodes: Vec<NodeData<ID, N>>,
edges: Vec<EdgeData<ID, E>>,
}
#[cfg_attr(feature = "serialize", derive(Serialize, Deserialize))]
struct NodeData<ID, N> {
first_out: ID,
first_in: ID,
attrs: N,
}
#[cfg_attr(feature = "serialize", derive(Serialize, Deserialize))]
struct EdgeData<ID, E> {
snk: ID,
next: ID,
eattrs: E,
}
pub struct NeighIter<'a, ID, E> {
edge: ID,
edges: &'a [EdgeData<ID, E>],
}
impl<'a, ID, E> Iterator for NeighIter<'a, ID, E>
where
ID: PrimInt + Unsigned,
{
type Item = (Edge<ID>, Node<ID>);
fn next(&mut self) -> Option<Self::Item> {
if self.edge != ID::max_value() {
let edge = self.edge;
self.edge = self.edges[edge.to_usize().unwrap()].next;
Some((Edge(edge), Node(self.edges[edge.to_usize().unwrap()].snk)))
} else {
None
}
}
}
pub struct OutEdgeIter<'a, ID, E> {
edge: ID,
edges: &'a [EdgeData<ID, E>],
}
impl<'a, ID, E> Iterator for OutEdgeIter<'a, ID, E>
where
ID: PrimInt + Unsigned,
{
type Item = (Edge<ID>, Node<ID>);
fn next(&mut self) -> Option<Self::Item> {
let edge = self.edge;
if (edge & ID::one()).is_zero() {
let e = edge.to_usize().unwrap();
self.edge = self.edges[e].next;
Some((Edge(edge), Node(self.edges[e].snk)))
} else {
None
}
}
}
pub struct NodeIter<ID>(Range<ID>);
impl<ID> Iterator for NodeIter<ID>
where
ID: PrimInt + Unsigned,
{
type Item = Node<ID>;
fn next(&mut self) -> Option<Self::Item> {
self.0.next().map(Node)
}
fn size_hint(&self) -> (usize, Option<usize>) {
self.0.size_hint()
}
}
pub struct EdgeIter<ID>(RangeStep<ID>);
impl<ID> Iterator for EdgeIter<ID>
where
ID: PrimInt + Unsigned,
{
type Item = Edge<ID>;
fn next(&mut self) -> Option<Self::Item> {
self.0.next().map(Edge)
}
fn size_hint(&self) -> (usize, Option<usize>) {
self.0.size_hint()
}
}
impl<'a, ID, N, E> GraphType<'a> for LinkedListGraph<ID, N, E>
where
ID: 'a + PrimInt + Unsigned,
{
type Node = Node<ID>;
type Edge = Edge<ID>;
}
impl<'a, ID, N, E> GraphSize<'a> for LinkedListGraph<ID, N, E>
where
ID: 'a + PrimInt + Unsigned,
{
type NodeIter = NodeIter<ID>;
type EdgeIter = EdgeIter<ID>;
fn num_nodes(&self) -> usize {
self.nodes.len()
}
fn num_edges(&self) -> usize {
self.edges.len() / 2
}
fn nodes(&'a self) -> Self::NodeIter {
NodeIter(range(ID::zero(), ID::from(self.num_nodes()).unwrap()))
}
fn edges(&self) -> Self::EdgeIter {
EdgeIter(range_step(
ID::zero(),
ID::from(self.edges.len()).unwrap(),
ID::from(2).unwrap(),
))
}
}
impl<'a, ID, N: 'a, E: 'a> Undirected<'a> for LinkedListGraph<ID, N, E>
where
ID: 'a + PrimInt + Unsigned,
{
type NeighIter = NeighIter<'a, ID, E>;
fn enodes(&self, e: Self::Edge) -> (Self::Node, Self::Node) {
let eid = e.0.to_usize().unwrap();
(Node(self.edges[eid | 1].snk), Node(self.edges[eid & !1].snk))
}
fn neighs(&'a self, u: Self::Node) -> Self::NeighIter {
let u = &self.nodes[u.index()];
NeighIter {
edge: if u.first_out < ID::max_value() {
u.first_out
} else {
u.first_in
},
edges: &self.edges,
}
}
}
impl<'a, ID, N: 'a, E: 'a> Directed<'a> for LinkedListGraph<ID, N, E>
where
ID: 'a + PrimInt + Unsigned,
{
type OutEdgeIter = OutEdgeIter<'a, ID, E>;
type InEdgeIter = NeighIter<'a, ID, E>;
type IncidentIter = NeighIter<'a, ID, E>;
type DirectedEdge = Self::Edge;
fn src(&self, e: Self::Edge) -> Self::Node {
Node(self.edges[e.0.to_usize().unwrap() | 1].snk)
}
fn snk(&self, e: Self::Edge) -> Self::Node {
Node(self.edges[e.0.to_usize().unwrap() & !1].snk)
}
fn outedges(&'a self, u: Self::Node) -> Self::OutEdgeIter {
OutEdgeIter {
edge: self.nodes[u.index()].first_out,
edges: &self.edges,
}
}
fn inedges(&'a self, u: Self::Node) -> Self::InEdgeIter {
NeighIter {
edge: self.nodes[u.index()].first_in,
edges: &self.edges,
}
}
fn incident_edges(&'a self, u: Self::Node) -> Self::IncidentIter {
self.neighs(u)
}
}
impl<'a, ID, N: 'a, E: 'a> IndexGraph<'a> for LinkedListGraph<ID, N, E>
where
ID: 'a + PrimInt + Unsigned,
{
fn node_id(&self, u: Self::Node) -> usize {
u.index()
}
fn id2node(&self, id: usize) -> Self::Node {
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 {
assert!(id << 1 < self.edges.len(), "Invalid edge id");
Edge(ID::from(id << 1).unwrap())
}
}
impl<'a, ID, N: 'a, E: 'a> NodeAttributes<'a, LinkedListGraph<ID, N, E>, N> for LinkedListGraph<ID, N, E>
where
ID: 'a + PrimInt + Unsigned,
{
fn node(&self, u: <Self as GraphType<'a>>::Node) -> &N {
&self.nodes[u.index()].attrs
}
fn node_mut(&mut self, u: <Self as GraphType<'a>>::Node) -> &mut N {
&mut self.nodes[u.index()].attrs
}
}
impl<'a, ID, N: 'a, E: 'a> EdgeAttributes<'a, LinkedListGraph<ID, N, E>, E> for LinkedListGraph<ID, N, E>
where
ID: 'a + PrimInt + Unsigned,
{
fn edge(&self, e: <Self as GraphType<'a>>::Edge) -> &E {
&self.edges[e.index()].eattrs
}
fn edge_mut(&mut self, e: <Self as GraphType<'a>>::Edge) -> &mut E {
&mut self.edges[e.index()].eattrs
}
}
pub struct LinkedListGraphBuilder<ID, N, E> {
graph: LinkedListGraph<ID, N, E>,
last_out: Vec<Option<ID>>,
}
impl<ID, N, E> Builder for LinkedListGraphBuilder<ID, N, E>
where
ID: PrimInt + Unsigned,
N: Default,
E: Default,
{
type Graph = LinkedListGraph<ID, N, E>;
type Node = Node<ID>;
type Edge = Edge<ID>;
fn with_capacities(nnodes: usize, nedges: usize) -> Self {
LinkedListGraphBuilder {
graph: LinkedListGraph {
nodes: Vec::with_capacity(nnodes),
edges: Vec::with_capacity(nedges),
},
last_out: Vec::with_capacity(nnodes),
}
}
fn reserve(&mut self, nnodes: usize, nedges: usize) {
self.graph.nodes.reserve(nnodes);
self.graph.edges.reserve(nedges);
self.last_out.reserve(nnodes);
}
fn num_nodes(&self) -> usize {
self.graph.nodes.len()
}
fn num_edges(&self) -> usize {
self.graph.edges.len() / 2
}
fn add_node(&mut self) -> Self::Node {
assert!(
self.graph.nodes.len() + 1 < ID::max_value().to_usize().unwrap(),
"Node capacity exceeded"
);
let id = self.graph.nodes.len();
self.graph.nodes.push(NodeData {
first_out: ID::max_value(),
first_in: ID::max_value(),
attrs: Default::default(),
});
self.last_out.push(None);
Node(ID::from(id).unwrap())
}
fn add_edge(&mut self, u: Self::Node, v: Self::Node) -> Self::Edge {
assert!(
self.graph.edges.len() + 2 < ID::max_value().to_usize().unwrap(),
"Edge capacity exceeded"
);
let eid = ID::from(self.graph.edges.len()).unwrap();
let uid = u.0.to_usize().unwrap();
let vid = v.0.to_usize().unwrap();
self.graph.edges.push(EdgeData {
snk: v.0,
next: self.graph.nodes[uid].first_out,
eattrs: Default::default(),
});
self.graph.edges.push(EdgeData {
snk: u.0,
next: self.graph.nodes[vid].first_in,
eattrs: Default::default(),
});
self.graph.nodes[uid].first_out = eid;
self.graph.nodes[vid].first_in = eid + ID::one();
if self.last_out[uid].is_none() {
self.last_out[uid] = Some(eid);
}
Edge(eid)
}
fn node2id(&self, u: Self::Node) -> usize {
IndexGraph::node_id(&self.graph, u)
}
fn edge2id(&self, e: Self::Edge) -> usize {
IndexGraph::edge_id(&self.graph, e)
}
fn to_graph(self) -> LinkedListGraph<ID, N, E> {
let mut g = self.graph;
for (u, e) in self
.last_out
.into_iter()
.enumerate()
.filter_map(|(u, e)| e.map(|e| (u, e)))
{
g.edges[e.to_usize().unwrap()].next = g.nodes[u].first_in;
}
g
}
}
impl<ID, N, E> Buildable for LinkedListGraph<ID, N, E>
where
ID: PrimInt + Unsigned,
N: Default,
E: Default,
{
type Builder = LinkedListGraphBuilder<ID, N, E>;
}
impl<ID, N, E> LinkedListGraph<ID, N, E>
where
ID: PrimInt + Unsigned,
{
pub fn new() -> LinkedListGraph<ID, N, E> {
LinkedListGraph {
nodes: vec![],
edges: vec![],
}
}
}
impl<ID, N, E> Default for LinkedListGraph<ID, N, E>
where
ID: PrimInt + Unsigned,
{
fn default() -> Self {
LinkedListGraph::new()
}
}
#[cfg(test)]
mod tests {
use crate::attributes::*;
use crate::classes::*;
use crate::traits::Indexable;
use crate::traits::*;
use crate::vec::{EdgeVec, NodeVec};
use crate::LinkedListGraph;
use std::cmp::{max, min};
#[test]
fn test_graph() {
const N: usize = 7;
let g = cycle::<LinkedListGraph>(N);
assert_eq!(g.num_nodes(), N);
assert_eq!(g.num_edges(), N);
let mut balances = NodeVec::new(&g, 0);
for u in g.nodes() {
balances[u] = u.index();
}
for u in g.nodes() {
assert_eq!(balances[u], u.index());
}
for u in g.nodes() {
let mut neighs: Vec<_> = g.neighs(u).collect();
for &(e, v) in &neighs {
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::<LinkedListGraph>(7);
let mut x = EdgeVec::new(&g, 0);
for (i, e) in g.edges().enumerate() {
x[e] = i;
}
for u in g.nodes() {
for (e, _) in g.neighs(u) {
assert_eq!(x[e], e.index());
}
}
}
#[test]
fn test_digraph() {
for g in [cycle::<LinkedListGraph>(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())
}
);
}
}
}
}
#[test]
fn test_attrs() {
#[derive(Default)]
struct NodeData {
balance: usize,
}
#[derive(Default)]
struct EdgeData {
upper: usize,
}
let mut g = peterson::<LinkedListGraph<u32, NodeData, EdgeData>>();
for u in g.nodes() {
g.node_mut(u).balance = u.index();
}
for e in g.edges() {
let uid = g.node_id(g.src(e));
g.edge_mut(e).upper = uid;
}
for u in g.nodes() {
assert_eq!(g.node(u).balance, g.node_id(u));
for (e, _) in g.outedges(u) {
assert_eq!(g.edge(e).upper, g.node_id(g.src(e)));
}
for (e, _) in g.inedges(u) {
assert_eq!(g.edge(e).upper, g.node_id(g.src(e)));
}
}
}
#[cfg(feature = "serialize")]
mod serialize {
use super::LinkedListGraph;
use crate::classes::peterson;
use crate::traits::{Directed, GraphSize, IndexGraph, Undirected};
use serde_json;
#[test]
fn test_serde() {
let g = peterson::<LinkedListGraph>();
let serialized = serde_json::to_string(&g).unwrap();
println!("serialized = {}", serialized);
let h: LinkedListGraph = 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 = LinkedListGraph::<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: LinkedListGraph<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)]);
}
}
}