ratio_markov/
sequence.rs

1//! # Sequencing module
2//!
3//! ## License
4//!
5//! This Source Code Form is subject to the terms of the Mozilla Public License, v. 2.0.
6//! If a copy of the MPL was not distributed with this file,
7//! You can obtain one at <https://mozilla.org/MPL/2.0/>.
8//!
9//! **Code examples both in the docstrings and rendered documentation are free to use.**
10
11use crate::{DMatrix, MarkovFlow};
12
13/// Sequencing a graph based on Markov steady-state flow calculations on its adjacency matrix.
14///
15/// # Arguments
16///
17/// * `adj` - Square adjacency matrix with nodes in identical order on both axis.
18///   Only positive adjacency values are used in the calculations.
19/// * `mu` - Evaporation constant. Factor by which flow is reduced after passing
20///   through a node.
21/// * `influence` - The weight by which nodal influence is taken into account.
22///   Forces influential nodes to be put earlier in the chain.
23/// * `dependency` - The weight by which nodal dependency is taken into account.
24///   Forces dependent nodes to be put later in the chain.
25///
26/// # Returns
27///
28/// A vector with the node indices in the sequenced order. E.g. the first vector entry
29/// denotes the node index w.r.t. the adjacency matrix that should be put first.
30pub fn sequence(adj: &DMatrix<f64>, mu: f64, influence: f64, dependency: f64) -> Vec<usize> {
31    let flow = MarkovFlow::new(adj, mu, true);
32
33    let influence_vector = flow.flow_matrix.row_sum();
34    let dependency_vector = flow.flow_matrix.column_sum();
35
36    let penalty_vector: Vec<f64> = (0..flow.dim)
37        .map(|i| dependency * dependency_vector[i] - influence * influence_vector[i])
38        .collect();
39
40    let mut sequence: Vec<usize> = (0..flow.dim).collect();
41    sequence.sort_by(|&i, &j| penalty_vector[i].partial_cmp(&penalty_vector[j]).unwrap());
42    sequence
43}
44
45#[cfg(test)]
46mod tests {
47    use super::*;
48    #[test]
49    fn test_sequence_trivial() {
50        // 0 very dependent on both, 1 slight dependent on 0, 2 very dependent on 1.
51        let adj = DMatrix::from_row_slice(3, 3, &[0.0, 5.0, 10.0, 1.0, 0.0, 0.0, 0.0, 10.0, 0.0]);
52        let seq = sequence(&adj, 2.0, 1.0, 1.0);
53        let reference: Vec<usize> = vec![1, 2, 0];
54        assert_eq!(seq, reference);
55    }
56}
ratio_markov/sequence.rs

ratio_markov/
sequence.rs
