Implement iterator that doesn't consume the sequence

Hi,
i'm trying to code the fruchterman_reingold algorithm for a graph (basic physics between nodes such that it lays out nicely)
I'm using this old lab as a guide.

I'm having trouble iterating over the vertices of the graph. i think it would be best to use iterator, but it seems to complicate everything.
I now need to have current as a member to remember where i'm iterating for the next() call.
I also have and id for the node. Without iterator i would juste use the index to compare.

Here is the code :

mod graph{
    use std::collections::HashMap;
    pub struct Graph{
        adjancy_list : Vec<Node>,
        current : usize,
    }

    #[derive(Clone,Debug)]
    pub struct Node {
        links : HashMap<usize,usize>, //node nth, weight
        color : String, //property will be needed when drawing
        position : (usize,usize),
        disp : (usize, usize),
        id : u128,
    }

    
    impl Node {
        fn new() -> Node{
            Node{links : HashMap::new(), color:"black".to_string(),position : (0,0),disp : (0,0),id :0 }
        }
        fn set_position(&mut self, (x,y):( usize, usize)){
            self.position = (x,y);            
        }
    }
    impl PartialEq for Node{
        fn eq(&self, other: &Self) ->bool{
            self.id == other.id
        }
    }
    impl Graph{
        fn new() -> Graph{
            Graph{adjancy_list : Vec::new(), current : 0}
        }
        pub  fn add_new_node(& mut self){
            let mut n = Node::new();
            n.id = self.adjancy_list.len();
            self.adjancy_list.push(n)
        }
        /*
        connect two node : from -> to with a weight of weight
         */
        pub  fn connect(&mut self, from : usize, to : usize, weight : usize) -> usize{
            if let Some(u) = self.adjancy_list[from].links.insert(to,weight){
                return u;
            }
            0
        }
        pub  fn len(&self) -> usize{
            self.adjancy_list.len()
        }
    }
    impl Iterator for Graph{
        type Item = Node;
        fn next(&mut self)->Option<Node>{
            if let Some(n) = self.adjancy_list.get(self.current){
                self.current+=1;
                return Some(n.clone());
            }
            None   
        }
    }
}
mod force_field{
    use crate::graph::Graph;

    pub fn fruchterman_reingold(x : usize, y : usize, graph : &mut Graph){
        let area = x * y;
        let k = ((area as f64) /(graph.len() as f64) as f64).sqrt();
        let step = 100;
        let attraction = |dst: usize| -> f64 { 
            (dst as f64) * (dst as f64) / k 
        };
        
        let repulsion = |dst: usize| -> f64 { 
            (k as f64) * (k as f64) / dst as f64
        };

        for node1  in graph{
            for node2 in graph{ //graph is moved in the previous iteration
                if node1 != node2{
                    //compute the distance vector
                }
            }
        }
    }
}

How can i iterate over the vertices without consuming the graph ?
I thought about borrowing it mutable, but there is two loops so it won't work because i can't mutably borrow 2 times or ?

What would you change in the code, would you still use iterators or change it to indexes ?
All comments are welcome :slight_smile:

Implementing Iterator for the Graph itself is not what you want here.
You need a function that returns an iterator.

impl Graph {
    pub fn nodes<'a>(&'a self) -> impl Iterator<Item=&'a Node> + 'a {
        self.adjancy_list.iter()
    }
}

mod force_field{
    use crate::graph::Graph;

    pub fn fruchterman_reingold(x : usize, y : usize, graph : &mut Graph){
        let area = x * y;
        let k = ((area as f64) /(graph.len() as f64) as f64).sqrt();
        let step = 100;
        let attraction = |dst: usize| -> f64 { 
            (dst as f64) * (dst as f64) / k 
        };
        
        let repulsion = |dst: usize| -> f64 { 
            (k as f64) * (k as f64) / dst as f64
        };

        for (i, node1) in graph.nodes().enumerate() {
            // can't mutate graph while iterator is alive.
            for (j, node2) in graph.nodes().enumerate() {
                if i != j {
                    //compute the distance vector
                }
            }
        }
    }
}

Thanks for the quick reply !
When should i implement iterator for a struct then ?

I'm still new to rust, is my understanding of the code correct ?

pub fn nodes<'a>(&'a self) -> impl Iterator<Item=&'a Node> + 'a {
        self.adjancy_list.iter()
    }

It creates a public member function for the struct Graph. It declares a lifetime 'a. The Graph instance should exist during a time 'a (&'a self). It returns an object implementing iterator on items of type node whose lifetime is 'a but what is the + 'a at the end ?

The + 'a says that the returned iterator lives for 'a (since it borrows data from &'a self).

Your first question is probably best answered by an example.

struct GraphIter<'a> {
    graph: &'a Graph,
    pos: 0
}
impl<'a> Iterator for GraphIter<'a> {
    type Item = &'a Node;
    fn next(&mut self) -> Option<&'a Node> {
        match self.graph.adjancy_list.get(self.pos) {
            Some(node) => {
                self.pos += 1;
                Some(node)
            }
            None => None
        }
    }
}
impl Graph {
    fn nodes<'a>(&'a self) -> GraphIter<'a> {
        GraphIter {
            graph: self,
            pos: 0
        }
    }
}

No, it is just an upper bound. It says that it would not be valid for the iterator to live for longer than 'a, but it says nothing about whether the iterator lives for exactly 'a or for some shorter duration.

Analogously the 'a on &'a self and &'a Node are lower bounds. They say that, whatever the reference points at, that thing must be valid for at least the lifetime 'a, but says nothing about whether the thing they point at is alive for exactly 'a, or for some longer duration.

1 Like

OK, i think i understand better how timelife works and it's syntax.

But i still don't get how certain action can be done with the borrowing restriction.
For exemple i need to calculate the force beetwen every node and modify the position of said node according to the distance between the nodes.
So i need to be able to modify the node's property while iterating:
Thus i changed your code like this :

pub fn nodes_mut<'a>(&'a mut self) -> impl Iterator<Item=&'a mut Node> + 'a{
    self.adjancy_list.iter_mut()
}

And i use it that way

  //compute repulsion
for (i,n)  in graph.nodes().enumerate(){
    for (ii,nn) in graph.nodes_mut().enumerate(){
        if i != ii {
            let dif = (n.position.0 - nn.position.0, n.position.1 - nn.position.1);
            let norm : usize = (((dif.0*dif.0) + (dif.1*dif.1)) as f64).sqrt() as usize; //i'll change the norm to f64 instead of usize, it doesn't make sens to be usize
            let factor = repulsion(norm) / ( norm as f64);
            nn.position.0 *= factor;
            nn.position.1 *= factor;
        }
    }
}

I should use a custom 2D vector struct for the position instead of a tuple and implement the addition and scalar multiplication. i'll do that later.

But my main concerne is how rust wants me to achieve this kind of computing on a collection if i can't have a mut borrow and a borrow, should i clone all the elements and have a mut borrow on the first collection and a simple ref on the cloned collection ?

i searched a bit and found this guy, he is trying to do the same as i (force between nodes).
Someonde suggested to do it like that :

let mut iter = graph.adjancy_list.iter_mut();
    while let Some(n) = iter.next(){
        for nn in iter[..]{
            let dif = (n.position.0 - nn.position.0, n.position.1 - nn.position.1);
            let norm : usize = (((dif.0*dif.0) + (dif.1*dif.1)) as f64).sqrt() as usize;
            let factor = repulsion(norm) / ( norm as f64);
            n.position.0 *= factor;
            n.position.1 *= factor;
        }
    }

Unfortunately the inner loop is not working it says "cannot index into a value of type std::slice::IterMut<'_, Node>rustc[E0608] (Rust Compiler Error Index)
The error is quite clear, but i don't understand why i can't index a slice or how to solve the nested loop problem i'm facing.

The reason the code is not working is that it’s pre-1.0. (See how it dates earlier than May 15, 2015.)

If you look at the 1.0.0-alpha.2 docs of slice::IterMut, you’ll find a

impl<'a, T> IndexMut<RangeFull> for IterMut<'a, T> {
    fn index_mut(&mut self, _index: &RangeFull) -> &mut [T]
}

This implementation is missing in the final 1.0 and later Rust versions. I’m not 100% sure why this is the case, and I’m not sure if there’s any nice ways to make the code example still work in a similar fashion. slice::IterMut certainly looks like it does not currently support any way to get a &mut [T] preview of all the remaining items.


Actually, thinking about it a bit... perhaps something like this might work:

(untested code)

let mut slice = &mut graph.adjancy_list[..];
    while let Some((n, new_slice)) = slice.split_first_mut() {
        slice = new_slice;
        for nn in slice {
            let dif = (n.position.0 - nn.position.0, n.position.1 - nn.position.1);
            let norm : usize = (((dif.0*dif.0) + (dif.1*dif.1)) as f64).sqrt() as usize;
            let factor = repulsion(norm) / ( norm as f64);
            n.position.0 *= factor;
            n.position.1 *= factor;
        }
    }

Well, there is IterMut::into_slice, but I guess that's arguably not a "preview" since it consumes the iterator. (You could convert the returned slice back into an IterMut when you're done looking at it, though.)

Should’ve called it “reborrow” instead of “preview”, I guess. As you probably already understood, I meant that there’s no way to convert

&'a mut slice::IterMut<'b, T> -> &'a mut [T]
1 Like

If you wrap everything in Option to get a Default impl you can do it (playground)… but I guess that's not relevant since you can't (?) get a &mut Option<X> from &mut X in general.

I didn't, my fault for dropping into the thread without reading the full context :‌)

That’s not a re-borrow though, that’s just pure destruction :laughing:

Right, I see now -- sorry for being dense!

To be honest, my split_first_mut approach could also be replaced by some iter_mut plus call next once plus immediately convert the remaining iterator back using into_slice kind of “dance”. So suggesting using into_slice is not totally absurd.


In particular I’m not 100% sure but this approach might compile

let mut iter = graph.adjancy_list.iter_mut();
    while let Some(n) = iter.next(){
        let slice = iter.into_slice();
        for nn in slice {
            let dif = (n.position.0 - nn.position.0, n.position.1 - nn.position.1);
            let norm : usize = (((dif.0*dif.0) + (dif.1*dif.1)) as f64).sqrt() as usize;
            let factor = repulsion(norm) / ( norm as f64);
            n.position.0 *= factor;
            n.position.1 *= factor;
        }
        iter = slice.iter_mut();
    }

There is a nightly: IterMut::as_slice, curious that there isnt a as_mut_slice

The into_slice documentation says why: it's to prevent mutable aliasing.

You can get fn as_mut_slice(&mut self) -> &mut [T], which is just as safe as as_slice (similar to how Pin::as_mut works)

1 Like

Hmm, that's the same signature that @steffahn said wasn't possible -- how would it be implemented?

I’m just saying it’s not possible with the current API of IterMut. Not that it is inherently impossible. Quite the contrary, I believe that it should probably be possible (and sound!) for the standard library to implement such a method, at least AFAICT by thinking about it for just a few minutes so far. It would work by accessing/using the private fields of IterMut.

3 Likes

hi thx everyone for all your answers
But they all seems quite complicated (at least for me and my understanding of rust)

Isn't there an easier way to do modify an element in a nested loop ?
It seems to me that you need nested loop in a lot of situation like power of matrix, you wouln't want to clone the hole matrix that be really unefficient.

The let slice = iter.into_slice(); "move occurs because iter has type std::slice::IterMut<'_, Node>, which does not implement the Copy trait"

If i implement the copy trait it's the same as copying the whole sequence isn't it ?

I think i'll juste clone the sequence and go one with the code, for now it's juste a few node, but it doesn't scale well if i have a huge sequence.

But i'd like to know if there is a rustacean way of doing this ?