在Rust中实现类似图形的数据结构 [英] Implement graph-like data structure in Rust

问题描述

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

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

它看起来像这样:

struct StateMachine {
    resources: Vec<Resource>,
    links: Vec<Link>,
}
struct Resource {
    kind: 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 because I need to be able to add and remove links and resources at runtime. Because of this, I cannot use the normal lifetime model and bind the resources to the parent struct's lifetime.

我了解我需要选择我自己的保证" ，但是我不确定解决此问题的最佳方法是什么.

I understand that I need to "choose my own guarantee" by picking the appropriate type, 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)

两个例子:

• HashMap< ResourceId，(资源，Vec< ResourceId>)>
• 类型R = RefCell< Resource> ， Vec< Rc< R>> 和 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屋！