R igraph：求解DAG河网中指定边测站层级排名的算法

算法思路 #

你当前的河网DAG场景适配拓扑排序+层级动态传递的计算逻辑，你之前尝试的DFS从下游出口反向遍历的方式，无法区分多支流汇流场景下的上游测站关联关系，而基于上游到下游的拓扑排序遍历，可以完美适配DAG的层级传递逻辑，不需要额外处理路径关联问题。
核心计算规则可灵活匹配你的需求：

• 最上游无任何测站的测站等级为1
• 下游测站等级可按两种规则计算：
  1. 取上游所有测站的最大等级+1（河网分级常用的最长路径规则）
  2. 上游存在N个独立测站则等级为N+1（完全匹配你描述的计数规则）

R代码实现 #

预处理（你的原始测试数据） #

library(igraph)

vertices_df <- data.frame(
  id = c(418,410,402,394,386,427,378,370,362,354,346,338,330,322,314,306,298,290,282,274,595,266,419,395,258,250,242,234,226,218,210,202,194,186,178,170,162,146,138,130,122,114,106,98,90,82,74,66,58,50,42,34,26,18,10,2,587,579,571,563,555,547,539,531,523,515,28,12,154,507,499,491,483,475,467,459,451,443,435,411,403,387,379,371,363,355,347,339,331,323,315,307,299,291,283,275,267,259,251,243,235,227,219,211,203,195,187,179,171,163,155,147,139,131,123,115,107,99,91,83,75,67,59,51,43,35,27,19,11,3,20,4),
  station = c(1,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0)
)

edges_df <- data.frame(
  from = c(410,402,394,378,427,403,370,362,354,346,338,330,322,314,306,298,290,282,274,595,587,395,107,3,250,218,226,26,58,66,146,34,18,98,106,74,130,507,571,563,443,547,539,531,523,515,28,20,499,491,483,475,467,459,451,435,411,355,387,379,347,371,331,307,195,291,115,147,171,43,99,123,227,259,27,2,234,10,386,419,194,202,186,122,170,162,258,178,266,242,114,210,154,11,75,90,42,82,50,138,579,67,323,555,179,211,243,219,267,12,4,35,315,363,19,299,51,187,91,155,275,163,339,203,283,131,139,59,83,235,251),
  to = c(418,410,402,394,386,427,378,370,362,354,346,338,330,322,314,306,298,290,282,274,595,266,419,395,258,250,242,234,226,218,210,202,194,186,178,170,162,587,579,571,563,555,547,539,531,523,515,28,507,499,491,483,475,467,459,451,443,435,411,403,387,379,371,363,355,347,339,331,323,315,307,299,291,283,275,418,410,402,394,386,370,362,354,346,338,330,322,314,306,298,282,274,595,419,395,250,234,226,218,210,587,579,571,563,555,547,539,531,523,515,28,507,491,483,467,459,451,443,435,411,403,387,379,355,347,331,323,307,299,291,283)
)

net <- graph.data.frame(
  edges_df[, c("from", "to")],
  directed=TRUE,
  vertices=vertices_df
)

核心分级计算 #

# 1. 获取上游到下游顺序的拓扑排序结果
topo_order <- V(net)$name[topological.sort(net, mode = "out")]

# 2. 初始化等级向量
station_rank <- rep(0, vcount(net))
names(station_rank) <- V(net)$name
station_nodes <- V(net)$name[V(net)$station == 1]

# 3. 遍历拓扑序列计算等级
for (v in topo_order) {
  upstream_nodes <- neighbors(net, v, mode = "in")$name
  upstream_max_rank <- max(station_rank[upstream_nodes], na.rm = T)
  if (v %in% station_nodes) {
    # 规则1：最长路径分级（上游最大等级+1，河网常用规则）
    station_rank[v] <- ifelse(upstream_max_rank == 0, 1, upstream_max_rank + 1)
    
    # 如需使用计数规则（上游有N个测站则等级为N+1），替换上面一行代码为：
    # upstream_station_cnt <- sum(station_rank[upstream_nodes] > 0, na.rm = T)
    # station_rank[v] <- upstream_station_cnt + 1
  } else {
    # 非测站节点直接传递上游等级
    station_rank[v] <- ifelse(upstream_max_rank == -Inf, 0, upstream_max_rank)
  }
}

# 4. 输出测站分级结果
result <- data.frame(
  station_id = station_nodes,
  rank = station_rank[station_nodes]
)
print(result)

内容的提问来源于stack exchange，提问作者Marc