aboutsummaryrefslogtreecommitdiff
path: root/src/rpc/graph_algo.rs
diff options
context:
space:
mode:
authorMendes <mendes.oulamara@pm.me>2022-09-22 19:30:01 +0200
committerMendes <mendes.oulamara@pm.me>2022-09-22 19:30:01 +0200
commitbd842e1388a324e2a3956465e9b32d0dc739a8d9 (patch)
tree449c79c43e4de6d7fe0e046f545fb63d782c7dc3 /src/rpc/graph_algo.rs
parent7f3249a23770fd4da981c2ecb1126da97e9b4ca5 (diff)
downloadgarage-bd842e1388a324e2a3956465e9b32d0dc739a8d9.tar.gz
garage-bd842e1388a324e2a3956465e9b32d0dc739a8d9.zip
Correction of a few bugs in the tests, modification of ClusterLayout::check
Diffstat (limited to 'src/rpc/graph_algo.rs')
-rw-r--r--src/rpc/graph_algo.rs41
1 files changed, 18 insertions, 23 deletions
diff --git a/src/rpc/graph_algo.rs b/src/rpc/graph_algo.rs
index 1a809b80..a5a1e4ba 100644
--- a/src/rpc/graph_algo.rs
+++ b/src/rpc/graph_algo.rs
@@ -182,7 +182,7 @@ impl Graph<FlowEdge>{
//assignation, we shuffle the neighbours of the nodes. Hence,
//the vertices do not consider their neighbours in the same order.
self.shuffle_edges();
-
+
//We run Dinic's max flow algorithm
loop {
//We build the level array from Dinic's algorithm.
@@ -206,7 +206,6 @@ impl Graph<FlowEdge>{
//There is no residual flow
break;
}
-
//Now we run DFS respecting the level array
let mut next_nbd = vec![0; nb_vertices];
let mut lifo = VecDeque::new();
@@ -220,14 +219,12 @@ impl Graph<FlowEdge>{
//The DFS reached the sink, we can add a
//residual flow.
lifo.pop_back();
- while !lifo.is_empty() {
- if let Some((id, _)) = lifo.pop_back() {
- let nbd = next_nbd[id];
- self.graph[id][nbd].flow += f as i32;
- let id_rev = self.graph[id][nbd].dest;
- let nbd_rev = self.graph[id][nbd].rev;
- self.graph[id_rev][nbd_rev].flow -= f as i32;
- }
+ while let Some((id, _)) = lifo.pop_back() {
+ let nbd = next_nbd[id];
+ self.graph[id][nbd].flow += f as i32;
+ let id_rev = self.graph[id][nbd].dest;
+ let nbd_rev = self.graph[id][nbd].rev;
+ self.graph[id_rev][nbd_rev].flow -= f as i32;
}
lifo.push_back((idsource, flow_upper_bound));
continue;
@@ -243,10 +240,14 @@ impl Graph<FlowEdge>{
continue;
}
//else we can try to send flow from id to its nbd
- let new_flow = min(f, self.graph[id][nbd].cap - self.graph[id][nbd].flow as u32 );
+ let new_flow = min(f as i32, self.graph[id][nbd].cap as i32 - self.graph[id][nbd].flow) as u32;
+ if new_flow == 0 {
+ next_nbd[id] += 1;
+ continue;
+ }
if let (Some(lvldest), Some(lvlid)) =
(level[self.graph[id][nbd].dest], level[id]){
- if lvldest <= lvlid || new_flow == 0 {
+ if lvldest <= lvlid {
//We cannot send flow to nbd.
next_nbd[id] += 1;
continue;
@@ -266,7 +267,6 @@ impl Graph<FlowEdge>{
// one needs to be present in the cost function.
pub fn optimize_flow_with_cost(&mut self , cost: &CostFunction, path_length: usize )
-> Result<(),String>{
-
//We build the weighted graph g where we will look for negative cycle
let mut gf = self.build_cost_graph(cost)?;
let mut cycles = gf.list_negative_cycles(path_length);
@@ -364,6 +364,7 @@ impl Graph<WeightedEdge>{
}
}
+
//If self.graph contains a negative cycle, then at this point the graph described
//by prev (which is a directed 1-forest/functional graph)
//must contain a cycle. We list the cycles of prev.
@@ -401,8 +402,9 @@ fn cycles_of_1_forest(forest: &[Option<usize>]) -> Vec<Vec<usize>> {
//We discovered an id that we explored at this iteration t.
//It means we are on a cycle
let mut cy = vec![id; 1];
- let id2 = id;
- while let Some(id2) = forest[id2] {
+ let mut id2 = id;
+ while let Some(id_next) = forest[id2] {
+ id2 = id_next;
if id2 != id {
cy.push(id2);
}
@@ -429,12 +431,5 @@ fn cycles_of_1_forest(forest: &[Option<usize>]) -> Vec<Vec<usize>> {
mod tests {
use super::*;
- #[test]
- fn test_flow() {
- let left_vec = vec![3; 8];
- let right_vec = vec![0, 4, 8, 4, 8];
- //There are asserts in the function that computes the flow
- }
-
- //maybe add tests relative to the matching optilization ?
}
+