 复合图公共祖先查询详解)
Cytoscape.js 集合 API 实战commonAncestors() 复合图公共祖先查询详解【免费下载链接】cytoscape.jsGraph theory (network) library for visualisation and analysis项目地址: https://gitcode.com/gh_mirrors/cy/cytoscape.jseles.commonAncestors()是 Cytoscape.js 面向复合图compound graph提供的集合遍历方法用于一次性求出一个节点集合中所有元素共同拥有的祖先节点。本篇以官方文档 commonAncestors.md 为主线结合 compounds.mjs 源码实现与 collection-compound-nodes.mjs 测试用例讲清它的排序语义、底层算法、性能特征与实战用法读完即可在分层网络、组织架构、基因通路等复合图场景中直接落地。一、方法定位复合图专属的集合运算在深入commonAncestors()之前需要先明确它的适用范围。Cytoscape.js 支持普通图、有向图、无向图、多重图以及复合图——复合节点就像 HTML DOM 元素包含子元素一样可以包含若干子节点。复合节点的层级关系通过节点data字段中的parent指定详见 notation.md 的 Compound nodes 一节与 data.md 中关于parent字段的说明parent: Theparentfield defines the parent (compound) node.const cy cytoscape({ elements: { nodes: [ { data: { id: n1 } }, { data: { id: n2, parent: n1 } }, { data: { id: n3, parent: n2 } }, { data: { id: n4, parent: n2 } } ] } });这段代码与 collection-compound-nodes.mjs 测试夹具中的图结构完全一致n1是根节点orphann2是n1的子节点n3、n4是n2的子节点形成两层嵌套的树形层级。官方在 compoundNodes.md 中明确说明parent()、parents()、children()、descendants()、siblings()、commonAncestors()、orphans()、nonorphans()这一族函数专门作用于复合图commonAncestors()正是这一族函数中负责求交集祖先的一员。二、核心语义由近到远的公共祖先序列commonAncestors()的返回值是一个集合collection其中包含调用集合中所有元素的公共祖先即在每个元素的祖先链中都出现的节点。官方文档 commonAncestors.md 给出了两个关键结论公共祖先按亲疏程度降序排列descending order of closeness即越靠近调用集合的祖先排得越靠前因此最近的公共祖先closest / lowest common ancestor可以通过nodes.commonAncestors().first()取得最远的公共祖先farthest可以通过nodes.commonAncestors().last()取得。这正对应图论与生物信息学中经典的 lowest common ancestorLCA最低公共祖先概念——它也是层次聚类、系统发育树、路由表合并等算法的基础原语。基本用法const cy cytoscape({ /* 复合图元素配置见上文 */ }); const n3 cy.$(#n3); const n4 cy.$(#n4); // 求 n3 与 n4 的公共祖先 const ancestors n3.add(n4).commonAncestors(); // 最近的公共祖先LCA const lca n3.add(n4).commonAncestors().first(); // 最远的公共祖先 const farthest n3.add(n4).commonAncestors().last();以上面的四节点图为例n3的祖先链是[n2, n1]n4的祖先链同样是[n2, n1]二者交集为[n2, n1]。由于n2比n1更接近调用集合集合内部顺序为n2在前、n1在后因此ancestors.length等于 2ancestors[0]即.first()是n2——最近的公共祖先ancestors[1]即.last()是n1——最远的公共祖先。这与测试 collection-compound-nodes.mjs 中的断言完全一致it(nodes.commonAncestors(), function(){ var ancestors n3.add(n4).commonAncestors(); expect( ancestors.length ).to.equal( 2 ); expect( ancestors[0].same( n2 ) ).to.be.true; expect( ancestors[1].same( n1 ) ).to.be.true; });支持的参数选择器过滤与parent()、parents()等复合图遍历方法一致commonAncestors()接受一个可选的选择器selector字符串参数只返回满足该选择器的公共祖先// 只取公共祖先中的复合父节点 const parentAncestors n3.add(n4).commonAncestors(:parent); // 只取具有指定 class 的公共祖先 const filtered n3.add(n4).commonAncestors(.group-a);当集合内元素没有任何公共祖先时例如两个分属不同根树的孤儿节点返回空集合.first()与.last()返回undefined调用前可用.empty()或.length做防御判断。三、源码剖析集合求交驱动的祖先链合并commonAncestors()的实现位于 compounds.mjs逻辑非常清晰核心是一个逐个元素求祖先链交集的过程commonAncestors: function( selector ){ let ancestors; for( let i 0; i this.length; i ){ let ele this[ i ]; let parents ele.parents(); ancestors ancestors || parents; ancestors ancestors.intersect( parents ); // current list must be common with current ele parents set } return ancestors.filter( selector ); },逐行解读其算法初始化ancestors初始为undefined首个元素的祖先链parents直接作为初始交集逐元素求交对调用集合中的每个元素调用ele.parents()拿到其全部祖先再与当前累计的ancestors做intersect()即当前累积结果必须是当前元素祖先集的子集——这正是公共祖先的定义选择器过滤最后统一.filter(selector)若未传选择器则不过滤。关键依赖一parents() 与祖先链的生成顺序ele.parents()定义在同文件的 compounds.mjs它先取元素的直接父节点然后循环上溯把每一层祖先收集进数组。注意它从近到远地收集祖先——先 push 直接父节点再 push 祖父节点依此类推parents: function( selector ){ let parents []; let eles this.parent(); while( eles.nonempty() ){ for( let i 0; i eles.length; i ){ let ele eles[ i ]; parents.push( ele ); } eles eles.parent(); } return this.spawn( parents, true ).filter( selector ); },同时 compounds.mjs 将ancestors注册为parents的别名elesfn.ancestors elesfn.parents;也就是说ele.ancestors()与ele.parents()等价。而parent()直接父节点在 compounds.mjs 中直接读取元素私有字段_private.parent对单元素调用还做了快速路径优化。正是因为parents()的收集顺序是从近到远commonAncestors()在逐元素求交时保留了这一顺序最终返回的公共祖先集合天然呈现由近到远的降序才有了first()取最近、last()取最远的文档结论。这是理解整个 API 的关键一环排序语义不是事后排序而是由底层parents()的遍历顺序自然继承而来。关键依赖二intersect() 的求交实现commonAncestors()依赖的intersect()定义在 filter.mjs。其实现会优先遍历较短的集合col1Smaller判断利用colL.has(ele)做 O(1) 成员判断将交集元素按短集合的顺序压入结果intersect: function( other ){ // if a selector is specified, then filter by it instead if( is.string( other ) ){ let selector other; return this.filter( selector ); } let elements this.spawn(); let col1 this; let col2 other; let col1Smaller this.length other.length; let colS col1Smaller ? col1 : col2; let colL col1Smaller ? col2 : col1; for( let i 0; i colS.length; i ){ let ele colS[i]; if( colL.has(ele) ){ elements.push(ele); } } return elements; },可以推断由于ancestors累积结果随着求交不断缩短通常它就是较短集合交集结果按它的顺序输出——也就是保留首个元素祖先链的由近到远顺序进而保证commonAncestors()结果的稳定有序。此外intersect()支持传入字符串选择器commonAncestors(selector)的过滤语义在实现上拥有两条等价路径。四、运行语义与边界情况4.1 单元素调用当调用集合只有一个元素时commonAncestors()退化为求该元素自身全部祖先即等价于ele.parents()n3.commonAncestors().same(n3.parents()); // true4.2 无公共祖先若集合中某个元素是孤儿节点无parent它的parents()为空集与任何集合求交都得到空集。此时返回空集合n1.add(n3).commonAncestors(); // empty collectionn1 为根无祖先4.3 父节点顺序的稳定性因为公共祖先来源于每个元素的parents()近到远且intersect()保留累积结果顺序所以对于树形层级完全一致的兄弟节点结果顺序是确定的测试断言ancestors[0]为n2、ancestors[1]为n1即为证明对于层级结构复杂的图同一深度的多个公共祖先的相对顺序按首个元素的祖先链顺序呈现。五、性能特征与最佳实践5.1 时间复杂度从源码结构看commonAncestors()对集合中的每个元素都要调用一次parents()全链上溯再做一次集合求交。若调用集合大小为m、图的最大深度为h则总代价约为O(m·h)的遍历加上逐次求交开销。相比逐个手写parents()再手工求交该方法把循环、求交、过滤全部封装代码更简洁且不易出错。5.2 与相关遍历 API 的配合commonAncestors()属于复合图遍历 API 家族与下列方法在 compounds.mjs 中同源实现可组合使用parent()直接父节点单层parents()/ancestors()全部祖先链自近而远children()/descendants()向下遍历其中children()带有基于 cache-traversal-call.mjs 的遍历缓存siblings()兄弟节点orphans()/nonorphans()无父/有父节点筛选forEachUp()高效的向上遍历内部辅助函数供内部批量操作使用。典型组合求某子图内所有节点对的最近公共祖先可先按层分桶再逐桶求交做面包屑导航或向上高亮时可用n.commonAncestors().first()快速定位归属层级。5.3 使用建议优先调用现成 API不要用parents()手工叠加intersect()commonAncestors()已封装完整语义且返回值顺序有文档保证注意空集合对可能存在孤立子树的结果先判空再取first()/last()选择器过滤放在参数中commonAncestors(selector)与commonAncestors().filter(selector)语义等价前者在单次调用内完成更简洁复合图成本意识如 performance.md 所述复合节点会显著增加样式计算与渲染开销若图不需要层级结构可通过避免使用parent字段换取更高性能。对高频调用的遍历结果可结合集合缓存手动缓存 LCA 结果。六、小结commonAncestors()是 Cytoscape.js 复合图能力中一个短小精悍的集合级 API它用一次调用完成多元素祖先链求交并通过底层parents()的自近而远遍历顺序天然保证返回集合亲密度降序从而让.first()与.last()分别直取最近、最远公共祖先。理解其实现compounds.mjs 的逐元素求交 filter.mjs 的短集合优先求交不仅能正确使用它也能在需要自定义祖先聚合逻辑时复用同样的收集-求交-过滤模式。【免费下载链接】cytoscape.jsGraph theory (network) library for visualisation and analysis项目地址: https://gitcode.com/gh_mirrors/cy/cytoscape.js创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
Cytoscape.js 集合 API 实战commonAncestors() 复合图公共祖先查询详解【免费下载链接】cytoscape.jsGraph theory (network) library for visualisation and analysis项目地址: https://gitcode.com/gh_mirrors/cy/cytoscape.jseles.commonAncestors()是 Cytoscape.js 面向复合图compound graph提供的集合遍历方法用于一次性求出一个节点集合中所有元素共同拥有的祖先节点。本篇以官方文档 commonAncestors.md 为主线结合 compounds.mjs 源码实现与 collection-compound-nodes.mjs 测试用例讲清它的排序语义、底层算法、性能特征与实战用法读完即可在分层网络、组织架构、基因通路等复合图场景中直接落地。一、方法定位复合图专属的集合运算在深入commonAncestors()之前需要先明确它的适用范围。Cytoscape.js 支持普通图、有向图、无向图、多重图以及复合图——复合节点就像 HTML DOM 元素包含子元素一样可以包含若干子节点。复合节点的层级关系通过节点data字段中的parent指定详见 notation.md 的 Compound nodes 一节与 data.md 中关于parent字段的说明parent: Theparentfield defines the parent (compound) node.const cy cytoscape({ elements: { nodes: [ { data: { id: n1 } }, { data: { id: n2, parent: n1 } }, { data: { id: n3, parent: n2 } }, { data: { id: n4, parent: n2 } } ] } });这段代码与 collection-compound-nodes.mjs 测试夹具中的图结构完全一致n1是根节点orphann2是n1的子节点n3、n4是n2的子节点形成两层嵌套的树形层级。官方在 compoundNodes.md 中明确说明parent()、parents()、children()、descendants()、siblings()、commonAncestors()、orphans()、nonorphans()这一族函数专门作用于复合图commonAncestors()正是这一族函数中负责求交集祖先的一员。二、核心语义由近到远的公共祖先序列commonAncestors()的返回值是一个集合collection其中包含调用集合中所有元素的公共祖先即在每个元素的祖先链中都出现的节点。官方文档 commonAncestors.md 给出了两个关键结论公共祖先按亲疏程度降序排列descending order of closeness即越靠近调用集合的祖先排得越靠前因此最近的公共祖先closest / lowest common ancestor可以通过nodes.commonAncestors().first()取得最远的公共祖先farthest可以通过nodes.commonAncestors().last()取得。这正对应图论与生物信息学中经典的 lowest common ancestorLCA最低公共祖先概念——它也是层次聚类、系统发育树、路由表合并等算法的基础原语。基本用法const cy cytoscape({ /* 复合图元素配置见上文 */ }); const n3 cy.$(#n3); const n4 cy.$(#n4); // 求 n3 与 n4 的公共祖先 const ancestors n3.add(n4).commonAncestors(); // 最近的公共祖先LCA const lca n3.add(n4).commonAncestors().first(); // 最远的公共祖先 const farthest n3.add(n4).commonAncestors().last();以上面的四节点图为例n3的祖先链是[n2, n1]n4的祖先链同样是[n2, n1]二者交集为[n2, n1]。由于n2比n1更接近调用集合集合内部顺序为n2在前、n1在后因此ancestors.length等于 2ancestors[0]即.first()是n2——最近的公共祖先ancestors[1]即.last()是n1——最远的公共祖先。这与测试 collection-compound-nodes.mjs 中的断言完全一致it(nodes.commonAncestors(), function(){ var ancestors n3.add(n4).commonAncestors(); expect( ancestors.length ).to.equal( 2 ); expect( ancestors[0].same( n2 ) ).to.be.true; expect( ancestors[1].same( n1 ) ).to.be.true; });支持的参数选择器过滤与parent()、parents()等复合图遍历方法一致commonAncestors()接受一个可选的选择器selector字符串参数只返回满足该选择器的公共祖先// 只取公共祖先中的复合父节点 const parentAncestors n3.add(n4).commonAncestors(:parent); // 只取具有指定 class 的公共祖先 const filtered n3.add(n4).commonAncestors(.group-a);当集合内元素没有任何公共祖先时例如两个分属不同根树的孤儿节点返回空集合.first()与.last()返回undefined调用前可用.empty()或.length做防御判断。三、源码剖析集合求交驱动的祖先链合并commonAncestors()的实现位于 compounds.mjs逻辑非常清晰核心是一个逐个元素求祖先链交集的过程commonAncestors: function( selector ){ let ancestors; for( let i 0; i this.length; i ){ let ele this[ i ]; let parents ele.parents(); ancestors ancestors || parents; ancestors ancestors.intersect( parents ); // current list must be common with current ele parents set } return ancestors.filter( selector ); },逐行解读其算法初始化ancestors初始为undefined首个元素的祖先链parents直接作为初始交集逐元素求交对调用集合中的每个元素调用ele.parents()拿到其全部祖先再与当前累计的ancestors做intersect()即当前累积结果必须是当前元素祖先集的子集——这正是公共祖先的定义选择器过滤最后统一.filter(selector)若未传选择器则不过滤。关键依赖一parents() 与祖先链的生成顺序ele.parents()定义在同文件的 compounds.mjs它先取元素的直接父节点然后循环上溯把每一层祖先收集进数组。注意它从近到远地收集祖先——先 push 直接父节点再 push 祖父节点依此类推parents: function( selector ){ let parents []; let eles this.parent(); while( eles.nonempty() ){ for( let i 0; i eles.length; i ){ let ele eles[ i ]; parents.push( ele ); } eles eles.parent(); } return this.spawn( parents, true ).filter( selector ); },同时 compounds.mjs 将ancestors注册为parents的别名elesfn.ancestors elesfn.parents;也就是说ele.ancestors()与ele.parents()等价。而parent()直接父节点在 compounds.mjs 中直接读取元素私有字段_private.parent对单元素调用还做了快速路径优化。正是因为parents()的收集顺序是从近到远commonAncestors()在逐元素求交时保留了这一顺序最终返回的公共祖先集合天然呈现由近到远的降序才有了first()取最近、last()取最远的文档结论。这是理解整个 API 的关键一环排序语义不是事后排序而是由底层parents()的遍历顺序自然继承而来。关键依赖二intersect() 的求交实现commonAncestors()依赖的intersect()定义在 filter.mjs。其实现会优先遍历较短的集合col1Smaller判断利用colL.has(ele)做 O(1) 成员判断将交集元素按短集合的顺序压入结果intersect: function( other ){ // if a selector is specified, then filter by it instead if( is.string( other ) ){ let selector other; return this.filter( selector ); } let elements this.spawn(); let col1 this; let col2 other; let col1Smaller this.length other.length; let colS col1Smaller ? col1 : col2; let colL col1Smaller ? col2 : col1; for( let i 0; i colS.length; i ){ let ele colS[i]; if( colL.has(ele) ){ elements.push(ele); } } return elements; },可以推断由于ancestors累积结果随着求交不断缩短通常它就是较短集合交集结果按它的顺序输出——也就是保留首个元素祖先链的由近到远顺序进而保证commonAncestors()结果的稳定有序。此外intersect()支持传入字符串选择器commonAncestors(selector)的过滤语义在实现上拥有两条等价路径。四、运行语义与边界情况4.1 单元素调用当调用集合只有一个元素时commonAncestors()退化为求该元素自身全部祖先即等价于ele.parents()n3.commonAncestors().same(n3.parents()); // true4.2 无公共祖先若集合中某个元素是孤儿节点无parent它的parents()为空集与任何集合求交都得到空集。此时返回空集合n1.add(n3).commonAncestors(); // empty collectionn1 为根无祖先4.3 父节点顺序的稳定性因为公共祖先来源于每个元素的parents()近到远且intersect()保留累积结果顺序所以对于树形层级完全一致的兄弟节点结果顺序是确定的测试断言ancestors[0]为n2、ancestors[1]为n1即为证明对于层级结构复杂的图同一深度的多个公共祖先的相对顺序按首个元素的祖先链顺序呈现。五、性能特征与最佳实践5.1 时间复杂度从源码结构看commonAncestors()对集合中的每个元素都要调用一次parents()全链上溯再做一次集合求交。若调用集合大小为m、图的最大深度为h则总代价约为O(m·h)的遍历加上逐次求交开销。相比逐个手写parents()再手工求交该方法把循环、求交、过滤全部封装代码更简洁且不易出错。5.2 与相关遍历 API 的配合commonAncestors()属于复合图遍历 API 家族与下列方法在 compounds.mjs 中同源实现可组合使用parent()直接父节点单层parents()/ancestors()全部祖先链自近而远children()/descendants()向下遍历其中children()带有基于 cache-traversal-call.mjs 的遍历缓存siblings()兄弟节点orphans()/nonorphans()无父/有父节点筛选forEachUp()高效的向上遍历内部辅助函数供内部批量操作使用。典型组合求某子图内所有节点对的最近公共祖先可先按层分桶再逐桶求交做面包屑导航或向上高亮时可用n.commonAncestors().first()快速定位归属层级。5.3 使用建议优先调用现成 API不要用parents()手工叠加intersect()commonAncestors()已封装完整语义且返回值顺序有文档保证注意空集合对可能存在孤立子树的结果先判空再取first()/last()选择器过滤放在参数中commonAncestors(selector)与commonAncestors().filter(selector)语义等价前者在单次调用内完成更简洁复合图成本意识如 performance.md 所述复合节点会显著增加样式计算与渲染开销若图不需要层级结构可通过避免使用parent字段换取更高性能。对高频调用的遍历结果可结合集合缓存手动缓存 LCA 结果。六、小结commonAncestors()是 Cytoscape.js 复合图能力中一个短小精悍的集合级 API它用一次调用完成多元素祖先链求交并通过底层parents()的自近而远遍历顺序天然保证返回集合亲密度降序从而让.first()与.last()分别直取最近、最远公共祖先。理解其实现compounds.mjs 的逐元素求交 filter.mjs 的短集合优先求交不仅能正确使用它也能在需要自定义祖先聚合逻辑时复用同样的收集-求交-过滤模式。【免费下载链接】cytoscape.jsGraph theory (network) library for visualisation and analysis项目地址: https://gitcode.com/gh_mirrors/cy/cytoscape.js创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
