wolf_graph/algo/
path_exists.rs

1use std::marker::PhantomData;
2
3use anyhow::Result;
4
5use crate::{DFSVisitor, DepthFirstSearch, EdgeID, NodeID, Nodes, VisitableGraph};
6
7/// A trait for a graph that supports checking whether a path exists between two nodes.
8pub trait PathExists {
9    type Graph: VisitableGraph;
10
11    fn path_exists_opt(&self, from: impl AsRef<NodeID>, to: impl AsRef<NodeID>, excluded_edge: Option<impl AsRef<EdgeID>>) -> Result<bool>;
12
13    fn path_exists(&self, from: impl AsRef<NodeID>, to: impl AsRef<NodeID>) -> Result<bool> {
14        self.path_exists_opt(from, to, None::<EdgeID>)
15    }
16
17    fn can_add_dag_edge(&self, from: impl AsRef<NodeID>, to: impl AsRef<NodeID>, excluded_edge: Option<impl AsRef<EdgeID>>) -> Result<bool> {
18        Ok(!self.path_exists_opt(to, from, excluded_edge)?)
19    }
20
21    fn can_move_dag_edge(&self, edge: impl AsRef<EdgeID>, new_source: impl AsRef<NodeID>, new_target: impl AsRef<NodeID>) -> Result<bool> {
22        self.can_add_dag_edge(new_source, new_target, Some(edge))
23    }
24}
25
26impl<G> PathExists for G
27where
28    G: DepthFirstSearch<G, bool> + VisitableGraph,
29{
30    type Graph = G;
31
32    fn path_exists_opt(&self, from: impl AsRef<NodeID>, to: impl AsRef<NodeID>, excluded_edge: Option<impl AsRef<EdgeID>>) -> Result<bool> {
33        let from = from.as_ref();
34        let to = to.as_ref();
35        let mut visitor = PathExistsVisitor::new(from.clone(), to.clone());
36        self.depth_first_search_opt(&mut visitor, &Nodes::from([from.clone()]), false, excluded_edge)
37    }
38}
39
40pub struct PathExistsVisitor<Graph> {
41    from: NodeID,
42    to: NodeID,
43    graph: PhantomData<Graph>,
44}
45
46impl<Graph> PathExistsVisitor<Graph>
47where
48    Graph: VisitableGraph,
49{
50    pub fn new(from: NodeID, to: NodeID) -> Self {
51        Self {
52            from,
53            to,
54            graph: PhantomData,
55        }
56    }
57}
58
59impl<Graph> DFSVisitor for PathExistsVisitor<Graph>
60where
61    Graph: VisitableGraph,
62{
63    type Graph = Graph;
64    type Output = bool;
65
66    fn discover_node(&mut self, _graph: &Self::Graph, node: &NodeID) -> Result<Option<bool>> {
67        Ok(if node == &self.to { Some(true) } else { None })
68    }
69
70    fn finish_node(&mut self, _graph: &Self::Graph, node: &NodeID) -> Result<Option<bool>> {
71        Ok(if node == &self.from { Some(false) } else { None })
72    }
73
74    fn finish(&mut self, _graph: &Self::Graph) -> Result<bool> {
75        Ok(false)
76    }
77}
wolf_graph/algo/path_exists.rs

wolf_graph/algo/
path_exists.rs
