(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202211148605.6 (22)申请日 2022.09.21 (71)申请人 浪潮软件科技有限公司 地址 250100 山东省济南市高新区浪潮路 1036号浪潮科技园 (72)发明人 夏华　贾俊龙　崔盛雅　王宁　 (74)专利代理 机构 济南信达专利事务所有限公 司 37100 专利代理师 潘悦梅 (51)Int.Cl. G06F 16/36(2019.01) G06F 16/34(2019.01) G06N 5/02(2006.01) (54)发明名称 基于树的图谱环形布局方法及系统 (57)摘要 本发明公开了基于树的图谱环形布局方法 及系统， 属于计算机数据可视化分析技术领域， 要解决的技术问题为如何提出一种快速美观的 图谱布局方式。 包括如下步骤： 基于图谱中的节 点构建图谱布局树， 所述图谱布局树以图谱中度 数最高的节 点作为根节点、 以与所述根节点关联 的节点作为子节点； 计算图谱布局树的布局坐 标： 层次遍历所述图谱布局树， 以根节点为中心， 根据图谱在所述图谱布局树的层数， 计算所述图 谱布局树的极坐标以作为节点的布局坐标， 将与 根节点关联的节点环形分层分布在所述根节点 的周围， 将与所述根节点不关联的节 点环形分布 在图谱布局树的外围； 将所述图谱布局树的极坐 标转换为 直角坐标。 权利要求书4页 说明书9页 附图2页 CN 115525767 A 2022.12.27 CN 115525767 A 1.一种基于树的图谱环形布局方法， 其特 征在于， 包括如下步骤： 基于图谱中的节点构建图谱布局树， 所述图谱布局树以图谱中度 数最高的节点作为根 节点、 以与所述 根节点关联的节点作为子节点； 计算图谱布局树的布局坐标： 层次遍历所述图谱布局树， 以根节点为中心， 根据图谱在 所述图谱布局 树的层数， 计算所述图谱布局 树的极坐标以作为节点的布局 坐标， 将与根节 点关联的节点环形分层分布在所述根节点的周围， 将与所述根节点不关联的节点环形分布 在图谱布局树的外围； 将所述图谱布局树的极坐标转换为 直角坐标。 2.根据权利要求1所述的基于树的图谱环形布局方法， 其特征在于， 基于图谱中的节点 构建图谱布局树， 包括如下步骤： 统计图谱中所有节点的度数； 将度数最高的节点作为图谱布局树的根节点； 将根节点关联的节点作为 根节点子节点； 对于度数大于1的根节点子节点， 将其关联节点作为所述根节点子节点的子节点， 直至 所有可达节点全部加入所述图谱布局树中， 同时记录不可达节点用于最后布局； 其中， 所述可达节点 为能够与所述 根节点子节点相关联的节点。 3.根据权利要求2所述的基于树的图谱环形布局方法， 其特征在于， 计算图谱布局树的 布局坐标， 包括如下步骤： 确定每个非叶子节点树布局的扇形角度： 递归计算图谱布局树中每个非叶子节点树的 高度及每个非 叶子节点树中叶子节点个数， 对于每个非 叶子节点树， 基于所述非 叶子节点 树的高度以及叶子节点 树个数确定所述非叶子节点 树布局的扇形角度； 层次遍历图谱布局树， 对每一层进行叶子节点布局和非叶子节点布局： 根据图谱布局 树的层数， 分层环绕根节点布局， 通过图谱布局参数指 定每层之间的间距， 并将叶子节点和 非叶子节点分层布局， 并根据非 叶子节点树布局的扇形角度， 将非 叶子节点树的节点限制 在其所属扇形中。 4.根据权利要求3所述的基于树的图谱环形布局方法， 其特征在于， 计算图谱布局树的 布局坐标， 包括如下步骤： 步骤一、 递归计算图谱布局树中每个非叶子节点树的高度Hi以及每个非叶子节点树中 叶子节点个数Ni， 对于每个非叶子节点树， 计算每层叶子节点的平均 值Pi， 每层 叶子节点的平均值Pi表示对应非叶子节点子树需要的布局空间， 每个非叶子节点子树所需 的扇形角度计算公式如下： 其中， P为同一层子树Pi的和； 步骤二、 层次遍历布局树， 对每一层分为叶子节点布局 和非叶子节点布局； 其中， 叶子节点布局为： 叶子节点均匀分布在一段圆弧上， 圆弧的角度范围为： 权　利　要　求　书 1/4 页 2 CN 115525767 A 2其中， S为圆弧起始角度， E为圆弧结束角度； θi为父节点的角坐标， 为第i个非叶子 子树布局扇形角度； 圆弧的半径即叶子节点的极经坐标为： R＝Ri+L 其中， Ri为父节点的极经， L 为图谱布局参数， 表示层与层的间距； 计算圆弧能容纳的节点个数： 其中D为节点的直径； 叶子节点的角坐标为： 其中， N为叶子节点个数， j为圆弧上的第j个节点， 当n<N即圆弧无法容纳 所有叶子节点 时， 多出的节点将圆弧半径增 加L， 在新的一层继续布局； 其中， 非叶子节点在叶子节点外层圆弧上布局， 对应极经坐标为最外层叶子节点极经 加上层与层的间距L； 角坐标为： 其中， S为节点父节点布局扇形起始角度， 为第i个非叶子子树布局扇形角度， i为圆 弧上的第i个节点； 步骤三、 基于步骤二， 通过层次遍历布局树， 以根节点为中心、 树中节点呈现环形布局 的方式计算极坐标， 对于不可达节点， 在可达节点布局的最外层按所述叶子节点布局方式 布局， 不可达节点对应圆弧角度范围为[0， 2 π ]。 5.根据权利要求1 ‑4任一项所述的基于树的图谱环形布局方法， 其特征在于， 将所述图 谱布局树的极坐标转换为 直角坐标， 所述 直角坐标的计算公式为： x＝r cosα y＝r sinα 其中r是极经坐标， α 是角坐标。 6.一种基于树的图谱环形布局系统， 其特征在于， 用于执行如权利要求1 ‑5任一项所述 的基于树的图谱环形布局方法实现图谱布局， 所述系统包括： 树构建模块， 所述树构建模块用于基于 图谱中的节点构建图谱布局树， 所述图谱布局 树以图谱中度数最高的节点作为 根节点、 以与所述 根节点关联的节点作为子节点； 极坐标计算模块， 所述极坐标计算模块用于计算图谱布局树的布局坐标： 层次遍历所 述图谱布局树， 以根节点为中心， 根据图谱在所述图谱布局树的层数， 计算所述图谱布局树权　利　要　求　书 2/4 页 3 CN 115525767 A 3