npe_graph/
net.rs

1//! Nets: the solver-facing view of connectivity.
2//!
3//! In a schematic, a *net* is everything that is electrically (or
4//! hydraulically) common — possibly many ports joined by many individual
5//! wires. The GUI cares about individual edges (each wire has its own route,
6//! its own selection state); a solver (MNA, flow network, signal propagation)
7//! cares about nets. This module derives the latter from the former.
8
9use crate::graph::Graph;
10use crate::id::{EdgeId, PortId};
11use std::collections::HashMap;
12
13/// A maximal set of ports connected (transitively) by edges.
14///
15/// Isolated ports form singleton nets with no edges — solvers usually want to
16/// see those too (a floating pin is a modeling fact, often a bug to report).
17#[derive(Debug, Clone, Default)]
18pub struct Net {
19    /// All ports on this net.
20    pub ports: Vec<PortId>,
21    /// All edges whose endpoints lie on this net.
22    pub edges: Vec<EdgeId>,
23}
24
25impl<N, P, E> Graph<N, P, E> {
26    /// Computes all nets (connected components over ports, treating every
27    /// edge as a perfect junction).
28    ///
29    /// O(ports + edges) with union-find; intended to be recomputed on demand
30    /// after edits rather than maintained incrementally — at the scale this
31    /// crate targets (hundreds of elements), that's microseconds.
32    ///
33    /// ```
34    /// # use npe_graph::Graph;
35    /// let mut g: Graph<(), (), ()> = Graph::new();
36    /// let n1 = g.add_node(()); let n2 = g.add_node(()); let n3 = g.add_node(());
37    /// let a = g.add_port(n1, ()).unwrap();
38    /// let b = g.add_port(n2, ()).unwrap();
39    /// let c = g.add_port(n3, ()).unwrap(); // floating
40    /// g.connect(a, b, ()).unwrap();
41    /// let nets = g.nets();
42    /// assert_eq!(nets.len(), 2);                       // {a,b} and {c}
43    /// assert!(nets.iter().any(|n| n.ports.len() == 2 && n.edges.len() == 1));
44    /// assert!(nets.iter().any(|n| n.ports == vec![c] && n.edges.is_empty()));
45    /// ```
46    pub fn nets(&self) -> Vec<Net> {
47        // Union-find over a dense renumbering of live ports.
48        let port_ids: Vec<PortId> = self.all_ports().map(|(id, _)| id).collect();
49        let index: HashMap<PortId, usize> =
50            port_ids.iter().enumerate().map(|(i, &p)| (p, i)).collect();
51
52        let mut uf = UnionFind::new(port_ids.len());
53        for (edge, _) in self.all_edges() {
54            let (a, b) = self.edge_endpoints(edge).expect("live edge");
55            uf.union(index[&a], index[&b]);
56        }
57
58        // Bucket ports and edges by component root.
59        let mut by_root: HashMap<usize, Net> = HashMap::new();
60        for (i, &port) in port_ids.iter().enumerate() {
61            by_root.entry(uf.find(i)).or_default().ports.push(port);
62        }
63        for (edge, _) in self.all_edges() {
64            let (a, _) = self.edge_endpoints(edge).expect("live edge");
65            by_root
66                .entry(uf.find(index[&a]))
67                .or_default()
68                .edges
69                .push(edge);
70        }
71        by_root.into_values().collect()
72    }
73}
74
75/// Minimal union-find with path halving + union by size.
76struct UnionFind {
77    parent: Vec<usize>,
78    size: Vec<usize>,
79}
80
81impl UnionFind {
82    fn new(n: usize) -> Self {
83        UnionFind {
84            parent: (0..n).collect(),
85            size: vec![1; n],
86        }
87    }
88
89    fn find(&mut self, mut x: usize) -> usize {
90        while self.parent[x] != x {
91            self.parent[x] = self.parent[self.parent[x]]; // path halving
92            x = self.parent[x];
93        }
94        x
95    }
96
97    fn union(&mut self, a: usize, b: usize) {
98        let (mut ra, mut rb) = (self.find(a), self.find(b));
99        if ra == rb {
100            return;
101        }
102        if self.size[ra] < self.size[rb] {
103            core::mem::swap(&mut ra, &mut rb);
104        }
105        self.parent[rb] = ra;
106        self.size[ra] += self.size[rb];
107    }
108}
npe_graph/net.rs

npe_graph/
net.rs
