eta_graph/algorithms/
dfs_bfs.rs

1use crate::handles::types::{Edge, VHandle, Weight};
2use crate::handles::{vh};
3use crate::traits::EdgeStore;
4use eta_algorithms::data_structs::array::Array;
5use eta_algorithms::data_structs::fat_ptr::{FatPtrMut};
6use eta_algorithms::data_structs::queue::Queue;
7use eta_algorithms::data_structs::stack::Stack;
8
9pub enum ControlFlow {
10    Resume,
11    End,
12    Exit,
13    Continue,
14}
15
16
17pub fn bfs<PreOrderFunc, Edges>(edge_storage: &mut Edges, start: Edge, vertices_count: usize, mut pre_order: PreOrderFunc)
18where
19    PreOrderFunc: FnMut(&mut Edge, Weight) -> ControlFlow,
20    Edges: EdgeStore,
21{
22    let mut was_queued_flags = Array::new_default_bytes(vertices_count, 0);
23
24    // Uses more memory than necessary. But rotates very quickly. Might be worth considering version with smaller memory footprint.
25    let mut visit_queue = Queue::<VHandle>::new_pow2_sized(vertices_count);
26    let mut end = 1;
27    let mut next_layer = 1;
28    let mut layer = 0;
29    visit_queue.push(vh(start));
30    was_queued_flags[0] = true;
31    let mut i = 0;
32
33    //Initial call
34    let mut start_edge = start;
35    match pre_order(&mut start_edge, layer) {
36        ControlFlow::End => {
37            return;
38        }
39        ControlFlow::Exit => {
40            return;
41        }
42        ControlFlow::Continue => {
43        }
44        ControlFlow::Resume => {}
45    }
46
47    while !visit_queue.is_empty() {
48        let handle = visit_queue.dequeue().unwrap();
49
50        for edge in edge_storage.edges_iter_mut(handle) {
51            if unsafe { *was_queued_flags.index_unchecked(vh(*edge) as usize) } {
52                continue;
53            }
54            unsafe { *was_queued_flags.index_unchecked_mut(vh(*edge) as usize) = true };
55
56            match pre_order(edge, layer + 1) {
57                ControlFlow::End => {
58                    break;
59                }
60                ControlFlow::Exit => {
61                    break;
62                }
63                ControlFlow::Continue => {
64                    i += 1;
65                    continue;
66                }
67                ControlFlow::Resume => {}
68            }
69
70            visit_queue.push(vh(*edge));
71            end += 1;
72        }
73        i += 1;
74
75        if i == next_layer {
76            layer += 1;
77            next_layer = end;
78        }
79    }
80}
81
82#[cfg_attr(not(debug_assertions), inline(always))]
83pub fn dfs<PreOrderFunc, PostOrderFunc, Edges>(edge_storage: &mut Edges, start: Edge, vertices_count: usize, pre_order_func: PreOrderFunc,
84                                               post_order_func: PostOrderFunc)
85where
86    PreOrderFunc: FnMut(&mut Edge) -> ControlFlow,
87    PostOrderFunc: FnMut(&mut Edge),
88    Edges: EdgeStore,
89{
90    let mut flags = Array::new_default_bytes(vertices_count, 0);
91    dfs_custom_flags(edge_storage, start, vertices_count, |to_visit| {
92        let was_visited = flags[vh(to_visit) as usize];
93        flags[vh(to_visit) as usize] = true;
94        was_visited
95    }, pre_order_func, post_order_func);
96}
97
98pub fn dfs_custom_flags<VisitedFunc, PreOrderFunc, PostOrderFunc, Edges>(edge_storage: &mut Edges, start: Edge, vertex_count: usize,
99                                                                         mut is_visited: VisitedFunc, mut pre_order_func: PreOrderFunc,
100                                                                         mut post_order_func: PostOrderFunc)
101where
102    VisitedFunc: FnMut(Edge) -> bool,
103    PreOrderFunc: FnMut(&mut Edge) -> ControlFlow,
104    PostOrderFunc: FnMut(&mut Edge),
105    Edges: EdgeStore,
106{
107    let mut start_edge = start;
108    let mut stack = Stack::<(FatPtrMut<Edge>, *mut Edge)>::new(vertex_count);
109    stack.push((edge_storage.edges_as_mut_ptr(vh(start)), (&mut start_edge) as *mut Edge));
110    if let ControlFlow::End = pre_order_func(&mut start_edge) {
111        return;
112    }
113
114    while !stack.is_empty() {
115        let (next_edges_ptr, current_edge) = stack.top_mut().unwrap();
116        let next = next_edges_ptr.next();
117        if next.is_none() {
118            post_order_func(unsafe { (*current_edge).as_mut().unwrap() });
119            stack.pop();
120            continue;
121        }
122        let next = next.unwrap();
123
124        if is_visited(*next) {
125            continue;
126        }
127
128        match pre_order_func(next) {
129            ControlFlow::End => {
130                break;
131            }
132            ControlFlow::Exit => {
133                return;
134            }
135            ControlFlow::Continue => {
136                continue;
137            }
138            ControlFlow::Resume => {}
139        }
140
141        let next_edges = edge_storage.edges_as_mut_ptr(vh(*next));
142        stack.push((next_edges, next));
143    }
144
145    // Return back to the src without exploring further
146    while !stack.is_empty() {
147        let (_, packed_edge) = stack.pop().unwrap();
148        post_order_func(unsafe { packed_edge.as_mut().unwrap() });
149    }
150}
eta_graph/algorithms/dfs_bfs.rs

eta_graph/algorithms/
dfs_bfs.rs
