📚 课程目录第4章边的定义与方向

4. 边的定义与方向：Edge 结构体详解、有向边创建、权重与标签

在 DAG 调度系统中，边（Edge）是连接两个任务节点的核心元素，它定义了任务之间的依赖关系与数据流向。本章将深入剖析 Edge 结构体的设计、有向边的创建方式，以及权重与标签在实际调度中的语义。

4.1 Edge 结构体定义

Edge 结构体是 DAG 中边的数据抽象，它需要同时承载拓扑信息（起点与终点）和调度元信息（权重、标签）。以下是一个典型的 Go 实现：

// Edge 表示 DAG 中的一条有向边
type Edge struct {
    ID     string      // 边的唯一标识
    From   string      // 源节点 ID
    To     string      // 目标节点 ID
    Weight float64     // 边的权重（通常表示传输代价或延迟）
    Label  string      // 边的标签（用于语义分类或路由策略）
    Meta   interface{} // 扩展元数据（可选）
}

字段	类型	说明	调度用途
ID	`string`	全局唯一标识	边索引与追踪
From	`string`	源节点 ID	确定依赖方向
To	`string`	目标节点 ID	确定执行顺序
Weight	`float64`	边权重	调度决策（如最小化通信开销）
Label	`string`	语义标签	策略分组与过滤
Meta	`interface{}`	扩展字段	自定义调度属性

设计要点：Edge 结构体采用 From 和 To 字符串引用节点 ID，而非直接存储节点指针。这种设计使得边序列化、跨进程传输和持久化更加便捷，同时避免了循环引用问题。

4.2 有向边的创建与方向语义

有向边（Directed Edge）严格规定了数据或控制的流动方向：从 From 节点指向 To 节点。在 DAG 调度中，这意味着 From 节点必须在 To 节点之前完成执行。

// NewEdge 创建一条有向边
func NewEdge(from, to string, opts ...EdgeOption) *Edge {
    e := &Edge{
        ID:   fmt.Sprintf("edge-%s-%s-%d", from, to, time.Now().UnixNano()),
        From: from,
        To:   to,
    }
    for _, opt := range opts {
        opt(e)
    }
    return e
}

// EdgeOption 函数式选项模式
type EdgeOption func(*Edge)

// WithWeight 设置边权重
func WithWeight(w float64) EdgeOption {
    return func(e *Edge) { e.Weight = w }
}

// WithLabel 设置边标签
func WithLabel(l string) EdgeOption {
    return func(e *Edge) { e.Label = l }
}

    方向规则：在 DAG 中，边 A → B 表示 A 是 B 的前驱（predecessor），B 是 A 的后继（successor）。调度器在计算就绪队列时，只有当一个节点的所有前驱边都已满足（即前驱节点执行完成），该节点才能被调度。

以下 SVG 展示了有向边的方向语义及其在 DAG 中的位置：

4.3 权重（Weight）的调度语义

边的权重通常表示从源节点到目标节点的传输代价或通信延迟。在异构计算环境中，权重直接影响调度决策：

通信开销模型：当两个任务被调度到不同处理器时，边权重表示数据传输时间；若在同一处理器，权重可视为 0。
关键路径计算：DAG 的关键路径（Critical Path）是权重之和最大的路径，决定了整个工作流的最短完成时间。
优先级调度：高权重的边意味着下游任务对上游数据的强依赖，调度器可能优先执行该路径上的任务。

// 权重在关键路径计算中的应用示例
func CriticalPathLength(graph *DAG, nodeID string) float64 {
    if len(graph.GetInEdges(nodeID)) == 0 {
        return 0
    }
    maxPredLen := 0.0
    for _, edge := range graph.GetInEdges(nodeID) {
        predLen := CriticalPathLength(graph, edge.From) + edge.Weight
        if predLen > maxPredLen {
            maxPredLen = predLen
        }
    }
    return maxPredLen
}

权重陷阱：不要将边权重与节点执行时间混淆。节点执行时间存储在 Task 结构体中，边权重仅表示节点间的通信或依赖代价。在调度建模时，两者应独立维护。

4.4 标签（Label）的语义分组

标签为边提供了语义分类能力，使得调度器可以根据业务逻辑对边进行分组处理：

标签值	语义	调度行为
`"data"`	数据依赖	必须等待上游数据就绪
`"control"`	控制依赖	仅需等待上游完成信号
`"resource"`	资源竞争	共享资源互斥访问
`"bypass"`	旁路连接	不影响调度顺序，仅用于信息传递

// 基于标签的调度过滤示例
func FilterEdgesByLabel(edges []*Edge, label string) []*Edge {
    var filtered []*Edge
    for _, e := range edges {
        if e.Label == label {
            filtered = append(filtered, e)
        }
    }
    return filtered
}

// 使用场景：只考虑数据依赖边进行就绪判断
dataEdges := FilterEdgesByLabel(task.InEdges, "data")
if len(dataEdges) == 0 {
    // 所有数据依赖已满足，任务就绪
    readyQueue.Push(task)
}

以下 SVG 展示了带权重和标签的边在 DAG 中的完整表示：

4.5 边操作的最佳实践

    边验证规则：在向 DAG 添加边之前，应执行以下检查：
    源节点和目标节点必须已存在于 DAG 中。
不能添加自环边（From == To）。
不能添加重复边（同一对 From-To 只能有一条边）。
添加边后不能形成环（需进行拓扑检测）。

// 安全的边添加方法
func (dag *DAG) AddEdge(edge *Edge) error {
    if edge.From == edge.To {
        return fmt.Errorf("self-loop edge not allowed: %s", edge.ID)
    }
    if !dag.HasNode(edge.From) || !dag.HasNode(edge.To) {
        return fmt.Errorf("node not found for edge %s", edge.ID)
    }
    if dag.HasEdge(edge.From, edge.To) {
        return fmt.Errorf("duplicate edge: %s → %s", edge.From, edge.To)
    }
    // 临时添加边并检测环
    dag.edges = append(dag.edges, edge)
    if dag.detectCycle() {
        dag.removeEdge(edge.ID)
        return fmt.Errorf("adding edge %s would create a cycle", edge.ID)
    }
    return nil
}

通过合理设计 Edge 结构体及其权重、标签属性，调度系统能够精确表达任务间的依赖关系，并为高级调度策略（如数据局部性感知、关键路径优先、标签路由）提供基础数据支持。