best_path/best_path_calculator/floyd_warshall/
calculator.rs

1#[cfg(not(feature = "std"))]
2#[allow(unused_imports)]
3use alloc::{
4    borrow::ToOwned,
5    collections::{BTreeMap, BTreeSet},
6    string::String,
7    vec, vec::Vec,
8};
9use super::algo;
10use crate::types::*;
11use crate::*;
12#[cfg(feature = "std")]
13use std::collections::{BTreeMap, BTreeSet};
14
15impl From<algo::PathCalculationError> for CalculatorError {
16    fn from(err: algo::PathCalculationError) -> Self {
17        match err {
18            algo::PathCalculationError::NegativeCyclesError => CalculatorError::NegativeCyclesError
19        } 
20    }
21}
22
23pub const SCALE: f64 = 1_000_000_000_000.0;
24
25pub struct FloydWarshallCalculator {}
26
27impl<C: Currency, A: Amount, P: Provider> BestPathCalculator<C, A, P> for FloydWarshallCalculator {
28
29    /// Implements calculation of the best PricePathGraph, utilizing Floyd-Warshall algorithm
30    /// Accepts graph represented with trait Currency, Amount, Provider and wraps these into primitive indexed internal representations. Unwraps back on exit.
31    ///
32    /// Typical usage below. Note all prices are in scale of 10^12, including self references, eg. cost of BNB -> BNB = 10^12
33    /// ```rust
34    /// # use best_path::prelude::*;
35    /// # use best_path::prelude::floyd_warshall::calculator::FloydWarshallCalculator;
36    /// 
37    /// let in_graph = &[
38    ///     (
39    ///         ProviderPair { pair: Pair { source: "BNB".to_owned(), target: "USDT".to_owned() }, provider: "CRYPTO_COMPARE".to_owned() },
40    ///         364_190_000_000_000_u128
41    ///     ),
42    ///     (
43    ///         ProviderPair { pair: Pair { source: "USDT".to_owned(), target: "ETH".to_owned() }, provider: "COINGECKO".to_owned() },
44    ///         2_745_000_000_u128
45    ///     ),
46    /// ];
47    /// let res_out = FloydWarshallCalculator::calc_best_paths(in_graph);
48    /// let res_ref = res_out.as_ref().unwrap();
49    /// assert_eq!(
50    ///     &PricePath { total_cost: 999_701_550_000_u128, steps: vec![
51    ///         PathStep { pair: Pair { source: "BNB".to_owned(), target: "USDT".to_owned() }, provider: "CRYPTO_COMPARE".to_owned(), cost: 364_190_000_000_000_u128 },
52    ///         PathStep { pair: Pair { source: "USDT".to_owned(), target: "ETH".to_owned() }, provider: "COINGECKO".to_owned(), cost: 2_745_000_000_u128 }
53    ///     ] },
54    ///     res_ref.get(&Pair { source: "BNB".to_owned(), target: "ETH".to_owned() }).unwrap()
55    /// );
56    /// ```
57	fn calc_best_paths(pairs_and_prices: &[(ProviderPair<C, P>, A)]) -> Result<PricePathGraph<C, A, P>, CalculatorError> {
58        // get unique and indexed currencies and providers
59        let currencies = pairs_and_prices.iter().flat_map(|(ProviderPair { pair: Pair{source, target}, .. }, ..)| vec![source, target].into_iter())
60            .collect::<BTreeSet<_>>().into_iter().collect::<Vec<_>>();
61        let providers = pairs_and_prices.iter().map(|(ProviderPair { provider, .. }, ..)| provider)
62            .collect::<BTreeSet<_>>().into_iter().collect::<Vec<_>>();
63        let currencies_by_ind = currencies.iter().enumerate().map(|(i, &x)| (x, i)).collect::<BTreeMap<_, _>>();
64        let providers_by_ind = providers.iter().enumerate().map(|(i, &x)| (x, i)).collect::<BTreeMap<_, _>>();
65
66        // construct the graph for Floyd-Warshall lib
67        let mut graph = Vec::new();
68        for &c in currencies.iter() {
69            for (pp, cost) in pairs_and_prices {
70                if c == &pp.pair.source {
71                    graph.push(algo::Edge {
72                        pair:        algo::Pair{source: currencies_by_ind[&pp.pair.source], target: currencies_by_ind[&pp.pair.target]},
73                        provider:    providers_by_ind[&pp.provider],
74                        cost:        TryInto::<u128>::try_into(*cost).map_err(|_| CalculatorError::ConversionError)? as f64 / SCALE
75                    });
76                }
77            }
78        }
79
80        // run Floyd-Warshall for all combinations of currencies in the graph
81        let res = algo::longest_paths_mult(&graph)?;
82        let res_map = res.into_iter().map(|(algo::Pair{source, target}, algo::Path{total_cost, edges})| {
83            let pair = Pair{source: currencies[source].clone(), target: currencies[target].clone()};
84            let total_cost_u128 = (total_cost * SCALE) as u128;
85            let path = PricePath{ total_cost: total_cost_u128.try_into().ok().unwrap(), steps: edges.into_iter().map(|algo::Edge{pair: algo::Pair{source, target, ..}, provider, cost}|
86                PathStep{pair: Pair{source: currencies[source].clone(), target: currencies[target].clone()}, provider: providers[provider].clone(), cost: ((cost * SCALE) as u128).try_into().ok().unwrap()}).collect()
87            };
88            (pair, path)
89        }).collect::<BTreeMap<_, _>>();
90        Ok(res_map)
91	}
92}
best_path/best_path_calculator/floyd_warshall/calculator.rs

best_path/best_path_calculator/floyd_warshall/
calculator.rs
