fleet_topology/

graph.rs

use serde::{Deserialize, Serialize};
use std::collections::{HashMap, HashSet, VecDeque};

/// Fleet topology graph.
/// Nodes are devices, edges are communication links.
/// Constraints propagate along edges.
/// Holonomy (cycle consistency) verified on every cycle.
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct FleetGraph {
    nodes: Vec<Node>,
    edges: Vec<Edge>,
}

#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct Node {
    pub id: String,
    pub device_type: DeviceType,
    pub capability: Capability,
    pub constraints: Vec<String>, // constraint IDs
}

#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct Edge {
    pub from: String,
    pub to: String,
    pub latency_us: u64,
    pub bandwidth_bps: u64,
    pub constraint_flow: bool,
}

#[derive(Debug, Clone, Serialize, Deserialize)]
pub enum DeviceType {
    RobotArm,
    SensorArray,
    Esp32,
    Jetson,
    Fpga,
    Gateway,
}

#[derive(Debug, Clone, Serialize, Deserialize, PartialEq)]
pub enum Capability {
    Raw,
    Aware,
    Enforcing,
    Commander,
}

impl FleetGraph {
    pub fn new() -> Self {
        FleetGraph {
            nodes: Vec::new(),
            edges: Vec::new(),
        }
    }

    pub fn add_node(&mut self, node: Node) {
        self.nodes.push(node);
    }

    pub fn add_edge(&mut self, edge: Edge) {
        self.edges.push(edge);
    }

    /// Find all cycles using Johnson's algorithm (simplified DFS-based approach).
    pub fn find_cycles(&self) -> Vec<Vec<String>> {
        let mut cycles = Vec::new();
        let node_ids: Vec<&str> = self.nodes.iter().map(|n| n.id.as_str()).collect();
        let adj = self.build_adjacency();

        let mut visited = HashSet::new();
        let mut stack = Vec::new();
        let mut in_stack = HashSet::new();

        for start in &node_ids {
            visited.clear();
            stack.clear();
            in_stack.clear();
            self.dfs_cycles(
                start,
                start,
                &adj,
                &mut visited,
                &mut stack,
                &mut in_stack,
                &mut cycles,
            );
        }

        // Deduplicate cycles (normalize by rotating to smallest element)
        let mut seen = HashSet::new();
        let mut unique = Vec::new();
        for cycle in cycles {
            if cycle.len() < 2 {
                continue;
            }
            let mut normalized = cycle.clone();
            let min_pos = normalized.iter().enumerate().min_by_key(|(_, v)| *v).map(|(i, _)| i);
            if let Some(pos) = min_pos {
                normalized.rotate_left(pos);
            }
            let key = normalized.join("|");
            if !seen.contains(&key) {
                seen.insert(key);
                unique.push(cycle);
            }
        }
        unique
    }

    fn dfs_cycles(
        &self,
        current: &str,
        start: &str,
        adj: &HashMap<&str, Vec<&str>>,
        visited: &mut HashSet<String>,
        stack: &mut Vec<String>,
        in_stack: &mut HashSet<String>,
        cycles: &mut Vec<Vec<String>>,
    ) {
        visited.insert(current.to_string());
        stack.push(current.to_string());
        in_stack.insert(current.to_string());

        if let Some(neighbors) = adj.get(&current) {
            for &next in neighbors {
                if next == start && stack.len() >= 2 {
                    cycles.push(stack.clone());
                } else if !visited.contains(next) && !in_stack.contains(next) {
                    // Only follow edges to nodes >= start to avoid duplicate cycles
                    if next >= start {
                        self.dfs_cycles(next, start, adj, visited, stack, in_stack, cycles);
                    }
                }
            }
        }

        stack.pop();
        in_stack.remove(current);
        visited.remove(current);
    }

    fn build_adjacency(&self) -> HashMap<&str, Vec<&str>> {
        let mut adj: HashMap<&str, Vec<&str>> = HashMap::new();
        for edge in &self.edges {
            adj.entry(&edge.from).or_default().push(&edge.to);
            adj.entry(&edge.to).or_default().push(&edge.from);
        }
        adj
    }

    /// Compute Betti number β₁ = |E| - |V| + c
    pub fn betti1(&self) -> usize {
        let c = self.connected_components();
        if self.edges.len() >= self.nodes.len() {
            self.edges.len() - self.nodes.len() + c
        } else {
            0
        }
    }

    /// Find path between two nodes (BFS)
    pub fn find_path(&self, from: &str, to: &str) -> Option<Vec<String>> {
        let adj = self.build_adjacency();
        let mut queue = VecDeque::new();
        let mut parent: HashMap<String, Option<String>> = HashMap::new();

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

        while let Some(current) = queue.pop_front() {
            if current == to {
                // Reconstruct path
                let mut path = Vec::new();
                let mut node = Some(to.to_string());
                while let Some(n) = node {
                    path.push(n.clone());
                    node = parent.get(&n).and_then(|p| p.clone());
                }
                path.reverse();
                return Some(path);
            }

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

    /// Get neighbors of a node
    pub fn neighbors(&self, node_id: &str) -> Vec<&Node> {
        let neighbor_ids: HashSet<&str> = self
            .edges
            .iter()
            .filter(|e| e.from == node_id || e.to == node_id)
            .map(|e| {
                if e.from == node_id {
                    e.to.as_str()
                } else {
                    e.from.as_str()
                }
            })
            .collect();

        self.nodes
            .iter()
            .filter(|n| neighbor_ids.contains(n.id.as_str()))
            .collect()
    }

    /// Constraint propagation: find all devices that should know about a constraint
    pub fn constraint_reach(&self, constraint_id: &str) -> Vec<&Node> {
        // Start from nodes that have this constraint, propagate along constraint_flow edges
        let sources: HashSet<&str> = self
            .nodes
            .iter()
            .filter(|n| n.constraints.contains(&constraint_id.to_string()))
            .map(|n| n.id.as_str())
            .collect();

        if sources.is_empty() {
            return Vec::new();
        }

        let constraint_adj: HashMap<&str, Vec<&str>> = self
            .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 reachable = HashSet::new();
        let mut queue: VecDeque<&str> = sources.iter().copied().collect();
        for &s in &sources {
            reachable.insert(s);
        }

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

        self.nodes
            .iter()
            .filter(|n| reachable.contains(n.id.as_str()))
            .collect()
    }

    /// Check if graph is connected
    pub fn is_connected(&self) -> bool {
        if self.nodes.is_empty() {
            return true;
        }
        self.connected_components() <= 1
    }

    fn connected_components(&self) -> usize {
        if self.nodes.is_empty() {
            return 0;
        }

        let adj = self.build_adjacency();
        let mut visited: HashSet<&str> = HashSet::new();
        let mut components = 0;

        for node in &self.nodes {
            if visited.contains(node.id.as_str()) {
                continue;
            }
            components += 1;
            let mut queue = VecDeque::new();
            queue.push_back(node.id.as_str());
            visited.insert(node.id.as_str());

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

    /// Get reference to nodes
    pub fn nodes(&self) -> &[Node] {
        &self.nodes
    }

    /// Get reference to edges
    pub fn edges(&self) -> &[Edge] {
        &self.edges
    }
}

impl Default for FleetGraph {
    fn default() -> Self {
        Self::new()
    }
}