在Rust中实现类似图的数据结构

Question

我有一个数据结构，可以表示为一些结构体之间的单向图，这些结构体通过链接对象相互连接，因为链接包含元数据。

它看起来像这样：

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,
}

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

我明白我需要通过选择适当的类型来选择我的担保, 但不确定解决这个问题的最佳方法是什么。

- Lorenz

Answer 1

在Rust中对于建模类似图形结构并不是一件简单的问题。这里有两个来自Mozilla的主要Rust开发人员Nick Cameron和Niko Matsakis的有价值的讨论。

图形和区域分配

使用向量索引在Rust中建模图形

- eulerdisk

Answer 2

对于类似于图结构的数据，最简单的解决方案是使用一个“arena”，例如TypedArena。

节点的生命周期将仅依赖于它们所属的“arena”实例的生命周期，这将大大简化资源管理。

警告：避免在图中动态添加/删除节点，因为除非删除了该“arena”，否则节点不会从“arena”中删除，因此“arena”的大小将无限增长。

---

如果你需要在运行时添加/删除节点，则另一种解决方案是：

• 拥有一个Resources的集合
• 仅间接引用Resources的边缘（既不是拥有者也不是借用者）

两个例子：

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

在任何情况下，当删除资源时，你都有责任清理边缘，否则可能会导致内存泄漏和恐慌（在解引用时），但安全性无碍。

上述内容可能有无限多种变体。

- Matthieu M.

---

我添加和删除许多节点，应用程序是服务器进程，因此内存泄漏是一个问题。你知道另一个解决方案吗？与此同时，我会看看其他答案。 - Lorenz

@Aragon0：我添加了另一个设计想法，其中解耦资源和对其他资源的引用（不使用直接指针），这需要更多的簿记，但是更加安全。 - Matthieu M.

这看起来是个不错的主意！只要整个过程安全且相对快速，我可以处理更多的簿记。 - Lorenz

Answer 3

对于类似图形结构的最简单解决方案是使用模拟图形的库。petgraph是一个不错的选择：

use petgraph::Graph; // 0.5.1
use std::{collections::HashMap, rc::Rc};

struct Resource;

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

struct SomeMetadataStruct;

fn main() {
    let mut graph = Graph::new();

    let n1 = graph.add_node(LinkTarget::LabelSelector(Default::default()));
    let n2 = graph.add_node(LinkTarget::LabelSelector(Default::default()));

    let _l2 = graph.add_edge(n1, n2, SomeMetadataStruct);
}

在这里选择的保证围绕着ResourceList成员。我假设你希望拥有单线程共享的不可变Resource。

• 如果需要在线程之间共享它们，请使用 Vec<Arc<Resource>>
• 如果它们没有被共享，您可以拥有它们 — Vec<Resource>
• 如果它们需要是可变的，请使用Vec<Rc<RefCell<Resource>>>（如果还要多线程，则使用Mutex或RwLock）

- Shepmaster