在 Rust 中实现类图数据结构

Question

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

看起来像这样：

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

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

我知道我需要 to "choose my own guarantee" 选择合适的类型，但我不确定解决这个问题的最佳方法是什么。

Answer 1

实际上，对于类似图的结构，最简单的解决方案是使用 TypedArena.

这样的 arena

节点的生命周期将仅取决于创建它们的类型化区域实例的生命周期，这将大大简化资源管理。

警告：避免动态 add/remove 节点到图表的情况，因为在删除该竞技场之前，节点不会从竞技场中移除，所以竞技场的规模会无限扩大。

如果您处于运行时将 add/remove 个节点的情况，另一种解决方案是：

collection 的 Resources
有边缘仅间接指代 Resources（不是所有者，也不是借款人）

两个例子：

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

在任何一种情况下，您都有责任在删除资源时清理边缘，忘记可能会导致内存泄漏和恐慌（在取消引用时），但在其他方面是安全的。

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

Answer 2

在 Rust 中建模 graph-like 结构不是一个简单的问题。这里有来自 Nick Cameron 和 Niko Matsakis（Mozilla 的两个主要 Rust 开发人员）的两个有价值的讨论。

Graphs and arena allocation

Modeling Graphs in Rust Using Vector Indices

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 的成员为中心。我假设您希望单线程共享不可变 Resources.

如果您需要跨线程共享它们，请使用 Vec<Arc<Resource>>
如果它们不是共享的，您可以拥有它们 — Vec<Resource>
如果它们需要可变，请使用 Vec<Rc<RefCell<Resource>>>（如果也是多线程，则使用 Mutex 或 RwLock）

在 Rust 中实现类图数据结构

Implement graph-like data structure in Rust

ownership

rust

data-structures