pub use crate::node::NodeTrait;
use crate::edge::{AllEdges, CompactDirection, Direction, EdgeType, Edges, IntoWeightedEdge};
use crate::node::Nodes;
use crate::traverse::{Neighbors, NeighborsDirected};
use indexmap::IndexMap;
use std::fmt;
use std::hash::Hash;
use std::iter::FromIterator;
use std::marker::PhantomData;
#[derive(Copy, Debug)]
pub enum Directed {}
copyclone!(Directed);
#[derive(Copy, Debug)]
pub enum Undirected {}
copyclone!(Undirected);
pub type UndirectedGraph<N, E> = Graph<N, E, Undirected>;
#[derive(Clone)]
pub struct Graph<N, E, Ty = Directed> {
nodes: IndexMap<N, Vec<(N, CompactDirection)>>,
edges: IndexMap<(N, N), E>,
ty: PhantomData<Ty>,
}
impl<N: Eq + Hash + fmt::Debug, E: fmt::Debug, Ty: EdgeType> fmt::Debug for Graph<N, E, Ty> {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
self.nodes.fmt(f)
}
}
impl<N, E, Ty> Graph<N, E, Ty>
where
N: NodeTrait,
Ty: EdgeType,
{
pub fn new() -> Self {
Self::default()
}
pub fn with_capacity(nodes: usize, edges: usize) -> Self {
Self {
nodes: IndexMap::with_capacity(nodes),
edges: IndexMap::with_capacity(edges),
ty: PhantomData,
}
}
pub fn capacity(&self) -> (usize, usize) {
(self.nodes.capacity(), self.edges.capacity())
}
#[inline]
pub fn edge_key(a: N, b: N) -> (N, N) {
if Ty::is_directed() || a <= b {
(a, b)
} else {
(b, a)
}
}
pub fn is_directed(&self) -> bool {
Ty::is_directed()
}
pub fn from_edges<I>(iterable: I) -> Self
where
I: IntoIterator,
I::Item: IntoWeightedEdge<E, NodeId = N>,
{
Self::from_iter(iterable)
}
pub fn node_count(&self) -> usize {
self.nodes.len()
}
pub fn edge_count(&self) -> usize {
self.edges.len()
}
pub fn clear(&mut self) {
self.nodes.clear();
self.edges.clear();
}
pub fn add_node(&mut self, n: N) -> N {
self.nodes.entry(n).or_insert(Vec::new());
n
}
pub fn contains_node(&self, n: N) -> bool {
self.nodes.contains_key(&n)
}
pub fn add_edge(&mut self, a: N, b: N, weight: E) -> Option<E> {
if let old @ Some(_) = self.edges.insert(Self::edge_key(a, b), weight) {
old
} else {
self.nodes
.entry(a)
.or_insert_with(|| Vec::with_capacity(1))
.push((b, CompactDirection::Outgoing));
if a != b {
self.nodes
.entry(b)
.or_insert_with(|| Vec::with_capacity(1))
.push((a, CompactDirection::Incoming));
}
None
}
}
pub fn contains_edge(&self, a: N, b: N) -> bool {
self.edges.contains_key(&Self::edge_key(a, b))
}
pub fn nodes(&self) -> Nodes<N> {
Nodes::new(self.nodes.keys().cloned())
}
pub fn neighbors(&self, a: N) -> Neighbors<N, Ty> {
let iter = match self.nodes.get(&a) {
Some(neigh) => neigh.iter(),
None => [].iter(),
};
Neighbors::new(iter, self.ty)
}
pub fn neighbors_directed(&self, a: N, dir: Direction) -> NeighborsDirected<N, Ty> {
let iter = match self.nodes.get(&a) {
Some(neigh) => neigh.iter(),
None => [].iter(),
};
NeighborsDirected::new(iter, dir, self.ty)
}
pub fn edges(&self, from: N) -> Edges<N, E, Ty> {
Edges::new(from, &self.edges, self.neighbors(from))
}
pub fn edge_weight(&self, a: N, b: N) -> Option<&E> {
self.edges.get(&Self::edge_key(a, b))
}
pub fn edge_weight_mut(&mut self, a: N, b: N) -> Option<&mut E> {
self.edges.get_mut(&Self::edge_key(a, b))
}
pub fn all_edges(&self) -> AllEdges<N, E, Ty> {
AllEdges::new(self.edges.iter(), self.ty)
}
}
impl<N, E, Ty> Default for Graph<N, E, Ty>
where
N: NodeTrait,
Ty: EdgeType,
{
fn default() -> Self {
Graph::with_capacity(0, 0)
}
}
impl<N, E, Ty, Item> FromIterator<Item> for Graph<N, E, Ty>
where
Item: IntoWeightedEdge<E, NodeId = N>,
N: NodeTrait,
Ty: EdgeType,
{
fn from_iter<I>(iterable: I) -> Self
where
I: IntoIterator<Item = Item>,
{
let iter = iterable.into_iter();
let (low, _) = iter.size_hint();
let mut g = Self::with_capacity(0, low);
g.extend(iter);
g
}
}
impl<N, E, Ty, Item> Extend<Item> for Graph<N, E, Ty>
where
Item: IntoWeightedEdge<E, NodeId = N>,
N: NodeTrait,
Ty: EdgeType,
{
fn extend<I>(&mut self, iterable: I)
where
I: IntoIterator<Item = Item>,
{
let iter = iterable.into_iter();
let (low, _) = iter.size_hint();
self.edges.reserve(low);
for elt in iter {
let (source, target, weight) = elt.into_weighted_edge();
self.add_edge(source, target, weight);
}
}
}
#[cfg(test)]
mod tests {
use crate::edge::Direction::{Incoming, Outgoing};
use crate::graph::{Directed, Graph, Undirected};
#[test]
fn new() {
let graph: Graph<&str, f32> = Graph::new();
assert_eq!(graph.node_count(), 0);
assert_eq!(graph.edge_count(), 0);
}
#[test]
fn new_with_tuple_as_node() {
let graph: Graph<(&str, &str), f32> = Graph::new();
assert_eq!(graph.node_count(), 0);
assert_eq!(graph.edge_count(), 0);
}
#[test]
fn with_capacity() {
let graph: Graph<&str, f32> = Graph::with_capacity(4, 6);
assert_eq!(graph.node_count(), 0);
assert_eq!(graph.edge_count(), 0);
}
#[test]
fn capacity() {
let nodes_capacity = 4;
let edges_capacity = 8;
let graph: Graph<&str, f32> = Graph::with_capacity(nodes_capacity, edges_capacity);
let (n, e) = graph.capacity();
assert!(
n >= nodes_capacity,
"Allocated nodes capacity `{}` must be equal or bigger then requested capacity `{}`.",
n,
nodes_capacity
);
assert!(
e >= edges_capacity,
"Allocated edges capacity `{}` must be equal or bigger then requested capacity `{}`.",
e,
edges_capacity
);
}
#[test]
fn edge_key() {
assert_eq!(Graph::<&str, f32, Directed>::edge_key("a", "b"), ("a", "b"));
assert_eq!(Graph::<&str, f32, Directed>::edge_key("b", "a"), ("b", "a"));
assert_eq!(
Graph::<&str, f32, Undirected>::edge_key("a", "b"),
("a", "b")
);
assert_eq!(
Graph::<&str, f32, Undirected>::edge_key("b", "a"),
("a", "b")
);
}
#[test]
fn is_directed_true() {
let graph: Graph<&str, f32, Directed> = Graph::new();
assert_eq!(graph.is_directed(), true)
}
#[test]
fn is_directed_false() {
let graph: Graph<&str, f32, Undirected> = Graph::new();
assert_eq!(graph.is_directed(), false)
}
#[test]
fn from_edges() {
let graph = Graph::<_, _>::from_edges(&[
(0, 1, 0.12),
(0, 2, 0.99),
(0, 3, 0.1),
(1, 2, 0.9),
(1, 3, 0.44),
(2, 3, 0.8),
]);
assert_eq!(graph.node_count(), 4);
assert_eq!(graph.edge_count(), 6);
assert_eq!(graph.edge_weight(0, 1), Some(&0.12));
assert_eq!(graph.edge_weight(2, 3), Some(&0.8));
}
#[test]
fn node_count() {
let mut graph: Graph<&str, f32> = Graph::new();
assert_eq!(graph.node_count(), 0);
graph.add_node("a");
graph.add_node("b");
assert_eq!(graph.node_count(), 2);
}
#[test]
fn edge_count() {
let mut graph: Graph<&str, f32> = Graph::new();
assert_eq!(graph.edge_count(), 0);
graph.add_edge("a", "b", 2.3);
graph.add_edge("b", "c", 4.1);
assert_eq!(graph.edge_count(), 2);
}
#[test]
fn clear() {
let mut graph: Graph<&str, f32> = Graph::new();
graph.add_edge("a", "b", 2.3);
assert_eq!(graph.node_count(), 2);
assert_eq!(graph.edge_count(), 1);
graph.clear();
assert_eq!(graph.node_count(), 0);
assert_eq!(graph.edge_count(), 0);
}
#[test]
fn add_node() {
let mut graph: Graph<&str, f32> = Graph::new();
graph.add_node("a");
assert_eq!(graph.node_count(), 1);
}
#[test]
fn add_node_as_tuple() {
let mut graph: Graph<(&str, &str), f32> = Graph::new();
graph.add_node(("s", "a"));
assert_eq!(graph.node_count(), 1);
}
#[test]
fn add_node_as_tuple_twide() {
let mut graph: Graph<(&str, &str), f32> = Graph::new();
graph.add_node(("s", "a"));
graph.add_node(("s", "a"));
assert_eq!(graph.node_count(), 1);
}
#[test]
fn add_edge() {
let mut graph: Graph<&str, f32> = Graph::new();
graph.add_edge("a", "b", 2.3);
assert_eq!(graph.node_count(), 2);
assert_eq!(graph.edge_count(), 1);
}
#[test]
fn add_edge_with_nodes_as_tuples() {
let mut graph: Graph<(&str, &str), f32> = Graph::new();
graph.add_edge(("s", "a"), ("r", "b"), 2.3);
assert_eq!(graph.node_count(), 2);
assert_eq!(graph.edge_count(), 1);
}
#[test]
fn edge_weight() {
let mut graph: Graph<&str, f32> = Graph::new();
let edge_weight = 2.4;
graph.add_edge("a", "b", edge_weight);
assert_eq!(graph.edge_weight("a", "b"), Some(&edge_weight));
}
#[test]
fn edge_weight_mut() {
let mut graph: Graph<&str, f32> = Graph::new();
let mut edge_weight = 2.4;
graph.add_edge("a", "b", edge_weight);
assert_eq!(graph.edge_weight_mut("a", "b"), Some(&mut edge_weight));
}
#[test]
fn edge_weight_with_nodes_as_tuples() {
let mut graph: Graph<(&str, &str), f32> = Graph::new();
let edge_weight = 2.4;
graph.add_edge(("s", "a"), ("r", "a"), 8.0);
graph.add_edge(("s", "a"), ("r", "a"), edge_weight);
assert_eq!(
graph.edge_weight(("s", "a"), ("r", "a")),
Some(&edge_weight)
);
}
#[test]
fn nodes() {
let mut graph: Graph<&str, f32> = Graph::new();
let list = ["a", "b", "c", "d"];
for index in list.iter() {
graph.add_node(*index);
}
for (i, node) in graph.nodes().enumerate() {
assert_eq!(list[i], node);
}
}
#[test]
fn check_nodes_and_edges() {
let mut graph: Graph<&str, f32> = Graph::with_capacity(4, 6);
graph.add_edge("a", "b", 2.0);
assert_eq!(graph.node_count(), 2);
assert_eq!(graph.edge_count(), 1);
assert!(graph.contains_edge("a", "b"));
assert!(!graph.contains_edge("b", "a"));
graph.add_edge("a", "c", 1.2);
graph.add_edge("a", "d", 4.2);
graph.add_edge("b", "c", 0.2);
graph.add_edge("b", "d", 3.3);
graph.add_edge("c", "b", 12.2);
assert_eq!(graph.node_count(), 4);
assert_eq!(graph.edge_count(), 6);
assert_eq!(graph.edge_weight("a", "b"), Some(&2.0));
assert_eq!(graph.edge_weight("a", "c"), Some(&1.2));
graph.add_edge("a", "b", 4.4);
assert_eq!(graph.edge_weight("a", "b"), Some(&4.4));
let weight = graph.edge_weight("c", "d");
assert_eq!(weight, None);
}
#[test]
fn fmt() {
let mut graph: Graph<u32, f32> = Graph::with_capacity(2, 1);
graph.add_edge(1, 2, 2.0);
let _text = print!("Debug::fmt() result:{:?}", graph);
}
#[test]
fn contains_node() {
let mut graph: Graph<u32, f32> = Graph::with_capacity(2, 0);
graph.add_node(1);
graph.add_node(2);
assert_eq!(graph.contains_node(1), true);
assert_eq!(graph.contains_node(2), true);
assert_eq!(graph.contains_node(3), false);
}
#[test]
fn contains_edge() {
let mut graph: Graph<u32, f32> = Graph::with_capacity(2, 1);
graph.add_edge(1, 2, 2.0);
assert_eq!(graph.contains_edge(1, 2), true);
assert_eq!(graph.contains_edge(1, 3), false);
}
#[test]
fn edges() {
let mut graph: Graph<u32, f32> = Graph::with_capacity(3, 3);
graph.add_edge(1, 2, 3.0);
graph.add_edge(2, 3, 5.0);
graph.add_edge(1, 3, 4.0);
let mut edges = graph.edges(1);
assert_eq!(edges.next(), Some((1, 2, &3.0)));
assert_eq!(edges.next(), Some((1, 3, &4.0)));
assert_eq!(edges.next(), None);
}
#[test]
fn all_edges() {
let mut graph: Graph<u32, f32> = Graph::with_capacity(3, 3);
graph.add_edge(1, 2, 3.0);
graph.add_edge(2, 3, 5.0);
graph.add_edge(1, 3, 4.0);
let mut edges = graph.all_edges();
assert_eq!(edges.next(), Some((1, 2, &3.0)));
assert_eq!(edges.next(), Some((2, 3, &5.0)));
assert_eq!(edges.next(), Some((1, 3, &4.0)));
assert_eq!(edges.next(), None);
}
#[test]
fn neighbors() {
let mut graph: Graph<u32, f32> = Graph::with_capacity(3, 3);
graph.add_edge(1, 2, 3.0);
graph.add_edge(2, 3, 5.0);
graph.add_edge(1, 3, 4.0);
let mut neighbors_1 = graph.neighbors(1);
assert_eq!(neighbors_1.next(), Some(2));
assert_eq!(neighbors_1.next(), Some(3));
assert_eq!(neighbors_1.next(), None);
let mut neighbors_2 = graph.neighbors(2);
assert_eq!(neighbors_2.next(), Some(3));
assert_eq!(neighbors_2.next(), None);
let mut neighbors_3 = graph.neighbors(3);
assert_eq!(neighbors_3.next(), None);
let mut neighbors_4 = graph.neighbors(4);
assert_eq!(neighbors_4.next(), None);
}
#[test]
fn neighbors_directed() {
let mut graph: Graph<u32, f32> = Graph::with_capacity(3, 3);
graph.add_edge(1, 2, 3.0);
graph.add_edge(2, 3, 5.0);
graph.add_edge(1, 3, 4.0);
let mut neighbors_1_incoming = graph.neighbors_directed(1, Incoming);
assert_eq!(neighbors_1_incoming.next(), None);
let mut neighbors_1_outgoing = graph.neighbors_directed(1, Outgoing);
assert_eq!(neighbors_1_outgoing.next(), Some(2));
assert_eq!(neighbors_1_outgoing.next(), Some(3));
assert_eq!(neighbors_1_outgoing.next(), None);
let mut neighbors_2_incoming = graph.neighbors_directed(2, Incoming);
assert_eq!(neighbors_2_incoming.next(), Some(1));
assert_eq!(neighbors_2_incoming.next(), None);
let mut neighbors_2_outgoing = graph.neighbors_directed(2, Outgoing);
assert_eq!(neighbors_2_outgoing.next(), Some(3));
assert_eq!(neighbors_2_outgoing.next(), None);
let mut neighbors_4 = graph.neighbors_directed(4, Incoming);
assert_eq!(neighbors_4.next(), None);
}
}