在Rust中实现图形状数据结构 [英] Implement graph-like datastructure in Rust

问题描述

我有一个数据结构，可以表示为一些结构之间的一个单向图，与链接对象链接（因为链接包含元数据）。

像这样：

  struct StateMachine {
 resources：Vec< Resource> 
 links：Vec< Link> ; 
} 
 struct Resource {
 type：ResourceType，
 // ... 
} 
 
枚举LinkTarget {
 ResourceList （Vec& Resource>），
 LabelSelector（HashMap< String，String>）
} 
 
 struct Link {
 from：LinkTarget，
到：LinkTarget，
元数据：SomeMetadataStruct 
} 
  

整个结构需要可变，我需要能够在运行时添加和删除链接和资源。因此，我不能使用正常的生命周期模型并将资源绑定到父结构的生命周期。

我明白，我需要一个或多个在此页面，但我不知道什么是解决此问题的最佳方法。

解决方案

实际上，对于像结构图，最简单的解决方案是使用一个竞技场，例如

节点的生命周期将会那么只能依赖于他们创建的类型竞技场的实例的生命周期，这将大大简化资源管理。

警告：避免在图形中动态添加/删除节点的场景，因为节点不会从竞技场中删除，直到竞技场被丢弃，所以竞技场的大小会增长，无限制。

---

如果您处于运行时添加/删除节点的情况，另一种解决方案是：

• 收集资源


• 只有边缘才间接参考资源（不是所有者，而不是借款人）

两个例子： p>

• HashMap< ResourceId，（资源，Vec< ResourceId>）>


• type R = RefCell< Resource> ， Vec< Rc< R> 和 Vec<（Weak R，Vec< Weak< R>）>

在任何一种情况下，您有责任在清除资源时清理边缘，并且遗忘可能会导致内存泄漏和紧急情况（解除引用时），否则将是安全的。

上面可能有无限的变化。

I have a data structure, which can be represented as a unidirectional graph between some structs, linked with link objects (because links contain metadata).

It looks something like this:

struct StateMachine {
  resources: Vec<Resource>,
  links: Vec<Link>
}
struct Resource {
  type: ResourceType,
  // ...
}

enum LinkTarget {
  ResourceList(Vec<&Resource>),
  LabelSelector(HashMap<String,String>)
}

struct Link {
  from: LinkTarget,
  to: LinkTarget,
  metadata: SomeMetadataStruct
}

The whole structure needs to be mutable, I need to be able to add and remove links and resources at runtime. So therefore I cannot use the normal lifetime model and bind the resources to the parent struct's lifetime.

I understand that I need one or more of the types mentioned on this page, but I'm not sure what's the best way to solve this problem.

解决方案

Actually, for a graph like structure, the simplest solution is to use an arena such as TypedArena.

The lifetime of the nodes will then be only dependent on the lifetime of the instance of the typed arena they were created from, which will greatly simplify resource management.

Warning: avoid a scenario where you dynamically add/remove nodes to the graph, as the nodes will NOT be removed from the arena until said arena is dropped, so the size of the arena would grow, unbounded.

---

If you are in a situation where you will add/remove nodes at runtime, another solution is to:

• have a collection of Resources
• have the edges only indirectly refer to the Resources (not owners, and not borrowers either)

Two examples:

• HashMap<ResourceId, (Resource, Vec<ResourceId>)>
• type R = RefCell<Resource>, Vec<Rc<R>> and Vec<(Weak<R>, Vec<Weak<R>>)>

in either case, you are responsible for cleaning up the edges when removing a resource, and forgetting may lead to a memory leak and panics (when dereferencing) but is otherwise safe.

There are, probably, infinite variations on the above.

这篇关于在Rust中实现图形状数据结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！