ratio-markov 0.5.1

Markov chain steady-state calculations with applications in graph clustering and sequencing.
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

//! # Sequencing module
//!
//! ## License
//!
//! This Source Code Form is subject to the terms of the Mozilla Public License, v. 2.0.
//! If a copy of the MPL was not distributed with this file,
//! You can obtain one at <https://mozilla.org/MPL/2.0/>.
//!
//! **Code examples both in the docstrings and rendered documentation are free to use.**

use crate::{DMatrix, MarkovFlow};

/// Sequencing a graph based on Markov steady-state flow calculations on its adjacency matrix.
///
/// # Arguments
///
/// * `adj` - Square adjacency matrix with nodes in identical order on both axis.
///   Only positive adjacency values are used in the calculations.
/// * `mu` - Evaporation constant. Factor by which flow is reduced after passing
///   through a node.
/// * `influence` - The weight by which nodal influence is taken into account.
///   Forces influential nodes to be put earlier in the chain.
/// * `dependency` - The weight by which nodal dependency is taken into account.
///   Forces dependent nodes to be put later in the chain.
///
/// # Returns
///
/// A vector with the node indices in the sequenced order. E.g. the first vector entry
/// denotes the node index w.r.t. the adjacency matrix that should be put first.
pub fn sequence(adj: &DMatrix<f64>, mu: f64, influence: f64, dependency: f64) -> Vec<usize> {
    let flow = MarkovFlow::new(adj, mu, true);

    let influence_vector = flow.flow_matrix.row_sum();
    let dependency_vector = flow.flow_matrix.column_sum();

    let penalty_vector: Vec<f64> = (0..flow.dim)
        .map(|i| dependency * dependency_vector[i] - influence * influence_vector[i])
        .collect();

    let mut sequence: Vec<usize> = (0..flow.dim).collect();
    sequence.sort_by(|&i, &j| penalty_vector[i].partial_cmp(&penalty_vector[j]).unwrap());
    sequence
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_sequence_trivial() {
        // 0 very dependent on both, 1 slight dependent on 0, 2 very dependent on 1.
        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]);
        let seq = sequence(&adj, 2.0, 1.0, 1.0);
        let reference: Vec<usize> = vec![1, 2, 0];
        assert_eq!(seq, reference);
    }
}