fera_graph/algs/
paths.rs

1// This Source Code Form is subject to the terms of the Mozilla Public
2// License, v. 2.0. If a copy of the MPL was not distributed with this
3// file, You can obtain one at http://mozilla.org/MPL/2.0/.
4
5//! Paths related algorithms, including find path between two vertices.
6
7use params::IntoOwned;
8use prelude::*;
9use props::Color;
10use traverse::*;
11
12pub trait Paths: Incidence {
13    fn find_path(&self, u: Vertex<Self>, v: Vertex<Self>) -> Option<Vec<Edge<Self>>>
14    where
15        Self: WithVertexProp<Color>,
16    {
17        if u == v {
18            return None;
19        }
20        let mut path = vec![];
21        self.dfs(RecordPath(&mut path, v)).root(u).run();
22        if path.is_empty() {
23            None
24        } else {
25            Some(path)
26        }
27    }
28
29    fn is_walk<I>(&self, edges: I) -> bool
30    where
31        I: IntoIterator,
32        I::Item: IntoOwned<Edge<Self>>,
33    {
34        let mut edges = edges.into_iter();
35        let mut last = if let Some(e) = edges.next() {
36            self.target(e.into_owned())
37        } else {
38            return true;
39        };
40
41        edges.all(|e| {
42            let (u, v) = self.ends(e.into_owned());
43            if last == u {
44                last = v;
45                true
46            } else {
47                false
48            }
49        })
50    }
51
52    fn is_path<I>(&self, edges: I) -> bool
53    where
54        Self: WithVertexProp<bool>,
55        I: IntoIterator,
56        I::Item: IntoOwned<Edge<Self>>,
57    {
58        let mut visited = self.default_vertex_prop(false);
59        let mut edges = edges.into_iter();
60
61        let mut last = if let Some(e) = edges.next() {
62            let (u, v) = self.ends(e.into_owned());
63            if u == v {
64                return false;
65            }
66            visited[u] = true;
67            visited[v] = true;
68            v
69        } else {
70            return true;
71        };
72
73        edges.all(|e| {
74            let (u, v) = self.ends(e.into_owned());
75
76            if last != u || visited[v] {
77                false
78            } else {
79                visited[v] = true;
80                last = v;
81                true
82            }
83        })
84    }
85}
86
87impl<G> Paths for G
88where
89    G: Incidence,
90{
91}
92
93pub struct RecordPath<'a, G: WithEdge> {
94    path: &'a mut Vec<Edge<G>>,
95    target: Vertex<G>,
96}
97
98#[allow(non_snake_case)]
99pub fn RecordPath<G>(path: &mut Vec<Edge<G>>, target: Vertex<G>) -> RecordPath<G>
100where
101    G: WithEdge,
102{
103    RecordPath {
104        path: path,
105        target: target,
106    }
107}
108
109impl<'a, G: WithEdge> Visitor<G> for RecordPath<'a, G> {
110    fn discover_tree_edge(&mut self, g: &G, e: Edge<G>) -> Control {
111        self.path.push(e);
112        break_if(g.target(e) == self.target)
113    }
114
115    fn finish_tree_edge(&mut self, _g: &G, e: Edge<G>) -> Control {
116        let r = self.path.pop();
117        debug_assert_eq!(Some(e), r);
118        Control::Continue
119    }
120}
121
122#[cfg(test)]
123mod tests {
124    use super::Paths;
125    use fera_fun::vec;
126    use prelude::*;
127
128    #[test]
129    fn find_path() {
130        let g: StaticGraph = graph!(6, (0, 1), (0, 2), (1, 4), (2, 3), (2, 4));
131        let e = vec(g.edges());
132
133        assert_eq!(None, g.find_path(0, 0));
134
135        assert_eq!(None, g.find_path(0, 5));
136
137        assert_eq!(vec![e[0]], g.find_path(0, 1).unwrap());
138
139        assert_eq!(vec![e[0], e[1], e[4]], g.find_path(1, 4).unwrap());
140    }
141}
fera_graph/algs/paths.rs

fera_graph/algs/
paths.rs
