digraphx-rs 0.1.2

Network Optimization Algorithms in Rust
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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

use petgraph::graph::DiGraph;
// use petgraph::visit::IntoNeighborsDirected;

struct NegCycleFinder<'a> {
    grph: &'a DiGraph<(), f64>,
    pred: std::collections::HashMap<petgraph::graph::NodeIndex, petgraph::graph::NodeIndex>,
}

impl<'a> NegCycleFinder<'a> {
    fn new(grph: &'a DiGraph<(), f64>) -> Self {
        Self {
            grph,
            pred: std::collections::HashMap::new(),
        }
    }

    fn find_cycle(&self) -> impl Iterator<Item = petgraph::graph::NodeIndex> + '_ {
        let mut visited = std::collections::HashMap::new();
        self.grph
            .node_indices()
            .filter(move |&v| !visited.contains_key(&v))
            .filter_map(move |v| {
                let mut u = v;
                while !visited.contains_key(&u) {
                    visited.insert(u, v);
                    u = self.pred.get(&u);
                    if visited.contains_key(&u) {
                        if visited[&u] == v {
                            return Some(u);
                        }
                        break;
                    }
                }
                None
            })
    }

    fn relax<F>(&mut self, dist: &mut [f64], get_weight: F) -> bool
    where
        F: Fn((petgraph::graph::NodeIndex, petgraph::graph::NodeIndex)) -> f64,
    {
        let mut changed = false;
        for u in self.grph.node_indices() {
            for v in self
                .grph
                .neighbors_directed(u, petgraph::Direction::Outgoing)
            {
                let wt = get_weight((u, v));
                let d = dist[u.index()] + wt;
                if dist[v.index()] > d {
                    dist[v.index()] = d;
                    self.pred.insert(v, u);
                    changed = true;
                }
            }
        }
        changed
    }

    fn find_neg_cycle<F>(
        &mut self,
        dist: &mut [f64],
        get_weight: F,
    ) -> Option<Vec<(petgraph::graph::NodeIndex, petgraph::graph::NodeIndex)>>
    where
        F: Fn((petgraph::graph::NodeIndex, petgraph::graph::NodeIndex)) -> f64,
    {
        self.pred.clear();
        let mut found = false;
        while !found && self.relax(dist, &get_weight) {
            for v in self.find_cycle() {
                found = true;
                return Some(self.cycle_list(v));
            }
        }
        None
    }

    fn cycle_list(
        &self,
        handle: petgraph::graph::NodeIndex,
    ) -> Vec<(petgraph::graph::NodeIndex, petgraph::graph::NodeIndex)> {
        let mut v = handle;
        let mut cycle = Vec::new();
        loop {
            let u = self.pred[&v];
            cycle.push((u, v));
            v = u;
            if v == handle {
                break;
            }
        }
        cycle
    }
}