CODEWITHSUNDEEP
rustimmutabilityborrow-checker
tjc
tjc

Reputation: 193

Updating mutable HashMap in a while loop

I am trying to implement Karger's algorithm in Rust and I have run into an issue while trying to update a mutable hashmap in a while loop.

The map is updated successfully, but then in the next iteration when it was cloned, the values that were updated don't seem to have been changed. However removing elements from the map is reflected on later iterations.

I have tried debugging and printing the values of the map, but the sequence of events doesn't make sense to me.

use itertools::Itertools;  // 0.8.0
use rand::seq::{IteratorRandom, SliceRandom}; // 0.6.5
use std::collections::HashMap;

fn contract_edge(graph: &mut HashMap<i32, Vec<i32>>, num_trials: i32) {
    let mut count = 0;

    while graph.len() > 2 && count < num_trials {
        // clone graph so I can mutate graph later
        let imut_graph = graph.clone();

        // choose random node
        let from_value = imut_graph
            .keys()
            .choose(&mut rand::thread_rng())
            .unwrap()
            .clone();
        let values = imut_graph.get(&from_value);
        let to_value = values
            .unwrap()
            .choose(&mut rand::thread_rng())
            .unwrap()
            .clone();

        let from_edges = imut_graph[&from_value].iter().clone();

        // accessing to_value in imut_graph gives error here later
        let to_edges = imut_graph[&to_value]
            .iter()
            .clone()
            .filter(|&x| *x != from_value && *x != to_value);

        let new_edges = from_edges.chain(to_edges);

        // since I am mutating the graph I thought the next time is is clone it would be updated?
        graph.insert(from_value, new_edges.map(|v| v.clone()).collect());
        graph.remove(&to_value);
        for (_key, val) in graph.iter_mut() {
            *val = val
                .iter()
                .map(|v| if v == &to_value { &from_value } else { v })
                .unique()
                .cloned()
                .collect();
        }
        count += 1;
    }
}

When I try to access the map, I get element not found error, but the keys which have been removed should not exist in the vector values at that point.

I am convinced this is something I don't understand about (Im)mutability in Rust.

Upvotes: 0

Views: 2151

Answers (1)

Peter Varo
Peter Varo

Reputation: 12160

I'm not really sure what you are trying to achieve here, but based on what I can see above, that is, you'd like to mutate your original graph (because you are passing that as a mutable borrow to your function) and that you don't have a return value, and that your question is about mutating a hashmap -- I assume that you'd like the changes to be reflected in your original HashMap. So why are you cloning it in the first place then?

If on the other hand you don't want to mutate your original object, then don't pass it in as a mutable borrow, but as an immutable one. Then create a clone of it before you start the loop and use that cloned version throughout your algorithm.

The problem you are facing with is happening because on every iteration you are cloning the original graph and not your cloned imut_graph, i.e. on every iteration you create a new HashMap, which then you are mutating, then you start a new cycle and you are still checking the length of the original one and then you clone the original one again.

So the two options you have are:

use std::collections::HashMap;

fn mutated(map: &mut HashMap<i32, Vec<i32>>) {
    map.insert(1, vec![4, 5, 6]);
}

fn cloned(map: &HashMap<i32, Vec<i32>>) -> HashMap<i32, Vec<i32>> {
    let mut map = map.clone();
    map.insert(2, vec![7, 8, 9]);
    map
}

fn main() {
    let mut map = HashMap::new();
    map.insert(0, vec![1, 2, 3]);

    println!("{:?}", cloned(&map));

    mutated(&mut map);
    println!("{:?}", map);
}

Which will give you:

{0: [1, 2, 3], 2: [7, 8, 9]}
{0: [1, 2, 3], 1: [4, 5, 6]}

Upvotes: 0

Related Questions