use indexmap::map::Keys;
use indexmap::map::{Iter as IndexMapIter, IterMut as IndexMapIterMut};
use indexmap::IndexMap;
use std::cmp::Ordering;
use std::collections::hash_map::RandomState;
use std::collections::HashSet;
use std::fmt;
use std::hash::{self, BuildHasher, Hash};
use std::iter::Copied;
use std::iter::FromIterator;
use std::marker::PhantomData;
use std::mem;
use std::ops::{Deref, Index, IndexMut};
use std::slice::Iter;
use crate::{Directed, Direction, EdgeType, Incoming, Outgoing, Undirected};
use crate::graph::node_index;
use crate::graph::Graph;
use crate::visit;
use crate::IntoWeightedEdge;
#[cfg(feature = "rayon")]
use indexmap::map::rayon::{ParIter, ParIterMut, ParKeys};
#[cfg(feature = "rayon")]
use rayon::prelude::*;
pub type UnGraphMap<N, E> = GraphMap<N, E, Undirected>;
pub type DiGraphMap<N, E> = GraphMap<N, E, Directed>;
#[derive(Clone)]
pub struct GraphMap<N, E, Ty, S = RandomState>
where
S: BuildHasher,
{
nodes: IndexMap<N, Vec<(N, CompactDirection)>, S>,
edges: IndexMap<(N, N), E, S>,
ty: PhantomData<Ty>,
}
impl<N: Eq + Hash + fmt::Debug, E: fmt::Debug, Ty: EdgeType, S: BuildHasher> fmt::Debug
for GraphMap<N, E, Ty, S>
{
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
self.nodes.fmt(f)
}
}
pub trait NodeTrait: Copy + Ord + Hash {}
impl<N> NodeTrait for N where N: Copy + Ord + Hash {}
#[derive(Copy, Clone, Debug, PartialEq)]
enum CompactDirection {
Outgoing,
Incoming,
}
impl CompactDirection {
#[inline]
pub fn opposite(self) -> CompactDirection {
match self {
CompactDirection::Outgoing => CompactDirection::Incoming,
CompactDirection::Incoming => CompactDirection::Outgoing,
}
}
}
impl From<Direction> for CompactDirection {
fn from(d: Direction) -> Self {
match d {
Outgoing => CompactDirection::Outgoing,
Incoming => CompactDirection::Incoming,
}
}
}
impl From<CompactDirection> for Direction {
fn from(d: CompactDirection) -> Self {
match d {
CompactDirection::Outgoing => Outgoing,
CompactDirection::Incoming => Incoming,
}
}
}
impl PartialEq<Direction> for CompactDirection {
fn eq(&self, rhs: &Direction) -> bool {
(*self as usize) == (*rhs as usize)
}
}
#[cfg(feature = "serde-1")]
impl<N, E, Ty, S> serde::Serialize for GraphMap<N, E, Ty, S>
where
Ty: EdgeType,
N: NodeTrait + serde::Serialize,
E: serde::Serialize,
S: BuildHasher,
Self: Clone,
{
fn serialize<Ser>(&self, serializer: Ser) -> Result<Ser::Ok, Ser::Error>
where
Ser: serde::Serializer,
{
let cloned_graph: GraphMap<N, E, Ty, S> = GraphMap::clone(self);
let equivalent_graph: Graph<N, E, Ty, u32> = cloned_graph.into_graph();
equivalent_graph.serialize(serializer)
}
}
#[cfg(feature = "serde-1")]
impl<'de, N, E, Ty, S> serde::Deserialize<'de> for GraphMap<N, E, Ty, S>
where
Ty: EdgeType,
N: NodeTrait + serde::Deserialize<'de>,
E: Clone + serde::Deserialize<'de>,
S: BuildHasher + Default,
{
fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
where
D: serde::Deserializer<'de>,
{
let equivalent_graph: Graph<N, E, Ty, u32> = Graph::deserialize(deserializer)?;
Ok(GraphMap::from_graph(equivalent_graph))
}
}
impl<N, E, Ty, S> GraphMap<N, E, Ty, S>
where
N: NodeTrait,
Ty: EdgeType,
S: BuildHasher,
{
pub fn new() -> Self
where
S: Default,
{
Self::default()
}
pub fn with_capacity(nodes: usize, edges: usize) -> Self
where
S: Default,
{
Self {
nodes: IndexMap::with_capacity_and_hasher(nodes, S::default()),
edges: IndexMap::with_capacity_and_hasher(edges, S::default()),
ty: PhantomData,
}
}
pub fn with_capacity_and_hasher(nodes: usize, edges: usize, hasher: S) -> Self
where
S: Clone,
{
Self {
nodes: IndexMap::with_capacity_and_hasher(nodes, hasher.clone()),
edges: IndexMap::with_capacity_and_hasher(edges, hasher),
ty: PhantomData,
}
}
pub fn capacity(&self) -> (usize, usize) {
(self.nodes.capacity(), self.edges.capacity())
}
#[inline]
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>,
S: Default,
{
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_default();
n
}
pub fn remove_node(&mut self, n: N) -> bool {
let links = match self.nodes.swap_remove(&n) {
None => return false,
Some(sus) => sus,
};
for (succ, dir) in links {
let edge = if dir == CompactDirection::Outgoing {
Self::edge_key(n, succ)
} else {
Self::edge_key(succ, n)
};
self.remove_single_edge(&succ, &n, dir.opposite());
self.edges.swap_remove(&edge);
}
true
}
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
}
}
fn remove_single_edge(&mut self, a: &N, b: &N, dir: CompactDirection) -> bool {
match self.nodes.get_mut(a) {
None => false,
Some(sus) => {
if Ty::is_directed() {
match sus.iter().position(|elt| elt == &(*b, dir)) {
Some(index) => {
sus.swap_remove(index);
true
}
None => false,
}
} else {
match sus.iter().position(|elt| &elt.0 == b) {
Some(index) => {
sus.swap_remove(index);
true
}
None => false,
}
}
}
}
}
pub fn remove_edge(&mut self, a: N, b: N) -> Option<E> {
let exist1 = self.remove_single_edge(&a, &b, CompactDirection::Outgoing);
let exist2 = if a != b {
self.remove_single_edge(&b, &a, CompactDirection::Incoming)
} else {
exist1
};
let weight = self.edges.swap_remove(&Self::edge_key(a, b));
debug_assert!(exist1 == exist2 && exist1 == weight.is_some());
weight
}
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 {
iter: self.nodes.keys().copied(),
}
}
#[cfg(feature = "rayon")]
pub fn par_nodes(&self) -> ParNodes<'_, N>
where
N: Send + Sync,
{
ParNodes {
iter: self.nodes.par_keys(),
}
}
pub fn neighbors(&self, a: N) -> Neighbors<N, Ty> {
Neighbors {
iter: match self.nodes.get(&a) {
Some(neigh) => neigh.iter(),
None => [].iter(),
},
ty: self.ty,
}
}
pub fn neighbors_directed(&self, a: N, dir: Direction) -> NeighborsDirected<N, Ty> {
NeighborsDirected {
iter: match self.nodes.get(&a) {
Some(neigh) => neigh.iter(),
None => [].iter(),
},
start_node: a,
dir,
ty: self.ty,
}
}
pub fn edges(&self, a: N) -> Edges<N, E, Ty, S> {
Edges {
from: a,
iter: self.neighbors(a),
edges: &self.edges,
}
}
pub fn edges_directed(&self, a: N, dir: Direction) -> EdgesDirected<N, E, Ty, S> {
EdgesDirected {
from: a,
iter: self.neighbors_directed(a, dir),
dir,
edges: &self.edges,
}
}
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 {
inner: self.edges.iter(),
ty: self.ty,
}
}
pub fn all_edges_mut(&mut self) -> AllEdgesMut<N, E, Ty> {
AllEdgesMut {
inner: self.edges.iter_mut(),
ty: self.ty,
}
}
#[cfg(feature = "rayon")]
pub fn par_all_edges(&self) -> ParAllEdges<N, E, Ty>
where
N: Send + Sync,
E: Sync,
{
ParAllEdges {
inner: self.edges.par_iter(),
ty: PhantomData,
}
}
#[cfg(feature = "rayon")]
pub fn par_all_edges_mut(&mut self) -> ParAllEdgesMut<N, E, Ty>
where
N: Send + Sync,
E: Send,
{
ParAllEdgesMut {
inner: self.edges.par_iter_mut(),
ty: PhantomData,
}
}
pub fn into_graph<Ix>(self) -> Graph<N, E, Ty, Ix>
where
Ix: crate::graph::IndexType,
{
let mut gr = Graph::with_capacity(self.node_count(), self.edge_count());
for (&node, _) in &self.nodes {
gr.add_node(node);
}
for ((a, b), edge_weight) in self.edges {
let ai = self.nodes.get_index_of(&a).unwrap();
let bi = self.nodes.get_index_of(&b).unwrap();
gr.add_edge(node_index(ai), node_index(bi), edge_weight);
}
gr
}
pub fn from_graph<Ix>(graph: Graph<N, E, Ty, Ix>) -> Self
where
Ix: crate::graph::IndexType,
E: Clone,
S: Default,
{
let mut new_graph: GraphMap<N, E, Ty, S> =
GraphMap::with_capacity(graph.node_count(), graph.edge_count());
for node in graph.raw_nodes() {
new_graph.add_node(node.weight);
}
for edge in graph.edge_indices() {
let (a, b) = graph.edge_endpoints(edge).unwrap();
new_graph.add_edge(
*graph.node_weight(a).unwrap(),
*graph.node_weight(b).unwrap(),
graph.edge_weight(edge).unwrap().clone(),
);
}
new_graph
}
}
impl<N, E, Ty, Item, S> FromIterator<Item> for GraphMap<N, E, Ty, S>
where
Item: IntoWeightedEdge<E, NodeId = N>,
N: NodeTrait,
Ty: EdgeType,
S: BuildHasher + Default,
{
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, S> Extend<Item> for GraphMap<N, E, Ty, S>
where
Item: IntoWeightedEdge<E, NodeId = N>,
N: NodeTrait,
Ty: EdgeType,
S: BuildHasher,
{
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);
}
}
}
iterator_wrap! {
impl (Iterator DoubleEndedIterator ExactSizeIterator) for
#[derive(Debug, Clone)]
struct Nodes <'a, N> where { N: 'a + NodeTrait }
item: N,
iter: Copied<Keys<'a, N, Vec<(N, CompactDirection)>>>,
}
#[derive(Debug, Clone)]
pub struct Neighbors<'a, N, Ty = Undirected>
where
N: 'a,
Ty: EdgeType,
{
iter: Iter<'a, (N, CompactDirection)>,
ty: PhantomData<Ty>,
}
impl<'a, N, Ty> Iterator for Neighbors<'a, N, Ty>
where
N: NodeTrait,
Ty: EdgeType,
{
type Item = N;
fn next(&mut self) -> Option<N> {
if Ty::is_directed() {
(&mut self.iter)
.filter_map(|&(n, dir)| if dir == Outgoing { Some(n) } else { None })
.next()
} else {
self.iter.next().map(|&(n, _)| n)
}
}
fn size_hint(&self) -> (usize, Option<usize>) {
let (lower, upper) = self.iter.size_hint();
if Ty::is_directed() {
(0, upper)
} else {
(lower, upper)
}
}
}
#[derive(Debug, Clone)]
pub struct NeighborsDirected<'a, N, Ty>
where
N: 'a,
Ty: EdgeType,
{
iter: Iter<'a, (N, CompactDirection)>,
start_node: N,
dir: Direction,
ty: PhantomData<Ty>,
}
impl<'a, N, Ty> Iterator for NeighborsDirected<'a, N, Ty>
where
N: NodeTrait,
Ty: EdgeType,
{
type Item = N;
fn next(&mut self) -> Option<N> {
if Ty::is_directed() {
let self_dir = self.dir;
let start_node = self.start_node;
(&mut self.iter)
.filter_map(move |&(n, dir)| {
if dir == self_dir || n == start_node {
Some(n)
} else {
None
}
})
.next()
} else {
self.iter.next().map(|&(n, _)| n)
}
}
fn size_hint(&self) -> (usize, Option<usize>) {
let (lower, upper) = self.iter.size_hint();
if Ty::is_directed() {
(0, upper)
} else {
(lower, upper)
}
}
}
#[derive(Debug, Clone)]
pub struct Edges<'a, N, E: 'a, Ty, S = RandomState>
where
N: 'a + NodeTrait,
Ty: EdgeType,
S: BuildHasher,
{
from: N,
edges: &'a IndexMap<(N, N), E, S>,
iter: Neighbors<'a, N, Ty>,
}
impl<'a, N, E, Ty, S> Iterator for Edges<'a, N, E, Ty, S>
where
N: 'a + NodeTrait,
E: 'a,
Ty: EdgeType,
S: BuildHasher,
{
type Item = (N, N, &'a E);
fn next(&mut self) -> Option<Self::Item> {
self.iter.next().map(|b| {
let a = self.from;
match self.edges.get(&GraphMap::<N, E, Ty>::edge_key(a, b)) {
None => unreachable!(),
Some(edge) => (a, b, edge),
}
})
}
fn size_hint(&self) -> (usize, Option<usize>) {
self.iter.size_hint()
}
}
#[derive(Debug, Clone)]
pub struct EdgesDirected<'a, N, E: 'a, Ty, S = RandomState>
where
N: 'a + NodeTrait,
Ty: EdgeType,
S: BuildHasher,
{
from: N,
dir: Direction,
edges: &'a IndexMap<(N, N), E, S>,
iter: NeighborsDirected<'a, N, Ty>,
}
impl<'a, N, E, Ty, S> Iterator for EdgesDirected<'a, N, E, Ty, S>
where
N: 'a + NodeTrait,
E: 'a,
Ty: EdgeType,
S: BuildHasher,
{
type Item = (N, N, &'a E);
fn next(&mut self) -> Option<Self::Item> {
self.iter.next().map(|mut b| {
let mut a = self.from;
if self.dir == Direction::Incoming {
mem::swap(&mut a, &mut b);
}
match self.edges.get(&GraphMap::<N, E, Ty>::edge_key(a, b)) {
None => unreachable!(),
Some(edge) => (a, b, edge),
}
})
}
fn size_hint(&self) -> (usize, Option<usize>) {
self.iter.size_hint()
}
}
#[derive(Debug, Clone)]
pub struct AllEdges<'a, N, E: 'a, Ty>
where
N: 'a + NodeTrait,
{
inner: IndexMapIter<'a, (N, N), E>,
ty: PhantomData<Ty>,
}
impl<'a, N, E, Ty> Iterator for AllEdges<'a, N, E, Ty>
where
N: 'a + NodeTrait,
E: 'a,
Ty: EdgeType,
{
type Item = (N, N, &'a E);
fn next(&mut self) -> Option<Self::Item> {
self.inner.next().map(|(&(a, b), v)| (a, b, v))
}
fn size_hint(&self) -> (usize, Option<usize>) {
self.inner.size_hint()
}
fn count(self) -> usize {
self.inner.count()
}
fn nth(&mut self, n: usize) -> Option<Self::Item> {
self.inner
.nth(n)
.map(|(&(n1, n2), weight)| (n1, n2, weight))
}
fn last(self) -> Option<Self::Item> {
self.inner
.last()
.map(|(&(n1, n2), weight)| (n1, n2, weight))
}
}
impl<'a, N, E, Ty> DoubleEndedIterator for AllEdges<'a, N, E, Ty>
where
N: 'a + NodeTrait,
E: 'a,
Ty: EdgeType,
{
fn next_back(&mut self) -> Option<Self::Item> {
self.inner
.next_back()
.map(|(&(n1, n2), weight)| (n1, n2, weight))
}
}
pub struct AllEdgesMut<'a, N, E: 'a, Ty>
where
N: 'a + NodeTrait,
{
inner: IndexMapIterMut<'a, (N, N), E>, ty: PhantomData<Ty>,
}
impl<'a, N, E, Ty> Iterator for AllEdgesMut<'a, N, E, Ty>
where
N: 'a + NodeTrait,
E: 'a,
Ty: EdgeType,
{
type Item = (N, N, &'a mut E);
fn next(&mut self) -> Option<Self::Item> {
self.inner
.next()
.map(|(&(n1, n2), weight)| (n1, n2, weight))
}
fn size_hint(&self) -> (usize, Option<usize>) {
self.inner.size_hint()
}
fn count(self) -> usize {
self.inner.count()
}
fn nth(&mut self, n: usize) -> Option<Self::Item> {
self.inner
.nth(n)
.map(|(&(n1, n2), weight)| (n1, n2, weight))
}
fn last(self) -> Option<Self::Item> {
self.inner
.last()
.map(|(&(n1, n2), weight)| (n1, n2, weight))
}
}
impl<'a, N, E, Ty> DoubleEndedIterator for AllEdgesMut<'a, N, E, Ty>
where
N: 'a + NodeTrait,
E: 'a,
Ty: EdgeType,
{
fn next_back(&mut self) -> Option<Self::Item> {
self.inner
.next_back()
.map(|(&(n1, n2), weight)| (n1, n2, weight))
}
}
impl<N, E, Ty, S> Index<(N, N)> for GraphMap<N, E, Ty, S>
where
N: NodeTrait,
Ty: EdgeType,
S: BuildHasher,
{
type Output = E;
fn index(&self, index: (N, N)) -> &E {
let index = Self::edge_key(index.0, index.1);
self.edge_weight(index.0, index.1)
.expect("GraphMap::index: no such edge")
}
}
impl<N, E, Ty, S> IndexMut<(N, N)> for GraphMap<N, E, Ty, S>
where
N: NodeTrait,
Ty: EdgeType,
S: BuildHasher,
{
fn index_mut(&mut self, index: (N, N)) -> &mut E {
let index = Self::edge_key(index.0, index.1);
self.edge_weight_mut(index.0, index.1)
.expect("GraphMap::index: no such edge")
}
}
impl<N, E, Ty, S> Default for GraphMap<N, E, Ty, S>
where
N: NodeTrait,
Ty: EdgeType,
S: BuildHasher + Default,
{
fn default() -> Self {
GraphMap::with_capacity(0, 0)
}
}
pub struct Ptr<'b, T: 'b>(pub &'b T);
impl<'b, T> Copy for Ptr<'b, T> {}
impl<'b, T> Clone for Ptr<'b, T> {
fn clone(&self) -> Self {
*self
}
}
fn ptr_eq<T>(a: *const T, b: *const T) -> bool {
a == b
}
impl<'b, T> PartialEq for Ptr<'b, T> {
fn eq(&self, other: &Ptr<'b, T>) -> bool {
ptr_eq(self.0, other.0)
}
}
impl<'b, T> PartialOrd for Ptr<'b, T> {
fn partial_cmp(&self, other: &Ptr<'b, T>) -> Option<Ordering> {
Some(self.cmp(other))
}
}
impl<'b, T> Ord for Ptr<'b, T> {
fn cmp(&self, other: &Ptr<'b, T>) -> Ordering {
let a: *const T = self.0;
let b: *const T = other.0;
a.cmp(&b)
}
}
impl<'b, T> Deref for Ptr<'b, T> {
type Target = T;
fn deref(&self) -> &T {
self.0
}
}
impl<'b, T> Eq for Ptr<'b, T> {}
impl<'b, T> Hash for Ptr<'b, T> {
fn hash<H: hash::Hasher>(&self, st: &mut H) {
let ptr = (self.0) as *const T;
ptr.hash(st)
}
}
impl<'b, T: fmt::Debug> fmt::Debug for Ptr<'b, T> {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
self.0.fmt(f)
}
}
#[derive(Debug, Clone)]
pub struct NodeIdentifiers<'a, N, E: 'a, Ty>
where
N: 'a + NodeTrait,
{
iter: IndexMapIter<'a, N, Vec<(N, CompactDirection)>>,
ty: PhantomData<Ty>,
edge_ty: PhantomData<E>,
}
impl<'a, N, E, Ty> Iterator for NodeIdentifiers<'a, N, E, Ty>
where
N: 'a + NodeTrait,
E: 'a,
Ty: EdgeType,
{
type Item = N;
fn next(&mut self) -> Option<Self::Item> {
self.iter.next().map(|(&n, _)| n)
}
fn size_hint(&self) -> (usize, Option<usize>) {
self.iter.size_hint()
}
}
#[derive(Debug, Clone)]
pub struct NodeReferences<'a, N, E: 'a, Ty>
where
N: 'a + NodeTrait,
{
iter: IndexMapIter<'a, N, Vec<(N, CompactDirection)>>,
ty: PhantomData<Ty>,
edge_ty: PhantomData<E>,
}
impl<'a, N, E, Ty> Iterator for NodeReferences<'a, N, E, Ty>
where
N: 'a + NodeTrait,
E: 'a,
Ty: EdgeType,
{
type Item = (N, &'a N);
fn next(&mut self) -> Option<Self::Item> {
self.iter.next().map(|(n, _)| (*n, n))
}
fn size_hint(&self) -> (usize, Option<usize>) {
self.iter.size_hint()
}
}
impl<N, E, Ty, S> visit::GraphBase for GraphMap<N, E, Ty, S>
where
N: Copy + PartialEq,
S: BuildHasher,
{
type NodeId = N;
type EdgeId = (N, N);
}
impl<N, E, Ty, S> visit::Data for GraphMap<N, E, Ty, S>
where
N: Copy + PartialEq,
Ty: EdgeType,
S: BuildHasher,
{
type NodeWeight = N;
type EdgeWeight = E;
}
impl<N, E, Ty, S> visit::Visitable for GraphMap<N, E, Ty, S>
where
N: Copy + Ord + Hash,
Ty: EdgeType,
S: BuildHasher,
{
type Map = HashSet<N>;
fn visit_map(&self) -> HashSet<N> {
HashSet::with_capacity(self.node_count())
}
fn reset_map(&self, map: &mut Self::Map) {
map.clear();
}
}
impl<N, E, Ty, S> visit::GraphProp for GraphMap<N, E, Ty, S>
where
N: NodeTrait,
Ty: EdgeType,
S: BuildHasher,
{
type EdgeType = Ty;
}
impl<'a, N, E, Ty, S> visit::IntoNodeReferences for &'a GraphMap<N, E, Ty, S>
where
N: NodeTrait,
Ty: EdgeType,
S: BuildHasher,
{
type NodeRef = (N, &'a N);
type NodeReferences = NodeReferences<'a, N, E, Ty>;
fn node_references(self) -> Self::NodeReferences {
NodeReferences {
iter: self.nodes.iter(),
ty: self.ty,
edge_ty: PhantomData,
}
}
}
impl<'a, N, E: 'a, Ty, S> visit::IntoNodeIdentifiers for &'a GraphMap<N, E, Ty, S>
where
N: NodeTrait,
Ty: EdgeType,
S: BuildHasher,
{
type NodeIdentifiers = NodeIdentifiers<'a, N, E, Ty>;
fn node_identifiers(self) -> Self::NodeIdentifiers {
NodeIdentifiers {
iter: self.nodes.iter(),
ty: self.ty,
edge_ty: PhantomData,
}
}
}
impl<N, E, Ty, S> visit::NodeCount for GraphMap<N, E, Ty, S>
where
N: NodeTrait,
Ty: EdgeType,
S: BuildHasher,
{
fn node_count(&self) -> usize {
(*self).node_count()
}
}
impl<N, E, Ty, S> visit::NodeIndexable for GraphMap<N, E, Ty, S>
where
N: NodeTrait,
Ty: EdgeType,
S: BuildHasher,
{
fn node_bound(&self) -> usize {
self.node_count()
}
fn to_index(&self, ix: Self::NodeId) -> usize {
self.nodes.get_index_of(&ix).unwrap()
}
fn from_index(&self, ix: usize) -> Self::NodeId {
assert!(
ix < self.nodes.len(),
"The requested index {} is out-of-bounds.",
ix
);
let (&key, _) = self.nodes.get_index(ix).unwrap();
key
}
}
impl<N, E, Ty, S> visit::NodeCompactIndexable for GraphMap<N, E, Ty, S>
where
N: NodeTrait,
Ty: EdgeType,
S: BuildHasher,
{
}
impl<'a, N: 'a, E, Ty, S> visit::IntoNeighbors for &'a GraphMap<N, E, Ty, S>
where
N: Copy + Ord + Hash,
Ty: EdgeType,
S: BuildHasher,
{
type Neighbors = Neighbors<'a, N, Ty>;
fn neighbors(self, n: Self::NodeId) -> Self::Neighbors {
self.neighbors(n)
}
}
impl<'a, N: 'a, E, Ty, S> visit::IntoNeighborsDirected for &'a GraphMap<N, E, Ty, S>
where
N: Copy + Ord + Hash,
Ty: EdgeType,
S: BuildHasher,
{
type NeighborsDirected = NeighborsDirected<'a, N, Ty>;
fn neighbors_directed(self, n: N, dir: Direction) -> Self::NeighborsDirected {
self.neighbors_directed(n, dir)
}
}
impl<N, E, Ty, S> visit::EdgeIndexable for GraphMap<N, E, Ty, S>
where
N: NodeTrait,
Ty: EdgeType,
S: BuildHasher,
{
fn edge_bound(&self) -> usize {
self.edge_count()
}
fn to_index(&self, ix: Self::EdgeId) -> usize {
self.edges.get_index_of(&ix).unwrap()
}
fn from_index(&self, ix: usize) -> Self::EdgeId {
assert!(
ix < self.edges.len(),
"The requested index {} is out-of-bounds.",
ix
);
let (&key, _) = self.edges.get_index(ix).unwrap();
key
}
}
impl<'a, N: 'a, E: 'a, Ty, S> visit::IntoEdges for &'a GraphMap<N, E, Ty, S>
where
N: NodeTrait,
Ty: EdgeType,
S: BuildHasher,
{
type Edges = Edges<'a, N, E, Ty, S>;
fn edges(self, a: Self::NodeId) -> Self::Edges {
self.edges(a)
}
}
impl<'a, N: 'a, E: 'a, Ty, S> visit::IntoEdgesDirected for &'a GraphMap<N, E, Ty, S>
where
N: NodeTrait,
Ty: EdgeType,
S: BuildHasher,
{
type EdgesDirected = EdgesDirected<'a, N, E, Ty, S>;
fn edges_directed(self, a: Self::NodeId, dir: Direction) -> Self::EdgesDirected {
self.edges_directed(a, dir)
}
}
impl<'a, N: 'a, E: 'a, Ty, S> visit::IntoEdgeReferences for &'a GraphMap<N, E, Ty, S>
where
N: NodeTrait,
Ty: EdgeType,
S: BuildHasher,
{
type EdgeRef = (N, N, &'a E);
type EdgeReferences = AllEdges<'a, N, E, Ty>;
fn edge_references(self) -> Self::EdgeReferences {
self.all_edges()
}
}
impl<N, E, Ty, S> visit::EdgeCount for GraphMap<N, E, Ty, S>
where
N: NodeTrait,
Ty: EdgeType,
S: BuildHasher,
{
#[inline]
fn edge_count(&self) -> usize {
self.edge_count()
}
}
impl<N, E, Ty, S> visit::GetAdjacencyMatrix for GraphMap<N, E, Ty, S>
where
N: Copy + Ord + Hash,
Ty: EdgeType,
S: BuildHasher,
{
type AdjMatrix = ();
#[inline]
fn adjacency_matrix(&self) {}
#[inline]
fn is_adjacent(&self, _: &(), a: N, b: N) -> bool {
self.contains_edge(a, b)
}
}
#[cfg(feature = "rayon")]
pub struct ParNodes<'a, N>
where
N: NodeTrait + Send + Sync,
{
iter: ParKeys<'a, N, Vec<(N, CompactDirection)>>,
}
#[cfg(feature = "rayon")]
impl<'a, N> ParallelIterator for ParNodes<'a, N>
where
N: NodeTrait + Send + Sync,
{
type Item = N;
fn drive_unindexed<C>(self, consumer: C) -> C::Result
where
C: rayon::iter::plumbing::UnindexedConsumer<Self::Item>,
{
self.iter.copied().drive_unindexed(consumer)
}
fn opt_len(&self) -> Option<usize> {
self.iter.opt_len()
}
}
#[cfg(feature = "rayon")]
impl<'a, N> IndexedParallelIterator for ParNodes<'a, N>
where
N: NodeTrait + Send + Sync,
{
fn drive<C>(self, consumer: C) -> C::Result
where
C: rayon::iter::plumbing::Consumer<Self::Item>,
{
self.iter.copied().drive(consumer)
}
fn len(&self) -> usize {
self.iter.len()
}
fn with_producer<CB>(self, callback: CB) -> CB::Output
where
CB: rayon::iter::plumbing::ProducerCallback<Self::Item>,
{
self.iter.copied().with_producer(callback)
}
}
#[cfg(feature = "rayon")]
pub struct ParAllEdges<'a, N, E, Ty>
where
N: NodeTrait + Send + Sync,
E: Sync,
{
inner: ParIter<'a, (N, N), E>,
ty: PhantomData<fn(Ty)>,
}
#[cfg(feature = "rayon")]
impl<'a, N, E, Ty> ParallelIterator for ParAllEdges<'a, N, E, Ty>
where
N: NodeTrait + Send + Sync,
E: Sync,
{
type Item = (N, N, &'a E);
fn drive_unindexed<C>(self, c: C) -> C::Result
where
C: rayon::iter::plumbing::UnindexedConsumer<Self::Item>,
{
self.inner.map(|(&(a, b), v)| (a, b, v)).drive_unindexed(c)
}
fn opt_len(&self) -> Option<usize> {
self.inner.opt_len()
}
}
#[cfg(feature = "rayon")]
impl<'a, N, E, Ty> IndexedParallelIterator for ParAllEdges<'a, N, E, Ty>
where
N: NodeTrait + Send + Sync,
E: Sync,
{
fn drive<C>(self, consumer: C) -> C::Result
where
C: rayon::iter::plumbing::Consumer<Self::Item>,
{
self.inner.map(|(&(a, b), v)| (a, b, v)).drive(consumer)
}
fn len(&self) -> usize {
self.inner.len()
}
fn with_producer<CB>(self, callback: CB) -> CB::Output
where
CB: rayon::iter::plumbing::ProducerCallback<Self::Item>,
{
self.inner
.map(|(&(a, b), v)| (a, b, v))
.with_producer(callback)
}
}
#[cfg(feature = "rayon")]
pub struct ParAllEdgesMut<'a, N, E: 'a, Ty>
where
N: NodeTrait + Send + Sync,
E: Send,
{
inner: ParIterMut<'a, (N, N), E>,
ty: PhantomData<fn(Ty)>,
}
#[cfg(feature = "rayon")]
impl<'a, N, E, Ty> ParallelIterator for ParAllEdgesMut<'a, N, E, Ty>
where
N: NodeTrait + Send + Sync,
E: Send,
{
type Item = (N, N, &'a mut E);
fn drive_unindexed<C>(self, c: C) -> C::Result
where
C: rayon::iter::plumbing::UnindexedConsumer<Self::Item>,
{
self.inner.map(|(&(a, b), v)| (a, b, v)).drive_unindexed(c)
}
fn opt_len(&self) -> Option<usize> {
self.inner.opt_len()
}
}
#[cfg(feature = "rayon")]
impl<'a, N, E, Ty> IndexedParallelIterator for ParAllEdgesMut<'a, N, E, Ty>
where
N: NodeTrait + Send + Sync,
E: Send,
{
fn drive<C>(self, consumer: C) -> C::Result
where
C: rayon::iter::plumbing::Consumer<Self::Item>,
{
self.inner.map(|(&(a, b), v)| (a, b, v)).drive(consumer)
}
fn len(&self) -> usize {
self.inner.len()
}
fn with_producer<CB>(self, callback: CB) -> CB::Output
where
CB: rayon::iter::plumbing::ProducerCallback<Self::Item>,
{
self.inner
.map(|(&(a, b), v)| (a, b, v))
.with_producer(callback)
}
}