Lib.rs

› 算法
#graph #graph-algorithms #vertices #edge #algorithm #analysis #data-structures

graphbench

稀疏图分析库

作者 Felix

5个版本

0.1.7 2022年10月27日
0.1.6 2022年7月11日
0.1.5 2022年6月27日
0.1.4 2022年6月27日
0.1.3 2022年5月7日

#1733 在 算法

MIT 许可证

145KB
3K SLoC

Graphbench

docs.rs crates.io github

此库提供各种针对特定算法风格的图数据结构，以及用于操作图的通用图数据结构。

基本用法

用于加载和修改图的主要结构是 EditGraph，它提供了常见的图操作。

use graphbench::graph::*;
use graphbench::editgraph::EditGraph;

fn main() {
    let mut graph = EditGraph::new();
    graph.add_vertex(&0);   
    graph.add_edge(&1, &2); // Vertices 1,2 are added implicitly
    graph.add_edge(&1, &1); // Loops are allowed

    println!("Graph has {} vertices and {} edges", graph.num_vertices(), graph.num_edges());

    // Use .contains(..) to query vertices
    assert_eq!(graph.contains(&0), true);
    assert_eq!(graph.contains(&3), false);

    // Use .adjacent(..) to query edges
    assert_eq!(graph.adjacent(&1, &1), true);
    assert_eq!(graph.adjacent(&1, &2), true);
    assert_eq!(graph.adjacent(&0, &2), false);

    // Use .degree(...) to query vertex degres
    assert_eq!(graph.degree(&0), 0);
    assert_eq!(graph.degree(&1), 3);
    assert_eq!(graph.degree(&2), 1);
}

文件I/O

Graphbench目前仅支持一种基本文件格式，其中每条边都在单独的一行上定义。每条边必须由两个用空格分隔的整数组成。例如，我们可以创建一个包含以下内容的文件 edges.txt

0 1
0 2
0 3

然后我们可以按如下方式加载该文件

use graphbench::graph::*;
use graphbench::editgraph::EditGraph;
use graphbench::iterators::EdgeIterable;

fn main() {
    let graph = EditGraph::from_txt("edges.txt").expect("Could not open edges.txt");
    println!("Vertices: {:?}", graph.vertices().collect::<Vec<&Vertex>>());
    println!("Edges: {:?}", graph.edges().collect::<Vec<Edge>>());
}

读取/写入图也可以用于上述文本格式的gzip文件，请参阅 graphbench::io 模块。


迭代

graphbench::iterators 模块提供了几个图内容的迭代器，我们建议使用 use graphbench::iterators::* 以简化。

use graphbench::graph::*;
use graphbench::editgraph::EditGraph;
use graphbench::iterators::*;

fn main() {
    let graph = EditGraph::path(5); // Path on 5 vertices 0...4

    for u in graph.vertices() {
        let degree = graph.degree(u);
        let neighs:Vec<&Vertex> = graph.neighbours(u).collect();
        println!("Vertex {} has {} neighbour(s): {:?}", u, degree, neighs);
    }

    // Needs trait graphbench::iterators::NeighIterable
    for (u,neighs_it) in graph.neighbourhoods() {
        let neighs:Vec<&Vertex> = neighs_it.collect();
        println!("Vertex {} has neighbour(s) {:?}", u, neighs);
    }

    // Needs trait graphbench::iterators::EdgeIterable
    for (u,v) in graph.edges() {
        println!("Edge {} {}", u, v);
    }
}

依赖项

~1MB
~17K SLoC