scirs2_graph/dynamic/
evolving.rs

1//! Evolving graph model: graphs that mutate through explicit, time-stamped operations.
2//!
3//! An `EvolvingGraph` records every structural change in a history log and can
4//! reconstruct its exact state at any past time by replaying the log.
5
6use std::collections::{HashMap, HashSet};
7
8/// An atomic structural change that can be applied to a graph.
9#[derive(Debug, Clone)]
10pub enum GraphChange {
11    /// Insert a new node.
12    AddNode(usize),
13    /// Delete a node (and any incident edges).
14    RemoveNode(usize),
15    /// Insert an undirected edge with the given weight.
16    AddEdge(usize, usize, f64),
17    /// Delete an undirected edge.
18    RemoveEdge(usize, usize),
19    /// Overwrite the weight of an existing (or new) edge.
20    UpdateEdgeWeight(usize, usize, f64),
21    /// Set a floating-point attribute on a node.
22    UpdateNodeAttribute(usize, String, f64),
23}
24
25/// A graph that evolves over time through a sequence of explicit changes.
26///
27/// Internally the current state is maintained for O(1) queries; the full history
28/// is kept so that `state_at` can reconstruct any past configuration.
29pub struct EvolvingGraph {
30    /// Chronological log of (timestamp, change) pairs.
31    pub history: Vec<(f64, GraphChange)>,
32    /// Timestamp of the most recent change applied.
33    pub current_time: f64,
34    nodes: HashSet<usize>,
35    /// Canonical edge key: (min(u,v), max(u,v)) → weight.
36    edges: HashMap<(usize, usize), f64>,
37    /// Per-node attribute maps.
38    node_attrs: HashMap<usize, HashMap<String, f64>>,
39}
40
41impl EvolvingGraph {
42    /// Create an empty evolving graph.
43    pub fn new() -> Self {
44        Self {
45            history: Vec::new(),
46            current_time: 0.0,
47            nodes: HashSet::new(),
48            edges: HashMap::new(),
49            node_attrs: HashMap::new(),
50        }
51    }
52
53    /// Apply a change at the given timestamp, updating internal state and history.
54    pub fn apply_change(&mut self, time: f64, change: GraphChange) {
55        self.current_time = time;
56        match &change {
57            GraphChange::AddNode(n) => {
58                self.nodes.insert(*n);
59            }
60            GraphChange::RemoveNode(n) => {
61                self.nodes.remove(n);
62                // Remove incident edges.
63                self.edges.retain(|&(a, b), _| a != *n && b != *n);
64                self.node_attrs.remove(n);
65            }
66            GraphChange::AddEdge(u, v, w) => {
67                self.nodes.insert(*u);
68                self.nodes.insert(*v);
69                let key = edge_key(*u, *v);
70                self.edges.insert(key, *w);
71            }
72            GraphChange::RemoveEdge(u, v) => {
73                let key = edge_key(*u, *v);
74                self.edges.remove(&key);
75            }
76            GraphChange::UpdateEdgeWeight(u, v, w) => {
77                let key = edge_key(*u, *v);
78                self.edges.insert(key, *w);
79            }
80            GraphChange::UpdateNodeAttribute(n, attr, val) => {
81                self.node_attrs
82                    .entry(*n)
83                    .or_default()
84                    .insert(attr.clone(), *val);
85            }
86        }
87        self.history.push((time, change));
88    }
89
90    /// Number of nodes in the current state.
91    pub fn n_nodes(&self) -> usize {
92        self.nodes.len()
93    }
94
95    /// Number of edges in the current state.
96    pub fn n_edges(&self) -> usize {
97        self.edges.len()
98    }
99
100    /// Whether node `n` exists in the current state.
101    pub fn has_node(&self, n: usize) -> bool {
102        self.nodes.contains(&n)
103    }
104
105    /// Whether an edge between `u` and `v` exists in the current state.
106    pub fn has_edge(&self, u: usize, v: usize) -> bool {
107        self.edges.contains_key(&edge_key(u, v))
108    }
109
110    /// Weight of the edge between `u` and `v`, if it exists.
111    pub fn edge_weight(&self, u: usize, v: usize) -> Option<f64> {
112        self.edges.get(&edge_key(u, v)).copied()
113    }
114
115    /// Get the value of attribute `attr` on node `n`, if set.
116    pub fn node_attribute(&self, n: usize, attr: &str) -> Option<f64> {
117        self.node_attrs.get(&n).and_then(|m| m.get(attr)).copied()
118    }
119
120    /// Reconstruct the graph state at `target_time` by replaying history.
121    ///
122    /// Only changes with timestamp `<= target_time` are applied.
123    pub fn state_at(&self, target_time: f64) -> Self {
124        let mut g = Self::new();
125        for (t, change) in &self.history {
126            if *t <= target_time {
127                g.apply_change(*t, change.clone());
128            }
129        }
130        g
131    }
132
133    /// Iterator over all current node identifiers (unordered).
134    pub fn nodes(&self) -> impl Iterator<Item = usize> + '_ {
135        self.nodes.iter().copied()
136    }
137
138    /// Iterator over all current edges: `(u, v, weight)`.
139    pub fn edges_iter(&self) -> impl Iterator<Item = (usize, usize, f64)> + '_ {
140        self.edges.iter().map(|(&(u, v), &w)| (u, v, w))
141    }
142}
143
144impl Default for EvolvingGraph {
145    fn default() -> Self {
146        Self::new()
147    }
148}
149
150/// Canonical undirected edge key.
151#[inline]
152fn edge_key(u: usize, v: usize) -> (usize, usize) {
153    (u.min(v), u.max(v))
154}
155
156#[cfg(test)]
157mod tests {
158    use super::*;
159
160    fn build_evolving() -> EvolvingGraph {
161        let mut g = EvolvingGraph::new();
162        g.apply_change(1.0, GraphChange::AddNode(0));
163        g.apply_change(2.0, GraphChange::AddNode(1));
164        g.apply_change(3.0, GraphChange::AddEdge(0, 1, 1.5));
165        g.apply_change(4.0, GraphChange::AddNode(2));
166        g.apply_change(5.0, GraphChange::AddEdge(1, 2, 2.0));
167        g.apply_change(6.0, GraphChange::RemoveNode(0));
168        g
169    }
170
171    #[test]
172    fn test_state_at_replays_history() {
173        let g = build_evolving();
174
175        // At t=3 nodes {0,1} and edge 0-1 should exist.
176        let s3 = g.state_at(3.0);
177        assert!(s3.has_node(0), "node 0 should be present at t=3");
178        assert!(s3.has_node(1), "node 1 should be present at t=3");
179        assert!(!s3.has_node(2), "node 2 should not be present at t=3");
180        assert!(s3.has_edge(0, 1), "edge 0-1 should be present at t=3");
181        assert!((s3.edge_weight(0, 1).unwrap_or(0.0) - 1.5).abs() < 1e-9);
182
183        // At t=5 nodes {0,1,2}, edges {0-1, 1-2}.
184        let s5 = g.state_at(5.0);
185        assert_eq!(s5.n_nodes(), 3);
186        assert_eq!(s5.n_edges(), 2);
187        assert!(s5.has_edge(1, 2));
188
189        // At t=6 node 0 and its incident edge are removed.
190        let s6 = g.state_at(6.0);
191        assert!(!s6.has_node(0), "node 0 should be removed at t=6");
192        assert!(!s6.has_edge(0, 1), "edge 0-1 should be removed at t=6");
193        assert!(s6.has_node(1));
194        assert!(s6.has_node(2));
195    }
196
197    #[test]
198    fn test_update_edge_weight() {
199        let mut g = EvolvingGraph::new();
200        g.apply_change(1.0, GraphChange::AddEdge(0, 1, 1.0));
201        g.apply_change(2.0, GraphChange::UpdateEdgeWeight(0, 1, 5.0));
202        assert!((g.edge_weight(0, 1).unwrap_or(0.0) - 5.0).abs() < 1e-9);
203    }
204
205    #[test]
206    fn test_node_attribute() {
207        let mut g = EvolvingGraph::new();
208        g.apply_change(1.0, GraphChange::AddNode(0));
209        g.apply_change(
210            2.0,
211            GraphChange::UpdateNodeAttribute(0, "weight".to_string(), std::f64::consts::PI),
212        );
213        assert!((g.node_attribute(0, "weight").unwrap_or(0.0) - std::f64::consts::PI).abs() < 1e-9);
214    }
215
216    #[test]
217    fn test_remove_node_cleans_edges() {
218        let mut g = EvolvingGraph::new();
219        g.apply_change(1.0, GraphChange::AddEdge(0, 1, 1.0));
220        g.apply_change(2.0, GraphChange::AddEdge(1, 2, 2.0));
221        g.apply_change(3.0, GraphChange::RemoveNode(1));
222        // Both edges incident to node 1 must be gone.
223        assert!(!g.has_edge(0, 1));
224        assert!(!g.has_edge(1, 2));
225        assert!(g.has_node(0));
226        assert!(g.has_node(2));
227    }
228
229    #[test]
230    fn test_canonical_edge_direction() {
231        let mut g = EvolvingGraph::new();
232        g.apply_change(1.0, GraphChange::AddEdge(3, 1, 7.0));
233        // Query in reverse direction should work (undirected).
234        assert!(g.has_edge(1, 3));
235        assert!((g.edge_weight(1, 3).unwrap_or(0.0) - 7.0).abs() < 1e-9);
236    }
237}
scirs2_graph/dynamic/evolving.rs

scirs2_graph/dynamic/
evolving.rs
