一个任意图的输出和编辑系统

本文给出了一个对任意图的输出算法，这个算法同其它的同类算法相比，具有更小的时间复杂性，并且由于此算法的参数是可控制的，所以对图的输出也是可控制的．另外，本文描述了一个图的显示和编辑系统ＧＬＥＡＭ，这个系统是基于所给出的新算法的，并且在本系统中使用了约束技术，使图的输出更美观、合理．ＧＬＥＡＭ是一个通用且可以扩充的系统，用户只要加入相应的具体领域知识，就可把其变为一个专用的系统.     

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

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

一种用于Marching-Graph图形绘制的快速收敛布局算法

Marching-Graph是一种将图形隐喻技术和空间隐喻技术集成为一体的新的可视化方法.它为用户提供了高度可交互性地图,使用户可访问那些具有地理属性的信息的逻辑结构.它通过有效的人图交互和跨空间浏览为用户提供了一种可视分析和挖掘未知信息的机制,而不是将已知的信息呈现在地图上.然而,传统的力导向布局算法在达到力量均衡配置方面非常慢.为使一个图形布局收敛,它们通常需花费几十秒的时间.因此。当用户快速行进于地理区间时,那些力导向布局算法就不能满足快速绘制一系列图形的要求.提出了一种快速收敛布局方法,当用户在Marching-Graph中通过力导向布局逐步探究一系列图形时,它可以加速交互时间.通过结合辐射树绘图技术和力导向图形绘制方法来取得能量最小化的快速收敛.     

The Grasper-CL graph management system

Grasper-CL is a system for manipulating and displaying graphs, and for building graph-based user interfaces for application programs. It is implemented in COMMON LISP and CLIM, and has been proven by use in a number of applications. Grasper-CL includes several advances in graph drawing. It contains a graph abstract datatype plus a comprehensive and novel language of operations on that datatype. The appearance of Grasper-CL graphs can be tailored by a wide variety of shape parameters that allow the application to customize the display of nodes and edges for different domains. Default values for shape parameters can be established at several levels. Grasper-CL employs a toolbox approach to graph layout: the system contains a suite of graph layout algorithms that can be applied individually, or in combination to produce hierarchical graph layouts. The system also contains an interactive graph browser.     

一种软构件依赖关系的拓扑布局算法

本文提出了一种圆环型的有向图拓扑布局算法,能够清晰地展示软构件之间的相互依赖关系,有助于设计人员更好地理解和分析多构件系统中构件间依赖关系的整体态势,进而优化系统结构,提高系统性能,实现高效的软构件组装。     

A layout algorithm for undirected compound graphs

We present an algorithm for the layout of undirected compound graphs, relaxing restrictions of previously known algorithms in regards to topology and geometry. The algorithm is based on the traditional force-directed layout scheme with extensions to handle multi-level nesting, edges between nodes of arbitrary nesting levels, varying node sizes, and other possible application-specific constraints. Experimental results show that the execution time and quality of the produced drawings with respect to commonly accepted layout criteria are quite satisfactory. The algorithm has also been successfully implemented as part of a pathway integration and analysis toolkit named PATIKA, for drawing complicated biological pathways with compartmental constraints and arbitrary nesting relations to represent molecular complexes and various types of pathway abstractions.     

Attributed graph mining in the presence of automorphism

Attributed directed graphs are directed graphs in which nodes are associated with sets of attributes. Many data from the real world can be naturally represented by this type of structure, but few algorithms are able to directly handle these complex graphs. Mining attributed graphs is a difficult task because it requires combining the exploration of the graph structure with the identification of frequent itemsets. In addition, due to the combinatorics on itemsets, subgraph isomorphisms (which have a significant impact on performances) are much more numerous than in labeled graphs. In this paper, we present a new data mining method that can extract frequent patterns from one or more directed attributed graphs. We show how to reduce the combinatorial explosion induced by subgraph isomorphisms thanks to an appropriate processing of automorphic patterns.     

Drawing complete binary trees inside rectilinear polygons

Most of graph drawing algorithms draw graphs on unbounded planes. However, there are applications that require graphs to be drawn on the plane inside a given polygon. In this paper, a new algorithm for planar orthogonal drawing of complete binary trees inside rectilinear polygons is presented. Uniform distribution of nodes of graphs on drawing regions is one of the aesthetics criteria in graph drawing. The goal of this paper is to produce planar orthogonal drawings with a relatively uniform node distribution and few edge bends. The proposed algorithm can be considered as a generalization of the H-tree layout method for rectilinear polygons. A new linear time algorithm is also given for bisecting rectilinear polygons into two equi-area rectilinear sub-polygons.     

An Algorithm for Straight-Line Drawing of Planar Graphs

We present a new algorithm for drawing planar graphs on the plane. It can be viewed as a generalization of the algorithm of Chrobak and Payne, which, in turn, is based on an algorithm by de Fraysseix, Pach, and Pollack. Our algorithm improves the previous ones in that it does not require a preliminary triangulation step; triangulation proves problematic in drawing graphs ``nicely,' as it has the tendency to ruin the structure of the input graph. The new algorithm retains the positive features of the previous algorithms: it embeds a biconnected graph of n vertices on a grid of size (2n-4) x (n-2) in linear time. We have implemented the algorithm as part of a software system for drawing graphs nicely. Received September 21, 1995; revised March 15, 1996.     

Graph visualization toolkits

The authors have created two toolkits that allow developers to easily integrate graph visualization capabilities into custom software applications. The Graph Layout Toolkit (GLT) provides interfaces for modeling, drawing, and automatically laying out graphs. The Graph Editing Toolkit (GET) provides a customizable display and editing layer, which facilitates rapidly developing tools that visualize data in the form of graphs. The authors present an architectural overview of these tools and discuss the challenges encountered during implementation and integration of theory and research results into such tools, In particular, they discuss automatic graph layout and labeling algorithms and complexity management techniques. In addition, they present examples of applications using these tools     

The Perception of Graph Properties in Graph Layouts

When looking at drawings of graphs, questions about graph density, community structures, local clustering and other graph properties may be of critical importance for analysis. While graph layout algorithms have focused on minimizing edge crossing, symmetry, and other such layout properties, there is not much known about how these algorithms relate to a user's ability to perceive graph properties for a given graph layout. In this study, we apply previously established methodologies for perceptual analysis to identify which graph drawing layout will help the user best perceive a particular graph property. We conduct a large scale (n = 588) crowdsourced experiment to investigate whether the perception of two graph properties (graph density and average local clustering coefficient) can be modeled using Weber's law. We study three graph layout algorithms from three representative classes (Force Directed ‐ FD, Circular, and Multi‐Dimensional Scaling ‐ MDS), and the results of this experiment establish the precision of judgment for these graph layouts and properties. Our findings demonstrate that the perception of graph density can be modeled with Weber's law. Furthermore, the perception of the average clustering coefficient can be modeled as an inverse of Weber's law, and the MDS layout showed a significantly different precision of judgment than the FD layout.     

Visual exploration of complex time-varying graphs

Quasi-trees, namely graphs with tree-like structure, appear in many application domains, including bioinformatics and computer networks. Our new SPF approach exploits the structure of these graphs with a two-level approach to drawing, where the graph is decomposed into a tree of biconnected components. The low-level biconnected components are drawn with a force-directed approach that uses a spanning tree skeleton as a starting point for the layout. The higher-level structure of the graph is a true tree with meta-nodes of variable size that contain each biconnected component. That tree is drawn with a new area-aware variant of a tree drawing algorithm that handles high-degree nodes gracefully, at the cost of allowing edge-node overlaps. SPF performs an order of magnitude faster than the best previous approaches, while producing drawings of commensurate or improved quality     

Straight-Line Drawing Algorithms for Hierarchical Graphs and Clustered Graphs

Hierarchical graphs and clustered graphs are useful non-classical graph models for structured relational information. Hierarchical graphs are graphs with layering structures; clustered graphs are graphs with recursive clustering structures. Both have applications in CASE tools, software visualization and VLSI design. Drawing algorithms for hierarchical graphs have been well investigated. However, the problem of planar straight-line representation has not been solved completely. In this paper we answer the question: does every planar hierarchical graph admit a planar straight-line hierarchical drawing? We present an algorithm that constructs such drawings in linear time. Also, we answer a basic question for clustered graphs, that is, does every planar clustered graph admit a planar straight-line drawing with clusters drawn as convex polygons? We provide a method for such drawings based on our algorithm for hierarchical graphs.     

Coherent time-varying graph drawing with multifocus+context interaction

We present a new approach for time-varying graph drawing that achieves both spatiotemporal coherence and multifocus+context visualization in a single framework. Our approach utilizes existing graph layout algorithms to produce the initial graph layout, and formulates the problem of generating coherent time-varying graph visualization with the focus+context capability as a specially tailored deformation optimization problem. We adopt the concept of the super graph to maintain spatiotemporal coherence and further balance the needs for aesthetic quality and dynamic stability when interacting with time-varying graphs through focus+context visualization. Our method is particularly useful for multifocus+context visualization of time-varying graphs where we can preserve the mental map by preventing nodes in the focus from undergoing abrupt changes in size and location in the time sequence. Experiments demonstrate that our method strikes a good balance between maintaining spatiotemporal coherence and accentuating visual foci, thus providing a more engaging viewing experience for the users.     

通用型控制系统仿真软件

该控制系统分析软件集线性微分方程数值求解、线性系统仿真、非线性系统仿真、采样系统仿真以及根轨迹绘制、波德图绘制、相轨迹绘制等功能于一体。可对各种系统进行直观的时域仿真分析和传统的图解分析。仿真精度在万分之一以上，仿真时间仅需数秒。另外，软件采用方框图可视人机对话方式，直接修改传递函数、输入量等参数就可实现对所有单变量系统的仿真，故软件使用非常方便，一看就会。本仿真软件的研制成功，克服了经典控制理论需要绘制大量图形以及对高阶系统、非线性系统和采样系统的分析误差大等缺点。可以加快自动控制技术的推广、普及，是自动控制领域的又一次重大突变。     

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.     

面向对象的动态图编辑器的设计与实现

提出了一种面向对象的动态图编辑器,该动态图编辑器区别一般图编辑器的方面在于：可以根据用户的需要在任何时候动态地执行用户程序定义的方法;产生可序列化的图;编辑部分和显示部分既能合并使用也能分开使用;允许用户定义任意形状的结点和弧;具有处理无向图和有向图的双重功能。用户可以分别利用交互式编辑环境和图布局机制输入小型图和中、大型图。动态图编辑器体系结构建立在软件工程设计模式和面向对象设计思想的基础上,用ＪＡ－ＶＡ２实现。     

用遗传算法画无向图

本文提出了一个新的画一般无向图的遗传算法.以前的无向图画图算法将顶点数较多且无弦的圈画成了凹多边形,为了克服这一缺点,本文的遗传算法设计了全新的变异算子--单点邻域变异,并在适应度函数中增加用于产生对称画法的分量,可将这种图画成凸多边形.新算法的优点是方法简单,易于实现,画出的图形美观,其灵活之处在于准则的权重可以改变.实验结果表明,在相同条件下,本文算法画出的图形要比标准遗传算法画出的图形美观.     

传输子网选择:度数有界最大支撑子图逼近

研究了源于无线网状网络的度数有界最大支撑子图问题:给定连通图G=(V,E)和正整数d≥2,求G的一个最大支撑子图H,满足对V中每个顶点v,v在H中的度数dH(v)不超过d。这里,支撑子图指图G的一个连通而且包括G中所有顶点的子图。就输入图的边是否带权,分别设计了多项式时间近似算法。当输入图为无权图时,证明了近似算法的近似比为2;当输入图为赋权图时,证明了算法输出一个最大度数不超过d+1、权重不低于最优解权重1/(d+2)的支撑子图。算法输出的度数有界支撑子图可以用作无线网状网络的传输子网。