Cytoscape.js breadthfirst 布局完全指南：基于 BFS 的层次化树图布局算法与参数详解

数据可视化【免费下载链接】cytoscape.jsGraph theory (network) library for visualisation and analysis项目地址https://gitcode.com/gh_mirrors/cy/cytoscape.js点击查看免费下载导读breadthfirst是 Cytoscape.js 内置的八种布局之一见 src/extensions/layout/index.mjs它基于图的广度优先遍历BFS将节点排布成清晰的层次结构。本文围绕 documentation/md/layouts/breadthfirst.md 的核心描述结合 src/extensions/layout/breadthfirst.mjs 的完整实现源码与 index.d.ts 的类型声明系统讲解其适用场景、全部配置项、默认值及底层算法原理。读完你不仅能直接上手配置出树状/环形层次图还能理解其根节点选取、同层排序、方向旋转等内部机制为复杂图数据的可视化布局调优打下基础。一、什么是 breadthfirst 布局官方文档对breadthfirst布局的定义只有一句话但信息量很大Thebreadthfirstlayout puts nodes in a hierarchy, based on a breadthfirst traversal of the graph.即breadthfirst布局基于图的广度优先遍历把节点放进一个层级hierarchy结构中。这是它与circle圆形排布、grid网格排布、cose力导向物理仿真等其他内置布局最本质的区别——它天然产出一个有明确深度depth概念的树状结果。1.1 适用场景文档进一步指明了它的两个最佳使用场景默认向下downward方向下最适合树tree和森林forest当图本身就是一棵树或由多棵树组成的森林时BFS 遍历的深度天然对应树的层数绘制结果直观且边长度均匀圆环模式circle modecircle: true下最适合有向无环图DAGDAG 中一个节点可能拥有多个父级垂直堆叠会难以消歧而同心圆式排布能更好地展现其层次归属。反过来理解如果图是稠密的无向图、包含大量环或长回边breadthfirst 布局的效果就会大打折扣——此时应优先考虑力导向类布局如cose。1.2 与内置布局生态的关系从 src/extensions/layout/index.mjs 可以看到Cytoscape.js 共内置了 8 种布局breadthfirst与circle、concentric、cose、grid、null、preset、random并列注册。其中concentric虽然也按层级半径排布但其分层的依据是节点的某个数值属性concentric()回调而非图的遍历深度breadthfirst的分层依据则是纯粹的结构性 BFS 深度二者定位不同。二、基本用法两行代码跑起来布局通过cy.layout(options)或eles.layout(options)调用且必须显式设置options.name为breadthfirst。以下是一个最小可用的完整示例节点与边的数据格式参考 documentation/demos/images-breadthfirst-layout/code.js 中的图结构一个 8 节点 7 边的食物链森林const cy cytoscape({ container: document.getElementById(cy), elements: { nodes: [ { data: { id: cat } }, { data: { id: bird } }, { data: { id: ladybug } }, { data: { id: aphid } }, { data: { id: rose } }, { data: { id: grasshopper } }, { data: { id: plant } }, { data: { id: wheat } } ], edges: [ { data: { source: cat, target: bird } }, { data: { source: bird, target: ladybug } }, { data: { source: bird, target: grasshopper } }, { data: { source: grasshopper, target: plant } }, { data: { source: grasshopper, target: wheat } }, { data: { source: ladybug, target: aphid } }, { data: { source: aphid, target: rose } } ] }, layout: { name: breadthfirst, directed: true, padding: 10 } });上述配置与官方 demo 一致directed: true, padding: 10。其中name: breadthfirst指定使用该布局directed: true声明图是方向向下的树布局会优先处理边方向padding: 10让 fit 缩放时留出 10px 内边距。如果你只想对图的一部分子图做布局可以改用集合方法例如对每个连通分量分别布局cy.elements().components().forEach(comp { comp.layout({ name: breadthfirst, directed: true }).run(); });关于cy.layout()与eles.layout()的区别可参考 documentation/md/layout/intro.mdcy.layout()作用于全图eles.layout()只作用于指定子集无论元素是否可见只要在布局集合内就会被重新定位。三、完整配置项与默认值一览源码 src/extensions/layout/breadthfirst.mjs 的defaults对象定义了所有可用选项及默认值index.d.ts中的BreadthFirstLayoutOptionsindex.d.ts继承自ShapedLayoutOptionsindex.d.ts、BaseLayoutOptionsindex.d.ts与AnimatedLayoutOptionsindex.d.ts类型声明与源码完全对应。完整参数表如下选项类型默认值说明namestring—必须设为breadthfirstfitbooleantrue布局完成后是否将视口缩放到恰好容纳整张图directedbooleanfalse是否为有向树边全部指向下方为false时边可指向任意方向directionstringdownward树结构的绘制方向downward|upward|rightward|leftwardpaddingnumber30fit时的内边距像素circlebooleanfalsetrue时按同心圆放置各深度层false时自上而下堆叠gridbooleanfalse是否把 DAG 平铺进均匀网格仅在circle: false时生效spacingFactornumber1.75节点间距的倍增系数越大间距越大若造成重叠则该值失效boundingBoxobjectundefined约束布局边界形如{ x1, y1, x2, y2 }或{ x1, y1, w, h }avoidOverlapbooleantrue防止节点重叠空间不足时可能溢出boundingBoxnodeDimensionsIncludeLabelsbooleanfalse计算节点包围盒时是否包含标签尺寸rootsstring/array/collectionundefined树的根节点详见下文根节点选取depthSortfunctionundefined同深度节点的排序函数例如(a, b) a.data(weight) - b.data(weight)animatebooleanfalse是否以动画过渡节点位置animationDurationnumber500动画时长毫秒animationEasingstringundefined动画缓动函数animateFilterfunction() true决定某个节点是否参与动画返回false的节点在布局开始时立即就位readyfunctionundefinedlayoutready事件回调stopfunctionundefinedlayoutstop事件回调transformfunction(node, position) position对每个节点的最终位置做变换常用于离散布局中调整流向3.1 已废弃选项Deprecated Options源码中另有一组deprecatedOptionDefaultssrc/extensions/layout/breadthfirst.mjs选项类型默认值说明maximalbooleanfalse是否把节点向下移动到其自然 BFS 深度之下以避免出现向上的边仅适用于 DAGacyclicbooleanfalse图是否为无环的设为true会同时把maximal置为true需要特别注意acyclic与maximal的组合陷阱源码在第 49 行将二者合并为maximal options.acyclic || options.maximal || options.maximalAdjustments 0。当directed maximal时算法会反复把节点下移adjustMaximally见第 163-189 行。若在含环图上开启maximal检测到同一节点需要第二次移动时didShift null布局会直接中止并打印警告Detected double maximal shift for node.... Bailing maximal adjustment due to cycle. Useoptions.maximal: trueonly on DAGs.源码见 src/extensions/layout/breadthfirst.mjs。因此源码注释明确建议如果不确定图是否无环请将acyclic保持为false以避免潜在死循环。类型声明中的maximalAdjustments兼容旧代码的最大调整次数同样属于废弃项index.d.ts。四、参数逐项详解与实战配置4.1 directed有向树还是任意方向directed: false默认时树结构不要求边方向一致directed: true时布局会优先以父在上、子在下的思路处理有向边。它在源码中有两处直接作用影响根节点选取策略详见下文与maximal/acyclic组合触发把所有边整理为向下的深度调整算法src/extensions/layout/breadthfirst.mjs。4.2 direction四种流向与旋转原理direction支持downward、upward、rightward、leftward四个取值。源码中通过一个旋转角度表实现src/extensions/layout/breadthfirst.mjsconst rotateDegrees { downward: 0, leftward: 90, upward: 180, rightward: -90, };实现逻辑是先按默认的自上而下方式计算出每个节点位置getPositionTopBottom再调用 src/util/position.mjs 的rotatePosAndSkewByBox绕布局包围盒中心旋转对应角度——upward旋转 180°、leftward旋转 90°、rightward旋转 -90°。旋转的同时会按包围盒宽高比做反向 skew 补偿movePointByBoxAspect保证旋转后节点仍落在布局区域内。若传入非法方向值源码会抛出util.errorInvalid direction xxx specified for breadthfirst layout. Valid values are: downward, upward, rightward, leftward见 src/extensions/layout/breadthfirst.mjs4.3 circle同心圆模式DAG 首选circle: true时每个深度的节点被均匀分布在以布局中心为圆心的圆环上。源码src/extensions/layout/breadthfirst.mjs的关键计算如下半径步长radiusStepSize min(bb.w / 2 / depthsLen, bb.h / 2 / depthsLen)并取max(radiusStepSize, minDistance)防止节点重叠第depth层的半径radius radiusStepSize * depth radiusStepSize - (…半径微调)即每层半径递增一个步长该层第index个节点的角度theta 2π / depthSize * index特例若只有一层且该层仅 1 个节点半径会被压到1节点落在圆心。由于同心圆不依赖边的方向消歧因此它是文档推荐的DAG 最佳排布方式。4.4 grid均匀网格模式grid: true仅在circle: false时生效。它把所有深度层平铺进一个均匀网格横向间距按整层中最大深度层的大小maxDepthSize计算而不是按当前层大小计算src/extensions/layout/breadthfirst.mjs从而保证各层的节点纵向对齐成整齐的列。适合节点多、层数少的宽 DAG。4.5 spacingFactor 与 avoidOverlap间距与防重叠spacingFactor默认1.75源码注释明确指出它是positive spacing factor, larger more space between nodes并且若开启avoidOverlap后间距仍不足以容纳节点则以防重叠为准spacingFactor 失效avoidOverlap: true默认时布局会扫描所有节点取最大节点宽高作为最小间距下限minDistancesrc/extensions/layout/breadthfirst.mjs确保相邻节点不重叠代价是当节点过大、空间不足时可能溢出boundingBox。nodeDimensionsIncludeLabels: false默认表示计算节点包围盒时不包含标签标签较长的图可考虑置为true以避免标签重叠。4.6 boundingBox约束布局范围boundingBox支持{ x1, y1, x2, y2 }与{ x1, y1, w, h }两种形式类型见 index.d.ts。源码中通过math.makeBoundingBox归一化src/extensions/layout/breadthfirst.mjs若未指定则使用cy.extent()即当前视口范围。headless 模式无 DOM 容器下必须显式传入boundingBox否则布局无从得知可放置区域见 documentation/md/layout/intro.md。值得注意的是一旦指定了boundingBox垂直/水平间距计算会跳过首尾两侧的 paddingsrc/extensions/layout/breadthfirst.mjs以尽量用满整个约束区域。4.7 动画相关选项animate: true时节点位置将以动画方式过渡相关参数animationDuration默认500ms动画时长animationEasing缓动函数例如ease-outanimateFilter(node, i)返回true的节点参与动画返回false的节点在布局开始时立即跳到最终位置。适合对某些锚定节点关闭动画。4.8 ready / stop / transform 回调ready在layoutready事件触发时调用stop在layoutstop事件触发时调用。这两个事件由 src/collection/layout.mjs 在布局执行流程中统一触发分别对应初始就位与动画/运行结束transform(node, position)允许对每个节点最终位置做后处理例如整体偏移、镜像或按业务坐标映射常用于离散布局调整流向index.d.ts。五、底层算法原理源码级解读BreadthFirstLayout的完整实现位于 src/extensions/layout/breadthfirst.mjs其run()方法第 42-406 行可拆解为如下流水线5.1 第一步根节点选取rootsroots选项决定 BFS 从哪些节点出发取值灵活元素或集合elementOrCollection直接作为根数组按数组中的 id 用cy.getElementById(id)逐条解析字符串当作选择器cy.$(selector)解析未指定时源码第 71-88 行directed: true取nodes.roots()入度为 0 的节点作为根directed: false对每个连通分量取度数最大的节点作为根comp.maxDegree(false)degree(false)筛选保证每个分量都至少有一个起点。5.2 第二步BFS 分层调用集合的graph.bfs(...)src/extensions/layout/breadthfirst.mjs在visit回调中按 BFS 深度把每个**无子节点childless**的节点写入depths[depth]数组并用ele.scratch(breadthfirst, { depth, index })暂存深度与层内索引。注意这里显式过滤了复合图中的父节点parent因为父节点的位置通常由其子节点决定。5.3 第三步孤儿节点兜底BFS 未能访问到的节点如无根小分量被收集为orphanNodes第 132-141 行在最后被统一放到一个新插入的顶层深度depths.unshift(orphanDepth)第 306-322 行避免任何节点丢失位置。5.4 第四步同层排序depthSort 与加权位置默认情况下每层内部的节点顺序并不是随意的而是依据加权百分比getWeightedPercent第 229-276 行重排对每个节点取其上一层邻居在该层内的相对位置index / depthSize的平均值作为该节点在层内的目标位置从而让父子链在水平方向上尽量对齐、连线不打折。相同百分比时按节点 id 升序兜底保证排序稳定。若提供了depthSort函数则完全替换这套默认排序逻辑第 293-295 行例如layout: { name: breadthfirst, directed: true, depthSort: (a, b) a.data(weight) - b.data(weight) // 同层按 weight 升序 }5.5 第五步坐标计算与旋转位置计算分两套非 circle 模式按深度逐层堆叠层间距distanceY与层内间距distanceX都取基于包围盒的算术值与最小防重叠距离minDistance中的较大者第 342-348、373-379 行节点在层内水平居中排布center.x (index 1 - (depthSize 1)/2) * distanceXcircle 模式按 4.3 节描述的极坐标公式排布。最后根据direction的旋转角度对整幅结果绕包围盒中心旋转并做宽高比 skew 校正rotatePosAndSkewByBox再经由eles.nodes().layoutPositions(...)第 403 行统一落位并触发layoutready/layoutstop事件。5.6 复杂度特征从源码结构可以推断breadthfirst 布局的核心开销来自一次 BFS 遍历O(V E)与每层内部的排序各层合计 O(V log V) 量级没有迭代式物理仿真因此在数千节点规模的树上也能秒级完成明显快于cose这类力导向算法。这一特征使它非常适合需要一次成型、结构清晰的场景。六、完整实战示例配置一次到位综合以上所有参数一个覆盖树 DAG 动画 回调场景的完整配置如下const layout cy.layout({ name: breadthfirst, directed: true, // 有向树边全部向下 direction: downward, // 或 upward / rightward / leftward circle: false, // DAG 场景可改为 true 使用同心圆模式 grid: false, // 宽 DAG 可开启均匀网格 spacingFactor: 1.75, // 间距系数 avoidOverlap: true, // 防重叠 nodeDimensionsIncludeLabels: false,// 标签是否计入包围盒 padding: 30, // fit 内边距 fit: true, // 布局后自动 fit 视口 boundingBox: { x1: 0, y1: 0, w: 800, h: 600 }, // headless 必须显式指定 roots: #root-node, // 指定根id / id 数组 / 选择器 / 元素集合 depthSort: (a, b) a.data(weight) - b.data(weight), animate: true, // 开启动画 animationDuration: 500, animationEasing: ease-out, animateFilter: (node, i) node.id() ! pinned, // 锚定节点不参与动画 ready: () console.log(layoutready), stop: () console.log(layoutstop), transform: (node, position) ({ x: position.x, y: -position.y }) // 垂直镜像 }); layout.run();6.1 事件与生命周期补充除ready/stop回调外你还可以用事件系统监听布局生命周期事件机制参见 documentation/md/layout/events.mdcy.on(layoutready, e console.log(ready, e.layout)); cy.on(layoutstop, e console.log(stop, e.layout));七、调试与 FAQ节点乱序或连线交叉检查directed是否正确声明在同层使用depthSort强制按业务字段排序必要时开启grid: true让各层对齐。节点重叠调大spacingFactor确认avoidOverlap: true检查是否给boundingBox留了过小区域。布局方向不对优先用direction切换四种流向而非手动transform。控制台报 Invalid directiondirection只接受downward/upward/rightward/leftward四个枚举值。布局后有节点跑出画布fit: true 合适的padding或通过boundingBox约束范围。headless 环境下位置全在原点未指定boundingBox布局退化为按cy.extent()计算请显式传入boundingBox。DAG 布局边往回指开启circle: true文档推荐 DAG 使用同心圆模式或在确认为无环的前提下启用废弃参数acyclic: true会同时启用maximal。八、延伸阅读布局总览与cy.layout()/eles.layout()使用说明documentation/md/layout/intro.md布局运行、停止与事件documentation/md/layout/run.md、documentation/md/layout/events.md其余内置布局对比documentation/md/layouts/circle.md圆形布局、documentation/md/layouts/concentric.md同心圆布局、documentation/md/layouts/cose.md力导向复合弹簧布局布局实现源码src/extensions/layout/breadthfirst.mjs、布局注册表src/extensions/layout/index.mjs类型定义index.d.ts仓库内的官方示例食物链动画 demo documentation/demos/images-breadthfirst-layout/code.js其layout: { name: breadthfirst, directed: true, padding: 10 }配置可直接在浏览器中打开运行验证。赞分享数据可视化【免费下载链接】cytoscape.jsGraph theory (network) library for visualisation and analysis项目地址https://gitcode.com/gh_mirrors/cy/cytoscape.js点击查看免费下载相关推荐Cytoscape.js布局算法大全从网格布局到力导向布局的完整指南Cytoscape.js布局算法大全从网格布局到力导向布局的完整指南 Cytoscape.js是一个强大的JavaScript图形理论库专门用于网络可视化和数据可视化Cytoscape.js布局算法与可视化技术详解Cytoscape.js布局算法与可视化技术详解 本文全面解析了Cytoscape.js的核心布局算法体系包括层次布局、圆形布局、网格布局、力导向布局和特殊用数据可视化vizceral布局算法全攻略LTR树形、环形、DNS布局详解想要掌握网络流量可视化的核心技术吗vizceral作为WebGL动画流量图可视化工具其强大的布局算法正是其精髓所在。本文将为你深度解析vizceral的三大上一篇Windows图形性能分析的终极指南深入解析PresentMon工具链下一篇【亲测免费】 Vue-D3-Network: 使用D3.js在Vue中绘制网络图创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考