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
57
58
59
60
61

//! General data structures for graph search.

use super::OfflineResult;
use crate::schedule::IntegralSchedule;
use serde_derive::{Deserialize, Serialize};
use std::{collections::HashMap, hash::Hash};

/// Resulting path alongside cache which can be used for subsequent iterations.
#[derive(Clone, Debug)]
pub struct CachedPath<C> {
    pub path: Path,
    pub cache: C,
}
impl<C> OfflineResult<i32> for CachedPath<C> {
    fn xs(self) -> IntegralSchedule {
        self.path.xs
    }
}

/// The minimal cost from some initial vertice alongside the shortest path to the final vertice.
#[derive(Clone, Debug, Deserialize, PartialEq, Serialize)]
pub struct Path {
    /// Schortest path.
    pub xs: IntegralSchedule,
    /// Associated (i.e. cached) cost.
    pub cost: f64,
}
impl OfflineResult<i32> for Path {
    fn xs(self) -> IntegralSchedule {
        self.xs
    }
}

/// Data structure to cache results of the algorithm up to some time slot $t$.
#[derive(Clone, Debug, Deserialize, Serialize)]
pub struct Cache<T>
where
    T: Eq + Hash,
{
    /// Time slot.
    pub t: i32,
    /// Computed paths up to time slot $t$.
    pub paths: Paths<T>,
}

/// Returns next initial time slot $t_init$ and $paths$ from cache.
pub fn read_cache<T>(
    cache: Option<Cache<T>>,
    default: impl Fn() -> (i32, Paths<T>),
) -> (i32, Paths<T>)
where
    T: Eq + Hash,
{
    match cache {
        Some(Cache { t: prev_t, paths }) => (prev_t + 1, paths),
        None => default(),
    }
}

/// Maps a vertice to its minimal cost from some initial vertice alongside the shortest path.
pub type Paths<T> = HashMap<T, Path>;