use std::collections::{
HashSet,
BitvSet,
RingBuf,
};
use std::collections::hash_map::Hasher;
use std::hash::Hash;
use super::{
graphmap,
graph,
EdgeType,
EdgeDirection,
Graph,
GraphMap,
};
use graph::{
IndexType,
};
pub trait Graphlike {
type NodeId: Clone;
}
pub trait NeighborIter<'a, N> {
type Iter: Iterator<Item=N>;
fn neighbors(&'a self, n: N) -> Self::Iter;
}
impl<'a, N, E, Ty, Ix> NeighborIter<'a, graph::NodeIndex<Ix>> for Graph<N, E, Ty, Ix> where
Ty: EdgeType,
Ix: IndexType,
{
type Iter = graph::Neighbors<'a, E, Ix>;
fn neighbors(&'a self, n: graph::NodeIndex<Ix>) -> graph::Neighbors<'a, E, Ix>
{
Graph::neighbors(self, n)
}
}
impl<'a, N, E> NeighborIter<'a, N> for GraphMap<N, E>
where N: Copy + Clone + Ord + Hash<Hasher> + Eq
{
type Iter = graphmap::Neighbors<'a, N>;
fn neighbors(&'a self, n: N) -> graphmap::Neighbors<'a, N>
{
GraphMap::neighbors(self, n)
}
}
pub struct AsUndirected<G>(pub G);
pub struct Reversed<G>(pub G);
impl<'a, 'b, N, E, Ty, Ix> NeighborIter<'a, graph::NodeIndex<Ix>> for AsUndirected<&'b Graph<N, E, Ty, Ix>> where
Ty: EdgeType,
Ix: IndexType,
{
type Iter = graph::Neighbors<'a, E, Ix>;
fn neighbors(&'a self, n: graph::NodeIndex<Ix>) -> graph::Neighbors<'a, E, Ix>
{
Graph::neighbors_undirected(self.0, n)
}
}
impl<'a, 'b, N, E, Ty, Ix> NeighborIter<'a, graph::NodeIndex<Ix>> for Reversed<&'b Graph<N, E, Ty, Ix>> where
Ty: EdgeType,
Ix: IndexType,
{
type Iter = graph::Neighbors<'a, E, Ix>;
fn neighbors(&'a self, n: graph::NodeIndex<Ix>) -> graph::Neighbors<'a, E, Ix>
{
Graph::neighbors_directed(self.0, n, EdgeDirection::Incoming)
}
}
pub trait VisitMap<N> {
fn visit(&mut self, N) -> bool;
fn is_visited(&self, &N) -> bool;
}
impl<Ix> VisitMap<graph::NodeIndex<Ix>> for BitvSet where
Ix: IndexType,
{
fn visit(&mut self, x: graph::NodeIndex<Ix>) -> bool {
self.insert(x.index())
}
fn is_visited(&self, x: &graph::NodeIndex<Ix>) -> bool {
self.contains(&x.index())
}
}
impl<N: Eq + Hash<Hasher>> VisitMap<N> for HashSet<N> {
fn visit(&mut self, x: N) -> bool {
self.insert(x)
}
fn is_visited(&self, x: &N) -> bool {
self.contains(x)
}
}
pub trait Visitable : Graphlike {
type Map: VisitMap<<Self as Graphlike>::NodeId>;
fn visit_map(&self) -> Self::Map;
}
impl<N, E, Ty, Ix> Graphlike for Graph<N, E, Ty, Ix> where
Ix: IndexType,
{
type NodeId = graph::NodeIndex<Ix>;
}
impl<N, E, Ty, Ix> Visitable for Graph<N, E, Ty, Ix> where
Ty: EdgeType,
Ix: IndexType,
{
type Map = BitvSet;
fn visit_map(&self) -> BitvSet { BitvSet::with_capacity(self.node_count()) }
}
impl<N: Clone, E> Graphlike for GraphMap<N, E>
{
type NodeId = N;
}
impl<N, E> Visitable for GraphMap<N, E>
where N: Copy + Clone + Ord + Eq + Hash<Hasher>
{
type Map = HashSet<N>;
fn visit_map(&self) -> HashSet<N> { HashSet::with_capacity(self.node_count()) }
}
impl<'a, V: Graphlike> Graphlike for AsUndirected<&'a V>
{
type NodeId = <V as Graphlike>::NodeId;
}
impl<'a, V: Graphlike> Graphlike for Reversed<&'a V>
{
type NodeId = <V as Graphlike>::NodeId;
}
impl<'a, V: Visitable> Visitable for AsUndirected<&'a V>
{
type Map = <V as Visitable>::Map;
fn visit_map(&self) -> <V as Visitable>::Map {
self.0.visit_map()
}
}
impl<'a, V: Visitable> Visitable for Reversed<&'a V>
{
type Map = <V as Visitable>::Map;
fn visit_map(&self) -> <V as Visitable>::Map {
self.0.visit_map()
}
}
pub trait HasAdjacencyMatrix : Graphlike {
type Map;
fn adjacency_matrix(&self) -> Self::Map;
fn is_adjacent(&self, matrix: &Self::Map, a: Self::NodeId, b: Self::NodeId) -> bool;
}
#[derive(Clone, Debug)]
pub struct Dfs<N, VM> {
pub stack: Vec<N>,
pub discovered: VM,
}
impl<G: Visitable> Dfs<G::NodeId, <G as Visitable>::Map>
{
pub fn new(graph: &G, start: G::NodeId) -> Self
{
let mut dfs = Dfs::empty(graph);
dfs.move_to(start);
dfs
}
pub fn empty(graph: &G) -> Self
{
Dfs {
stack: Vec::new(),
discovered: graph.visit_map(),
}
}
}
impl<N, VM> Dfs<N, VM> where
N: Clone,
VM: VisitMap<N>
{
pub fn move_to(&mut self, start: N)
{
self.discovered.visit(start.clone());
self.stack.clear();
self.stack.push(start);
}
}
impl<N, VM> Dfs<N, VM> where
N: Clone,
VM: VisitMap<N>
{
pub fn next<'a, G>(&mut self, graph: &'a G) -> Option<N> where
G: for<'b> NeighborIter<'b, N>,
{
while let Some(node) = self.stack.pop() {
for succ in graph.neighbors(node.clone()) {
if self.discovered.visit(succ.clone()) {
self.stack.push(succ);
}
}
return Some(node);
}
None
}
}
#[derive(Clone)]
pub struct DfsIter<'a, G, N, VM> where
G: 'a,
{
graph: &'a G,
dfs: Dfs<N, VM>,
}
impl<'a, G: Visitable> DfsIter<'a, G, G::NodeId, <G as Visitable>::Map>
{
pub fn new(graph: &'a G, start: G::NodeId) -> DfsIter<'a, G, G::NodeId, <G as Visitable>::Map>
{
DfsIter {
graph: graph,
dfs: Dfs::new(graph, start)
}
}
}
impl<'a, G: Visitable, VM> Iterator for DfsIter<'a, G, G::NodeId, VM> where
G: 'a,
VM: VisitMap<G::NodeId>,
G: for<'b> NeighborIter<'b, G::NodeId>,
{
type Item = G::NodeId;
fn next(&mut self) -> Option<G::NodeId>
{
self.dfs.next(self.graph)
}
}
#[derive(Clone)]
pub struct Bfs<N, VM> {
pub stack: RingBuf<N>,
pub discovered: VM,
}
impl<N, G> Bfs<N, <G as Visitable>::Map> where
N: Clone,
G: Visitable<NodeId=N>,
<G as Visitable>::Map: VisitMap<N>,
{
pub fn new(graph: &G, start: N) -> Self
{
let mut discovered = graph.visit_map();
discovered.visit(start.clone());
let mut stack = RingBuf::new();
stack.push_front(start.clone());
Bfs {
stack: stack,
discovered: discovered,
}
}
}
impl<N, VM> Bfs<N, VM> where
N: Clone,
VM: VisitMap<N>
{
pub fn next<'a, G>(&mut self, graph: &'a G) -> Option<N> where
G: for<'b> NeighborIter<'b, N>,
{
while let Some(node) = self.stack.pop_front() {
for succ in graph.neighbors(node.clone()) {
if self.discovered.visit(succ.clone()) {
self.stack.push_back(succ);
}
}
return Some(node);
}
None
}
}
#[derive(Clone)]
pub struct BfsIter<'a, G, N, VM> where
G: 'a,
{
graph: &'a G,
bfs: Bfs<N, VM>,
}
impl<'a, G, N> BfsIter<'a, G, N, <G as Visitable>::Map> where
N: Clone,
G: Visitable<NodeId=N>,
<G as Visitable>::Map: VisitMap<N>,
{
pub fn new(graph: &'a G, start: N) -> BfsIter<'a, G, N, <G as Visitable>::Map>
{
BfsIter {
graph: graph,
bfs: Bfs::new(graph, start)
}
}
}
impl<'a, G, N, VM> Iterator for BfsIter<'a, G, N, VM> where
G: 'a,
N: Clone,
VM: VisitMap<N>,
G: for<'b> NeighborIter<'b, N>,
{
type Item = N;
fn next(&mut self) -> Option<N>
{
self.bfs.next(self.graph)
}
}