5 层 Trait 详解

Trait 系统是 mbtgraph 的架构核心，它通过 5 层分层设计实现了算法与存储的完全解耦。理解这一设计是高效使用本库的关键。

设计哲学

三大设计原则

原则	实现方式	核心价值
接口隔离 (ISP)	每层只提供必要的方法	存储只需实现所需能力，避免过度设计
里氏替换 (LSP)	只读存储不实现 Writable	编译期保证类型安全，避免运行时错误
依赖倒置 (DIP)	算法依赖 Trait 抽象	新增存储无需修改算法代码

为什么需要分层？

传统图库（如 NetworkX）通常只有一种统一接口：

# NetworkX: 所有操作都在一个 Graph 类上
G = nx.DiGraph()
G.add_node(1)
G.add_edge(1, 2)
nx.shortest_path(G, source=1)  # 无法在编译期优化

问题：

❌ 无法区分只读/可写存储
❌ 编译器无法进行静态优化
❌ CSR 等高性能存储被迫实现不需要的接口

mbtgraph 的解决方案：

// 泛型约束让编译器知道存储的能力
pub fn[G : @core.GraphReadable] bfs(graph : G, start : NodeId) -> BfsResult {
  // 编译器知道 G 至少有 node_count(), neighbors() 等 12 个方法
  // 可以针对不同存储生成最优代码
}

// CSR 存储：只实现 GraphReadable + GraphBatchReadable（轻量）
// AdjList 存储：实现 GraphFull（完整功能）

Trait 层级总览

Layer 0: GraphReadable (基础只读)
    │ 12 个方法，所有存储必须实现
    │
    ├── Layer 1A: GraphWritable (可写扩展)
    │   └── +5 方法，动态存储专属（AdjList/Matrix/EdgeList）
    │       │
    │       └── Layer 2: GraphDirected (有向扩展)
    │           └── +6 方法，入边查询能力
    │               │
    │               └── Layer 3: GraphFull (便捷别名)
    │                   = GraphWritable + GraphDirected
    │
    ├── Layer 1B: GraphBatchReadable (批量优化)
    │   └── +2 方法，CSR/CSC 专属
    │
    └── Layer 2: GraphPartial / GraphFull (可选组合)
        └── 便捷别名，无需额外方法

Layer 0: GraphReadable - 基础只读接口

定义

/// 图只读接口
///
/// 所有存储实现的最低要求，符合接口隔离原则 (ISP)。
/// 只包含所有实现都能提供的方法。
pub(open) trait GraphReadable {
  /// 节点数量
  node_count(Self) -> Int

  /// 边数量
  edge_count(Self) -> Int

  /// 检查节点是否存在
  contains_node(Self, NodeId) -> Bool

  /// 检查边是否存在
  contains_edge(Self, NodeId, NodeId) -> Bool

  /// 获取节点数据
  get_node(Self, NodeId) -> Double?

  /// 获取边数据
  get_edge(Self, NodeId, NodeId) -> Double?

  /// 获取邻居节点（出边目标）
  neighbors(Self, NodeId) -> Iter[NodeId]

  /// 获取邻居节点及边权重（优化用）
  neighbors_with_weight(Self, NodeId) -> Iter[(NodeId, Double)]

  /// 节点度（无向图）或出度（有向图）
  degree(Self, NodeId) -> Int

  /// 是否为有向图
  is_directed(Self) -> Bool

  /// 是否为空图
  is_empty(Self) -> Bool

  /// 迭代所有节点 ID
  node_ids(Self) -> Iter[NodeId]

  /// 迭代所有边 (from, to, weight)
  edges(Self) -> Iter[(NodeId, NodeId, Double)]
}

方法分类

统计信息 (2 个)

let n = @core.GraphReadable::node_count(graph)      // 节点数
let m = @core.GraphReadable::edge_count(graph)      // 边数
let empty = @core.GraphReadable::is_empty(graph)    // 是否为空
let directed = @core.GraphReadable::is_directed(graph) // 是否有向

存在性检查 (2 个)

if (@core.GraphReadable::contains_node(graph, id)) { ... }
if (@core.GraphReadable::contains_edge(graph, from, to)) { ... }

数据访问 (2 个)

// 返回 Option，必须处理 None 情况
match @core.GraphReadable::get_node(graph, id) {
  Some(data) => println("节点数据: \{data\}")
  None => println("节点不存在")
}

match @core.GraphReadable::get_edge(graph, from, to) {
  Some(weight) => println("边权重: \{weight\}")
  None => println("边不存在")
}

邻居查询 (3 个)

// 方式 1: 仅获取邻居 ID（需二次查询权重）
@core.GraphReadable::neighbors(graph, id)
  |> iter::each(fn(neighbor_id) { ... })

// 方式 2: 获取带权重的邻居（推荐，避免二次查询）
@core.GraphReadable::neighbors_with_weight(graph, id)
  |> iter::each(fn((neighbor_id, weight)) {
    println("\{id\} -> \{neighbor_id\} (\{weight\})")
  })

// 方式 3: 获取度数
let deg = @core.GraphReadable::degree(graph, id)

全量遍历 (2 个)

// 遍历所有节点
@core.GraphReadable::node_ids(graph)
  |> iter::each(fn(id) { ... })

// 遍历所有边
@core.GraphReadable::edges(graph)
  |> iter::each(fn((from, to, weight)) { ... })

适用范围

✅ 所有 8 种存储都必须实现此 Trait

存储类型	实现 GraphReadable?	备注
DirectedAdjList	✅	默认推荐
UndirectedAdjList	✅	无向场景首选
DirectedMatrix	✅	稠密小图
UndirectedMatrix	✅	无向稠密图
EdgeList	✅	Kruskal 友好
UndirectedEdgeList	✅	无向边集
CSR	✅	大规模静态图
CSC	✅	入边密集查询

使用示例：编写通用算法

/// 计算图的平均度数
pub fn[G : @core.GraphReadable] average_degree(graph : G) -> Double {
  let n = @core.GraphReadable::node_count(graph)
  if (n == 0) { return 0.0 }

  let total_degree : Int = 0
  @core.GraphReadable::node_ids(graph)
    |> iter::fold(total_degree, fn(acc, id) {
      acc + @core.GraphReadable::degree(graph, id)
    })

  (total_degree.to_double()) / (n.to_double())
}

/// 打印图的基本信息
pub fn[G : @core.GraphReadable] print_info(graph : G) -> Unit {
  let n = @core.GraphReadable::node_count(graph)
  let m = @core.GraphReadable::edge_count(graph)
  let avg_deg = average_degree(graph)

  println("=== 图统计信息 ===")
  println("节点数: \{n\}")
  println("边数: \{m\}")
  println("平均度数: \{avg_deg:.2f\}")
  println("是否有向: \{@core.GraphReadable::is_directed(graph)\}")
}

// 使用示例
fn main() {
  let adj_list = create_adj_list_graph()
  let csr_graph = create_csr_graph()

  print_info(adj_list)  // ✅ 同一函数适用于不同存储
  print_info(csr_graph)
}

Layer 1A: GraphWritable - 可写扩展

定义

/// 图可写接口
///
/// 仅适用于支持动态修改的存储（邻接表、邻接矩阵）。
/// CSR 等只读存储不实现此 trait，符合里氏替换原则 (LSP)。
pub(open) trait GraphWritable: GraphReadable {
  /// 添加节点，返回其 ID
  add_node(Self, Double) -> NodeId

  /// 删除节点及其关联的所有边
  remove_node(Self, NodeId) -> Bool

  /// 添加边
  add_edge(Self, NodeId, NodeId, Double) -> Result[Unit, GraphError]

  /// 删除边
  remove_edge(Self, NodeId, NodeId) -> Bool

  /// 清空图
  clear(Self) -> Unit
}

新增方法详解

`add_node(data) -> NodeId`

添加新节点并返回自动分配的 ID：

let g = @storage.new_directed()
let id0 = @core.GraphWritable::add_node(g, 100.0)  // 返回 NodeId(0)
let id1 = @core.GraphWritable::add_node(g, 200.0)  // 返回 NodeId(1)

// data 参数的语义取决于应用场景
let user_id = @core.GraphWritable::add_node(g, 0.95)     // 用户影响力
let city_id = @core.GraphWritable::add_node(g, 43.5)     // 海拔高度
let router_id = @core.GraphWritable::add_node(g, 1000.0)  // 带宽容量

`add_edge(from, to, weight) -> Result[Unit, GraphError]`

添加边并处理可能的错误：

// 成功情况
match @core.GraphWritable::add_edge(g, id0, id1, 5.0) {
  Ok(_) => println("边添加成功")
  Err(e) => handle_error(e)
}

// 错误处理
fn handle_error(e : GraphError) -> Unit {
  match e {
    NodeNotFound(id) =>
      println("❌ 错误: 节点 \{id\} 不存在，请先添加节点")

    EdgeAlreadyExists(from, to) =>
      println("⚠️ 警告: 边 (\{from\}, \{to\}) 已存在")

    InvalidNodeId =>
      println("❌ 错误: 无效的节点 ID")
  }
}

`remove_node(id) -> Bool` 和 `remove_edge(from, to) -> Bool`

删除操作返回是否成功：

// 删除节点（会同时删除所有关联边）
if (@core.GraphWritable::remove_node(g, id)) {
  println("节点及其所有边已删除")
} else {
  println("节点不存在，无需删除")
}

// 删除单条边
if (@core.GraphWritable::remove_edge(g, from, to)) {
  println("边已删除")
} else {
  println("边不存在")
}

`clear()` 清空图

@core.GraphWritable::clear(g)  // 移除所有节点和边
println("图已清空，当前节点数: \{@core.GraphReadable::node_count(g)\}")  // 0

适用范围

仅动态存储实现此 Trait：

存储类型	实现 GraphWritable?	原因
DirectedAdjList	✅	支持动态增删
UndirectedAdjList	✅	支持动态增删
DirectedMatrix	✅	支持动态增删
UndirectedMatrix	✅	支持动态增删
EdgeList	✅	支持动态增删
UndirectedEdgeList	✅	支持动态增删
CSR	❌	只读存储，构建后不可修改
CSC	❌	只读存储，构建后不可修改

典型使用模式

/// 构建一个社交网络图
fn build_social_network() -> DirectedAdjList {
  let mut g = @storage.new_directed()

  // 批量添加用户
  let alice = @core.GraphWritable::add_node(g, 0.95)
  let bob = @core.GraphWritable::add_node(g, 0.72)
  let charlie = @core.GraphWritable::add_node(g, 0.88)

  // 添加关注关系
  @core.GraphWritable::add_edge(g, alice, bob, 1.0) |> ignore
  @core.GraphWritable::add_edge(g, alice, charlie, 1.0) |> ignore
  @core.GraphWritable::add_edge(g, bob, charlie, 1.0) |> ignore

  g
}

Layer 2: GraphDirected - 有向图扩展

定义

/// 有向图扩展接口
///
/// 提供入边查询能力。邻接表需维护反向索引以支持此 trait。
/// 无向图实现可通过返回相同的邻居列表来适配。
pub(open) trait GraphDirected: GraphReadable {
  /// 获取前驱节点（入边源）
  in_neighbors(Self, NodeId) -> Iter[NodeId]

  /// 获取后继节点（出边目标）
  out_neighbors(Self, NodeId) -> Iter[NodeId]

  /// 入度
  in_degree(Self, NodeId) -> Int

  /// 出度
  out_degree(Self, NodeId) -> Int

  /// 前驱边 (源节点, 边数据)
  predecessors(Self, NodeId) -> Iter[(NodeId, Double)]

  /// 后继边 (目标节点, 边数据)
  successors(Self, NodeId) -> Iter[(NodeId, Double)]
}

为什么需要单独的 Trait？

GraphReadable 的 degree() 和 neighbors() 对有向图和无向图语义模糊：

无向图: degree(v) = 邻居总数
有向图: 需要区分 in_degree(入度) 和 out_degree(出度)

GraphDirected 明确了这些概念。

使用示例

/// 分析节点的连接特征
pub fn[G : @core.GraphDirected] analyze_connectivity(graph : G, id : NodeId) -> Unit {
  let in_deg = @core.GraphDirected::in_degree(graph, id)
  let out_deg = @core.GraphDirected::out_degree(graph, id)

  println("=== 节点 \{id\} 连接分析 ===")
  println("入度 (被多少人关注): \{in_deg\}")
  println("出度 (关注了多少人): \{out_deg\}")

  if (in_deg > out_deg * 2) {
    println("⭐ 该节点是影响力节点（被高度关注）")
  } else if (out_deg > in_deg * 2) {
    println("📢 该节点是活跃节点（关注很多人）")
  }

  // 列出所有粉丝（入边源）
  println("\n粉丝列表:")
  @core.GraphDirected::predecessors(graph, id)
    |> iter::each(fn((fan_id, _)) {
      println("  ← 来自节点 \{fan_id\}")
    })
}

/// PageRank 简化版（需要入边访问）
pub fn[G : @core.GraphDirected] simplified_pagerank(
  graph : G,
  iterations : Int,
  damping : Double
) -> Array[Double] {
  let n = @core.GraphReadable::node_count(graph)
  let mut ranks = Array::make(n, 1.0 / n.to_double())

  for i in 0..iterations {
    let mut new_ranks = Array::make(n, (1.0 - damping) / n.to_double())

    @core.GraphReadable::node_ids(graph) |> iter::each(fn(node_id) {
      match node_id {
        NodeId(idx) => {
          // 分发排名给所有后继节点
          let out_deg = @core.GraphDirected::out_degree(graph, node_id).to_double()
          if (out_deg > 0.0) {
            let rank_contribution = ranks[idx] * damping / out_deg
            @core.GraphDirected::successors(graph, node_id)
              |> iter::each(fn((succ_id, _)) {
                match succ_id {
                  NodeId(succ_idx) => {
                    new_ranks[succ_idx] = new_ranks[succ_idx] + rank_contribution
                  }
                }
              })
          }
        }
      }
    })

    ranks = new_ranks
  }

  ranks
}

适用范围

存储类型	实现 GraphDirected?	实现方式
DirectedAdjList	✅	维护反向邻接表
DirectedMatrix	✅	直接访问矩阵列
CSR	⚠️ 可选	需额外构建 CSC 或转置
CSC	✅	天然支持入边查询
Undirected*	✅	`in_neighbors == out_neighbors`

Layer 3: GraphFull - 便捷别名

定义

/// 完整图接口
///
/// 组合可写 + 有向图能力，适用于邻接表等通用实现。
pub(open) trait GraphFull: GraphWritable + GraphDirected {
  // 无需额外方法，仅作类型约束的便捷别名
}

使用场景

当你需要同时具备读写能力和有向图查询时：

/// 需要完整功能的算法示例：有向图的动态更新 + 分析
pub fn[G : @core.GraphFull] dynamic_analysis_demo(graph : G) -> Unit {
  // 1. 写操作（需要 GraphWritable）
  let new_id = @core.GraphWritable::add_node(graph, 0.5)

  // 2. 有向图查询（需要 GraphDirected）
  let in_deg = @core.GraphDirected::in_degree(graph, new_id)
  let out_deg = @core.GraphDirected::out_degree(graph, new_id)

  // 3. 基础查询（继承自 GraphReadable）
  println("新节点: 入度=\{in_deg\}, 出度=\{out_deg\}")

  // 4. 复合操作
  @core.GraphDirected::predecessors(graph, new_id)
    |> iter::each(fn((pred, w)) {
      // 可以安全地调用任何三层方法
      if (@core.GraphReadable::contains_edge(graph, pred, new_id)) {
        println("确认边存在: \{pred\} -> \{new_id\}")
      }
    })
}

实现此 Trait 的存储

✅ DirectedAdjList （推荐）
✅ DirectedMatrix
❌ CSR / CSC （不可写）

Layer 1B: GraphBatchReadable - 批量优化

定义

/// CSR 批量读取接口
///
/// 提供批量处理优化，适合大图计算。
/// 仅 CSR 等支持连续内存访问的存储实现此 trait。
pub(open) trait GraphBatchReadable: GraphReadable {
  /// 批量获取邻居
  batch_neighbors(Self, Array[NodeId]) -> Array[Array[NodeId]]

  /// 批量获取边数据
  batch_edges(Self, Array[(NodeId, NodeId)]) -> Array[Double?]
}

性能优势

对比逐个查询 vs 批量查询：

/// 逐个查询（慢）
fn slow_query[G : @core.GraphReadable](graph : G, ids : Array[NodeId]) -> Array[Array[NodeId]] {
  Array::map(ids, fn(id) {
    @core.GraphReadable::neighbors(graph, id) |> iter::to_array
  })
}

/// 批量查询（快，仅限 GraphBatchReadable）
fn fast_query[G : @core.GraphBatchReadable](graph : G, ids : Array[NodeId]) -> Array[Array[NodeId]] {
  @core.GraphBatchReadable::batch_neighbors(graph, ids)
}

性能差异（10 万节点图）：

操作方式	时间复杂度	实际耗时
逐个查询	O(k × queries)	~500ms
批量查询	O(k)（缓存友好）	~50ms

适用范围

存储类型	实现 GraphBatchReadable?	原因
CSR	✅	连续内存，SIMD 友好
CSC	✅	同上
AdjList	❌	链表结构，批量无优势
Matrix	❌	已足够快，无需优化

使用示例：BFS 批量优化

/// 使用批量优化的 BFS（适用于超大规模图）
pub fn[G : @core.GraphBatchReadable] bfs_batch_optimized(
  graph : G,
  start : NodeId
) -> Array[Int] {
  let n = @core.GraphReadable::node_count(graph)
  let mut distances = Array::make(n, -1)
  let mut visited = Array::make(n, false)
  let mut queue = Array::new()

  match start {
    NodeId(s) => { distances[s] = 0; visited[s] = true }
  }

  queue.push(start)

  while (queue.length() > 0) {
    // 批量出队（一次处理多个节点）
    let batch_size = min(queue.length(), 64)  // 缓存行大小优化
    let current_batch = Array::make(batch_size, @core.NodeId(0))

    for i in 0..batch_size {
      current_batch[i] = queue.shift_unsafe()
    }

    // 批量获取邻居
    let all_neighbors = @core.GraphBatchReadable::batch_neighbors(graph, current_batch)

    // 处理所有邻居
    for neighbor_list in all_neighbors {
      for neighbor in neighbor_list {
        match neighbor {
          NodeId(idx) => {
            if (not visited[idx]) {
              visited[idx] = true
              distances[idx] = distances[match start { NodeId(s) => s }] + 1
              queue.push(neighbor)
            }
          }
        }
      }
    }
  }

  distances
}

Trait 组合策略

如何选择合适的 Trait 约束？

根据算法需求选择最小满足原则：

// 场景 1: 只读取统计信息 → GraphReadable
pub fn[G : @core.GraphReadOnly] count_nodes(graph : G) -> Int { ... }

// 场景 2: 需要修改图结构 → GraphWritable
pub fn[G : @core.GraphWritable] add_complete_graph(graph : G, n : Int) -> G { ... }

// 场景 3: 有向图分析 → GraphDirected
pub fn[G : @core.GraphDirected] compute_pagerank(graph : G) -> Array[Double] { ... }

// 场景 4: 动态有向图 → GraphFull
pub fn[G : @core.GraphFull] dynamic_shortest_path(graph : G) -> PathResult { ... }

// 场景 5: 大规模批处理 → GraphBatchReadable
pub fn[G : @core.GraphBatchReadable] batch_bfs(graph : G, sources : Array[NodeId]) { ... }

类型推断示例

MoonBit 编译器会根据 Trait 约束推断可用方法：

/// 这个函数可以使用哪些方法？
pub fn demo[G : @core.GraphWritable](graph : G) -> Unit {
  // ✅ 可以使用 GraphReadable 的 12 个方法
  let n = @core.GraphReadable::node_count(graph)

  // ✅ 可以使用 GraphWritable 的 5 个方法
  let id = @core.GraphWritable::add_node(graph, 1.0)

  // ❌ 编译错误: 不能使用 GraphDirected 的方法
  // let in_deg = @core.GraphDirected::in_degree(graph, id)  // Error!

  // ❌ 编译错误: 不能使用 BatchReadable 的方法
  // let batch = @core.GraphBatchReadable::batch_neighbors(graph, [id])  // Error!
}

最佳实践总结

1. 算法开发者的 Checklist

确定算法需要的最小 Trait 集
在泛型约束中使用最具体的 Trait
文档说明对 Trait 的要求
测试时覆盖多种存储类型

2. 存储使用者的决策树

需要修改图？
├─ 是 → 需要 GraphWritable
│      ├─ 需要入边查询？→ 是 → 使用 GraphFull (DirectedAdjList)
│      └─ 否 → 使用 GraphWritable (UndirectedAdjList)
│
└─ 否 → 只读即可
       ├─ 大规模 (>10万节点)？→ 是 → 使用 GraphBatchReadable (CSR/CSC)
       └─ 一般用途 → 使用 GraphReadable (任意存储)

3. 性能优化建议

场景	推荐存储	推荐 Trait	原因
交互式编辑	AdjList	GraphFull	O(1) 增删
批量分析	CSR	GraphBatchReadable	缓存友好
算法竞赛	Matrix	GraphReadable	O(1) 随机访问

下一步

掌握 Trait 系统后，你可以：

存储选型指南 - 选择最适合你需求的存储实现
错误处理机制 - 正确处理 Result 和 Option
创建第一个图 - 动手实践完整工作流

💡

进阶提示

深入理解源码:

Trait 定义：lib/core/traits.mbt
实现示例：lib/storage/directed_adj_list.mbt
设计文档：Trait 设计决策记录

5 层 Trait 详解

5 层 Trait 详解

设计哲学

三大设计原则

为什么需要分层？

Trait 层级总览

Layer 0: GraphReadable - 基础只读接口

定义

方法分类

统计信息 (2 个)

存在性检查 (2 个)

数据访问 (2 个)

邻居查询 (3 个)

全量遍历 (2 个)

适用范围

使用示例：编写通用算法

Layer 1A: GraphWritable - 可写扩展

定义

新增方法详解

add_node(data) -> NodeId

add_edge(from, to, weight) -> Result[Unit, GraphError]

remove_node(id) -> Bool 和 remove_edge(from, to) -> Bool

clear() 清空图

适用范围

典型使用模式

Layer 2: GraphDirected - 有向图扩展

定义

为什么需要单独的 Trait？

使用示例

适用范围

Layer 3: GraphFull - 便捷别名

定义

使用场景

实现此 Trait 的存储

Layer 1B: GraphBatchReadable - 批量优化

定义

性能优势

适用范围

使用示例：BFS 批量优化

Trait 组合策略

如何选择合适的 Trait 约束？

类型推断示例

最佳实践总结

1. 算法开发者的 Checklist

2. 存储使用者的决策树

3. 性能优化建议

下一步

`add_node(data) -> NodeId`

`add_edge(from, to, weight) -> Result[Unit, GraphError]`

`remove_node(id) -> Bool` 和 `remove_edge(from, to) -> Bool`

`clear()` 清空图