rshyper_algo/
depth_first.rs

1/*
2    Appellation: dft <module>
3    Contrib: @FL03
4*/
5//! this module implements a Depth-First Traversal algorithm for hypergraphs
6use crate::error::Result;
7use crate::traits::{Search, Traversal};
8use core::hash::{BuildHasher, Hash};
9use hashbrown::{DefaultHashBuilder, HashSet};
10use rshyper::idx::{HashIndex, HyperIndex, VertexId, VertexSet};
11use rshyper::rel::RawLayout;
12use rshyper::{GraphProps, HyperGraph};
13
14/// Depth-First Traversal algorithm for hypergraphs
15pub struct DepthFirstTraversal<'a, N, E, A, H, S = DefaultHashBuilder>
16where
17    A: GraphProps,
18    H: HyperGraph<N, E, A>,
19{
20    pub(crate) graph: &'a H,
21    pub(crate) stack: Vec<VertexId<A::Ix>>,
22    pub(crate) visited: VertexSet<A::Ix, S>,
23    _marker: core::marker::PhantomData<(N, E)>,
24}
25
26impl<'a, N, E, H, A, S> DepthFirstTraversal<'a, N, E, A, H, S>
27where
28    A: GraphProps,
29    H: HyperGraph<N, E, A>,
30    S: BuildHasher,
31{
32    /// Create a new DepthFirstTraversal instance
33    pub fn new(graph: &'a H) -> Self
34    where
35        S: Default,
36    {
37        Self {
38            graph,
39            stack: Vec::new(),
40            visited: VertexSet::default(),
41            _marker: core::marker::PhantomData::<(N, E)>,
42        }
43    }
44    /// returns an immutable reference to the stack
45    pub const fn stack(&self) -> &Vec<VertexId<A::Ix>> {
46        &self.stack
47    }
48    /// returns a mutable reference to the stack
49    pub const fn stack_mut(&mut self) -> &mut Vec<VertexId<A::Ix>> {
50        &mut self.stack
51    }
52    /// returns an immutable reference to the visited vertices
53    pub const fn visited(&self) -> &VertexSet<A::Ix, S> {
54        &self.visited
55    }
56    /// returns a mutable reference to the visited vertices
57    pub const fn visited_mut(&mut self) -> &mut VertexSet<A::Ix, S> {
58        &mut self.visited
59    }
60    /// returns true if the vertex has been visited
61    pub fn has_visited<Q>(&self, vertex: &Q) -> bool
62    where
63        A::Ix: Eq + Hash,
64        Q: ?Sized + Eq + Hash,
65        VertexId<A::Ix>: core::borrow::Borrow<Q>,
66    {
67        self.visited().contains(vertex)
68    }
69    /// reset the traversal state
70    pub fn reset(&mut self) -> &mut Self {
71        #[cfg(feature = "tracing")]
72        tracing::debug!("resetting the depth-first traversal operator state...");
73        // clear the stack
74        self.stack_mut().clear();
75        // clear the visited set
76        self.visited_mut().clear();
77        self
78    }
79    /// a convience method to perform a search
80    pub fn search(
81        &mut self,
82        start: VertexId<A::Ix>,
83    ) -> Result<<Self as Search<VertexId<A::Ix>>>::Output>
84    where
85        Self: Search<VertexId<A::Ix>>,
86        A::Ix: HyperIndex,
87    {
88        Search::search(self, start)
89    }
90    /// include the given index in both the stack and visited stores
91    pub(crate) fn register_vertex(&mut self, index: VertexId<A::Ix>) -> &mut Self
92    where
93        A::Ix: Copy + Eq + Hash,
94    {
95        self.stack_mut().push(index);
96        self.visited_mut().insert(index);
97        self
98    }
99}
100
101impl<'a, N, E, A, H, S> Traversal<VertexId<A::Ix>> for DepthFirstTraversal<'a, N, E, A, H, S>
102where
103    A: GraphProps,
104    H: HyperGraph<N, E, A>,
105    S: BuildHasher,
106    A::Ix: HashIndex,
107{
108    type Store<I2> = HashSet<I2, S>;
109
110    fn has_visited(&self, vertex: &VertexId<A::Ix>) -> bool {
111        self.visited().contains(vertex)
112    }
113
114    fn visited(&self) -> &Self::Store<VertexId<A::Ix>> {
115        &self.visited
116    }
117}
118
119impl<'a, N, E, A, H, S> Search<VertexId<A::Ix>> for DepthFirstTraversal<'a, N, E, A, H, S>
120where
121    A: GraphProps,
122    H: HyperGraph<N, E, A>,
123    S: BuildHasher,
124    A::Ix: HyperIndex,
125    for<'b> &'b <H::Edge<E> as RawLayout>::Store: IntoIterator<Item = &'b VertexId<A::Ix>>,
126{
127    type Output = Vec<VertexId<A::Ix>>;
128
129    fn search(&mut self, start: VertexId<A::Ix>) -> Result<Self::Output> {
130        // Reset state
131        self.reset();
132
133        // Check if starting vertex exists
134        if !self.graph.contains_node(&start) {
135            return Err(rshyper::Error::NodeNotFound.into());
136        }
137
138        // Add start vertex to stack and mark as visited
139        self.register_vertex(start);
140
141        // Path to return (traversal order)
142        let mut path = Vec::new();
143
144        // DFT algorithm
145        while let Some(current) = self.stack.pop() {
146            path.push(current);
147
148            // For each hyperedge, visit all vertices that haven't been visited yet
149            for edge_id in self.graph.find_edges_with_node(&current) {
150                let vertices = self.graph.get_edge_domain(edge_id).expect("Edge is empty");
151
152                // Add vertices in reverse order to maintain expected DFS behavior
153                let mut new_vertices = vertices
154                    .into_iter()
155                    .filter(|&v| !self.has_visited(v))
156                    .copied()
157                    .collect::<Vec<_>>();
158
159                // Sort in reverse order (arbitrary but consistent)
160                new_vertices.sort_by(|&a, &b| b.cmp(a));
161
162                for v in new_vertices {
163                    // add the index to the stack and indicate it has been viewed
164                    self.register_vertex(v);
165                }
166            }
167        }
168
169        Ok(path)
170    }
171}
rshyper_algo/depth_first.rs

rshyper_algo/
depth_first.rs
