wolf-graph 0.1.0

Data structures and algorithms for working with graphs with reference or value semantics.
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

use std::marker::PhantomData;

use anyhow::Result;

use crate::{DFSVisitor, DepthFirstSearch, EdgeID, NodeID, Nodes, VisitableGraph};

/// A trait for a graph that supports checking whether a path exists between two nodes.
pub trait PathExists {
    type Graph: VisitableGraph;

    fn path_exists_opt(&self, from: impl AsRef<NodeID>, to: impl AsRef<NodeID>, excluded_edge: Option<impl AsRef<EdgeID>>) -> Result<bool>;

    fn path_exists(&self, from: impl AsRef<NodeID>, to: impl AsRef<NodeID>) -> Result<bool> {
        self.path_exists_opt(from, to, None::<EdgeID>)
    }

    fn can_add_dag_edge(&self, from: impl AsRef<NodeID>, to: impl AsRef<NodeID>, excluded_edge: Option<impl AsRef<EdgeID>>) -> Result<bool> {
        Ok(!self.path_exists_opt(to, from, excluded_edge)?)
    }

    fn can_move_dag_edge(&self, edge: impl AsRef<EdgeID>, new_source: impl AsRef<NodeID>, new_target: impl AsRef<NodeID>) -> Result<bool> {
        self.can_add_dag_edge(new_source, new_target, Some(edge))
    }
}

impl<G> PathExists for G
where
    G: DepthFirstSearch<G, bool> + VisitableGraph,
{
    type Graph = G;

    fn path_exists_opt(&self, from: impl AsRef<NodeID>, to: impl AsRef<NodeID>, excluded_edge: Option<impl AsRef<EdgeID>>) -> Result<bool> {
        let from = from.as_ref();
        let to = to.as_ref();
        let mut visitor = PathExistsVisitor::new(from.clone(), to.clone());
        self.depth_first_search_opt(&mut visitor, &Nodes::from([from.clone()]), false, excluded_edge)
    }
}

pub struct PathExistsVisitor<Graph> {
    from: NodeID,
    to: NodeID,
    graph: PhantomData<Graph>,
}

impl<Graph> PathExistsVisitor<Graph>
where
    Graph: VisitableGraph,
{
    pub fn new(from: NodeID, to: NodeID) -> Self {
        Self {
            from,
            to,
            graph: PhantomData,
        }
    }
}

impl<Graph> DFSVisitor for PathExistsVisitor<Graph>
where
    Graph: VisitableGraph,
{
    type Graph = Graph;
    type Output = bool;

    fn discover_node(&mut self, _graph: &Self::Graph, node: &NodeID) -> Result<Option<bool>> {
        Ok(if node == &self.to { Some(true) } else { None })
    }

    fn finish_node(&mut self, _graph: &Self::Graph, node: &NodeID) -> Result<Option<bool>> {
        Ok(if node == &self.from { Some(false) } else { None })
    }

    fn finish(&mut self, _graph: &Self::Graph) -> Result<bool> {
        Ok(false)
    }
}