Add the ability to clear the visited status of a node when working with VisitMap<N>. #610
Description
Summary
Allow nodes to be marked as unvisited when visiting them via a VisitMap<N>.
Motivation
Currently, there is no way to ask a VisitMap implementor to clear the visited status for a node.
And iiuc it is not currently possible to implement an algorithm that requires visiting and unvisiting nodes dynamically.
Details
The following changes would provide that ability in a backwards compatible way.
I propose we add another method to the VisitMap trait:
/// A mapping for storing the visited status for NodeId `N`.
pub trait VisitMap<N> {
/// Mark `a` as visited.
///
/// Return **true** if this is the first visit, false otherwise.
fn visit(&mut self, a: N) -> bool;
/// Return whether `a` has been visited before.
fn is_visited(&self, a: &N) -> bool;
/// Mark `a` as unvisited.
///
/// Return **true** if this vertex was marked as visited at the time of unsetting it, false otherwise.
fn unvisit(&mut self, a: N) -> bool {
false // or maybe unimplemented!("whoops") is a better default?
}
}and the impls:
impl<Ix> VisitMap<Ix> for FixedBitSet
where
Ix: IndexType,
{
fn visit(&mut self, x: Ix) -> bool {
!self.put(x.index())
}
fn is_visited(&self, x: &Ix) -> bool {
self.contains(x.index())
}
fn unvisit(&mut self, x: Ix) -> bool {
if self.is_visited(&x) {
self.toggle(x.index());
return true;
}
false
}
}
impl<N, S> VisitMap<N> for HashSet<N, S>
where
N: Hash + Eq,
S: BuildHasher,
{
fn visit(&mut self, x: N) -> bool {
self.insert(x)
}
fn is_visited(&self, x: &N) -> bool {
self.contains(x)
}
fn unvisit(&mut self, x: N) -> bool {
self.remove(&x)
}
}