graphrs

graphrs 是一个用于创建、操作和分析 图 的 Rust 包。

它允许创建支持以下功能的图：

• 有向和无向边
• 两个节点之间的多条边
• 自环

Graph 有两个泛型参数

• T: 指定节点名称使用的类型。
• A: 指定节点和边属性的类型。属性是与节点或边相关联的 可选 额外数据。例如，如果节点代表人员且 T 是他们的员工 ID 的 i32，则节点属性可能存储他们的名字和姓氏。

主要结构体

• Graph
• Node
• Edge

示例

创建一个加权、有向图

use graphrs::{Edge, Graph, GraphSpecs, Node};

let nodes = vec![
    Node::from_name("n1"),
    Node::from_name("n2"),
    Node::from_name("n3"),
];

let edges = vec![
    Edge::with_weight("n1", "n2", 1.0),
    Edge::with_weight("n2", "n1", 2.0),
    Edge::with_weight("n1", "n3", 3.0),
    Edge::with_weight("n2", "n3", 3.0),
];

let specs = GraphSpecs::directed();

let graph = Graph::<&str, ()>::new_from_nodes_and_edges(
    nodes,
    edges,
    specs
);

仅从边创建无向图

use graphrs::{Edge, Graph, GraphSpecs};

let mut graph: Graph<&str, ()> = Graph::new(GraphSpecs::undirected_create_missing());
let result = graph.add_edges(vec![
    Edge::new("n1", "n2"),
    Edge::new("n2", "n3"),
]);

使用所有可能规范创建空图

use graphrs::{Graph, GraphSpecs, EdgeDedupeStrategy, MissingNodeStrategy, SelfLoopsFalseStrategy};

let graph = Graph::<&str, ()>::new(
    GraphSpecs {
        directed: true,
        edge_dedupe_strategy: EdgeDedupeStrategy::Error,
        missing_node_strategy: MissingNodeStrategy::Error,
        multi_edges: false,
        self_loops: false,
        self_loops_false_strategy: SelfLoopsFalseStrategy::Error,
    }
);

生成一个 "完整" 图

use graphrs::{generators};
let graph = generators::classic::complete_graph(5, true);

找到两个节点之间的最短路径

use graphrs::{Edge, Graph, GraphSpecs, Node};
use graphrs::{algorithms::{shortest_path::{dijkstra}}};

let mut graph = Graph::<&str, ()>::new(GraphSpecs::directed_create_missing());
graph.add_edges(vec![
    Edge::with_weight("n1", "n2", 1.0),
    Edge::with_weight("n2", "n1", 2.0),
    Edge::with_weight("n1", "n3", 3.0),
    Edge::with_weight("n2", "n3", 1.1),
]);

let shortest_paths = dijkstra::single_source(&graph, true, "n1", Some("n3"), None, false);
assert_eq!(shortest_paths.unwrap().get("n3").unwrap().distance, 2.1);

计算所有节点的介数中心性

use graphrs::{algorithms::{centrality::{betweenness}}, generators};
let graph = generators::social::karate_club_graph();
let centralities = betweenness::betweenness_centrality(&graph, false, true);

性能

可以在 此处 找到 Dijkstra "所有对" 算法在 NetworkX 和 graphrs 之间的性能比较。

致谢

API 的一些结构和一些算法受到了 NetworkX 的启发。

许可证

MIT