Repository: meilisearch/meilisearch
File: milli/src/search/new/ranking_rule_graph/cheapest_paths.rs (Rust)

Code before:
            let cur_node_edges = &self.edges_of_node.get(cur_node);
            for edge_idx in cur_node_edges.iter() {
                let edge = self.edges_store.get(edge_idx).as_ref().unwrap();
                let succ_node = edge.dest_node;
                let succ_costs = costs_to_end.get(succ_node);
                for succ_cost in succ_costs {
                    self_costs.push(edge.cost as u64 + succ_cost);
                }
            }
            self_costs.sort_unstable();
            self_costs.dedup();

            *costs_to_end.get_mut(cur_node) = self_costs;
        });
        costs_to_end
    }

    pub fn update_all_costs_before_node(
        &self,
        node_with_removed_outgoing_conditions: Interned<QueryNode>,
        costs: &mut MappedInterner<QueryNode, Vec<u64>>,
    ) {
        self.traverse_breadth_first_backward(node_with_removed_outgoing_conditions, |cur_node| {
            let mut costs_to_remove = FxHashSet::default();
            costs_to_remove.extend(costs.get(cur_node).iter().copied());

            let cur_node_edges = &self.edges_of_node.get(cur_node);
            for edge_idx in cur_node_edges.iter() {
                let edge = self.edges_store.get(edge_idx).as_ref().unwrap();
                for cost in costs.get(edge.dest_node).iter() {
                    costs_to_remove.remove(&(*cost + edge.cost as u64));
                    if costs_to_remove.is_empty() {
                        return;
                    }
                }
            }
            if costs_to_remove.is_empty() {
                return;
            }
            let mut new_costs = BTreeSet::from_iter(costs.get(cur_node).iter().copied());
            for c in costs_to_remove {
                new_costs.remove(&c);
            }
            *costs.get_mut(cur_node) = new_costs.into_iter().collect();
        });
    }

    /// Traverse the graph backwards from the given node such that every time
    /// a node is visited, we are guaranteed that all its successors either:
    /// 1. have already been visited; OR
    /// 2. were not reachable from the given node

Review comment (suggestion):
```suggestion
        // Traverse the graph backward from the target node, recomputing the cost for each of its predecessors.
        // We first check that no other node is contributing the same total cost to a predecessor before removing
        // the cost from the predecessor. 
        self.traverse_breadth_first_backward(node_with_removed_outgoing_conditions, |cur_node| {
```

Code after:
            let cur_node_edges = &self.edges_of_node.get(cur_node);
            for edge_idx in cur_node_edges.iter() {
                let edge = self.edges_store.get(edge_idx).as_ref().unwrap();
                let succ_node = edge.dest_node;
                let succ_costs = costs_to_end.get(succ_node);
                for succ_cost in succ_costs {
                    self_costs.push(edge.cost as u64 + succ_cost);
                }
            }
            self_costs.sort_unstable();
            self_costs.dedup();

            *costs_to_end.get_mut(cur_node) = self_costs;
        });
        costs_to_end
    }

    pub fn update_all_costs_before_node(
        &self,
        node_with_removed_outgoing_conditions: Interned<QueryNode>,
        costs: &mut MappedInterner<QueryNode, Vec<u64>>,
    ) {
        // Traverse the graph backward from the target node, recomputing the cost for each of its predecessors.
        // We first check that no other node is contributing the same total cost to a predecessor before removing
        // the cost from the predecessor.
        self.traverse_breadth_first_backward(node_with_removed_outgoing_conditions, |cur_node| {
            let mut costs_to_remove = FxHashSet::default();
            costs_to_remove.extend(costs.get(cur_node).iter().copied());

            let cur_node_edges = &self.edges_of_node.get(cur_node);
            for edge_idx in cur_node_edges.iter() {
                let edge = self.edges_store.get(edge_idx).as_ref().unwrap();
                for cost in costs.get(edge.dest_node).iter() {
                    costs_to_remove.remove(&(*cost + edge.cost as u64));
                    if costs_to_remove.is_empty() {
                        return;
                    }
                }
            }
            if costs_to_remove.is_empty() {
                return;
            }
            let mut new_costs = BTreeSet::from_iter(costs.get(cur_node).iter().copied());
            for c in costs_to_remove {
                new_costs.remove(&c);
            }
            *costs.get_mut(cur_node) = new_costs.into_iter().collect();
        });
    }

    /// Traverse the graph backwards from the given node such that every time