nodify 0.1.0

A small crate providing utilies to explore graph (boosted by Rayon)
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

//! This module contains the implementation of [`DFS`]

use super::{ContainsAny, Process};
use crate::Node;
use std::hash::Hash;

/// A [DFS](https://en.wikipedia.org/wiki/Depth-first_search) implementation of some processes
///
/// In particular, the following [`Process`es](Process) are implemented:
/// - [`ContainsAny`].
pub struct DFS<N> {
    node: N,
}

impl<N: Node> Process for DFS<N> {
    type Node = N;

    fn from_node(node: Self::Node) -> Self {
        Self { node }
    }
}

impl<N, P> ContainsAny<P> for DFS<N>
where
    N: Copy + Eq + Hash + Node,
    P: Fn(Self::Node) -> bool,
{
    fn contains_any(&self, pred: P) -> bool {
        type HashSet<K> = std::collections::HashSet<K, ahash::RandomState>;

        let mut is_visited = HashSet::default();
        let mut to_visit = vec![self.node];

        while let Some(node) = to_visit.pop() {
            if pred(node) {
                return true;
            } else if is_visited.insert(node) {
                let next = node.outgoing().filter(|node| !is_visited.contains(node));
                to_visit.extend(next);
            }
        }

        false
    }
}