bixverse_methods/methods/
graph_diffusions.rs

1//! Implementation of the tied diffusion method from Paull, et al.,
2//! Bioinformatics, 2013
3
4#![allow(dead_code)]
5
6use rayon::prelude::*;
7use std::sync::Arc;
8
9use crate::graph::page_rank::*;
10use crate::prelude::BixverseFloat;
11
12///////////
13// Enums //
14///////////
15
16/// Enum for the TiedSumType types
17#[derive(Clone, Debug, Default)]
18pub enum TiedSumType {
19    /// Minimum between the two diffusion vectors
20    #[default]
21    Min,
22    /// Maximum between the two diffusion vectors
23    Max,
24    /// Average between the two diffusion vectors
25    Avg,
26}
27
28/// Parsing the tied summarisation types
29///
30/// ### Params
31///
32/// * `s` - The string that defines the tied summarisation type
33///
34/// ### Results
35///
36/// The `TiedSumType` defining the tied summarisation type
37pub fn parse_tied_sum(s: &str) -> Option<TiedSumType> {
38    match s.to_lowercase().as_str() {
39        "max" => Some(TiedSumType::Max),
40        "min" => Some(TiedSumType::Min),
41        "mean" => Some(TiedSumType::Avg),
42        _ => None,
43    }
44}
45
46////////////////////
47// Main functions //
48////////////////////
49
50/// Calculates the tied diffusion between two graphs
51///
52/// Function is designed to handle permutations of the personalisation vectors
53/// and leverages parallel processing for efficiency.
54///
55/// ### Params
56///
57/// * `node_names` - The names of the nodes in the graph
58/// * `from` - The source nodes of the edges in the graph
59/// * `to` - The destination nodes of the edges in the graph
60/// * `weights` - The weights of the edges in the graph
61/// * `summarisation_fun` - The function used to summarise the personalisation
62///   vectors (i.e., the tied diffusion)
63/// * `personalise_vecs_1` - The personalisation vectors for the first graph
64/// * `personalise_vecs_2` - The personalisation vectors for the second graph
65/// * `undirected` - Whether the graph is undirected
66/// * `damping_factor` - PageRank damping factor, i.e. the probability of
67///   continuing the walk
68/// * `max_iter` - Maximum number of power iterations
69/// * `tol` - Convergence threshold on the L1 change between iterations
70///
71/// ### Returns
72///
73/// * `Vec<Vec<T>>` - The tied diffusion between the two graphs for all of the
74///   supplied personalisation vectors
75#[allow(clippy::too_many_arguments)]
76pub fn tied_diffusion_parallel<T>(
77    node_names: Vec<String>,
78    from: Vec<String>,
79    to: Vec<String>,
80    weights: Option<&[T]>,
81    summarisation_fun: String,
82    personalise_vecs_1: &[Vec<T>],
83    personalise_vecs_2: &[Vec<T>],
84    undirected: bool,
85    damping_factor: T,
86    max_iter: usize,
87    tol: T,
88) -> Vec<Vec<T>>
89where
90    T: BixverseFloat + std::iter::Sum,
91{
92    let summarisation_type: TiedSumType = parse_tied_sum(&summarisation_fun).unwrap();
93    let pagerank_graph_1 = Arc::new(PageRankGraph::from_strings(
94        &node_names,
95        &from,
96        &to,
97        weights,
98        undirected,
99    ));
100
101    // For tied diffusion in the directed case, the directionality is reversed
102    let pagerank_graph_2 = Arc::new(if !undirected {
103        PageRankGraph::from_strings(&node_names, &to, &from, weights, undirected)
104    } else {
105        PageRankGraph::from_strings(&node_names, &from, &to, weights, undirected)
106    });
107
108    let half = T::from_f64(0.5).unwrap();
109
110    let tied_res: Vec<Vec<T>> = personalise_vecs_1
111        .into_par_iter()
112        .zip(personalise_vecs_2.into_par_iter())
113        .map_init(
114            || (PageRankWorkingMemory::new(), PageRankWorkingMemory::new()),
115            |(working_mem1, working_mem2), (diff1, diff2)| {
116                let pr1 = personalised_page_rank_optimised(
117                    &pagerank_graph_1,
118                    damping_factor,
119                    diff1,
120                    max_iter,
121                    tol,
122                    working_mem1,
123                );
124                let pr2 = personalised_page_rank_optimised(
125                    &pagerank_graph_2,
126                    damping_factor,
127                    diff2,
128                    max_iter,
129                    tol,
130                    working_mem2,
131                );
132
133                pr1.iter()
134                    .zip(pr2.iter())
135                    .map(|(&v1, &v2)| match summarisation_type {
136                        TiedSumType::Max => v1.max(v2),
137                        TiedSumType::Min => v1.min(v2),
138                        TiedSumType::Avg => (v1 + v2) * half, // multiplication is faster
139                    })
140                    .collect()
141            },
142        )
143        .collect();
144
145    tied_res
146}
bixverse_methods/methods/graph_diffusions.rs

bixverse_methods/methods/
graph_diffusions.rs
