一种GMF图形编辑器创建有向图的自动布局方法

摘要

本发明提出了一种GMF图形编辑器创建有向图的自动布局方法，包括如下步骤：解析GMF图形编辑器建立的有向图数据，获取图元信息；使用拓扑排序的方法对所有的组件图元进行分层处理；设置有向图中连接点的位置；设置每个组件图元位置；设置每个组件图元大小；使用Mikami-Tabuchi布线算法布置图元之间的连线的路径，当连线出现重叠时，使用近邻连线避让策略消除重叠。本发明所公开的该GMF图形编辑器创建有向图的自动布局方法与GMF图形编辑器自带的布局算法相比，具有诸多优点：组件图元之间不会发生相互重叠的现象；每层组件中的图元都被整齐排列，外观清晰；图元之间的连线不会穿过组件图元，且连线之间不会相互重叠。

说明书

技术领域

本发明涉及图形布局技术，具体涉及一种GMF图形编辑器创建有向图的自动布局方法。

背景技术

图形建模框架（Graphical Modeling Framework，简称GMF）是Eclipse平台中用于图形化编辑器开发的框架。开发者利用GMF提供的组件及其运行时环境，进行必要的图形元素建模和相关配置，便可生成图形化编辑器工程源代码。因为图形编辑器代码编写实现了高度自动化，使得图形编辑器的设计与实现变得简单而迅速。

图形布局指按照要求设置图元的大小、位置、图元之间连线的路径等信息。GMF图形编辑器图元具有嵌套组合的特点：大图元由小图元组成，小图元又由小一级的图元组成。大图元的布局策略需要处理其内部子图元的布局排放，而内部子图元又能拥有自己的布局策略。一个好的布局算法既能保证图形排版的美观，又能增强图形编辑器的易用性。

目前GMF框架中，已经由Randy Hudson等人提供了一种有向图布局算法的实现。但该算法执行过程中有一个限制条件，该有向图必须是有连接关系的图，否则每个结点计算出的水平位置相同，所有结点从上往下排成一列。而且，对于图元之间连线多，图元层次复杂等情况，该算法在布局时会导致图元布局重叠、图元之间连线穿过图元等现象的发生。

发明内容

为解决上述问题，得到图元连线简洁、图元间无重叠的图形布局，本发明提出了一种GMF图形编辑器创建有向图的自动布局方法，其具体技术方案如下：

一种GMF图形编辑器创建有向图的自动布局方法，包括如下步骤：

S10：解析GMF图形编辑器建立的有向图数据，获取图元信息，将每个组件图元拥有的有向连线起点的个数作为该图元的出度，将其拥有的有向连线的终点的个数作为该图元的入度；

S20：使用拓扑排序的方法对所有的组件图元进行分层处理；

S30：设置连接图元的位置：将同一个组件图元中，所有是有向连线起点的连接点均放置在组件图元的右侧，是有向连线终点的连接点放置在组件图元的左侧，两个连接点之间等间距放置；然后在此前提下，将与同一个组件图元相连的连接图元相邻放置；

S40：设置每个组件图元的位置：将同一层次的组件图元设置在同一个水平位置上，以图元间所有连线的曼哈顿距离最短为目标，进行目标规划，以此设置每个层次中图元的垂直位置；

S50：设置每个组件图元的大小：将每个组件图元的宽度设置为固定的值，然后根据该组件图元左右两侧拥有的连接图元的个数来设置组件图元的长度；

S60：使用Mikami-Tabuchi布线算法布置图元之间的连线的路径，当连线出现重叠时，使用近邻连线避让策略消除重叠。

进一步的，步骤S20中对组件图元进行拓扑排序的具体包括：

S201：完成对不构成连线环路、且不孤立的图元的层次设置；将无直接前驱的图元层次数设置为固定值，其他图元的层次数为其所有直接前驱中层次数最大的加上1；

S202：对构成连接环路的图元，将环路中层次数最低的任意一个图元的层次数设置为当前的层次数加1,然后将这些图元重新加入到排序中；如果仍然存在连接环路，则重复执行该步骤；

S203：对于孤立的图元，将孤立的图元的层次数依次设置为1,2,3…n，n为正整数；当某个孤立图元的层次数达到n时，如果仍有孤立的图元，则对剩余的图元重新从1开始编号，直至结束。

进一步的，步骤S40包括：

S401：:将每个组件图元长度、宽度设置为固定相同的值，令同一个层次中的图元在本层次中根据垂直的距离均匀分布，并令其水平位置相同；

S402：使用每个图元的重心代表该图元的位置，计算所有存在连接的图元之间的曼哈顿距离，其中：如果两个连接图元之间有多条连接，则在计算两者距离时，每条连接的距离计算一次；最终得到当前布局情况下，各个图元之间的距离的总和；

S403：调整每个层次中的组件图元的垂直方向的位置，保证每个组件图元水平方向不变，垂直方向均匀分布，重新按照步骤S402计算距离值；最终将距离值最小的图形布局设置为最终布局。

进一步的，步骤S50还包括：

如果连接图元具有大小，则将连接图元大小固定，然后每个连接图元相距等同的距离，分别计算组件图元左右两边的长度，取两者中长度较大的那个作为组件图元的最终长度；

如果连接图元没有大小时，则将连接图元之间的距离设置为相同的值，分别计算组件图元左右两边的长度，取两者中长度较大的那个作为组件图元的最终长度。

进一步的，所述近邻连线避让策略包括：首先检测重叠路径两侧某距离的地方是否有布线，如果没有则随机选择一边进行布线；否则增加检测的距离，直至找到一个合适的路径为止。

本发明的技术构思是：提出一种自动布局GMF图形编辑器有向图的方法，该方法对组件图元进行分层处理，将同一个层次的组件水平整齐排列，图元之间的布线避免了穿过基本图元，且连线之间没有重叠。这个避免了GMF框架原有布局策略组件图元之间的相互重叠、连线穿过组件图元的情况。

与现有技术相比，本发明至少具有以下优点：（1）组件图元之间不会发生相互重叠的现象；（2）每层组件中的图元都被整齐排列，外观清晰；（3）图元之间的连线不会穿过组件图元，且连线之间不会相互重叠。

附图说明

图1本发明实施例有向图自动布局的方法示意图。

图2本发明实施例根据图元信息进行拓扑排序分层的流程图。

图3本发明实施例设置图元位置步骤的具体流程图。

图4本发明实施例对连线重新布置步骤的流程图。

具体实施方式

下面结合附图和实施例对本发明作进一步说明：

本实施例中，使用的GMF图形编辑器是一个汽车开放系统架构 (AUTomotive Open System Architecture，简称AUTOSAR) 图形编辑器，在该编辑器中可以创建于AUTOSAR模型。其中：对于复杂具有多个层次图元的GMF图形编辑器，组件图元指的是拥有连接点的最小图元，连接图元指的是组件图元所拥有的连接点，所有图元均是矩形图元。AUTOSAR模型的图元有Composition、Component、Port、连线。其中Composition图元是组合图元，该图元可以包括一个Composition、Component、Port、连线等图元，是整个有向图的容器，包含整个有向图；Component则是组件图元，是拥有连接点Port的图元；两个组件之间可以通过连线连接起来，其中连线的起点和终点均为Port，起点称为RPort，终点称为PPort。Composition、Component、Port图元均为矩形图元。

本实施例的主要步骤如下：

1）解析有向图数据，对组件图元进行分层设置：

S10：解析AUTOSAR图形编辑器所建立的有向图数据，获取每个Component拥有的Port的个数，并记录与该Component相关的连线，以及与该Component相连的Component等信息；将这些信息处理存放在一个类数据结构中。将每个Component中与其他的Component相连的RPort的个数记为其入度；将每个Component中与其他Component相连的PPort的个数记为其出度。

S20：使用拓扑排序的方法对所有的Component进行分层处理。

其中：对组件图元进行拓扑排序的步骤包括：

S201：对Component开始进行拓扑排序，将拓扑排序能够遍历到的Component标记分层；当遍历到一个Component时将其直接后继的入度减1，并将其后继的当前层次加1。

S202：如果有Component与其他的Component构成有向环路，将环路中当前层数最低的Component中的某个Component的入度置为0，然后使拓扑排序进行下去；重复执行步骤S202直至没有Component环路为止。

S203：对于孤立与其他组件没有相连的Component，将所有孤立的Component的层次数依次设置为1,2,3…n，n为正整数；当某个孤立Component的层次达到n时，仍有孤立的Component，则对剩余的图元重新从1开始编号，直至结束。

在该实施例中我们取层数n为5，当然n还可以是4、6、7等其它正整数。即：对于孤立与其他组件没有相连的Component，将所有孤立的Component的层次数依次设置为1,2,3,4,5；当某个孤立Component的层次达到5时，仍有孤立的Component，则对剩余的图元重新从1开始编号，直至结束。

S30：设置Port的位置：将同一个Component中，所有的是PPort均放置在Component右侧，将RPort均放置在Component左侧，两个Port之间等间距放置。然后在此前提下，将与同一个Component相连的PPort或RPort放置相邻位置，即所有与同一个组件图元Component相连的连接图元（PPort或RPort）之间是相邻放置的。

S40：设置每个Component的在Composition中的位置：将分层数相同的Component设置在同一个水平位置上；以Component间所有连线的曼哈顿距离最短为目标，进行目标规划；以此设置每个层次中Component的垂直位置。

步骤S40在设置同一层次中Component的位置时，具体步骤包括：

S401：首先将每Component长度、宽度设置为固定相同的值，令同一个层次中的Component在本层次中根据垂直的距离均匀分布，并令其水平位置相同。

S402：计算Component的重心，并以此来表示该Component的位置，计算所有存在连接的Component之间的曼哈顿距离；其中如果两个连接图元之间的有多条连接，则在计算两者距离时，每条连接的距离计算一次；最终得到当前布局情况下，各个Component之间的距离的总和。

S403：调整每个层次中的Component的垂直方向的位置，保证每个Component水平方向不变，垂直方向均匀分布，重新按照步骤S402计算距离值；最终将总距离值最小的图形布局设置为最终布局。

S50：设置每个Component的大小：将Component的宽度设置为固定的值，然后根据该Component左右两侧拥有的Port的个数来设置Component的长度；其中每个Port都是大小相同的矩形图元。

其中在设置Component的大小时，其宽度被设置为一个固定的数值；在计算其长度时，其左边至少需要的长度为所有RPort的本身长度与每个RPort之间距离的总和；其右边至少需要的长度为所有PPort本身的长度与每个PPort之间距离的总和。得到左右两边至少需要的长度后，比较两者的值，将两者中较大的数值设置为Component的长度。

S60：使用Mikami-Tabuchi布线算法布置Component之间的连线的路径；当连线出现重叠时，使用近邻连线避让策略消除重叠。

其中在使用Mikami-Tabuchi算法设置连线的路径时，将Port的宽度设置为Mikami-Tabuchi算法中网格的宽度；然后将整个Composition进行网格化，然后执行Mikami-Tabuchi算法。如果发生路径重叠现象，在执行近邻避让算法时，依次检测距离该段连线1/4网格、1/2网格、3/4个网格…等地方是否有连线，直到没有重叠为止。

以上本说明书实施例所述的内容仅仅是对发明构思的实现形式的列举，本发明的保护范围不应当被视为仅限于实施例所陈述的具体形式，本发明的保护范围也及于本领域技术人员根据本发明构思所能够想到的等同技术手段。