三类算法的统一框架
连通分量、SSSP、三角计数都写成顶点程序:每超步收消息、更新自身、决定是否继续活跃。区别只在消息内容与收敛条件。
连通分量与最短路径
连通分量每超步把「当前最小 id」传给邻居,收敛到分量内最小 id:{0,1,2} 收敛到 0,顶点 1 并入分量 0;孤链 {3,4} 分量 id 3(用例 50-51)。
SSSP 沿边传「当前最短距离」:路径图距离 3(Bellman-Ford 超步,用例 43),源点距离 0(用例 44);多跳路径 0→1→2→4 距离 3,不可达顶点保持 -1(用例 52-53)。
三角计数
三角计数不靠消息收敛,靠统计邻接交集:顶点 0 位于三角形 (0,1,2) 中,全图仅 1 个三角形(用例 54-55)。它是 motif 计数的原型,超步里比对邻居集合。
验证
从卷十一实验包 解包,用 algo 用例 50、51 验证连通分量收敛到最小 id(0 与孤链 3);用例 43、44、52、53 验证 SSSP 距离 3、源点 0、不可达 -1;用例 54、55 验证顶点 0 在 1 个三角形、全图仅 1 个三角形。
一手资料
继续阅读
探索更多技术文章
浏览归档,发现更多关于系统设计、工具链和工程实践的内容。