CN114528518B - 一种基于web端的流程图自动布局方法及系统 - Google Patents

Abstract

本发明提出了一种基于web端的流程图自动布局方法及系统，包括：获得web端流程图的每个节点的坐标及相关参数，输出每个节点的Y轴对称布局后的横坐标及纵坐标；对任意流程图进行Y轴对称布局之后统计当前流程图中连线的交叉点个数，记为第一数值，进入条件循环，记录当前节点排序后，通过邻域权重启发算法对当前节点进行顺序重排，重新按照Y轴进行对称布局之后再次统计节点连线交叉点个数并将其设置为第一数值，进入下次循环；基于Y轴对称布局后的横坐标及纵坐标，在渲染层中绘制流程图。布局后各业务线之间各节点之间的逻辑关系更加清晰，便于业务开发人员理解各部门之间的业务关系，提升各部门间数据的数据共享质量。

Description

一种基于web端的流程图自动布局方法及系统

技术领域

本发明属于计算机处理技术领域，尤其涉及一种基于web端的流程图自动布局方法及系统。

背景技术

本部分的陈述仅仅是提供了与本发明相关的背景技术信息，不必然构成在先技术。

政务信息化建设总体进入了以数据赋能、协同治理、智慧决策、优质服务为主要特征的融慧治理新阶段，并对政务数据治理平台提出了新的需求，包括：集中建设统一的国家政务交换平台、按需扩展基础数据字段项、提升多元化数据采集和主题化数据汇集能力等需求。

为了满足目前的要求，政务数据治理平台需实现多数据源引入、复杂ETL(数据抽取、转换、加载)过程灵活配置、流程可视化、数据主题化等一系列数据治理流程图相关的复杂功能。因为政务业务逻辑的复杂性，用户往往会依据实际的业务属性来手工创建、组织流程图，导致创建的流程图结构复杂、混乱，无法直观明确地体现出数据流向及各业务线之间、各流程节点之间蕴含的逻辑关系。

目前混乱的流程图不利于业务理解，不利于支撑跨部门业务协同，也不利于提升各部门之间共享的数据资源质量。

发明内容

为克服上述现有技术的不足，本发明提供了一种基于web端的流程图自动布局方法，布局后各业务线之间各节点之间的逻辑关系更加清晰，便于业务开发人员理解各部门之间的业务关系，提升各部门间数据的数据共享质量。

为实现上述目的，本发明的一个或多个实施例提供了如下技术方案：

第一方面，公开了一种基于web端的流程图自动布局方法，包括：

获得web端流程图的每个节点的坐标及相关参数，输出每个节点的Y轴对称布局后的横坐标及纵坐标；

对任意流程图进行Y轴对称布局之后统计当前流程图中连线的交叉点个数，记为第一数值，进入条件循环，记录当前节点排序后，通过邻域权重启发算法对当前节点进行顺序重排，重新按照Y轴进行对称布局之后再次统计节点连线交叉点个数并将其设置为第一数值，进入下次循环；

当跳出循环时将当前节点按照记录中的排序进行Y轴对称布局，以减少流程图中连线交叉；

基于Y轴对称布局后的横坐标及纵坐标，在渲染层中绘制流程图。

进一步的技术方案，获得web端流程图的每个节点的坐标及相关参数，具体包括：

当前节点的横坐标、纵坐标、节点层级、当前节点在某层级中的索引值、节点纵向间隔、横向间隔，流程图中所有层级中节点最多层级的节点个数、当前层级的层级数。

进一步的技术方案，Y轴对称布局后每个节点的横坐标x为L*M2，纵坐标为(LL*M2–CL*M1)/2+I*M1；

当前节点的横坐标为x，纵坐标为y，节点层级为L，当前节点在某层级中的索引值为I，节点间隔为纵向M1，横向M2，流程图中所有层级中节点最多层级的节点个数为LL，当前层级的层级数为CL。

进一步的技术方案，还包括：节点层级确定步骤，具体为：

初始化各节点的数据层级后通过递归算法，从所有头节点出发沿连线遍历图中的每个节点，确定图中每个节点的数据层级。

进一步的技术方案，从所有头节点出发沿连线遍历图中的每个节点时，每访问一个节点：

将访问节点的id推入‘访问记录栈’中；

检查访问节点所有的上级节点的id是否存在于访问记录栈中，如果存在则取上级节点中最大的数据层级加一作为访问节点的数据层级，对访问节点的所有下级节点进行递归调用；如果存在访问节点的上级节点的id不存在于访问记录栈中，则退出当前递归调用；

遍历结束后计算各节点在其数据层级中的索引值从小到大依次排序。

进一步的技术方案，通过流程图中连线交叉点来统计当前流程图中连线的交叉点个数，流程图中连线交叉点判断步骤为：

通过向量叉乘的方法判断两个线段是否相交，线段由起始端点和截至端点两个对象组成，每个端点由端点的x坐标和y坐标组成。

进一步的技术方案，由A、B两点和C、D两点所组成的两线段AB和CD，构造A指向C和B指向D的两个二维向量，将这两个向量进行向量的叉乘，若结果为正数则说明AB和CD两线段相交，否则不相交。

进一步的技术方案，通过邻域权重启发算法对当前节点进行顺序重排，具体为：

根据节点的相邻节点在相邻层级中的平均次序值来重排节点；

若当前节点的数据层级为0，即当前节点为头节点，则当前节点的邻域平均次序值为第二层中与当前节点相连的节点所在第二层中索引值之和除以第二层节点的个数；

若当前节点非头节点也非尾节点，设当前节点的数据层级为L，则当前节点的邻域平均次序值为当前节点上级节点在L–1层中索引值之和加上当前节点的所有在L+1层中的下级节点的索引值之和后除以L-1层与L+1层中节点的总数；

若当前节点为尾节点，当前层级为L，即没有下级节点，当前节点的邻域平均索引值为上级节点在L-1层中的索引值之和除以L-1层中节点总数。

第二方面，公开了一种基于web端的流程图自动布局系统，包括：

节点坐标获取模块，被配置为：获得web端流程图的每个节点的坐标及相关参数，输出每个节点的Y轴对称布局后的横坐标及纵坐标；

Y轴对称式布局节点坐标计算模块，被配置为：对任意流程图进行Y轴对称布局之后统计当前流程图中连线的交叉点个数，记为第一数值，进入条件循环，记录当前节点排序后，通过邻域权重启发算法对当前节点进行顺序重排，重新按照Y轴进行对称布局之后再次统计节点连线交叉点个数并将其设置为第一数值，进入下次循环；

当跳出循环时将当前节点按照记录中的排序进行Y轴对称布局，以减少流程图中连线交叉；

绘制流程图模块，被配置为：基于Y轴对称布局后的横坐标及纵坐标，在渲染层中绘制流程图。

以上一个或多个技术方案存在以下有益效果：

本发明提出的基于web端的流程图自动布局方法，即对流程图中的节点按照其在图中的节点层级对称排列并使数据流动方向一致。尽量保持流程图结构紧凑、避免长边、减少边的交叉以保持图中节点的均衡布局。相同层级的节点处于同一列，在web画布中的x值相同；各业务线按照输入源水平排列，避免交叉。布局后各业务线之间各节点之间的逻辑关系更加清晰，便于业务开发人员理解各部门之间的业务关系，提升各部门间数据的数据共享质量。

本发明的方案在一定程度上使手工生成的流程图更具可读性，使节点之间和流程之间的逻辑关系更加清晰。此方法完善了政务数据治理平台综合运维管理体系，便于政务数据治理平台业务人员理解政务数据流传方向，提升了政务数据治理平台的运维保障能力，提高了跨部门业务协同和数据集成水平。

本发明附加方面的优点将在下面的描述中部分给出，部分将从下面的描述中变得明显，或通过本发明的实践了解到。

附图说明

构成本发明的一部分的说明书附图用来提供对本发明的进一步理解，本发明的示意性实施例及其说明用于解释本发明，并不构成对本发明的不当限定。

图1为本发明实施例自动布局前流程图；

图2为本发明实施例自动布局后流程图；

图3为本发明实施例自动布局流程示意图。

具体实施方式

应该指出，以下详细说明都是示例性的，旨在对本发明提供进一步的说明。除非另有指明，本文使用的所有技术和科学术语具有与本发明所属技术领域的普通技术人员通常理解的相同含义。

需要注意的是，这里所使用的术语仅是为了描述具体实施方式，而非意图限制根据本发明的示例性实施方式。

在不冲突的情况下，本发明中的实施例及实施例中的特征可以相互组合。

实施例一

参见附图3所示，本实施例公开了一种基于web端的流程图自动布局方法，具体包括：节点层级确定，减少交叉，画布渲染三个步骤组成。

步骤一：节点层级确定步骤：

初始化各节点的数据层级后通过递归算法，从所有头节点出发沿连线遍历图中的每个节点。

在这个过程中每访问一个节点：

将访问节点的id推入‘访问记录栈’中；

检查访问节点所有的上级节点的id是否存在于访问记录栈中。如果存在则取上级节点中最大的数据层级加一作为访问节点的数据层级，对访问节点的所有下级节点进行递归调用；如果存在访问节点的上级节点的id不存在于访问记录栈中，则退出当前递归调用。

遍历结束后计算各节点在其数据层级中的索引值从小到大依次排序。

通过上述方法可以确定图中每个节点的数据层级，为下一步骤做好准备。

步骤二：减少交叉步骤：减少交叉为本方法中的核心步骤其又可以细分为两个的步骤：

2-1.流程图中连线交叉点计算；

流程图中连线交叉点计算：通过向量叉乘的方法判断两个线段是否相交，线段由起始端点和截至端点两个对象组成，每个端点由端点的x坐标和y坐标组成。

例：若有由A、B两点和C、D两点所组成的两线段AB和CD。构造A指向C和B指向D的两个二维向量，将这两个向量进行向量的叉乘。若结果为正数则说明AB和CD两线段相交，否则不相交。

2-2.邻域权重启发式算法重新排列。

邻域权重启发算法：根据节点相邻节点(上级节点、下级节点)在相邻层级中的平均次序值(d2)来重排节点。

例1：若当前节点的数据层级为0(第一层)，即当前节点为头节点，则当前节点的邻域平均次序值(d2)为第二层中与当前节点相连的节点所在第二层中索引值之和除以第二层节点的个数。

例2：若当前节点非头节点也非尾节点，设当前节点的数据层级为L，则当前节点的邻域平均次序值为当前节点上级节点在L–1层中索引值之和加上当前节点的所有在L+1层中的下级节点的索引值之和后除以L-1层与L+1层中节点的总数。

例3：若当前节点为尾节点，当前层级为L，即没有下级节点，当前节点的邻域平均次序值为上级节点在L-1层中的索引值之和除以L-1层中节点总数。

上述次序平均值的概念类似加权平均指数(weighted average index number)，为计算在同一数据层级下表示相邻层级数据次序权重的一种形式，用来对同一数据层级中的节点进行从小到大的排序。

其基本特点是：先计算某节点的相邻层级的次序值(即各个连接的上下游节点在相邻层级中的次序值之和)，然后再对个体节点的相邻层级次序值进行加权平均以求得个体节点的次序平均值，他的目的是为了衡量当前节点的上下游节点的排序对当前节点排序的影响。

Y轴对称布局方法：设当前节点的横坐标为x，纵坐标为y，节点层级为L，当前节点在某层级中的索引值为I，节点间隔为纵向M1，横向M2(单位px,例：200像素)，流程图中所有层级中节点最多层级的节点个数为LL，当前层级的层级数为CL。则Y轴对称布局后的节点坐标：每个节点的横坐标x为L*M2，纵坐标为(LL*M2–CL*M1)/2+I*M1。

自动布局时在对任意流程图进行Y轴对称布局之后统计当前图模型中连线的交叉点个数，记为CountNumber，设o_countNumber为无穷大。进入条件循环当o_countNumber大于CountNumber时：设o_countNumber等于CountNumber，记录当前节点排序O1后，通过邻域权重启发算法对当前节点进行顺序重排，重新按照Y轴进行对称布局之后再次统计节点连线交叉点个数并将其设置为CountNumber。进入下次循环。当跳出循环时将当前节点按照O1记录中的排序进行Y轴对称布局。

o_countNumber为int类型的值，记录的是在上一次循环中，在计算平均次序值并重新排序后图中连线交叉点的数量，其初始值为无穷大，而后在邻域权重启发式算法的过程中重新赋值为重排后的连线交叉点数量。

当前节点排序O1为：当前图中所有节点在其数据层级中的排列顺序。作用是：在邻域权重启发式算法中，最佳节点排序为退出时O1所记录的上次循环的节点排序。

步骤三：画布渲染：

按照步骤二产出的节点坐标，在渲染层中绘制流程图并将流程图的重心移至画布中心。

附图1为自动布局之前的流程图，图2为自动布局之后的流程图。

实施例二

本实施例的目的是提供一种计算装置,包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，所述处理器执行所述程序时实现上述方法的步骤。

实施例三

本实施例的目的是提供一种计算机可读存储介质。

一种计算机可读存储介质，其上存储有计算机程序，该程序被处理器执行时执行上述方法的步骤。

实施例四

本实施例的目的是提供一种基于web端的流程图自动布局系统。该系统在结构上分为渲染层和数据逻辑层，渲染层基于第三方库JsPlumb实现，负责流程图渲染；数据逻辑层主要负责储存维护流程图中各节点及其连线的数据集合，及各种流程图相关的逻辑运算。

其中图的类型为有向无环图，本方法中涉及到的数据类型及概念如下：

头节点：所有入度为0的节点，即流程图中所有没有前驱节点的节点的集合。

尾节点：所有出度为0的节点，即流程图中没有下级节点的节点的集合。

连线集合：流程图中所有连线所组成的集合，其中连线是由来源节点、目标节点所描述的对象。

节点集合：流程图中所有节点所组成的集合。

节点：由id，节点类型，横坐标，纵坐标，数据层级，下级节点集合，上级节点集合及其他业务属性所描述的对象。

下级节点：流程图中某节点上所有连线所指向的节点的集合。

上级节点：于下级节点相对，流程图中所有存在连线指向某节点的节点的集合。

数据层级：某节点在图中的层级，初始值为0，某节点在图中只属于一个层级。

再次参见附图3所示，该实施例子具体公开了一种基于web端的流程图自动布局系统，包括：

节点坐标获取模块，被配置为：获得web端流程图的每个节点的坐标及相关参数，输出每个节点的Y轴对称布局后的横坐标及纵坐标；

Y轴对称式布局节点坐标计算模块，被配置为：对任意流程图进行Y轴对称布局之后统计当前流程图中连线的交叉点个数，记为第一数值，进入条件循环，记录当前节点排序后，通过邻域权重启发算法对当前节点进行顺序重排，重新按照Y轴进行对称布局之后再次统计节点连线交叉点个数并将其设置为第一数值，进入下次循环；

当跳出循环时将当前节点按照记录中的排序进行Y轴对称布局，以减少流程图中连线交叉；

绘制流程图模块，被配置为：基于Y轴对称布局后的横坐标及纵坐标，在渲染层中绘制流程图。

还包括：图中连线交叉点数计算模块：被配置为执行：流程图中连线交叉点计算：利用数学知识，通过向量叉乘的方法判断两个线段是否相交(线段由起始端点和截至端点两个对象组成，每个端点由端点的x坐标和y坐标组成)。

例：若有由A、B两点和C、D两点所组成的两线段AB和CD。构造A指向C和B指向D的两个二维向量，将这两个向量进行向量的叉乘。若结果为正数则说明AB和CD两线段相交，否则不相交。

领域权重启发式重排模块：被配置为：根据节点相邻节点(上级节点、下级节点)在相邻层级中的平均次序值(d2)来重排节点。

若当前节点的数据层级为0(第一层)，即当前节点为头节点，则当前节点的邻域平均次序值(d2)为第二层中与当前节点相连的节点所在第二层中索引值之和除以第二层节点的个数。

若当前节点非头节点也非尾节点，设当前节点的数据层级为L，则当前节点的邻域平均次序值为当前节点上级节点在L–1层中索引值之和加上当前节点的所有在L+1层中的下级节点的索引值之和后除以L-1层与L+1层中节点的总数。

若当前节点为尾节点，当前层级为L，即没有下级节点，当前节点的邻域平均索引值为上级节点在L-1层中的索引值之和除以L-1层中节点总数。

以上实施例二、三和四的装置中涉及的各步骤与方法实施例一相对应，具体实施方式可参见实施例一的相关说明部分。术语“计算机可读存储介质”应该理解为包括一个或多个指令集的单个介质或多个介质；还应当被理解为包括任何介质，所述任何介质能够存储、编码或承载用于由处理器执行的指令集并使处理器执行本发明中的任一方法。

本领域技术人员应该明白，上述本发明的各模块或各步骤可以用通用的计算机装置来实现，可选地，它们可以用计算装置可执行的程序代码来实现，从而，可以将它们存储在存储装置中由计算装置来执行，或者将它们分别制作成各个集成电路模块，或者将它们中的多个模块或步骤制作成单个集成电路模块来实现。本发明不限制于任何特定的硬件和软件的结合。

上述虽然结合附图对本发明的具体实施方式进行了描述，但并非对本发明保护范围的限制，所属领域技术人员应该明白，在本发明的技术方案的基础上，本领域技术人员不需要付出创造性劳动即可做出的各种修改或变形仍在本发明的保护范围以内。

Claims (8)

1.一种基于web端的流程图自动布局方法，其特征是，包括：

获得web端流程图的每个节点的坐标及相关参数，输出每个节点的Y轴对称布局后的横坐标及纵坐标；

从所有头节点出发沿连线遍历图中的每个节点时，每访问一个节点：

将访问节点的id推入‘访问记录栈’中；

检查访问节点所有的上级节点的id是否存在于访问记录栈中，如果存在则取上级节点中最大的数据层级加一作为访问节点的数据层级，对访问节点的所有下级节点进行递归调用；如果存在访问节点的上级节点的id不存在于访问记录栈中，则退出当前递归调用；

遍历结束后计算各节点在其数据层级中的索引值从小到大依次排序；

对任意流程图进行Y轴对称布局之后统计当前流程图中连线的交叉点个数，记为第一数值，进入条件循环，记录当前节点排序后，通过邻域权重启发算法对当前节点进行顺序重排，重新按照Y轴进行对称布局之后再次统计节点连线交叉点个数并将其设置为第一数值，进入下次循环；

通过邻域权重启发算法对当前节点进行顺序重排，具体为：

根据节点的相邻节点在相邻层级中的平均次序值来重排节点；

若当前节点的数据层级为0，即当前节点为头节点，则当前节点的邻域平均次序值为第二层中与当前节点相连的节点所在第二层中索引值之和除以第二层节点的个数；

若当前节点非头节点也非尾节点，设当前节点的数据层级为L，则当前节点的邻域平均次序值为当前节点上级节点在L–1层中索引值之和加上当前节点的所有在L+1层中的下级节点的索引值之和后除以L-1层与L+1层中节点的总数；

若当前节点为尾节点，当前层级为L，即没有下级节点，当前节点的邻域平均索引值为上级节点在L-1层中的索引值之和除以L-1层中节点总数；

当跳出循环时将当前节点按照记录中的排序进行Y轴对称布局，以减少流程图中连线交叉；

基于Y轴对称布局后的横坐标及纵坐标，在渲染层中绘制流程图。

2.如权利要求1所述的一种基于web端的流程图自动布局方法，其特征是，获得web端流程图的每个节点的坐标及相关参数，具体包括：

当前节点的横坐标、纵坐标、节点层级、当前节点在某层级中的索引值、节点纵向间隔、横向间隔，流程图中所有层级中节点最多层级的节点个数、当前层级的层级数；

Y轴对称布局后每个节点的横坐标x为，纵坐标为；

当前节点的横坐标为x，纵坐标为y，节点层级为L，当前节点在某层级中的索引值为I，节点间隔为纵向M1，横向M2，流程图中所有层级中节点最多层级的节点个数为LL，当前层级的层级数为CL。

3.如权利要求1所述的一种基于web端的流程图自动布局方法，其特征是，还包括：节点层级确定步骤，具体为：

初始化各节点的数据层级后通过递归算法，从所有头节点出发沿连线遍历图中的每个节点，确定图中每个节点的数据层级。

4.如权利要求1所述的一种基于web端的流程图自动布局方法，其特征是，通过流程图中连线交叉点来统计当前流程图中连线的交叉点个数，流程图中连线交叉点判断步骤为：

通过向量叉乘的方法判断两个线段是否相交，线段由起始端点和截至端点两个对象组成，每个端点由端点的x坐标和y坐标组成；

由A、B两点和C、D两点所组成的两线段AB和CD，构造A指向C和B指向D的两个二维向量，将这两个向量进行向量的叉乘，若结果为正数则说明AB和CD两线段相交，否则不相交。

5.采用权利要求1所述方法的一种基于web端的流程图自动布局系统，其特征是，包括：

节点坐标获取模块，被配置为：获得web端流程图的每个节点的坐标及相关参数，输出每个节点的Y轴对称布局后的横坐标及纵坐标；

Y轴对称式布局节点坐标计算模块，被配置为：对任意流程图进行Y轴对称布局之后统计当前流程图中连线的交叉点个数，记为第一数值，进入条件循环，记录当前节点排序后，通过邻域权重启发算法对当前节点进行顺序重排，重新按照Y轴进行对称布局之后再次统计节点连线交叉点个数并将其设置为第一数值，进入下次循环；

当跳出循环时将当前节点按照记录中的排序进行Y轴对称布局，以减少流程图中连线交叉；

绘制流程图模块，被配置为：基于Y轴对称布局后的横坐标及纵坐标，在渲染层中绘制流程图。

6.如权利要求5所述的一种基于web端的流程图自动布局系统，其特征是，还包括：图中连线交叉点数计算模块：被配置为执行：流程图中连线交叉点计算：利用数学知识，通过向量叉乘的方法判断两个线段是否相交，线段由起始端点和截至端点两个对象组成，每个端点由端点的x坐标和y坐标组成；

若有由A、B两点和C、D两点所组成的两线段AB和CD，构造A指向C和B指向D的两个二维向量，将这两个向量进行向量的叉乘，若结果为正数则说明AB和CD两线段相交，否则不相交；

进一步的，还包括：领域权重启发式重排模块：被配置为：根据节点相邻节点在相邻层级中的平均次序值来重排节点；

若当前节点的数据层级为0，即当前节点为头节点，则当前节点的邻域平均次序值为第二层中与当前节点相连的节点所在第二层中索引值之和除以第二层节点的个数；

若当前节点非头节点也非尾节点，设当前节点的数据层级为L，则当前节点的邻域平均次序值为当前节点上级节点在L–1层中索引值之和加上当前节点的所有在L+1层中的下级节点的索引值之和后除以L-1层与L+1层中节点的总数；

若当前节点为尾节点，当前层级为L，即没有下级节点，当前节点的邻域平均索引值为上级节点在L-1层中的索引值之和除以L-1层中节点总数。

7.一种计算装置,包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，其特征是，所述处理器执行所述程序时实现上述权利要求1-5任一所述的方法的步骤。

8.一种计算机可读存储介质，其上存储有计算机程序，其特征是，该程序被处理器执行时执行上述权利要求1-5任一所述的方法的步骤。