fast-graph

图数据结构的一个快速、轻量且可扩展的实现。

注意

⚠️ 在至少 1-2 周内，直到版本 1.0.0 发布之前，可能会有一些破坏性更改。

路线图

通用

• 无-std 支持
• 基准测试
• 与替代方案的基准测试比较

算法

• 拓扑排序
• 深度优先遍历
  • 连通分量
  • 寻找环
• 广度优先

并行化

• Rayon 支持

轻量且快速。

默认情况下，使用 SlotMaps 存储节点和边，这解决了 ABA 问题，同时提供了 O(1) 的插入、删除和查找时间。

可扩展 & 泛型

Graph 是节点和边数据类型的泛型。如果需要，还有用于创建更多定制化图样数据结构的特质的特质的特质的特质的特质。

Serde & Specta

有可选功能来启用 [serde] & [specta] 支持。

分类

CategorizedGraph 结构使用哈希表将类别名称 (String) 映射到类别节点 (NodeID)（其中节点的边是属于该类别的节点）。还有一些有用的额外功能来查询类别及其节点，以及一个 Categorized 特质，如果需要，可以为其自定义结构实现。

换句话说，这是对图的一个简单扩展，允许通过字符串有效地对节点进行分组。

结构

Node - 表示图中的节点的结构体。包含一个NodeID，它是节点在slotmap中的键，包含一个泛型数据字段和边列表。

Edge - 表示图中边的结构体。包含一个EdgeID，它是slotmap中边的键，以及两个NodeID，表示边连接的节点（从 & 到）。边也可以有“数据”，可以是任何东西或没有；例如连接的权重或表示其他内容的结构体或枚举。

GraphInterface - 定义修改图的方法的特质，即添加、删除和编辑节点和边。

Graph - 默认的图结构体，实现了GraphInterface。它只包含两个slotmap，一个用于节点，一个用于边。

Categorized - 扩展Graph的特质，提供特定于类别的操作方法。

CategorizedGraph - 带有类别的图。类别是普通节点（可以包含边和数据），但图还包含一个hashmap，将类别名称映射到类别节点，以便于访问。

示例

简单Graph和ABA问题。

use fast_graph::{Graph, Node, Edge};
/* We need to have this trait in scope: */
use fast_graph::{GraphInterface};

#[derive(Debug)]
struct EdgeData(String);

#[derive(Debug)]
struct NodeData(String);

let mut graph: Graph<NodeData, EdgeData> = Graph::new();

let node1 = graph.add_node(NodeData("Node 1".into()));
let node2 = graph.add_node(NodeData("Node 2".into()));
let edge1 = graph.add_edge(node1.id, node2.id, EdgeData("Edge 1".into()));

assert_eq!(graph.node(node1.id).unwrap().id, node1.id);
assert_eq!(graph.edge(edge1.id).unwrap().id, edge1.id);

graph.remove_node(node1.id).unwrap();

// Since we just removed node 1, it should be None now.
assert_eq!(graph.node(node1.id), None);
// And node 2 still points to node 2.
assert_eq!(graph.node(node2.id).unwrap().id, node2.id);

println!("{:#?}", graph);

CategorizedGraph示例

use fast_graph::*;

#[derive(Clone, Debug, Default, PartialEq)]
#[cfg_attr(feature = "serde", derive(serde::Serialize))]
enum NodeData {
    Number(u32),
    CategoryData(String),
    #[default]
    None,
}

let mut graph: CategorizedGraph<NodeData, ()> = CategorizedGraph::new();

let node1 = graph.add_node(NodeData::Number(1)).id;
let node2 = graph.add_node(NodeData::Number(2)).id;
let node3 = graph.add_node(NodeData::Number(3)).id;

let category1 = graph.create_category("Category 1", vec![node1, node2],
    NodeData::CategoryData("Category 1".into())
).unwrap();

assert_eq!(graph.category("Category 1").unwrap().connections.len(), 2);

// The category node should have the same data as the one we passed in.
let category1_data = graph.category("Category 1").unwrap().data;
if let NodeData::CategoryData(category1_name) = category1_data {
   assert_eq!(category1_name, "Category 1".to_string());
}

// Adding to a category that doesn't exist will create it. 
let category2 = graph.add_to_category("Category 2", vec![node2]);
assert_eq!(graph.all_categories().len(), 2);

// Adding to the same category twice will return the same category node.
let category2_1 = graph.add_to_category("Category 2", vec![node3]);
assert_eq!(graph.all_categories().len(), 2);
assert_eq!(category2, category2_1);

// The "Category 2" node should have two connections, one to node2 and one to node3.
let category2_node = graph.category("Category 2").unwrap();
assert_eq!(
// this:
    category2_node.connections.iter()
        .map(|edge_id|
            graph.edge(*edge_id).unwrap().to
        )
        .collect::<Vec<NodeID>>(),
// should equal:
    vec![node2, node3]
);

// Creating a category twice will error.
assert!(
    graph.create_category("Category 1",
        vec![node3], NodeData::CategoryData("Category 1".into())
    ).is_err()
);

变更日志