Lib.rs

智能引用您的图节点。

internode 提供了一种轻松管理图结构所有权的便捷方式。

特性

• 所有权传播到连接节点
• 无泄漏的循环引用
• 自定义节点实现
• 线程安全
• 做好一件事™
• 几乎零依赖（仅在 genawaiter 直到 生成器 稳定）

用法

首先，定义您节点的形状。在这个例子中，我们将使用一个简单的实现，它持有表示入边和出边的列表对。这里的关键点是，节点间引用应通过 Internode 来持有

use internode::*;

#[derive(Default)]
struct Entity {
	succs: Vec<Internode<Entity>>,
	preds: Vec<Internode<Entity>>,
}

impl Entity {
	fn add_edge(from: &Internode<Entity>, to: &Internode<Entity>) {
		// Accessing the content of node is done by `lock`.
		from.lock().unwrap().succs.push(to.clone());
		to.lock().unwrap().preds.push(from.clone());
	}
}

impl Neighbors for Entity {
	type Iter<'a> = std::iter::Cloned<std::slice::Iter<'a, Internode<Entity>>>;
	fn outgoing(&self) -> Self::Iter<'_> { self.succs.iter().cloned() }
	fn incoming(&self) -> Self::Iter<'_> { self.preds.iter().cloned() }
}

然后，通过 Node::new 创建节点

let (a_weak, b) = {
	// `Node` is owning reference, while `Internode` is non-owning.
	let a = Node::new(Entity::default());
	let b = Node::new(Entity::default());
	// `Node` implements `Deref` to `Internode`.
	Entity::add_edge(&*a, &*b);
	// Downgrading `Node` yields `Internode`.
	let a_weak = a.downgrade();
	(a_weak, b)
	// `a` is dropped here.
};
// Downgrading `Internode` yields `Option<Node>`.
assert!(a_weak.upgrade().is_some());
// Dropping the last owning reference to the graph drops all nodes.
drop(b);
assert!(a_weak.upgrade().is_none());

循环图

循环引用无需手动管理即可正常工作，且不会发生内存泄漏

let (a_weak, b_weak, c_weak, c) = {
	let a = Node::new(Entity::default());
	let b = Node::new(Entity::default());
	let c = Node::new(Entity::default());
	Entity::add_edge(&*a, &*b);
	Entity::add_edge(&*b, &*c);
	Entity::add_edge(&*c, &*a);
	let a_weak = a.downgrade();
	let b_weak = b.downgrade();
	let c_weak = c.downgrade();
	(a_weak, b_weak, c_weak, c)
	// `a` and `b` are dropped here.
};
assert!(a_weak.upgrade().is_some());
assert!(b_weak.upgrade().is_some());
assert!(c_weak.upgrade().is_some());
drop(c);
assert!(a_weak.upgrade().is_none());
assert!(b_weak.upgrade().is_none());
assert!(c_weak.upgrade().is_none());

因此，您无需再为管理循环而烦恼。

节点遍历

作为对实现 Neighbors 的奖励，提供了执行深度优先搜索和广度优先搜索的方法

let a = Node::new(Entity::default());
let b = Node::new(Entity::default());
let c = Node::new(Entity::default());
let d = Node::new(Entity::default());
Entity::add_edge(&*a, &*b);
Entity::add_edge(&*a, &*c);
Entity::add_edge(&*b, &*d);
Entity::add_edge(&*c, &*d);
Entity::add_edge(&*d, &*a);
assert!(a.dfs_outgoing().eq([&*a, &*b, &*d, &*c].into_iter().cloned()));
assert!(a.dfs_incoming().eq([&*a, &*d, &*b, &*c].into_iter().cloned()));
assert!(a.bfs_outgoing().eq([&*a, &*b, &*c, &*d].into_iter().cloned()));
assert!(a.bfs_incoming().eq([&*a, &*d, &*b, &*c].into_iter().cloned()));

设计考虑

此crate受dendron（特别是“任何节点的引用都保留整个树”的概念）的启发，该crate仅限于树结构以确保良好的属性，并提供了一组有用的方法来操作，同时还具有如针对编辑冻结节点的防御性编程功能。这些高级功能超出了 internode 的范围，留给用户自行实现，因为需求各不相同。例如，如果您希望您的节点被冻结，那么frozen或更严格的实现将是不错的选择。