rust-igraph：用 Rust 从零实现 igraph——纯 Rust 图计算库的工程实践与架构深度解析

背景：为什么我们需要一个纯 Rust 的图计算库？

图计算：被忽视的工程重镇

在 AI 时代，当所有人都在追逐大语言模型和 RAG 架构时，有一个领域悄然成为了工程界的"隐形战场"——图计算（Graph Computing）。社交网络分析、推荐系统、知识图谱、代码搜索、网络安全、分子结构分析、路径规划……这些场景背后，无一例外都依赖图算法的高效执行。

然而，长期以来，这个领域的工程实现几乎是 C/Python 双垄断的格局：

• C/C++ 层：igraph、CGAL、Boost Graph Library ——性能极强，但 API 晦涩，学习曲线陡峭，内存管理全靠手撸
• Python 层：networkx ——易用性拉满，但性能拉胯，一个 PageRank 跑几十秒是常态

有没有一种可能：用 Rust 重写一套图计算库，让性能和安全性兼得，同时保留 ergonomics？

这就是 rust-igraph 项目诞生的背景——一个从零开始的 Rust 实现，目标是对齐 igraph C 库（v1.0.x）的全部 ~850 个公共 API，同时利用 Rust 的类型系统、所有权机制和并发模型带来 C 实现无法提供的安全保障。

项目概览

一、架构设计：从 C 到 Rust 的范式迁移

1.1 igraph C 库的核心架构回顾

要理解 rust-igraph 为什么这样设计，必须先了解它移植的对象——igraph C 库的架构。

igraph C 是一个诞生于 2003 年的老牌图库，其核心架构有几个鲜明的特点：

（1）全局图对象 + 回调风格

// igraph 的典型使用方式：创建一个图对象，然后调用函数修改它
igraph_t graph;
igraph_integer_t n = 1000;
igraph_full(&graph, n, IGRAPH_UNDIRECTED, IGRAPH_NO_LOOPS);

// 调用函数查询图属性
igraph_integer_t vertex_count, edge_count;
igraph_vcount(&graph, &vertex_count);
igraph_ecount(&graph, &edge_count);

// 销毁
igraph_destroy(&graph);

igraph C 的 API 全部是过程式的：图对象通过指针传递，所有函数都是 igraph_xxx(&graph, ...) 的风格。这种设计在 C 里很自然，但到了 Rust 里就成了类型系统的噩梦——你需要处理大量的 &mut IGraph 引用。

（2）多种底层数据结构并存
igraph C 内部支持多种图的存储格式：

• 邻接矩阵（Adjacency Matrix）：O(V²) 空间，适合密集图
• 邻接列表（Adjacency List）：O(V + E) 空间，适合稀疏图
• 边列表（Edge List）：最简单，用于特定场景

不同算法在不同数据结构上效率差异巨大，所以 igraph C 会根据操作动态选择最优表示。

（3）属性系统（Attribute System）
igraph C 支持为顶点和边附加任意属性（字符串、整数、浮点数等），这是一个极其复杂的设计，也是 rust-igraph 移植过程中最棘手的部分之一。

1.2 rust-igraph 的架构决策

rust-igraph 面对的核心问题是：如何把一个过程式的 C 库，用 Rust 的方式优雅地重写？

这是一个经典的"翻译"问题——不是字面对应，而是找到 Rust 生态中等价且更符合 Rust 惯用法（idiomatic Rust）的表达。

决策一：用 Builder 模式替代过程式 API

C 语言的风格：

igraph_integer_t n = 1000;
igraph_full(&graph, n, IGRAPH_UNDIRECTED, IGRAPH_NO_LOOPS);

rust-igraph 的 Rust 风格：

use rust_igraph::prelude::*;

let graph = Graph::full(1000, Undirected, NoLoops);

这看起来简单，但背后需要做大量的 API 设计工作。rust-igraph 使用了 Rust 的**方法链（method chaining）**模式，将多个配置选项通过 builder 累积：

use rust_igraph::prelude::*;
use rust_igraph::builder::GraphBuilder;
use rust_igraph::types::*;

let graph = GraphBuilder::new()
    .n(1000)
    .directed(Directed)
    .self_loops(false)
    .build()
    .unwrap();

决策二：用类型系统编码图的性质

igraph C 用枚举来区分图的性质（有无向、是否有自环等），这些性质作为函数参数传递。rust-igraph 则把这些编译时就能确定的信息编码进类型系统：

// 有向图类型
pub struct Graph<D: Directedness, S: SelfLoops> {
    // ...
}

// 两个 phantom type 参数：D 表示有向性，S 表示自环
type Undirected = IsUndirected;
type Directed = IsDirected;
type WithLoops = WithSelfLoops;
type NoLoops = NoSelfLoops;

// 这样，编译器就能在编译期阻止非法操作：
// 不可能在一个 NoLoops 图上调用"添加自环"的方法

这个设计的好处是编译期安全。在 C 里，你可以在一个"不应该有自环"的图上调用 igraph_add_edge(&graph, v, v)，然后期待运行时报错。在 Rust 里，这根本编译不过：

// 假设 graph 的类型是 Graph<Undirected, NoLoops>
// 这段代码编译失败——因为类型系统保证不会有自环操作
graph.add_edge(0, 0)?; // ❌ 编译错误：NoLoops 类型的图不允许自环

决策三：所有权与生命周期

igraph C 的内存管理依赖显式的 igraph_destroy() 调用。忘记销毁会导致内存泄漏，多重释放会导致段错误。rust-igraph 则利用 Rust 的所有权系统：

fn calculate_pagerank(graph: &Graph) -> Vec<f64> {
    // graph 的所有权不转移，函数结束后自动释放（如果实现了 Drop）
    let ranks = graph.pagerank();
    ranks
} // graph 的生命周期结束，内存自动释放

对于需要独占访问的场景，rust-igraph 使用 &mut self：

impl Graph {
    /// 添加一条边（需要可变借用）
    pub fn add_edge(&mut self, from: VertexId, to: VertexId) -> Result<(), Error> {
        // ...
    }
    
    /// 获取 PageRank（只需要只读借用）
    pub fn pagerank(&self) -> Vec<f64> {
        // ...
    }
}

二、核心数据结构：图在 Rust 中如何存储

2.1 存储格式的选择困境

图计算领域有一个经典问题：用什么数据结构存储图？

这个问题的答案取决于图的特征：

现实世界的图几乎都是稀疏的——社交网络有上亿用户，但平均每个用户只关注几百人，边的密度远低于顶点对的数量。因此，邻接列表是主流选择。

2.2 rust-igraph 的邻接表实现

rust-igraph 的邻接表实现是一个典型的链表 + 数组混合结构：

// 简化的邻接表结构（实际实现更复杂）
pub struct AdjacencyList<N: Numeric> {
    // 顶点表：每个顶点对应一个可变长的邻居列表
    vertices: Vec<AdjacencyListVertex<N>>,
    
    // 边表：存储所有边的属性
    edges: Vec<EdgeRef<N>>,
}

pub struct AdjacencyListVertex<N: Numeric> {
    // 邻居顶点 ID 列表
    neighbors: Vec<VertexId>,
    
    // 指向边数据的索引（如果有多个平行边）
    edge_indices: Vec<usize>,
}

pub struct EdgeRef<N: Numeric> {
    pub source: VertexId,
    pub target: VertexId,
    pub weight: N,
    // 其他边属性...
}

这种设计的精妙之处在于：

1. 邻居查询：给定一个顶点，直接通过 vertices[v].neighbors 访问，O(deg(v)) 时间
2. 空间效率：只存储实际存在的边，O(V + E) 空间
3. 缓存友好：Rust 的 Vec 是连续的内存块，遍历邻居时缓存命中率高

2.3 用图可视化理解数据结构

假设我们有一个简单的社交网络图：

Alice (0) ─── Bob (1)
   │            │
   │            │
Carol (2) ─── Dave (3)

对应的邻接表存储：

// 顶点表
vertices[0] -> neighbors: [1, 2]      // Alice 认识 Bob 和 Carol
vertices[1] -> neighbors: [0, 3]      // Bob 认识 Alice 和 Dave
vertices[2] -> neighbors: [0, 3]      // Carol 认识 Alice 和 Dave
vertices[3] -> neighbors: [1, 2]      // Dave 认识 Bob 和 Carol

// 边表
edges[0] -> (0, 1)  // Alice-Bob
edges[1] -> (0, 2)  // Alice-Carol
edges[2] -> (1, 3)  // Bob-Dave
edges[3] -> (2, 3)  // Carol-Dave

三、核心算法实现：如何在 Rust 中实现高性能图算法

3.1 BFS（广度优先搜索）：最基础的图遍历

BFS 是几乎所有图算法的基石。rust-igraph 的 BFS 实现展示了 Rust 并发模型的优势：

use rust_igraph::prelude::*;
use rust_igraph::algorithms::bfs::*;
use std::collections::VecDeque;

pub fn bfs<N: Numeric>(graph: &Graph, root: VertexId) -> BFSResult {
    let n = graph.vertex_count();
    let mut dist = vec![-1i32; n];        // 距离数组，-1 表示未访问
    let mut parent = vec![None; n];       // 父节点数组
    let mut queue = VecDeque::new();
    
    dist[root.as_usize()] = 0;
    queue.push_back(root);
    
    while let Some(current) = queue.pop_front() {
        // 获取当前顶点的所有邻居
        for neighbor in graph.neighbors(current) {
            let nid = neighbor.id().as_usize();
            if dist[nid] == -1 {
                dist[nid] = dist[current.as_usize()] + 1;
                parent[nid] = Some(current);
                queue.push_back(neighbor.id());
            }
        }
    }
    
    BFSResult { dist, parent }
}

// BFS 的并行化版本（利用 Rayon）
pub fn bfs_parallel<N: Numeric>(graph: &Graph, roots: &[VertexId]) -> Vec<BFSResult> {
    use rayon::prelude::*;
    
    roots.par_iter()
        .map(|&root| bfs(graph, root))
        .collect()
}

为什么这里用 Rayon 而不是 Tokio？ 因为 BFS 是计算密集型任务，不是 I/O 密集型。Rayon 的工作窃取线程池更适合这种场景。

3.2 PageRank：特征向量中心性的经典算法

PageRank 是 Google 创始人 Larry Page 在 1998 年发明的算法，最初用于网页排名，如今广泛应用于推荐系统、社交网络分析、知识图谱排序等场景。

算法原理：

• 一个网页的重要性取决于：(1) 指向它的网页数量；(2) 这些网页自身的重要性
• 通过迭代计算，最终收敛到稳定的排名分布

rust-igraph 的实现：

use rust_igraph::prelude::*;
use rust_igraph::algorithms::centrality::*;
use std::f64::consts::EPSILON;

/// 计算 PageRank
/// 
/// 参数说明：
/// - alpha: 阻尼系数（通常 0.85），表示随机跳转的概率
/// - max_iter: 最大迭代次数
/// - tol: 收敛阈值
pub fn pagerank<N: Numeric>(
    graph: &Graph,
    alpha: f64,
    max_iter: usize,
    tol: f64,
) -> Result<Vec<f64>, Error> {
    let n = graph.vertex_count();
    
    // 初始化 PageRank 值（均匀分布）
    let mut pr = vec![1.0 / n as f64; n];
    let mut pr_next = vec![0.0; n];
    
    for _iter in 0..max_iter {
        // 计算新的 PageRank 值
        for v in 0..n {
            let mut sum = 0.0;
            
            // 遍历所有指向 v 的顶点（入边）
            for (u_idx, _) in graph.edges().iter().enumerate() {
                let edge = &graph.edges()[u_idx];
                if edge.target.as_usize() == v {
                    // 计算 u 对 v 的贡献
                    let out_degree = graph.outdegree(VertexId::new(edge.source.as_usize()));
                    if out_degree > 0 {
                        sum += pr[edge.source.as_usize()] / out_degree.as_f64();
                    }
                }
            }
            
            pr_next[v] = (1.0 - alpha) / n as f64 + alpha * sum;
        }
        
        // 归一化
        let sum: f64 = pr_next.iter().sum();
        for v in 0..n {
            pr_next[v] /= sum;
        }
        
        // 检查收敛
        let diff: f64 = pr.iter()
            .zip(pr_next.iter())
            .map(|(a, b)| (a - b).abs())
            .sum();
        
        if diff < tol {
            return Ok(pr_next);
        }
        
        std::mem::swap(&mut pr, &mut pr_next);
    }
    
    Ok(pr)
}

性能优化技巧：

/// 优化版 PageRank：使用稀疏矩阵乘法
pub fn pagerank_sparse<N: Numeric>(
    graph: &SparseGraph,
    alpha: f64,
    max_iter: usize,
    tol: f64,
) -> Result<Vec<f64>, Error> {
    let n = graph.vertex_count();
    
    // 构建稀疏矩阵（CSR 格式）
    let csr = SparseMatrix::from_graph(graph);
    
    let mut pr = vec![1.0 / n as f64; n];
    
    for _iter in 0..max_iter {
        // 稀疏矩阵乘法：pr_next = alpha * (csr^T * pr) + (1-alpha)/n
        let pr_next = csr.multiply_transpose(&pr);
        
        for v in 0..n {
            pr_next[v] = (1.0 - alpha) / n as f64 + alpha * pr_next[v];
        }
        
        // 检查收敛...
    }
    
    Ok(pr)
}

3.3 最短路径：Dijkstra 算法与 A* 搜索

Dijkstra 算法是图论中最经典的单源最短路径算法，rust-igraph 提供了多种实现：

use rust_igraph::prelude::*;
use rust_igraph::algorithms::shortest_paths::*;
use std::collections::BinaryHeap;
use std::cmp::Reverse;

/// Dijkstra 算法（加权图）
pub fn dijkstra<N: Numeric>(
    graph: &Graph,
    source: VertexId,
    target: Option<VertexId>,
) -> Result<ShortestPaths, Error> {
    let n = graph.vertex_count();
    let mut dist = vec![f64::INFINITY; n];
    let mut prev = vec![None; n];
    
    dist[source.as_usize()] = 0.0;
    
    // 最小堆：优先弹出距离最小的顶点
    let mut heap = BinaryHeap::new();
    heap.push((Reverse(0.0), source));
    
    while let Some((Reverse(d), u)) = heap.pop() {
        // 如果已经找到了目标，可以提前退出
        if let Some(t) = target {
            if u == t {
                break;
            }
        }
        
        // 跳过已处理的顶点（更高效的写法用 Visited 集合）
        if d > dist[u.as_usize()] {
            continue;
        }
        
        // 遍历所有出边
        for edge in graph.edges_from(u) {
            let v = edge.target;
            let w = edge.weight.as_f64().unwrap_or(1.0);
            let new_dist = dist[u.as_usize()] + w;
            
            if new_dist < dist[v.as_usize()] {
                dist[v.as_usize()] = new_dist;
                prev[v.as_usize()] = Some(u);
                heap.push((Reverse(new_dist), v));
            }
        }
    }
    
    ShortestPaths::new(dist, prev)
}

/// A* 算法（带启发式函数的最短路径）
pub fn astar<N: Numeric, H: Fn(VertexId) -> f64>(
    graph: &Graph,
    source: VertexId,
    target: VertexId,
    heuristic: H,
) -> Option<(f64, Vec<VertexId>)> {
    let mut g_score = std::collections::HashMap::new();
    let mut f_score = std::collections::HashMap::new();
    let mut came_from = std::collections::HashMap::new();
    
    g_score.insert(source, 0.0);
    f_score.insert(source, heuristic(source));
    
    let mut open_set = BinaryHeap::new();
    open_set.push((Reverse(heuristic(source)), source));
    let mut closed_set = std::collections::HashSet::new();
    
    while let Some((Reverse(_f), current)) = open_set.pop() {
        if current == target {
            // 重建路径
            let mut path = vec![target];
            let mut node = target;
            while let Some(parent) = came_from.get(&node) {
                path.push(*parent);
                node = *parent;
            }
            path.reverse();
            return Some((g_score[&target], path));
        }
        
        if closed_set.contains(&current) {
            continue;
        }
        closed_set.insert(current);
        
        for edge in graph.edges_from(current) {
            if closed_set.contains(&edge.target) {
                continue;
            }
            
            let tentative_g = g_score.get(&current).unwrap_or(&f64::INFINITY) 
                             + edge.weight.as_f64().unwrap_or(1.0);
            
            if tentative_g < *g_score.get(&edge.target).unwrap_or(&f64::INFINITY) {
                came_from.insert(edge.target, current);
                g_score.insert(edge.target, tentative_g);
                let h = heuristic(edge.target);
                f_score.insert(edge.target, tentative_g + h);
                open_set.push((Reverse(tentative_g + h), edge.target));
            }
        }
    }
    
    None // 无路径
}

3.4 连通分量：Union-Find 算法

连通分量是图分析的基础操作。rust-igraph 使用**并查集（Union-Find）**实现高效的连通分量检测：

use rust_igraph::prelude::*;
use rust_igraph::algorithms::components::*;

/// Union-Find（并查集）数据结构
#[derive(Debug)]
pub struct UnionFind {
    parent: Vec<usize>,
    rank: Vec<usize>,
    count: usize,
}

impl UnionFind {
    pub fn new(n: usize) -> Self {
        UnionFind {
            parent: (0..n).collect(),
            rank: vec![0; n],
            count: n,
        }
    }
    
    /// 查找（带路径压缩）
    pub fn find(&mut self, x: usize) -> usize {
        if self.parent[x] != x {
            self.parent[x] = self.find(self.parent[x]); // 路径压缩
        }
        self.parent[x]
    }
    
    /// 合并（按秩合并）
    pub fn union(&mut self, x: usize, y: usize) {
        let px = self.find(x);
        let py = self.find(y);
        
        if px == py {
            return;
        }
        
        // 按秩合并：秩小的合并到秩大的
        if self.rank[px] < self.rank[py] {
            self.parent[px] = py;
        } else if self.rank[px] > self.rank[py] {
            self.parent[py] = px;
        } else {
            self.parent[py] = px;
            self.rank[px] += 1;
        }
        
        self.count -= 1;
    }
    
    pub fn count(&self) -> usize {
        self.count
    }
}

/// 计算连通分量
pub fn connected_components<N: Numeric>(
    graph: &Graph,
) -> Result<ComponentResult, Error> {
    let n = graph.vertex_count();
    let mut uf = UnionFind::new(n);
    
    // 遍历所有边，将相连的顶点合并
    for edge in graph.edges() {
        uf.union(
            edge.source.as_usize(),
            edge.target.as_usize(),
        );
    }
    
    // 统计每个连通分量的大小
    let mut comp_sizes: std::collections::HashMap<usize, usize> 
        = std::collections::HashMap::new();
    
    for v in 0..n {
        let root = uf.find(v);
        *comp_sizes.entry(root).or_insert(0) += 1;
    }
    
    Ok(ComponentResult {
        component_count: uf.count(),
        component_sizes: comp_sizes.into_values().collect(),
    })
}

并查集的复杂度分析：

其中 α(n) 是 Ackermann 函数的反函数，在所有实际应用中，α(n) ≤ 4。这意味着并查集的操作几乎是 O(1) 的！

四、性能优化：让 Rust 代码跑得比 C 还快

4.1 SIMD 加速：利用 CPU 的向量化能力

现代 CPU 的 SIMD（Single Instruction Multiple Data）指令可以在一条指令中处理多个数据。rust-igraph 利用 std::simd 和 packed_simd 库加速矩阵运算：

use std::simd::{SimdFloat, f32x4, u32x4};

/// SIMD 加速的向量点积
pub fn dot_product_simd(a: &[f32], b: &[f32]) -> f32 {
    assert_eq!(a.len(), b.len());
    assert_eq!(a.len() % 4, 0); // 对齐到 4
    
    let mut result = f32x4::splat(0.0);
    
    for chunk in a.chunks_exact(4) {
        let a_simd = f32x4::from_slice(chunk);
        let b_simd = f32x4::from_slice(&b[chunk.as_ptr().offset_from(b.as_ptr()) as usize * 4..]);
        result += a_simd * b_simd;
    }
    
    result.reduce_sum()
}

/// SIMD 加速的矩阵-向量乘法（稀疏矩阵 CSR 格式）
pub fn sparse_matrix_vector_multiply_simd(
    csr: &CsrMatrix<f32>,
    x: &[f32],
) -> Vec<f32> {
    let n = csr.rows();
    let mut y = vec![0.0f32; n];
    
    for i in 0..n {
        let row_start = csr.row_ptr[i];
        let row_end = csr.row_ptr[i + 1];
        
        let mut sum = f32x4::splat(0.0);
        
        // SIMD 处理 4 个元素一组
        let mut j = row_start;
        while j + 4 <= row_end {
            let values = f32x4::from_slice(&csr.values[j..j+4]);
            let indices: [usize; 4] = [
                csr.col_indices[j],
                csr.col_indices[j+1],
                csr.col_indices[j+2],
                csr.col_indices[j+3],
            ];
            let x_vals = f32x4::from_array([
                x[indices[0]],
                x[indices[1]],
                x[indices[2]],
                x[indices[3]],
            ]);
            sum += values * x_vals;
            j += 4;
        }
        
        // 处理剩余元素
        while j < row_end {
            sum += csr.values[j] * x[csr.col_indices[j]];
            j += 1;
        }
        
        y[i] = sum.reduce_sum();
    }
    
    y
}

4.2 多线程并行化：Rayon 的工作窃取

Rayon 是 Rust 生态中最优雅的并行化库，它基于**工作窃取（Work Stealing）**算法实现：

use rayon::prelude::*;
use rust_igraph::prelude::*;
use rust_igraph::algorithms::parallel::*;

/// 并行 BFS：从多个源点同时搜索
pub fn parallel_bfs_from_multiple_sources<N: Numeric>(
    graph: &Graph,
    sources: &[VertexId],
) -> Vec<ParallelBFSResult> {
    sources.par_iter()
        .map(|&source| {
            bfs(graph, source)
        })
        .collect()
}

/// 并行 PageRank：多线程迭代
pub fn parallel_pagerank<N: Numeric>(
    graph: &Graph,
    alpha: f64,
    max_iter: usize,
    tol: f64,
    num_threads: usize,
) -> Result<Vec<f64>, Error> {
    let n = graph.vertex_count();
    let mut pr = vec![1.0 / n as f64; n];
    
    // 配置 Rayon 线程数
    let pool = rayon::ThreadPoolBuilder::new()
        .num_threads(num_threads)
        .build()
        .unwrap();
    
    pool.install(|| {
        for _iter in 0..max_iter {
            let pr_next = compute_pagerank_iteration(graph, &pr, alpha);
            
            // 检查收敛
            let diff = pr.iter()
                .zip(pr_next.iter())
                .map(|(a, b)| (a - b).abs())
                .sum::<f64>();
            
            if diff < tol {
                return Ok(pr_next);
            }
            
            pr = pr_next;
        }
        Ok(pr)
    })
}

/// 在 Rayon 线程池中并行计算每个顶点的邻居贡献
fn compute_pagerank_iteration<N: Numeric>(
    graph: &Graph,
    pr: &[f64],
    alpha: f64,
) -> Vec<f64> {
    let n = graph.vertex_count();
    
    // 并行计算每个顶点的入边贡献
    (0..n).into_par_iter()
        .map(|v| {
            let mut sum = 0.0;
            
            for edge in graph.edges_to(VertexId::new(v)) {
                let out_degree = graph.outdegree(edge.source);
                if out_degree > 0 {
                    sum += pr[edge.source.as_usize()] / out_degree.as_f64();
                }
            }
            
            (1.0 - alpha) / n as f64 + alpha * sum
        })
        .collect()
}

4.3 内存布局优化：SoA vs AoS

数据结构的不同内存布局对缓存命中率和 SIMD 效率有巨大影响：

AoS（Array of Structures） - 传统布局：

struct Edge {
    source: VertexId,
    target: VertexId,
    weight: f64,
}

let edges = vec![Edge { source: ..., target: ..., weight: ... }; n];
// 问题：访问所有 source 需要跳跃访问不同的结构体字段

SoA（Structure of Arrays） - 缓存友好布局：

struct EdgeList {
    sources: Vec<VertexId>,
    targets: Vec<VertexId>,
    weights: Vec<f64>,
}

let edges = EdgeList {
    sources: vec![...],
    targets: vec![...],
    weights: vec![...],
};
// 优点：连续访问所有 source，数据打包在相邻内存中
//       SIMD 一次性加载 4 个 float

rust-igraph 的内部实现大量使用 SoA 布局来提升缓存效率：

pub struct EdgeListSoA {
    pub sources: Vec<usize>,
    pub targets: Vec<usize>,
    pub weights: Vec<f64>,
    pub attributes: Attributes,
}

impl EdgeListSoA {
    pub fn degree(&self, vertex: usize) -> usize {
        self.sources.iter().filter(|&&s| s == vertex).count()
            + self.targets.iter().filter(|&&t| t == vertex).count()
    }
    
    pub fn neighbors(&self, vertex: usize) -> Vec<usize> {
        let mut result = Vec::new();
        for i in 0..self.sources.len() {
            if self.sources[i] == vertex {
                result.push(self.targets[i]);
            }
            if self.targets[i] == vertex {
                result.push(self.sources[i]);
            }
        }
        result
    }
}

4.4 性能对比：rust-igraph vs igraph C vs networkx

以下是一个典型的性能对比测试（基于 PageRank 算法，处理一个 100 万顶点、1000 万边的图）：

关键发现：

1. 纯 Rust 可以比 C 快：在单线程情况下，rust-igraph 已经超越了 igraph C，这得益于 Rust 的零成本抽象和更好的内存布局控制
2. 多线程扩展性好：8 线程并行时，速度提升约 4 倍（接近线性扩展）
3. 内存效率更高：Rust 的 Vec<f64> 比 C 的 double* 有更紧凑的元数据

五、与 Python 生态的集成：让数据科学家也能用

5.1 PyO3 绑定：用 Rust 写 Python 扩展

rust-igraph 通过 PyO3 实现 Python 绑定，让 Python 用户能享受 Rust 的性能：

use pyo3::prelude::*;
use pyo3::wrap_pyfunction;

/// PageRank 计算函数（导出给 Python）
#[pyfunction]
fn pagerank(graph: &PyGraph, alpha: f64, max_iter: usize) -> PyResult<Vec<f64>> {
    let igraph = graph.as_rust_graph();
    Ok(igraph.pagerank(alpha, max_iter).unwrap())
}

/// 图对象（Python 侧）
#[pyclass]
struct Graph {
    inner: rust_igraph::Graph,
}

#[pyo3::pymethods]
impl Graph {
    #[new]
    fn new(num_vertices: usize, directed: bool) -> Self {
        Graph {
            inner: rust_igraph::Graph::new(num_vertices, directed),
        }
    }
    
    fn add_edge(&mut self, from: usize, to: usize) -> PyResult<()> {
        self.inner.add_edge(
            VertexId::new(from),
            VertexId::new(to),
        ).map_err(|e| PyErr::new::<pyo3::exceptions::PyValueError, _>(e.to_string()))
    }
    
    fn pagerank(&self, alpha: f64, max_iter: usize) -> PyResult<Vec<f64>> {
        Ok(self.inner.pagerank(alpha, max_iter).unwrap())
    }
}

#[pymodule]
fn rust_igraph_py(_: Python, m: &PyModule) -> PyResult<()> {
    m.add_function(wrap_pyfunction!(pagerank, m)?)?;
    m.add_class::<Graph>()?;
    Ok(())
}

Python 使用方式：

import rust_igraph

# 创建图
g = rust_igraph.Graph(1000, directed=False)

# 添加边
for i in range(1000):
    g.add_edge(i, (i + 1) % 1000)

# 计算 PageRank
ranks = g.pagerank(alpha=0.85, max_iter=100)
print(f"Top vertex: {max(range(len(ranks)), key=lambda i: ranks[i])}")

5.2 与 DataFrame 集成：polars 的图扩展

在现代数据科学生态中，polars 是 pandas 的高性能替代品。rust-igraph 可以与 polars 深度集成：

use polars::prelude::*;

/// 从 polars DataFrame 构建图
pub fn from_dataframe(df: &DataFrame) -> Result<Graph, Error> {
    let source_col = df.column("source")?;
    let target_col = df.column("target")?;
    let weight_col = df.column("weight").ok();
    
    let n_vertices = find_max_vertex(source_col, target_col)?;
    let mut graph = Graph::new(n_vertices + 1, Undirected);
    
    for i in 0..source_col.len() {
        let s = source_col.get(i)?.try_extract::<u64>()? as usize;
        let t = target_col.get(i)?.try_extract::<u64>()? as usize;
        
        if let Some(wc) = weight_col {
            let w = wc.get(i)?.try_extract::<f64>()?;
            graph.add_edge_with_weight(VertexId::new(s), VertexId::new(t), w)?;
        } else {
            graph.add_edge(VertexId::new(s), VertexId::new(t))?;
        }
    }
    
    Ok(graph)
}

/// 将图结果写回 DataFrame
pub fn to_dataframe(result: &ShortestPaths) -> DataFrame {
    let df = df!(
        "vertex" => (0..result.dist.len()).collect::<Vec<_>>(),
        "distance" => result.dist.clone(),
        "parent" => result.parent.iter()
            .map(|p| p.map(|v| v.as_usize() as u64))
            .collect::<Vec<_>>(),
    ).unwrap();
    df
}

六、生产级实战：从网络日志分析到安全威胁检测

6.1 场景：大规模网络日志分析

假设我们有 1000 万条防火墙日志，需要分析网络攻击路径和异常行为：

use rust_igraph::prelude::*;
use rust_igraph::builder::GraphBuilder;
use std::collections::HashMap;

/// 从防火墙日志构建通信图
pub fn build_network_graph(logs: &[FirewallLog]) -> Graph {
    let mut ip_map: HashMap<IpAddr, VertexId> = HashMap::new();
    let mut next_id: VertexId = VertexId::new(0);
    
    let mut builder = GraphBuilder::new();
    
    // 第一遍：建立 IP -> VertexId 映射
    for log in logs {
        if !ip_map.contains_key(&log.src_ip) {
            ip_map.insert(log.src_ip, next_id);
            next_id = VertexId::new(next_id.as_usize() + 1);
        }
        if !ip_map.contains_key(&log.dst_ip) {
            ip_map.insert(log.dst_ip, next_id);
            next_id = VertexId::new(next_id.as_usize() + 1);
        }
    }
    
    // 第二遍：构建图
    let n = ip_map.len();
    let mut graph = Graph::new(n, Directed);
    
    for log in logs {
        let src = ip_map[&log.src_ip];
        let dst = ip_map[&log.dst_ip];
        
        // 边权重 = 通信次数
        if let Ok(existing) = graph.edge_id(src, dst) {
            graph.increment_edge_weight(existing);
        } else {
            graph.add_edge_with_weight(src, dst, 1.0).unwrap();
        }
    }
    
    graph
}

/// 检测可疑的横向移动
pub fn detect_lateral_movement(graph: &Graph) -> Vec<AttackPath> {
    let mut suspicious_paths = Vec::new();
    
    // 找出所有连通分量
    let components = connected_components(graph).unwrap();
    
    for component_id in 0..components.component_count {
        let vertices: Vec<VertexId> = graph.vertices()
            .filter(|v| components.component_of(v.id()) == component_id)
            .map(|v| v.id())
            .collect();
        
        // 寻找"出度小但入度大"的顶点（可能的跳板机）
        for &v in &vertices {
            let in_degree = graph.indegree(v);
            let out_degree = graph.outdegree(v);
            
            if in_degree > 10 && out_degree > 5 && in_degree > out_degree * 2 {
                // 可能是被入侵的服务器
                let paths = find_shortest_paths_from(graph, v, &vertices);
                suspicious_paths.push(AttackPath {
                    pivot: v,
                    outgoing_connections: paths,
                });
            }
        }
    }
    
    suspicious_paths
}

6.2 场景：推荐系统中的协同过滤

图算法在推荐系统中也有广泛应用。以下是一个基于图传播的协同过滤实现：

use rust_igraph::prelude::*;

/// 基于图扩散的推荐算法
pub fn graph_based_recommendation(
    user_item_graph: &Graph,
    target_user: VertexId,
    k: usize,  // 推荐数量
) -> Vec<(VertexId, f64)> {
    let n = user_item_graph.vertex_count();
    
    // Step 1: 构建用户-用户相似度图（基于共同评分）
    let user_graph = build_user_similarity_graph(user_item_graph);
    
    // Step 2: 在用户相似度图上做 Label Propagation
    let mut labels = vec![0.0f64; n];
    labels[target_user.as_usize()] = 1.0;
    
    for _iter in 0..10 {
        labels = label_propagation_step(&user_graph, &labels);
    }
    
    // Step 3: 找出与目标用户最相似的 K 个用户
    let mut similarities: Vec<_> = (0..n)
        .map(|i| (VertexId::new(i), labels[i]))
        .collect();
    similarities.sort_by(|a, b| b.1.partial_cmp(&a.1).unwrap());
    
    let similar_users: Vec<VertexId> = similarities[1..=k]
        .iter()
        .map(|(v, _)| *v)
        .collect();
    
    // Step 4: 聚合相似用户的评分
    let mut recommendations: HashMap<VertexId, f64> = HashMap::new();
    
    for &user in &similar_users {
        for item in user_item_graph.neighbors(user) {
            let weight = labels[user.as_usize()];
            *recommendations.entry(item.id()).or_insert(0.0) += weight;
        }
    }
    
    // 排序并返回 Top K
    let mut recs: Vec<_> = recommendations.into_iter().collect();
    recs.sort_by(|a, b| b.1.partial_cmp(&a.1).unwrap());
    recs.into_iter().take(k).collect()
}

fn label_propagation_step(graph: &Graph, labels: &[f64]) -> Vec<f64> {
    let n = graph.vertex_count();
    let mut new_labels = vec![0.0f64; n];
    
    for v in 0..n {
        let neighbors: Vec<_> = graph.neighbors(VertexId::new(v))
            .iter()
            .map(|n| n.id().as_usize())
            .collect();
        
        if neighbors.is_empty() {
            new_labels[v] = labels[v];
        } else {
            // 取邻居标签的均值
            let sum: f64 = neighbors.iter().map(|&n| labels[n]).sum();
            new_labels[v] = sum / neighbors.len() as f64;
        }
    }
    
    new_labels
}

七、对比与总结：rust-igraph 的定位

7.1 与其他 Rust 图库的对比

7.2 适用场景与局限

适合使用 rust-igraph 的场景：

• 需要 igraph C 兼容 API 的项目（直接迁移）
• 大规模图计算（>1000 万顶点）
• 对性能有极致要求的场景
• 需要多线程并行的图算法
• 与 Python 数据科学生态集成

目前不适合的场景：

• 小规模图（直接用 petgraph 更轻量）
• 需要频繁修改图结构的场景（Rust 的借用检查器会限制灵活性）
• 对编译时间敏感的项目（rust-igraph 编译较慢）

7.3 未来展望

rust-igraph 目前仍在积极开发中，以下是值得关注的方向：

1. GPU 加速：利用 CUDA/WGPU 实现大规模矩阵运算的 GPU 加速
2. 图神经网络（GNN）层：与 PyTorch Geometric 深度集成
3. 动态图支持：支持图的增量更新（添加/删除顶点/边）
4. 分布式计算：基于 Apache Arrow 和 DataFusion 的分布式图计算

总结

rust-igraph 是一个雄心勃勃的项目——用纯 Rust 从零实现一个功能完整的图计算库。它不仅仅是 igraph C 的"翻译"，更是一次利用 Rust 类型系统和并发模型重新思考图计算的工程实践。

从 Builder 模式替代过程式 API，到类型系统编码图的性质；从 SIMD 向量化加速，到 Rayon 工作窃取并行化——rust-igraph 展示了 Rust 在高性能计算领域的巨大潜力。

如果你正在寻找一个高性能、安全可靠、功能完整的图计算库，rust-igraph 值得你深入研究和实际应用。

项目地址：github.com/Totoro-jam/rust-igraph

本文原创，代码示例基于 rust-igraph 的公开 API 和设计文档。如有疏漏，欢迎指正。