raphy

一个具有多种实现的图数据结构库。

Brandon Lucia -- 2020

raphy::fast_csr::FastCSR - 一个快速稀疏图数据结构

FastCSR 是 CSR 数据结构的一个改进版本，它使用内存映射文件，而不是使用文本和大型内存缓冲区。

实现是 100% 零拷贝，这意味着可以在不将文件内容从文件复制到内存缓冲区的情况下，以 CSR 格式加载和遍历图。这种设计的结果是，加载极大的图非常快，因为虚拟内存会根据您的遍历需要将图数据懒加载到内存中，否则数据将仅坐在图下方的文件中。

raphy::csr::CSR - 压缩稀疏行 (CSR) 图数据结构

CSR 是一种优化的图数据表示，特别适用于使用稀疏图数据。稀疏图是在其邻接矩阵中有很多零的图。该结构有三个数组，偏移数组、邻居数组和 vtxprop 数组。偏移数组根据源顶点的 ID 索引，一个条目存储源顶点邻居在 neighbs 数组中的起始索引。
顶点 i 的邻居（和权重）存储在 neighbs[ offsets[i] ] 通过 neighbs[ offsets[i+1] ] 的元组 (v,w) 中；Neighbs 根据 offsets 中获取的值索引，列出顶点的邻接点。vtxprop 是一个辅助数组，存储顶点属性，每个顶点一个。目前，此属性是 f64，但实际上它应该是泛型，并将最终实现。

当前的 CSR 实现提供了对边的扫描和对顶点的 BFS 遍历。您使用这些扫描的方式是传递一个 FnMut，该 FnMut 可以看到每个边或顶点在遍历时的状态。边扫描 FnMut 接收 (v0,v1,w)，其中 v0、v1 是边的源和目标，w 是权重。bfs 遍历 FnMut 只接收一个顶点 v。bfs_traversal API 还接受起始顶点的 id：usize。

那么如何使用 CSR & FastCSR 呢？

FastCSR 预期的是一个二进制文件格式，包含两个 8 字节值，分别是顶点数和边数。然后文件包含一系列 8 字节值，每个顶点一个值。然后文件包含一系列 8 字节值，每个边一个值。结构的意义与其存储的 CSR 完全相同：第一个序列的 8 字节值是偏移数组，第二个序列的 8 字节值是邻居数组。

您可以使用 FastCSR::new(String) 函数直接以这种格式加载 CSR，该函数的参数是一个文件名字符串。

从那里，您可以使用 neighbor_scan(f: impl Fn(usize,&[usize])) 来遍历您的图。此函数接受您提供的闭包。您的闭包应接受一个 usize 参数，它是源顶点的 ID，以及一个 usizes 的切片引用，它是源顶点相邻顶点的顶点 ID。

作为替代，您可以使用 read_only_scan(f: impl Fn(usize,usize)) 来遍历您的图。此函数接受您提供的闭包。您的闭包应接受两个 usize 参数，它们是边的源顶点和目标顶点。函数对图中的每个边都会调用。

以下是一个实现类似于 PageRank 算法的示例程序

fn main() {

    let fcsr = FastCSR::new(String::from("./large.csr"));

    let mut vp1 = Vec::with_capacity(fcsr.getv());
    for _ in 0..fcsr.getv() {
        vp1.push(RwLock::new(0.0));
    }

    for _ in 0..10 {
        let mut vp2 = Vec::with_capacity(fcsr.getv());
        for _ in 0..fcsr.getv() {
            vp2.push(RwLock::new(0.0));
        }

        let vf = |v: usize, nei: &[usize]| {
            const D: f64 = 0.85;
            let mut n_upd: f64 = 0.0;

            nei.iter()
                .for_each(|v1| n_upd = n_upd + *vp1[*v1].read().unwrap() / (nei.len() as f64));

            {
                let mut prop = vp2[v].write().unwrap();
                *prop = (1.0 - D) / (fcsr.getv() as f64) + D * n_upd;
            }
        };

        fcsr.neighbor_scan(vf);
        for v in 0..(vp1.len() - 1) {
            *vp1[v].write().unwrap() = *vp2[v].read().unwrap();
        }
    }

    vp1.iter().enumerate().for_each(|(i, v)| {
        println!("{} {}", i, *v.read().unwrap());
    });
    
}

那么，如果您只有边列表会怎样呢？

CSR 模块现在包含从二进制格式化的边列表创建 CSR 的支持。二进制边列表格式是一系列 8 字节值的对。每一对 8 字节值代表一条边。

要从二进制边列表创建 CSR，您调用 new_from_el_mmap(v: usize, f: String)。此函数的第一个参数是您图中的顶点数，您必须事先提供。您可以通过扫描图一次来获取此信息，但这代价相对较高，要进行 |E| 遍历来计算 |V|，因此 API 要求此参数。第二个参数是包含二进制边列表的文件名字符串。

一个从二进制边列表生成 FastCSR 的示例程序会这样做

fn main() {

    let csr = CSR::new_from_el_mmap(10000000,String::from("large.el"));

    csr.write_fastcsr(String::from("large.csr"));
    
}

raphy::graph::Graph - 基本图数据结构

图具有具有数值标识符的顶点，并且可以多态地携带任何可显示和可排序的有效负载/值类型（参见 VtxTrait 定义）。

不以 csr_ 前缀为前缀的示例是您可以使用图执行的操作类型的好参考。BFS 和 DFS 示例显示了如何遍历图的顶点。rand_graph 和 iter_graph 示例显示了如何扫描图的顶点，忽略图结构。

边列表文件格式（用于在 raphy::csr::CSR 中读取边列表）

格式非常简单，并且故意设计成现在可由人类阅读。

v0,v1
v0,v2
v1,v0
v1,v2
v2,v0
v2,v1
...

csr_rand_graph 示例使用一个扫描闭包以正确格式写入边列表。您可以通过运行 csr_rand_graph 示例并将其输出放入文件中来创建测试输入文件。

待办事项

• 从 CSR 中删除权重
• 将边列表类型添加到 CSR（不实施）
• 添加随机边列表生成器
• 添加边列表的文件读取功能
• BFS 中的 frontier 和 visited 的 bit-vec 支持
• CSR 构造中的传播阻塞
• 任意遍历中的传播阻塞
• 性能比较的基准测试（与 C 实现）
• 使用遍历例程的更多算法实现进行测试
• 并行 CSR 构造
• 优化大型图的文件读取