Fastgraph

!!!预期会有破坏性更改

一个提供强大图特质的图API，允许构建多种类型的图以适应不同的用途。实现强大的并行遍历算法，在遍历图时提供加速。

示例用法

use fastgraph::core::{Empty, Traverse};
use fastgraph::collections::*;

fn main() {
	let mut g = Digraph::<usize, Empty, Empty>::new();

	g.add_node(1, Empty);
	g.add_node(2, Empty);
	g.add_node(3, Empty);
	g.add_node(4, Empty);
	g.add_node(5, Empty);
	g.add_node(6, Empty);

	g.add_edge(1, 2, Empty);
	g.add_edge(1, 3, Empty);
	g.add_edge(2, 1, Empty);
	g.add_edge(2, 3, Empty);
	g.add_edge(3, 1, Empty);
	g.add_edge(3, 5, Empty);
	g.add_edge(5, 2, Empty);
	g.add_edge(5, 4, Empty);
	g.add_edge(5, 1, Empty);
	g.add_edge(4, 5, Empty);
	g.add_edge(4, 3, Empty);
	g.add_edge(4, 2, Empty);
	g.add_edge(4, 6, Empty);

	let sink = g.get_node(6).unwrap();
	let shortest_tree = g.par_breadth_first(1,
		|edge|{
			if edge.target() == sink {
				Traverse::Finish
			} else {
				Traverse::Include
			}
		}).unwrap();

	let shortest_path = fastgraph::core::backtrack_edges(&shortest_tree);

	for edge in shortest_path {
		println!("{}", edge.upgrade().unwrap())
	}
}

1 -> 3
3 -> 5
5 -> 4
4 -> 6

实现

Fastgraph通过允许快速和并发处理图来实现。其底层表示基本上是一个邻接表，但边和节点都实现了自己的结构，并且可以在遍历时原子性地向每个线程提供任意数据。

类型

Fastgraph有Edge<K, N, E>和Node<K, N, E>类型。这些类型无需任何容器类型，并实现了基本操作和遍历的方法。

可以使用Graph特质在任意类型的容器之上实现图。该包提供了通用的Digraph和Ungraph类型，但也可以通过实现如何通过选定的容器访问节点来轻松实现具有不同类型容器的其他类型。

遍历

在遍历图时，我们需要跟踪visited节点。这通常通过某种查找表，如哈希表或二叉树来完成，我们使用它来检查节点是否已被访问。这是一种非常低效的方法，并且在多线程场景中使用时，写入数据结构时可能会阻塞。

In fastgraph中，每个节点本身都包含一个原子锁，我们可以从任何线程安全地切换这个锁，从而阻止节点被遍历。当遍历完成时，我们再次打开锁。

当我们进行遍历时，我们会创建一个额外的数据结构，即最短路径树。然后，这个树通过breadth_first和depth_first（以及它们的并行版本）返回。如果我们正在寻找到特定节点的最短路径，那么该节点将是列表中最后一个边的目标节点，我们可以通过回溯最短路径树来收集最短路径。

性能

该仓库包含比较顺序迭代和并行迭代的速度基准测试。可以使用 cargo bench 命令 运行。在详细测试中，我们观察到，只要图的大小足够大以抵消开销，并行迭代相比顺序迭代有非常好的性能提升。在底层，fastgraph 使用 rayon 库来并行化遍历循环。

!继续