Refactoring an adjacency array

[pseudo current]

Hello! I've been using an adj array to describe a graph. As in, each node has many children and many parents. This is synonymous to a DAG (https://en.wikipedia.org/wiki/Directed_acyclic_graph)

Traversing and modifying this graph has been tough without reference counting or interior mutability. After lots of hacky tricks (multiple clones, rerunning functions on the clones since the clone is passed back to the adjarray later, anti-programming practices, etc.) I've decided to finally go ahead and try to implement Rc<Refcell<T>>. The existing AdjArray is really a hashmap named ReqHolder described as (alongside Req):

#[derive(Debug, Clone)]
struct ReqHolder {
    reqs: HashMap<i32, Req>
}

pub struct Req {
    pub id: i32,
    pub name: String,
    pub children: Vec<i32>,
    pub parents: Vec<i32>,
    pub in_analysis: bool,
}

where Req has children and parents that hold indices into this hashmap. Because of Rc<Refcell<T>>, should children instead hold references instead of indices?
If children holds references instead of indices, I expect due my crappy programming skills, to run into lots of runtime errors. However, I'll no longer need this struct as long as I have a reference to the root Req. So, should I keep ReqHolder and have the value be reqs: HashMap<i32, Rc<RefCell<T>>>, or should I modify Req and have children + parents be Vec<Rc<RefCell<T>>>? Much appreciated for any suggestions!

Refactoring an adjacency array

[hollow saddle]

simplest way would be to use an arena, Vec<Req> where children and parents are stored as indexes

[pseudo current]

That was the original implementation. Unfortunately, I'm traversing up and down the graph in multiple directions, meaning that sometimes a parent mutates the child that called it. Any implementation on something like that would break borrow checking rules

[hollow saddle]

you need to not keep a reference to parent when mutating children, so to not keep borrow of the "root" (ReqHolder).

[pseudo current]

Are you implying that Reqholder contains Vec<Req> or the children of Req should be Vec<Req>

in either case, this fails

I can explain accordingly

The reason I went with a HashMap over Vec<Req> was to use an anti-programming practice of throwing an error when an indice was -1 since it's an i32. Yes, I understand how awful that sounds. This is why I'm trying to throw almost everything away.
The traversal requires about 4 different mutually recursive functions, so getting it to work was the priority. Now it does, and I am just wondering if it'd be advantageous to throw away ReqHolder entirely

[hollow saddle]

?eval

struct ReqHolder { reqs: Vec<Req> }
struct Req {
    value: i32,
    children: Vec<usize>,
    parent: Option<usize>,
}
impl ReqHolder {
    fn inc_recursive(&mut self, req_id: usize) {
        let mut to_inc = vec![req_id];
        while let Some(id) = to_inc.pop() {
            let req = &mut self.reqs[id];
            req.value += 1;
            to_inc.extend(req.children.iter());
        }
    }
}

[flat gust]

     Running `target/debug/playground`

()

[hollow saddle]

don't keep reference for longer than necessary. if you need to keep something, keep index

[pseudo current]

while let is super neat. Please hold on, thanks so much for the assistance

I want to show you an implementation

i can't do it

it's like 500 lines

i can't simplify it

thanks for the help anyway

[pseudo current]

Hi again! I want to follow up on this. Here is my example:

let reqholder = ReqHolder.new();
//implementation of adding reqs to reqholder not shown
...

fn do_something(&mut self, &mut parent_req, &mut req) {

  for child in req.children {
    let child_req = reqholder.get_req(child)   //child in req.children is a key in reqholder's hashmap
    do_something(req, child_req);
  }
}

how do I not do this given this:

struct ReqHolder { reqs: HashMap<i32, Req> }
impl ReqHolder {...}
struct Req {
    value: i32,
    children: Vec<i32>,
    parent: Option<Vec<i32>
>,
}

notice that I can't just pass in an indice, because I'll need to modify child in req.children as well as perform operations on req (not children within the recursive call) and child within the recursive call

My current solution was to clone() parent_req and child_req at places in this program, and then set that clone to their locations in ReqHolder via *. But, speed has now become a concern. Any ideas?

[warped night]

Generally speaking, you can always pass an index and use it later, I'm not sure I follow why you'd not be able to

[pseudo current]

because mainly of this loop. If I'm already in req.children, I can't just tell the borrow checker, hey I'm definitely not gonna mutate req.children, so when I get_mut with the req.id, it fails

[warped night]

So: child_req borrows from reqholder, which I'm going to guess is inside self?

Where does that variable come from, actually

[pseudo current]

child_req is a mutable reference to a Req which is part of a larger graph which req and child_req are a part of. They're parents and children to each other.

child_req does borrow from reqholder

req borrows from reqholder

[warped night]

The general solution is to not pass child_req at all.

Instead, pass both the hashmap and its key down to the next recursive step. The idea is that you replace pointers with keys, and only hold on to pointers while not making recursive calls

[pseudo current]

hmmm ok, so if I do this correctly, I can throw my Rc<RefCell<T>> trash away?

[warped night]

Probably

Can't say for sure, but probably

[pseudo current]

nice, thanks

[pseudo current]

Once again I've got an issue. Since the req is in the req_holder, I cannot pass it:

let reqholder = ReqHolder::new();
//implementation of adding reqs to reqholder not shown
...

fn do_something(&mut self, 
req_holder: &mut ReqHolder, parent_id: i32, req_id: i32) -> Status {
  let req: &mut Req = req_holder.get_req(req_id);

  for (child_id, status) in &mut req.children {

    status = do_something(req_holder, req.id, child_id);

  }
}

tbecause I borrow ReqHolder when getting my Req, this cannot work...but I have to manipulate req.children

[hollow saddle]

clone children vec

[pseudo current]

and then set it back to the req's children afterwards?

This is a high performance cost operation

[hollow saddle]

you don't need to set it back

[pseudo current]

but it makes a copy

ok, ill see

req.children really contains a tuple, which is (child_id, status), in which the status is modified to one of multiple values, such as Checked, Selected, Undesirable

I will modify

[pseudo current]

if I have to modify status as edited, then I'm assuming I will have to clone, right

I mean assign it back afterwards

[hollow saddle]

if you modify it, then yes

[pseudo current]

so much performance lost

wish i could just tell it that I'm a man of danger and that if it doesn't work, do indeed tell me that I'm completely wrong

laugh at me even