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

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

我知道我需要通过选择合适的类型来"选择我自己的保证",但我不确定解决这个问题的最佳方法是什么.

Answer 1

在Rust中建模图形结构不是一个简单的问题.Nick Cameron和Niko Matsakis(Mozilla的两位主要Rust开发人员)进行了两次有价值的讨论.

图表和竞技场分配

用矢量索引建立Rust中的图形

Answer 2

实际上,对于类似图形的结构,最简单的解决方案是使用诸如的竞技场TypedArena.

然后,节点的生存期将仅取决于它们所创建的类型化竞技场实例的生命周期,这将极大地简化资源管理.

警告:避免在图形中动态添加/删除节点的情况,因为在竞技场被丢弃之前,节点不会从竞技场中移除,因此竞技场的大小会增长,无限制.

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

• 有一个集合 Resources
• 边缘只是间接地指Resources(不是所有者,也不是借款人)

两个例子:

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

在任何一种情况下,你都有责任在删除资源时清理边缘,忘记可能会导致内存泄漏和恐慌(解除引用时),但在其他方面是安全的.

上面可能有无限的变化.

Answer 3

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

extern crate petgraph;

use std::rc::Rc;
use std::collections::HashMap;

use petgraph::Graph;

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也可以是多线程的）