durs_wot/operations/
path.rs

1//  Copyright (C) 2017-2019  The AXIOM TEAM Association.
2//
3// This program is free software: you can redistribute it and/or modify
4// it under the terms of the GNU Affero General Public License as
5// published by the Free Software Foundation, either version 3 of the
6// License, or (at your option) any later version.
7//
8// This program is distributed in the hope that it will be useful,
9// but WITHOUT ANY WARRANTY; without even the implied warranty of
10// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
11// GNU Affero General Public License for more details.
12//
13// You should have received a copy of the GNU Affero General Public License
14// along with this program.  If not, see <https://www.gnu.org/licenses/>.
15
16//! Provide a trait and implementations to find paths between nodes.
17
18use crate::data::WebOfTrust;
19use crate::data::WotId;
20use std::collections::HashSet;
21
22/// Find paths between 2 nodes of a `WebOfTrust`.
23pub trait PathFinder<T: WebOfTrust> {
24    /// Get paths from one node to the other.
25    fn find_paths(&self, wot: &T, from: WotId, to: WotId, k_max: u32) -> Vec<Vec<WotId>>;
26}
27
28/// A new "rusty-er" implementation of `WoT` path finding.
29#[derive(Debug, Clone, Copy)]
30pub struct RustyPathFinder;
31
32impl<T: WebOfTrust> PathFinder<T> for RustyPathFinder {
33    fn find_paths(&self, wot: &T, from: WotId, to: WotId, k_max: u32) -> Vec<Vec<WotId>> {
34        if from.0 >= wot.size() || to.0 >= wot.size() {
35            return vec![];
36        }
37
38        // 1. We explore the k_max area around `to`, and only remember backward
39        //    links of the smallest distance.
40
41        // Stores for each node its distance to `to` node and its backward links.
42        // By default all nodes are out of range (`k_max + 1`) and links are known.
43        let mut graph: Vec<(u32, Vec<WotId>)> =
44            (0..wot.size()).map(|_| (k_max + 1, vec![])).collect();
45        // `to` node is at distance 0, and have no backward links.
46        graph[to.0] = (0, vec![]);
47        // Explored zone border.
48        let mut border = HashSet::new();
49        border.insert(to);
50
51        for distance in 1..=k_max {
52            let mut next_border = HashSet::new();
53
54            for node in border {
55                for source in &wot
56                    .get_links_source(node)
57                    .expect("links source must not be None")
58                {
59                    match graph[source.0].0 {
60                        path_distance if path_distance > distance => {
61                            // shorter path, we replace
62                            graph[source.0] = (distance, vec![node]);
63                            next_border.insert(*source);
64                        }
65                        path_distance if path_distance == distance => {
66                            // same length, we combine
67                            graph[source.0].1.push(node);
68                            next_border.insert(*source);
69                        }
70                        _ => unreachable!(),
71                    }
72                }
73            }
74
75            border = next_border;
76        }
77
78        // 2. If `from` is found, we follow the backward links and build paths.
79        //    For each path, we look at the last element sources and build new paths with them.
80        let mut paths = vec![vec![from]];
81
82        for _ in 1..=k_max {
83            let mut new_paths = vec![];
84
85            for path in &paths {
86                let node = path.last().expect("path should not be empty");
87
88                if node == &to {
89                    // If path is complete, we keep it.
90                    new_paths.push(path.clone())
91                } else {
92                    // If not complete we comlete paths
93                    let sources = &graph[node.0];
94                    for source in &sources.1 {
95                        let mut new_path = path.clone();
96                        new_path.push(*source);
97                        new_paths.push(new_path);
98                    }
99                }
100            }
101
102            paths = new_paths;
103        }
104
105        paths
106    }
107}
durs_wot/operations/path.rs

durs_wot/operations/
path.rs
