Cytoscape.js 双连通分量与割点分析:`eles.htbc()` / `hopcroftTarjanBiconnected()` 完整指南
Cytoscape.js 双连通分量与割点分析:eles.htbc() / hopcroftTarjanBiconnected() 完整指南
导读
本文系统讲解 Cytoscape.js 提供的 Hopcroft-Tarjan 双连通分量分析能力,覆盖 htbc()、htb()、hopcroftTarjanBiconnected()、hopcroftTarjanBiconnectedComponents() 四组等价 API 的返回值结构、子图语义与调用方式,并结合仓库源码剖析其基于 DFS 的 low 值算法实现、割点判定规则与自环、孤立节点等边界处理,帮助你在网络可视化项目中准确识别割点与双连通块,用于健壮性分析、图分割与网络拓扑洞察。
一、功能定位:找出"图在哪里断开"
在无向图论中,割点(cut vertex / articulation point) 是指移除后会使图分裂为更多连通分量的节点;双连通分量(biconnected component) 则是不含割点的最大连通子图,块内任意两条边都位于同一个简单环上(桥边和孤立点构成退化分量)。
Cytoscape.js 将 Hopcroft-Tarjan 算法封装为集合方法 eles.htbc(),可以在不引入外部图算法库的情况下,直接对当前图(或图中任意子集)计算:
- 全部双连通分量(每个分量是一个同时包含节点与边的 collection);
- 全部割点(以节点 collection 形式返回)。
该 API 是 src/collection/algorithms/index.mjs 中统一导出的图算法族成员,与 dijkstra、kargerStein、tarjanStronglyConnected 等并列,注册到所有集合(collection)原型上,因此任意节点/边集合都可以直接调用。
二、API 签名与四个等价别名
在 index.d.ts 的类型声明中,四个名称均指向同一功能,返回类型完全一致:
hopcroftTarjanBiconnected(): { cut: NodeCollection; components: CollectionReturnValue };
hopcroftTarjanBiconnectedComponents(): { cut: NodeCollection; components: CollectionReturnValue };
htb(): { cut: NodeCollection; components: CollectionReturnValue };
htbc(): { cut: NodeCollection; components: CollectionReturnValue };
对应别名在 hopcroft-tarjan-biconnected.mjs 源码末尾统一导出:
export default {
hopcroftTarjanBiconnected,
htbc: hopcroftTarjanBiconnected,
htb: hopcroftTarjanBiconnected,
hopcroftTarjanBiconnectedComponents: hopcroftTarjanBiconnected
};
四个名称共用同一个实现函数,你可以在不同场景按可读性或缩写习惯任选其一。
三、返回值详解
依据 hopcroftTarjanBiconnected.md,该函数返回如下形式的对象:
{
cut, /* Collection of nodes identified as cut vertices */
components /* An array of collections corresponding to each biconnected component */
}
| 字段 | 类型 | 含义 |
|---|---|---|
cut |
节点集合(eles.spawn(cutVertices),见 源码第 103-108 行) |
被识别为割点的所有节点 |
components |
集合数组 | 每个双连通分量对应一个 collection,同时包含该分量内的节点与边 |
需要特别指出的是:components 中的每个分量不仅是节点列表,而是同时混入节点与边的完整集合(由源码 component.merge(edge) 与 component.merge(node) 构建,见 源码第 21-36 行)。因此你可以直接对分量调用 select()、addClass() 等集合方法做可视化高亮。
四、子图语义:只在调用集合内计算
原文档特别强调了一个关键语义:
Note that this function identifies biconnected components and cut vertices only within the subset of the graph in the calling collection.
也就是说,算法运行在调用该方法的集合所代表的子图上,而不是整张图。这一点在源码中有三处显式体现:
- 每个节点参与计算时,其关联边先与调用集合求交集(第 47-49 行):
let edges = eles.getElementById(currentNode) .connectedEdges() .intersection(eles); - 构建分量时,节点及其关联边同样与调用集合求交集(第 22-28 行);
- 顶层循环仅遍历调用集合内的节点(第 91-101 行)。
这意味着你可以只对感兴趣的局部子图(例如某个复合节点的子节点集合、或某个社区)调用 htbc(),割点判定与分量划分将完全局限于该子集的连通结构内,非常便于聚焦分析。
五、基本用法示例
原文档给出的最小可运行示例为:
var ht = cy.elements().htbc();
ht.components[0].select();
在此基础上可以扩展出更实用的用法——例如在 ready 回调中分析全图,并对割点与各分量施加不同样式:
var cy = cytoscape({
container: document.getElementById('cy'),
elements: [ /* 节点与边数据 */ ],
style: [
{ selector: 'node', style: { 'background-color': '#ccc' } },
{ selector: 'node.cut', style: { 'background-color': '#e33', 'border-width': 2 } },
{ selector: 'edge', style: { 'width': 2 } }
],
ready: function () {
var ht = this.elements().htbc();
// 高亮割点
ht.cut.addClass('cut');
// 依次遍历每个双连通分量
ht.components.forEach(function (comp, i) {
console.log('Component #' + i, comp.map(function (ele) {
return ele.id();
}));
});
}
});
cut 是标准 collection,可以继续链式调用 select()、addClass()、json() 等全部集合 API;components 中的每个元素同样如此。
六、源码级原理剖析
该实现位于 src/collection/algorithms/hopcroft-tarjan-biconnected.mjs,是一个基于深度优先搜索(DFS)的经典 Hopcroft-Tarjan 线性时间算法,核心机制如下。
6.1 DFS 编号与 low 值
每个节点记录三个状态(第 42-46 行):
nodes[currentNode] = {
id : id, // DFS 访问顺序编号
low : id++, // 子树中通过回边能到达的最小编号
cutVertex : false
};
biconnectedSearch(root, currentNode, parent) 从根出发递归搜索:
- 树边:访问未遍历的邻居
otherNodeId后,用子节点的 low 值更新父节点(第 75-76 行):nodes[currentNode].low = Math.min(nodes[currentNode].low, nodes[otherNodeId].low); - 回边:访问已编号的邻居时,用其 DFS 编号更新 low 值(第 83-84 行):
nodes[currentNode].low = Math.min(nodes[currentNode].low, nodes[otherNodeId].id);
每条被遍历的边在首次遇到时压入边栈 stack(第 64-71 行),并由 visitedEdges 去重,确保无向图中的每条边只处理一次。
6.2 割点判定规则
- 非根节点:当子节点
otherNodeId满足nodes<a href="https://link.gitcode.com/i/27d9436d8274409710ce8071e37654f5" target="_blank">currentNode].id <= nodes[otherNodeId].low时([第 78-81 行),说明该子树无法通过回边绕回当前节点上方,当前节点即为割点,并立即用边栈构建一个双连通分量:if (nodes[currentNode].id <= nodes[otherNodeId].low) { nodes[currentNode].cutVertex = true; buildComponent(currentNode, otherNodeId); } - 根节点:根节点的割点性由子树数量决定。算法统计根出发的 DFS 子树边数
edgeCount,若edgeCount > 1则根是割点(第 95-98 行):edgeCount = 0; biconnectedSearch(nodeId, nodeId); nodes[nodeId].cutVertex = (edgeCount > 1);
6.3 分量构建与边界情况
buildComponent(x, y) 从边栈顶部一直弹出到边 (x, y) 为止,形成该双连通块的所有边,再将边的端点节点与节点自身的关联边合并进分量(第 10-38 行)。实现中还覆盖了三个经典边界情况:
- 孤立节点:没有任何关联边(
edges.size() === 0)的节点被作为单元素分量直接加入components(第 51-52 行); - 自环边:当节点是割点时,只把该节点的自环边合并进分量,避免跨分量污染(第 30-34 行);
- 非连通图:顶层
eles.forEach会为每个未访问的节点启动新一轮 DFS,因此调用集合本身不必是连通的,所有连通块都会被完整分析。
七、测试用例验证
仓库在 test/collection-hopcroft-tarjan-biconnected.mjs 中为该功能提供了两组关键断言,可直接运行测试复现:
- 单分量无割点(第 102-115 行):
cy0与cy2各返回components.length === 1且cut为空数组。其中cy2包含自环边(2-5、2-8),验证自环不会导致误判割点; - 多分量多割点(第 117-129 行):
cy1返回 8 个双连通分量,割点为1-2、1-7、1-8、1-10四个节点;components[0]是孤立节点1-0的单元素分量,恰好印证了上文所述的孤立节点处理逻辑。
测试数据表明,每个分量 collection 中节点与边按算法遍历顺序混排(例如 components[1] 为 [ "1-21", "1-2", "1-4", "1-24", "1-3", "1-20" ]),因此按索引消费 components 时不宜假设特定顺序,更稳妥的做法是按元素 group() 或 isNode()/isEdge() 分别过滤。
八、与相关算法的区分
使用时应将本方法与另一割集类算法区分开:
eles.htbc()(本方法):无向图上的双连通分量 + 割点,cut是节点集合,适用于检测"移除哪些节点会破坏连通性";eles.tarjanStronglyConnected():有向图上的强连通分量,cut是边集合(见 tarjanStronglyConnected.md),适用于有向依赖分析;eles.kargerStein():随机化最小割算法,返回最小割边集合与划分,适用于全局最小割估算。
三者同属于 src/collection/algorithms 目录下的图算法族,可根据图的类型与目标(节点脆弱性 / 环路依赖 / 最小割)选择对应入口。
九、典型应用场景
- 网络健壮性分析:定位通信网、社交网中的关键节点(割点),评估单点故障影响范围;
- 图结构分解:将复杂图按双连通块拆分,便于分块渲染、局部样式或按块进行布局计算;
- 环路可视化:双连通分量内的边必然位于环上,可据此高亮环状结构,辅助环路识别与展示;
- 交互辅助:对用户圈选(
cy.$(':selected'))或复合节点的子集合调用htbc(),实现子图级的结构洞察。