基于力导向模型的网络图自动布局算法综述

实现网络图形中节点和边自动布局一直是可视化研究中一个重要内容,基于力导向模型的自动布局算法则是该类研究中应用最广、文献最多的一类方法。根据研究方向出现的时间顺序,从基本模型、基于多维尺度分析的布局算法、多层迭代布局算法、非欧空间节点布局算法、受约束图形自动布局算法等五个方面对基于力引导模型的网络图自动布局算法的典型方法、研究进展、分支情况等进行了描述,并对发展前沿进行了讨论。     

面向线束预装配的多约束线束布局方法研究

线束由一组线束段按树状结构连接而成,是飞机汽车等产品中连接各电气设备的接线部件。为提高安装效率,复杂线束需要在线束工装板图上进行预安装,即根据角度、距离、交叉、边界等工艺约束在工装板上摆放线束,是一个多约束下的线束布局问题。通过借鉴图布局算法,将线束布局转换为优化问题,并采用随机梯度下降法SGD每次随机挑选一对线束段进行优化,逐步迭代收敛。因为线束段是长度不变的刚体,所以移动一根线束段时会带动相连的其他线束段,进而导致SGD迭代过程出现震荡,难以收敛。通过提出双向传递的线束段移动算法,在保证线束段能移动到目标位置的同时尽量少相连线束段的变动。使用合成线束案例和某真实飞机线束案例进行有效性验证,结果表明各工艺约束能均能得到满足,符合线束预装配的生产要求。     

图布局FR算法的研究与实现

近年来,对信息技术可视化的研究越来越广泛,信息技术可视化也在各个领域中得到越来越广泛的应用。图布局是用图结构解决现实世界中信息可视化问题的一种重要技术。该文介绍图布局FR算法的基本模型,研究FR算法实现方法,及FR算法的优化。     

基于工程语义约束的线束预装配自动规划方法

线束预装配是线束生产的重要环节,论文通过总结线束工艺设计中的工程 语义约束信息,建立装配关联图模型,提出了一种线束预装配自动规划方法。该方法通过主 件选择、最大子装配体提取、工程语义约束检测来实现对预装配序列自动规划,而无需与用 户进行交互。最后的实例表明该方法是有效可行的,能较好的解决大线束图纸中装配序列规 划问题。     

基于大规模社会网络的并行布局算法框架

随着社会网络的迅速发展,针对大规模社会网络的可视化已经成为数据挖掘领域中的一项重要的研究课题。传统的布局算法已经无法对大规模的社区网络进行全局管理和展示。因此,该框架基于并行化技术以及分层的思想,实现了大规模社会网络的可视化框架。其贡献主要有:提出了一种基于力导引算法的非重叠社区布局算法(简称NFR);设计了一个基于Spark的并行计算框架;将图数据库(Neo4j)无缝地整合到框架中。最后通过在真实数据集上的测试,验证了该框架的有效性。     

一种基于约束的布局求解算法

在研究现有布局求解的基础上，提出了一个基于约束的布局求解算法，该算法借助机构分析与综合中有关自由度分析的概念，在两个层次上进行布局求解，即在高层次上对层布局顺序进行规划，而在较低层次上进行具体的数值定位，通过两层次上交替进行求解最终求得布局结果。     

输电网接线图增量自动成图算法

输电线网接线图自动成图算法是一个非常复杂的全局优化问题.它涉及到厂站位置的自动布局和输电线路自动规划两个方面.本文给出了解决该问题的一种具体思路和算法,将该问题划分为3个部分:首先,利用力导向算法对厂站位置进行初始布局,采用模拟退火算法进行迭代计算,通过并发技术实现引力、斥力系数进行选择,得到代价最小的初始厂站初始布局.其次,利用A^*算法对输电线路进行线路规划,构建了一个线路走向的代价模型,通过代价模型规范线路走向,得到美观的线路布局.最后,对布局结果评价反馈再布局,将常见的几种布局缺陷通过程序的方式进行消缺,减少人工干预.同时,本文还对历史线路和新增线路做了处理,使得算法可以实现在不改变历史厂站线路布局的情况下,对新增厂站线路进行布局规划.通过实验显示,该方法得到的图形结果满足线路规划美观,布局合理,交叉少,拐角少等优点.     

基于神经网络的自动布局算法

本文提出了一种基于神经网络理论的高速印制版自动布局算法 ,它通过建立布局目标的能量函数 ,利用神经元权值自适应特性 ,从整体上自动优化布局方案 ,以满足约束条件为目标。理论分析结果表明 ,这个算法布局质量优于许多常用的算法 ,具有快捷、灵活的特点 ,适于 PCB元件布局     

复杂生物网络自动画图算法分析

介绍适应分子网络建模和信息系统需求的自动画图算法的研究成果。在分析代谢途径自动布局、力导向布局和基于网格的布局等3类具有代表性的自动画图算法的基础上,探究其各自的原理、内在联系、存在的优缺点以及亟待解决的问题,为应用网络可视化手段分析和解决具体生物问题提供参考和线索。     

基于社团划分的网络聚类布局算法

复杂网络日益受到广大专家和学者们的关注,对其进行可视化展示可以帮助用户发现复杂网络表征的复杂系统中隐藏的知识信息,对计算机科学、社会学、生物学等领域具有重要的意义。力导引布局算法是复杂网络可视化领域的主流算法,它用节点连接图的形式对复杂网络进行抽象表示,布局遵循一定的美学标准如节点的均匀分布、边长尽量一致等,这在一定程度上阻碍了对复杂网络的社团结构的展示。针对以上问题,本文提出引入基于度中心性的社团斥力与引力对力导引算法进行改进,以对复杂网络进行聚类布局。实验结果表明,本文算法可有效地展示复杂网络的社团结构,同时又能保留社团之间边缘节点的信息。     

A fast successive over-relaxation algorithm for force-directed network graph drawing

Force-directed approach is one of the most widely used methods in graph drawing research. There are two main problems with the traditional force-directed algorithms. First, there is no mature theory to ensure the convergence of iteration sequence used in the algorithm and further, it is hard to estimate the rate of convergence even if the convergence is satisfied. Second, the running time cost is increased intolerablely in drawing largescale graphs, and therefore the advantages of the force-directed approach are limited in practice. This paper is focused on these problems and presents a sufficient condition for ensuring the convergence of iterations. We then develop a practical heuristic algorithm for speeding up the iteration in force-directed approach using a successive over-relaxation (SOR) strategy. The results of computational tests on the several benchmark graph datasets used widely in graph drawing research show that our algorithm can dramatically improve the performance of force-directed approach by decreasing both the number of iterations and running time, and is 1.5 times faster than the latter on average.     

网络图自动绘制的超松弛加速算法

大规模网络的自动布局与绘制问题近年来得到了广泛的研究,其中基于力导引优化的迭代算法成为最成功的方法之一.传统力导引算法在理论与实践中存在两个困难,一是迭代序列收敛性判定及收敛速度估计在理论上尚不完备,二是针对大型网络使用迭代算法的运行时间开销巨大从而极大地限制了其实用价值.本文对这两方面难题进行了探索,首先基于非线性迭代理论给出力导引优化迭代过程收敛速度估计的一种理论方法,其次基于超松弛加速原理给出加速力导引迭代收敛过程的一种实用启发式方法.通过对基准测试数据及应用中的图实例数据进行的实验结果表明,与现有方法相比,本文的超松弛加速方法能有效降低运行时间开销,平均加速达1.5倍左右.本文最后对下一步工作进行了总结和展望.     

基于GPU的大尺度网络布局显示

复杂网络的可视化是复杂网络研究中的重要手段.随着Web2.0时代和大数据时代的来临,作为研究对象的复杂网络的规模越来越大,这对复杂网络可视化布局算法的布局效果和运算速度提出了新的挑战.本文针对复杂网络布局的力导引算法,从布局效果和算法效率两方面对该算法进行了改进和实现.布局效果方面,利用复杂网络中的关节点,对网络数据进行抽象合并,从而实现分层次的网络布局显示.算法效率方面,针对压缩后的网络采用具有强大浮点运算能力的GPU进行计算,对力导引算法需要斥力计算、引力计算和坐标更新三个部分均实现了基于GPU的并行计算,大大提高了计算效率.     

UML类图层次化自动布图算法

UML类图能够有效地帮助软件工程师理解大规模的软件系统,而优化图元的空间布局可以增强类图的可读性和可理解性.由于类图中继承关系具有明显的层次特性,因此类图自动布局大多采用层次化的布图算法.此外,类图布局需要考虑相关的领域知识以及绘制准则,因而通用嵌套有向图层次化布局算法不能直接用于类图的绘制,它们必须加以扩展.但是,已有的类图层次化方法并没有考虑类图中图元的嵌套关系,这将导致自动布局方法不能处理类图中包与类、接口之间的包含关系.在考虑图绘制美学、UML类图绘制以及软件可视化等相关知识的基础上,选取了一组布     

Algorithm of automatic generation of technology process and process relations of automotive wiring harnesses

Identifying each process and their constraint relations from the complex wiring harness drawings quickly and accurately is the basis for formulating process routes.According to the knowledge of automotive wiring harness and the characteristics of wiring harness components,we established the model of wiring harness graph.Then we research the algorithm of identifying technology processes automatically,finally we describe the relationships between processes by introducing the constraint matrix,which is in order to lay a good foundation for harness process planning and production scheduling.     

Inverse Markov Process Based Constrained Dynamic Graph Layout

In online dynamic graph drawing,constraints over nodes and node pairs help preserve a coherent mental map in a sequence of graphs.Defining the constraints is challenging due to the requirements of both preserving mental map and satisfying the visual aesthetics of a graph layout.Most existing algorithms basically depend on local changes but fail to do proper evaluations on the global propagation when setting constraints.To solve this problem,we introduce a heuristic model derived from PageRank which simulates the node movement as an inverse Markov process hence to give a global analysis of the layout's change,according to which different constraints can be set.These constraints,along with stress function,generate layouts maintaining spatial positions and shapes of relatively stable substructures between adjacent graphs.Experiments demonstrate that our method preserves both structure and position similarity to help users track graph changes visually.     

基于三维配筋的水工结构钢筋图自动标注研究

研究了钢筋图中钢筋的自动标注技术,具体探讨了标注实体的表达,标注规划表示以及标注干涉处理等问题。