solvr 0.2.0-beta.2

Advanced computing library for real-world problem solving - optimization, differential equations, interpolation, statistics, and more
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

//! Minimum spanning tree algorithm traits.
use crate::DType;

use numr::error::Result;
use numr::runtime::Runtime;

use super::types::{GraphData, MSTResult};

/// Minimum spanning tree algorithms.
///
/// Finds the subset of edges that connects all nodes with minimum total weight.
/// Only meaningful for undirected graphs.
pub trait MSTAlgorithms<R: Runtime<DType = DType>> {
    /// Compute the minimum spanning tree using Kruskal's algorithm.
    ///
    /// Sorts edges by weight and greedily adds edges that don't form cycles
    /// (using union-find). Sequential algorithm.
    ///
    /// # Complexity
    /// O(E log E) for sorting + O(E α(V)) for union-find.
    ///
    /// # Errors
    /// Returns error if the graph is directed.
    fn minimum_spanning_tree(&self, graph: &GraphData<R>) -> Result<MSTResult<R>>;
}