fleet-topology 0.1.0

Fleet network topology with constraint-aware routing and holonomy verification
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115

use crate::graph::FleetGraph;
use std::collections::{HashMap, HashSet, VecDeque};

/// Route messages through the fleet considering constraint propagation.
/// Messages that carry constraints must follow edges with constraint_flow=true.
pub struct ConstraintRouter<'a> {
    graph: &'a FleetGraph,
}

impl<'a> ConstraintRouter<'a> {
    pub fn new(graph: &'a FleetGraph) -> Self {
        ConstraintRouter { graph }
    }

    /// Find shortest constraint-capable path between two nodes
    pub fn route(&self, from: &str, to: &str) -> Option<Route> {
        let constraint_adj: HashMap<&str, Vec<(&str, u64)>> = self
            .graph
            .edges()
            .iter()
            .filter(|e| e.constraint_flow)
            .fold(HashMap::new(), |mut acc, e| {
                acc.entry(&e.from)
                    .or_default()
                    .push((&e.to, e.latency_us));
                acc.entry(&e.to)
                    .or_default()
                    .push((&e.from, e.latency_us));
                acc
            });

        let mut queue = VecDeque::new();
        let mut parent: HashMap<String, Option<(String, u64)>> = HashMap::new();

        queue.push_back(from.to_string());
        parent.insert(from.to_string(), None);

        while let Some(current) = queue.pop_front() {
            if current == to {
                let mut path = Vec::new();
                let mut total_latency = 0u64;
                let mut node = Some(to.to_string());
                while let Some(n) = node {
                    let latency = parent
                        .get(&n)
                        .and_then(|p| p.as_ref().map(|(_, l)| *l))
                        .unwrap_or(0);
                    total_latency += latency;
                    path.push(n.clone());
                    node = parent.get(&n).and_then(|p| p.as_ref().map(|(p, _)| p.clone()));
                }
                path.reverse();
                return Some(Route {
                    hops: path.len().saturating_sub(1),
                    path,
                    total_latency_us: total_latency,
                });
            }

            if let Some(neighbors) = constraint_adj.get(current.as_str()) {
                for &(neighbor, latency) in neighbors {
                    let n = neighbor.to_string();
                    if !parent.contains_key(&n) {
                        parent.insert(
                            n.clone(),
                            Some((current.clone(), latency)),
                        );
                        queue.push_back(n);
                    }
                }
            }
        }
        None
    }

    /// Find all devices that can reach a given device via constraint edges
    pub fn constraint_neighborhood(&self, device: &str) -> Vec<String> {
        let constraint_adj: HashMap<&str, Vec<&str>> = self
            .graph
            .edges()
            .iter()
            .filter(|e| e.constraint_flow)
            .fold(HashMap::new(), |mut acc, e| {
                acc.entry(&e.from).or_default().push(&e.to);
                acc.entry(&e.to).or_default().push(&e.from);
                acc
            });

        let mut visited = HashSet::new();
        let mut queue = VecDeque::new();
        let mut result = Vec::new();

        queue.push_back(device);
        visited.insert(device);

        while let Some(current) = queue.pop_front() {
            result.push(current.to_string());
            if let Some(neighbors) = constraint_adj.get(current) {
                for &next in neighbors {
                    if !visited.contains(next) {
                        visited.insert(next);
                        queue.push_back(next);
                    }
                }
            }
        }
        result
    }
}

pub struct Route {
    pub path: Vec<String>,
    pub total_latency_us: u64,
    pub hops: usize,
}