How to model complex recursive data structures (graphs)?

by

You can’t represent an arbitrary graph structure in safe rust.

The best way to implement this pattern is to use unsafe code and raw pointers, or an existing abstraction that wraps this functionality in a safe api, for example http://static.rust-lang.org/doc/master/std/cell/struct.RefCell.html

For example, the typical bi directional linked list would be:

struct Node {
  next: Option<Node>, // Each node 'owns' the next one
  prev: *mut Node     // Backrefs are unsafe
}

There have been a number of ‘safe’ implementations floating around, where you have something like:

struct Node {
    id: u32,
    next: u32,
    prev: u32
}
struct Nodes {
  all:Vec<Node>,
  root:Option<Node>
}

This is ‘technically’ safe, but it’s a terrible pattern; it breaks all the safety rules by just manually implementing raw pointers. I strongly advise against it.

You could try using references, eg:

struct Container<'a> {
  edges:Vec<Edge<'a>>,
  pub root: Node
}

struct Node {
  children:Vec<Node>  
}

struct Edge<'a> {
  n1: &'a Node,
  n2: &'a Node
}

…but you’ll stumble almost immediately into borrow checker hell. For example, when you remove a node, how does the borrow checker know that the associated links in ‘edges’ are no longer valid?

Although you might be able to define the structures, populating them will be extremely troublesome.

I know that’s probably a quite unsatisfying answer; you may find it useful to search github for ‘rust graph’ and ‘rust tree’ and look at the implementations other people have done.

Typically they enforce single-ownership of a sub-tree to a parent object.

More Related Contents:

  1. Why can’t I store a value and a reference to that value in the same struct?
  2. The compiler suggests I add a ‘static lifetime because the parameter type may not live long enough, but I don’t think that’s what I want
  3. How do I stop iteration and return an error when Iterator::map returns a Result::Err?
  4. Why does Iterator::take_while take ownership of the iterator?
  5. When should I implement std::convert::From vs std::convert::Into?
  6. Efficiently mutate a vector while also iterating over the same vector
  7. How can I call a mutating method while holding a reference to self?
  8. How do you actually use dynamically sized types in Rust?
  9. How do I use the Entry API with an expensive key that is only constructed if the Entry is Vacant?
  10. “parameter `’a` is never used” error when ‘a is used in type parameter bound
  11. Borrowing references to attributes in a struct
  12. How do I split a string in Rust?
  13. Is it possible to implement methods on type aliases?
  14. How can I use a module from outside the src folder in a binary project, such as for integration tests or benchmarks?
  15. How to match on data type in Rust?
  16. How can I modify self in a closure called from a member function?
  17. How do I synchronously return a value calculated in an asynchronous Future?
  18. How do I move out of a struct field that is an Option?
  19. Removing elements from a Vec based on some condition [duplicate]
  20. How can I change enum variant while moving the field to the new variant?
  21. What is unwrap in Rust, and what is it used for?
  22. print! macro not executed until pressing Enter
  23. How can I define an async method in a trait?
  24. How do I specify the linker path in Rust?
  25. Why am I getting “parameter is never used [E0392]”?
  26. Why is Rust’s assert_eq! implemented using a match?
  27. How to repeat a static string at compile time
  28. Is there a good way to convert a Vec to an array?
  29. How to concatenate static strings in Rust
  30. How can I conditionally provide a default reference without performing unnecessary computation when it isn’t used?

Leave a Comment