rustygraph/core/
visibility_graph.rs

1//! Visibility graph construction and representation.
2//!
3//! This module provides types for building and working with visibility graphs
4//! from time series data. It supports both natural and horizontal visibility algorithms.
5//!
6//! # Examples
7//!
8//! ```rust
9//! use rustygraph::{TimeSeries, VisibilityGraph};
10//!
11//! let series = TimeSeries::from_raw(vec![1.0, 3.0, 2.0, 4.0, 1.0]).unwrap();
12//! let graph = VisibilityGraph::from_series(&series)
13//!     .natural_visibility()
14//!     .unwrap();
15//!
16//! println!("Number of edges: {}", graph.edges().len());
17//! ```
18
19use crate::core::time_series::TimeSeries;
20use crate::core::features::FeatureSet;
21use std::collections::HashMap;
22use std::fmt;
23
24/// Visibility graph representation with node features.
25///
26/// A visibility graph represents temporal connectivity patterns in time series data.
27/// Each data point becomes a node, and edges connect points that have "visibility"
28/// to each other according to the chosen algorithm.
29///
30/// # Examples
31///
32/// ## Basic usage
33///
34/// ```rust
35/// use rustygraph::{TimeSeries, VisibilityGraph};
36///
37/// let series = TimeSeries::from_raw(vec![1.0, 3.0, 2.0, 4.0, 1.0]).unwrap();
38/// let graph = VisibilityGraph::from_series(&series)
39///     .natural_visibility()
40///     .unwrap();
41///
42/// // Access graph properties
43/// println!("Nodes: {}", graph.node_count);
44/// println!("Edges: {}", graph.edges().len());
45/// println!("Degree sequence: {:?}", graph.degree_sequence());
46/// ```
47///
48/// ## With features
49///
50/// ```rust
51/// use rustygraph::{TimeSeries, VisibilityGraph, FeatureSet, BuiltinFeature};
52///
53/// let series = TimeSeries::from_raw(vec![1.0, 3.0, 2.0, 4.0]).unwrap();
54/// let graph = VisibilityGraph::from_series(&series)
55///     .with_features(
56///         FeatureSet::new()
57///             .add_builtin(BuiltinFeature::DeltaForward)
58///             .add_builtin(BuiltinFeature::LocalSlope)
59///     )
60///     .natural_visibility()
61///     .unwrap();
62/// ```
63#[derive(Debug, Clone)]
64pub struct VisibilityGraph<T> {
65    /// Number of nodes (data points)
66    pub node_count: usize,
67    /// Graph edges as (source, target) pairs
68    pub(crate) edges: HashMap<(usize, usize), f64>,
69    /// Adjacency list representation
70    adjacency: Vec<Vec<f64>>,
71    /// Computed features for each node
72    pub node_features: Vec<HashMap<String, T>>,
73    /// Whether the graph is directed
74    pub directed: bool,
75}
76
77/// Direction mode for visibility graphs.
78#[derive(Debug, Clone, Copy, PartialEq, Eq)]
79pub enum GraphDirection {
80    /// Undirected graph (default) - edges go both ways
81    Undirected,
82    /// Directed graph - edges only from earlier to later time points
83    Directed,
84}
85
86impl<T> VisibilityGraph<T> {
87    /// Creates a visibility graph builder from a time series.
88    ///
89    /// This is the main entry point for constructing visibility graphs.
90    /// Use the returned builder to configure options and select an algorithm.
91    ///
92    /// # Arguments
93    ///
94    /// - `series`: Reference to time series data
95    ///
96    /// # Returns
97    ///
98    /// A [`VisibilityGraphBuilder`] for configuration
99    ///
100    /// # Examples
101    ///
102    /// ```rust
103    /// use rustygraph::{TimeSeries, VisibilityGraph};
104    ///
105    /// let series = TimeSeries::from_raw(vec![1.0, 2.0, 3.0]).unwrap();
106    /// let graph = VisibilityGraph::from_series(&series)
107    ///     .natural_visibility()
108    ///     .unwrap();
109    /// ```
110    pub fn from_series(series: &TimeSeries<T>) -> VisibilityGraphBuilder<'_, T> {
111        VisibilityGraphBuilder {
112            series,
113            feature_set: None,
114            direction: GraphDirection::Undirected,
115        }
116    }
117
118    /// Returns all edges in the graph.
119    ///
120    /// Each edge is represented as a tuple `(source, target)` where both
121    /// values are node indices.
122    ///
123    /// # Examples
124    ///
125    /// ```rust
126    /// use rustygraph::{TimeSeries, VisibilityGraph};
127    ///
128    /// let series = TimeSeries::from_raw(vec![1.0, 3.0, 2.0]).unwrap();
129    /// let graph = VisibilityGraph::from_series(&series)
130    ///     .natural_visibility()
131    ///     .unwrap();
132    ///
133    /// for (&(src, dst), &weight) in graph.edges() {
134    ///     println!("{} -> {}: {}", src, dst, weight);
135    /// }
136    /// ```
137    pub fn edges(&self) -> &HashMap<(usize, usize), f64> {
138        &self.edges
139    }
140
141    /// Returns the adjacency list for a specific node.
142    ///
143    /// # Arguments
144    ///
145    /// - `node`: Node index
146    ///
147    /// # Returns
148    ///
149    /// Slice of adjacent node indices, or `None` if node doesn't exist
150    ///
151    /// # Examples
152    ///
153    /// ```rust
154    /// use rustygraph::{TimeSeries, VisibilityGraph};
155    ///
156    /// let series = TimeSeries::from_raw(vec![1.0, 3.0, 2.0, 4.0]).unwrap();
157    /// let graph = VisibilityGraph::from_series(&series)
158    ///     .natural_visibility()
159    ///     .unwrap();
160    ///
161    /// if let Some(neighbors) = graph.neighbors(0) {
162    ///     println!("Node 0 is connected to: {:?}", neighbors);
163    /// }
164    /// ```
165    pub fn neighbors(&self, node: usize) -> Option<&[f64]> {
166        self.adjacency.get(node).map(|v| v.as_slice())
167    }
168
169    /// Checks if an edge exists between two nodes.
170    ///
171    /// # Arguments
172    ///
173    /// - `from`: Source node index
174    /// - `to`: Target node index
175    ///
176    /// # Returns
177    ///
178    /// `true` if an edge exists, `false` otherwise
179    pub fn has_edge(&self, from: usize, to: usize) -> bool {
180        self.edges.contains_key(&(from, to)) ||
181        (!self.directed && self.edges.contains_key(&(to, from)))
182    }
183
184    /// Returns the indices of neighboring nodes.
185    ///
186    /// # Arguments
187    ///
188    /// - `node`: Node index
189    ///
190    /// # Returns
191    ///
192    /// Vector of neighbor node indices
193    pub fn neighbor_indices(&self, node: usize) -> Vec<usize> {
194        self.edges
195            .keys()
196            .filter_map(|(i, j)| {
197                if *i == node {
198                    Some(*j)
199                } else if !self.directed && *j == node {
200                    Some(*i)
201                } else {
202                    None
203                }
204            })
205            .collect()
206    }
207
208    /// Returns the degree of a node (number of connections).
209    ///
210    /// # Arguments
211    ///
212    /// - `node`: Node index
213    ///
214    /// # Returns
215    ///
216    /// The number of edges connected to this node, or `None` if node doesn't exist
217    ///
218    /// # Examples
219    ///
220    /// ```rust
221    /// use rustygraph::{TimeSeries, VisibilityGraph};
222    ///
223    /// let series = TimeSeries::from_raw(vec![1.0, 3.0, 2.0, 4.0]).unwrap();
224    /// let graph = VisibilityGraph::from_series(&series)
225    ///     .natural_visibility()
226    ///     .unwrap();
227    ///
228    /// if let Some(degree) = graph.degree(0) {
229    ///     println!("Node 0 has degree {}", degree);
230    /// }
231    /// ```
232    pub fn degree(&self, node: usize) -> Option<usize> {
233        self.adjacency.get(node).map(|v| v.len())
234    }
235
236    /// Returns the degree sequence of all nodes.
237    ///
238    /// The degree sequence is a vector where each element is the degree
239    /// of the corresponding node.
240    ///
241    /// # Examples
242    ///
243    /// ```rust
244    /// use rustygraph::{TimeSeries, VisibilityGraph};
245    ///
246    /// let series = TimeSeries::from_raw(vec![1.0, 3.0, 2.0, 4.0]).unwrap();
247    /// let graph = VisibilityGraph::from_series(&series)
248    ///     .natural_visibility()
249    ///     .unwrap();
250    ///
251    /// let degrees = graph.degree_sequence();
252    /// println!("Degree sequence: {:?}", degrees);
253    /// ```
254    pub fn degree_sequence(&self) -> Vec<usize> {
255        self.adjacency.iter().map(|v| v.len()).collect()
256    }
257
258    /// Returns computed features for a specific node.
259    ///
260    /// # Arguments
261    ///
262    /// - `node`: Node index
263    ///
264    /// # Returns
265    ///
266    /// A map of feature names to values, or `None` if node doesn't exist
267    /// or no features were computed
268    ///
269    /// # Examples
270    ///
271    /// ```rust
272    /// use rustygraph::{TimeSeries, VisibilityGraph, FeatureSet, BuiltinFeature};
273    ///
274    /// let series = TimeSeries::from_raw(vec![1.0, 3.0, 2.0]).unwrap();
275    /// let graph = VisibilityGraph::from_series(&series)
276    ///     .with_features(
277    ///         FeatureSet::new().add_builtin(BuiltinFeature::DeltaForward)
278    ///     )
279    ///     .natural_visibility()
280    ///     .unwrap();
281    ///
282    /// if let Some(features) = graph.node_features(0) {
283    ///     for (name, value) in features {
284    ///         println!("{}: {}", name, value);
285    ///     }
286    /// }
287    /// ```
288    pub fn node_features(&self, node: usize) -> Option<&HashMap<String, T>> {
289        self.node_features.get(node)
290    }
291
292    /// Exports the graph to an adjacency matrix.
293    ///
294    /// The adjacency matrix is a square boolean matrix where `matrix[i][j]`
295    /// is `true` if there is an edge from node `i` to node `j`.
296    ///
297    /// # Examples
298    ///
299    /// ```rust
300    /// use rustygraph::{TimeSeries, VisibilityGraph};
301    ///
302    /// let series = TimeSeries::from_raw(vec![1.0, 3.0, 2.0]).unwrap();
303    /// let graph = VisibilityGraph::from_series(&series)
304    ///     .natural_visibility()
305    ///     .unwrap();
306    ///
307    /// let matrix = graph.to_adjacency_matrix();
308    /// for row in &matrix {
309    ///     println!("{:?}", row);
310    /// }
311    /// ```
312    pub fn to_adjacency_matrix(&self) -> Vec<Vec<f64>> {
313        let mut matrix = vec![vec![0.0; self.node_count]; self.node_count];
314        for &(src, dst) in self.edges.keys() {
315            matrix[src][dst] = self.edges[&(src, dst)];
316        }
317        matrix
318    }
319}
320
321/// Builder for constructing visibility graphs with options.
322///
323/// This builder allows you to configure features and select the visibility
324/// algorithm before constructing the graph.
325///
326/// # Examples
327///
328/// ```rust
329/// use rustygraph::{TimeSeries, VisibilityGraph, FeatureSet, BuiltinFeature};
330///
331/// let series = TimeSeries::from_raw(vec![1.0, 2.0, 3.0]).unwrap();
332/// let graph = VisibilityGraph::from_series(&series)
333///     .with_features(
334///         FeatureSet::new().add_builtin(BuiltinFeature::DeltaForward)
335///     )
336///     .natural_visibility()
337///     .unwrap();
338/// ```
339pub struct VisibilityGraphBuilder<'a, T> {
340    #[allow(dead_code)] // Will be used when algorithms are implemented
341    series: &'a TimeSeries<T>,
342    feature_set: Option<FeatureSet<T>>,
343    direction: GraphDirection,
344}
345
346impl<'a, T> VisibilityGraphBuilder<'a, T>
347where
348    T: Copy + PartialOrd + Into<f64>,
349{
350    /// Specifies features to compute for each node.
351    ///
352    /// Features are computed after the graph structure is built.
353    ///
354    /// # Arguments
355    ///
356    /// - `features`: A configured [`FeatureSet`]
357    ///
358    /// # Examples
359    ///
360    /// ```rust
361    /// use rustygraph::{TimeSeries, VisibilityGraph, FeatureSet, BuiltinFeature};
362    ///
363    /// let series = TimeSeries::from_raw(vec![1.0, 2.0, 3.0]).unwrap();
364    /// let graph = VisibilityGraph::from_series(&series)
365    ///     .with_features(
366    ///         FeatureSet::new()
367    ///             .add_builtin(BuiltinFeature::DeltaForward)
368    ///             .add_builtin(BuiltinFeature::LocalSlope)
369    ///     )
370    ///     .natural_visibility()
371    ///     .unwrap();
372    /// ```
373    pub fn with_features(mut self, features: FeatureSet<T>) -> Self {
374        self.feature_set = Some(features);
375        self
376    }
377
378    /// Sets the graph direction mode.
379    ///
380    /// # Arguments
381    ///
382    /// - `direction`: Whether the graph should be directed or undirected
383    ///
384    /// # Examples
385    ///
386    /// ```rust
387    /// use rustygraph::{TimeSeries, VisibilityGraph, GraphDirection};
388    ///
389    /// let series = TimeSeries::from_raw(vec![1.0, 2.0, 3.0]).unwrap();
390    /// let graph = VisibilityGraph::from_series(&series)
391    ///     .with_direction(GraphDirection::Directed)
392    ///     .natural_visibility()
393    ///     .unwrap();
394    /// ```
395    pub fn with_direction(mut self, direction: GraphDirection) -> Self {
396        self.direction = direction;
397        self
398    }
399
400    /// Constructs a natural visibility graph.
401    ///
402    /// In a natural visibility graph, two nodes (i, yi) and (j, yj) are connected
403    /// if all intermediate points (k, yk) satisfy the visibility criterion:
404    ///
405    /// `yk < yi + (yj - yi) * (tk - ti) / (tj - ti)`
406    ///
407    /// # Algorithm
408    ///
409    /// Uses a monotonic stack optimization for O(n) complexity per node.
410    ///
411    /// # Errors
412    ///
413    /// Returns [`GraphError`] if the time series is empty or feature computation fails.
414    ///
415    /// # Examples
416    ///
417    /// ```rust
418    /// use rustygraph::{TimeSeries, VisibilityGraph};
419    ///
420    /// let series = TimeSeries::from_raw(vec![1.0, 3.0, 2.0, 4.0, 1.0]).unwrap();
421    /// let graph = VisibilityGraph::from_series(&series)
422    ///     .natural_visibility()
423    ///     .unwrap();
424    /// ```
425    pub fn natural_visibility(self) -> Result<VisibilityGraph<T>, GraphError>
426    where
427        T: Copy + PartialOrd + Into<f64> + std::ops::Add<Output = T> + std::ops::Sub<Output = T>
428           + std::ops::Mul<Output = T> + std::ops::Div<Output = T> + From<f64> + Send + Sync,
429    {
430        use crate::core::algorithms::edges::{VisibilityEdges as create_visibility_edges, VisibilityType};
431
432        // Check for empty series
433        if self.series.is_empty() {
434            return Err(GraphError::EmptyTimeSeries);
435        }
436
437        // Check for all missing values
438        if self.series.values.iter().all(|v| v.is_none()) {
439            return Err(GraphError::AllValuesMissing);
440        }
441
442        // Compute edges using natural visibility algorithm
443        // Use parallel computation when available (significant speedup for large graphs)
444        let edges: HashMap<(usize, usize), f64> = {
445            let edge_computer = create_visibility_edges::new(
446                self.series,
447                VisibilityType::Natural,
448                |_, _, _, _| 1.0
449            );
450
451            #[cfg(feature = "parallel")]
452            {
453                edge_computer.compute_edges_parallel()
454            }
455
456            #[cfg(not(feature = "parallel"))]
457            {
458                edge_computer.compute_edges()
459            }
460        };
461
462        // Compute adjacency list
463        let directed = matches!(self.direction, GraphDirection::Directed);
464        let adj: Vec<Vec<f64>> = build_adjacency_list(self.series.len(), &edges, directed);
465
466        // Compute node features if feature set is provided
467        let node_features = if let Some(feature_set) = self.feature_set {
468            compute_node_features(&self.series.values, &feature_set)
469        } else {
470            vec![]
471        };
472
473        Ok(VisibilityGraph {
474            node_count: self.series.len(),
475            edges,
476            adjacency: adj,
477            node_features,
478            directed,
479        })
480    }
481
482    /// Constructs a horizontal visibility graph.
483    ///
484    /// In a horizontal visibility graph, two nodes are connected if all
485    /// intermediate values are strictly lower than both endpoints.
486    ///
487    /// # Algorithm
488    ///
489    /// Uses a linear scan approach with O(n) average case complexity.
490    ///
491    /// # Errors
492    ///
493    /// Returns [`GraphError`] if the time series is empty or feature computation fails.
494    ///
495    /// # Examples
496    ///
497    /// ```rust
498    /// use rustygraph::{TimeSeries, VisibilityGraph};
499    ///
500    /// let series = TimeSeries::from_raw(vec![1.0, 3.0, 2.0, 4.0, 1.0]).unwrap();
501    /// let graph = VisibilityGraph::from_series(&series)
502    ///     .horizontal_visibility()
503    ///     .unwrap();
504    /// ```
505    pub fn horizontal_visibility(self) -> Result<VisibilityGraph<T>, GraphError>
506    where
507        T: Copy + PartialOrd + Into<f64> + std::ops::Add<Output = T> + std::ops::Sub<Output = T>
508           + std::ops::Mul<Output = T> + std::ops::Div<Output = T> + From<f64> + Send + Sync,
509    {
510        use crate::core::algorithms::edges::{VisibilityEdges as create_visibility_edges, VisibilityType};
511
512        // Check for empty series
513        if self.series.is_empty() {
514            return Err(GraphError::EmptyTimeSeries);
515        }
516
517        // Check for all missing values
518        if self.series.values.iter().all(|v| v.is_none()) {
519            return Err(GraphError::AllValuesMissing);
520        }
521
522        // Compute edges using horizontal visibility algorithm
523        // Use parallel computation when available (significant speedup for large graphs)
524        let edges: HashMap<(usize, usize), f64> = {
525            let edge_computer = create_visibility_edges::new(
526                self.series,
527                VisibilityType::Horizontal,
528                |_, _, _, _| 1.0
529            );
530
531            #[cfg(feature = "parallel")]
532            {
533                edge_computer.compute_edges_parallel()
534            }
535
536            #[cfg(not(feature = "parallel"))]
537            {
538                edge_computer.compute_edges()
539            }
540        };
541
542        // Compute adjacency list
543        let directed = matches!(self.direction, GraphDirection::Directed);
544        let adj: Vec<Vec<f64>> = build_adjacency_list(self.series.len(), &edges, directed);
545
546        // Compute node features if feature set is provided
547        let node_features = if let Some(feature_set) = self.feature_set {
548            compute_node_features(&self.series.values, &feature_set)
549        } else {
550            vec![]
551        };
552
553        Ok(VisibilityGraph {
554            node_count: self.series.len(),
555            edges,
556            adjacency: adj,
557            node_features,
558            directed,
559        })
560    }
561}
562
563/// Errors during visibility graph construction.
564#[derive(Debug, Clone, PartialEq)]
565pub enum GraphError {
566    /// Time series is empty
567    EmptyTimeSeries,
568    /// Feature computation failed
569    FeatureComputationFailed {
570        /// Name of the feature that failed
571        feature: String,
572        /// Node index where failure occurred
573        node: usize,
574    },
575    /// All values are missing
576    AllValuesMissing,
577}
578
579impl fmt::Display for GraphError {
580    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
581        match self {
582            GraphError::EmptyTimeSeries => write!(f, "Time series is empty"),
583            GraphError::FeatureComputationFailed { feature, node } => {
584                write!(f, "Feature '{}' computation failed at node {}", feature, node)
585            }
586            GraphError::AllValuesMissing => write!(f, "All values are missing"),
587        }
588    }
589}
590
591
592fn build_adjacency_list(node_count: usize, edges: &HashMap<(usize, usize), f64>, directed: bool) -> Vec<Vec<f64>> {
593    let mut adjacency = vec![Vec::new(); node_count];
594    for &(src, dst) in edges.keys() {
595        let weight = edges.get(&(src, dst)).copied().unwrap_or(0.0);
596        adjacency[src].push(weight);
597        if !directed {
598            adjacency[dst].push(weight); // Add reverse edge for undirected
599        }
600    }
601    adjacency
602}
603
604/// Computes all features for all nodes in the series.
605///
606/// This function automatically uses parallel computation when the `parallel` feature is enabled,
607/// otherwise falls back to sequential computation.
608pub(crate) fn compute_node_features<T>(
609    series: &[Option<T>],
610    feature_set: &FeatureSet<T>,
611) -> Vec<HashMap<String, T>>
612where
613    T: Copy + PartialOrd + std::ops::Add<Output = T> + std::ops::Sub<Output = T>
614       + std::ops::Mul<Output = T> + std::ops::Div<Output = T> + From<f64> + Into<f64>
615       + Send + Sync,
616{
617    // Use parallel implementation when parallel feature is enabled
618    #[cfg(feature = "parallel")]
619    {
620        crate::performance::parallel::compute_node_features_parallel(series, feature_set)
621    }
622
623    // Fall back to sequential implementation
624    #[cfg(not(feature = "parallel"))]
625    {
626        let mut node_features = Vec::with_capacity(series.len());
627
628        for i in 0..series.len() {
629            let mut features = HashMap::new();
630
631            // Compute each feature for this node
632            for feature in &feature_set.features {
633                if let Some(value) = feature.compute(series, i, &feature_set.missing_strategy) {
634                    features.insert(feature.name().to_string(), value);
635                }
636            }
637
638            node_features.push(features);
639        }
640
641        node_features
642    }
643}
644
645impl std::error::Error for GraphError {}
646
rustygraph/core/visibility_graph.rs

rustygraph/core/
visibility_graph.rs
