dsalgo 0.3.10

A package for Datastructures and Algorithms.
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
57
58
59
60
61
62

use crate::{
    adjacency_list_graph_old::AdjacencyList,
    graph::edge::{
        From,
        To,
        Weight,
    },
    negative_cycle::NegativeCycleError,
    spfa::spfa,
};

pub trait ShortestPathPotentialEdge:
    From<V = usize>
    + To<V = usize>
    + Weight<i64>
    + std::convert::From<(usize, usize, i64)>
{
}

impl<T> ShortestPathPotentialEdge for T where
    T: From<V = usize>
        + To<V = usize>
        + Weight<i64>
        + std::convert::From<(usize, usize, i64)>
{
}

/// used to map edge weights from i64 to u64 space.
/// mainly spawned as preprocessing
/// before calling Dijkstra's algorithm multiple times
/// on a graph which might be containing negative weighted edges.

pub fn shortest_path_potential<E>(
    v_size: usize,
    mut directed_edges: Vec<E>,
) -> Result<Vec<i64>, NegativeCycleError>
where
    E: ShortestPathPotentialEdge,
{
    directed_edges.extend((0..v_size).map(|i| (v_size, i, 0).into()));

    let g = AdjacencyList::<E>::from((v_size + 1, directed_edges));

    match spfa(g.edges(), v_size) {
        Ok(mut potential) => {
            potential.pop();

            Ok(potential.into_iter().map(|x| x.unwrap()).collect())
        }
        Err(e) => Err(e),
    }
}

// TODO
#[cfg(test)]

mod tests {

    #[test]

    fn test() {}
}