A tabu search based approach for graph layout

This paper describes an automated tabu search based method for drawing general graph layouts with straight lines. To our knowledge, this is the first time tabu methods have been applied to graph drawing. We formulated the task as a multi-criteria optimization problem with a number of metrics which are used in a weighted fitness function to measure the aesthetic quality of the graph layout. The main goal of this work is to speed up the graph layout process without sacrificing layout quality. To achieve this, we use a tabu search based method that goes through a predefined number of iterations to minimize the value of the fitness function. Tabu search always chooses the best solution in the neighbourhood. This may lead to cycling, so a tabu list is used to store moves that are not permitted, meaning that the algorithm does not choose previous solutions for a set period of time. We evaluate the method according to the time spent to draw a graph and the quality of the drawn graphs. We give experimental results applied on random graphs and we provide statistical evidence that our method outperforms a fast search-based drawing method (hill climbing) in execution time while it produces comparably good graph layouts. We also demonstrate the method on real world graph datasets to show that we can reproduce similar results in a real world setting.     

Algorithms for multi-level graph planarity testing and layout

In this paper we consider the problems of testing a multi-level graph for planarity and laying out or, drawing, a multi-level graph in a clear way. We introduce a new abstraction of a common integer linear programming formulation of the problems that we call a vertex-exchange graph. We demonstrate how this concept can be used to solve the problems by providing clear and simple algorithms for testing a multi-level graph for planarity and laying out a multi-level graph when planar.     

一种基于有向图的工作流测试方法

已有工作流测试方法在测试完备性和充分性方面存在不足。针对此问题文章对有向图工作流模型进行扩展,提出了一种新的工作流测试方法,设计并实现了其算法。该方法能够自动生成完备且充分的测试路径和测试用例。实例验证该方法有效。     

A graph grammars based framework for querying graph-like data

The widespread use of graph-based models for representing data collections (e.g. object-oriented data, XML data, etc.) has stimulated the database research community to investigate the problem of defining declarative languages for querying graph-like databases. In this paper, a new framework for querying graph-like data based on graph grammars is proposed. The new paradigm allows us to verify structural properties of graphs and to extract sub-graphs. More specifically, a new form of query (namely graph query) is proposed, consisting in a particular graph grammar which defines a class of graphs to be matched on the graph representing the database. Thus, differently from path queries, the answer of a graph query is not just a set of nodes, but a subgraph, extracted from the input graph, which satisfies the structural properties defined by the graph grammar. Expressiveness and complexity of different forms of graph queries are discussed, and some practical applications are shown.     

A dynamic stochastic model for automatic grammar‐based test generation

Grammar‐based test generation provides a systematic approach to producing test cases from a given context‐free grammar. Unfortunately, naive grammar‐based test generation is problematic because of the fact that exhaustive random test case production is often explosive, and grammar‐based test generation with explicit annotation controls often causes unbalanced testing coverage. In this paper, we present an automatic grammar‐based test generation approach, which takes a symbolic grammar as input, requires zero control input from users, and produces well‐distributed test cases. Our approach utilizes a novel dynamic stochastic model where each variable is associated with a tuple of probability distributions, which are dynamically adjusted along the derivation. We further present a coverage tree illustrating the distribution of generated test cases and their detailed derivations. More importantly, the coverage tree supports various implicit derivation control mechanisms. We implemented this approach in a Java‐based system, named Gena. Each test case generated by Gena automatically comes with a set of structural features, which can play an important and effective role on automated failure causes localization. Experimental results demonstrate the effectiveness of our approach, the well‐balanced distribution of generated test cases over grammatical structures, and a case study on grammar‐based failure causes localization. Copyright © 2014 John Wiley & Sons, Ltd.     

Graph grammar‐driven parallel partial differential equation solver

The paper presents an extension of the composite programmable graph grammar (CP‐graph grammar) suitable for modeling the parallel direct solver algorithm utilized by the hp finite element method (hp‐FEM). In the proposed graph grammar model, the computational mesh is represented by a CP‐graph. The presented graph grammar models the solver algorithm by a set of graph grammar productions. The graph grammar model makes it possible to examine the concurrency of the algorithm by analyzing the interdependence between the atomic tasks, tasks and super‐tasks. The atomic tasks correspond to the graph grammar productions, representing basic undividable parts of the algorithms. The level of atomic tasks models the concurrency for the shared memory architectures. On the other hand, the tasks correspond to the groups of atomic tasks with predefined inter‐task communication channels. They constitute the grain for the decomposition of the parallel algorithm for the distributed memory architecture. Finally, the super‐tasks correspond to a group of tasks resulting from the execution of load balancing algorithm. The solver algorithm is tested on distributed memory linux cluster for up to 192 processors. Copyright © 2009 John Wiley & Sons, Ltd.     

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.     

基于主干子图的混合布局算法

基于主干子图理论,提出了一种能够对幂率特征图进行布局的混合布局算法,其基本思想就是将待布局的原始图分解为主干子图和若干桩树,采用不同的布局算法对其进行分别布局。实验结果表明,当图的规模小于一定常数时,算法性能要优于传统的K-K算法,且在布局效果上,能使用户较容易地区分出图中的主干子图和各桩树。     

Categorical approach to the construction of fuzzy graph grammars

The categorical approach is proposed to the formalization of fuzzy graph grammars obtained as a result of generalization of sequential graph grammars. This approach takes into consideration the basic types of fuzziness that arise in constructing categories of fuzzy objects and describing transformations of fuzzy graphs generated by fuzzy sets. All the problems of undecidability that are well known for Chomsky grammars are proved to hold true for fuzzy graph grammars. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 130–144, July–August 2006.     

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

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

基于结构图的ETL过程建模方法

ETL是数据仓库获得高质量数据的重要环节,在数据仓库建设过程中占有极其重要的地位。为了便于ETL过程的设计、维护和修改,提出一种基于结构图的ETL过程建模方法,并依据该方法完成了ETL概念模型的设计。通过图形化ETL过程中的元素和关联,该模型清晰直观地反映了数据的来源和流向、源数据与目标数据之间的映射和转换关系,辅助设计人员更好地进行ETL过程的设计和ETL过程的编码实现,使整个ETL设计过程更加方便、灵活。     

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 dynamic multi-objective approach for the reconfigurable multi-facility layout problem

The multi-facility layout problem involves the physical organization of departments inside several facilities, to allow flexible and efficient operations. This work studies the facility layout problem in a new perspective, considering a group of facilities, and two different concerns: the location of departments within a group of facilities, and the location of departments inside each facility itself. The problem is formulated as a Quadratic Programming Problem with multiple objectives and unequal areas, allowing layout reconfigurations in each planning period. The objectives of the model are: the minimization of costs (material handling inside facilities and between facilities, and re-layout); the maximization of adjacency between departments; and the minimization of the “unsuitability” of department positions and locations. This unsuitability measure is a new objective proposed in this work, to combine the characteristics of existing locations with the requirements of departments. The model was tested with data from the literature as well as with a problem inspired in a first tier supplier in the automotive industry. Preliminary results show that this work can be viewed as an innovative and promising integrated approach for tackling real, complex facility layout problems.     

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.     

A microcomputer-based pallet layout system to evaluate and improve storage space utilization

This paper discusses a microcomputer-based system used to maximize the storage space utilization for palletized materials. Pallet and carton sizes and stacking constraints for specific stock numbers are used to compute and select the best layout from several possible alternatives. The results, giving the simplest stable layout, are converted to graphic form and printed on a dot-matrix printer for use by Engineers and Warehouse personnel in evaluating and improving storage space utilization.     

Computing with graphs and graph transformations

Many software applications require the construction and manipulation of graphs. In standard programming languages, this is accomplished using low‐level mechanisms such as pointer manipulation or array indexing. In contrast, graph productions are a convenient high‐level visual notation for coding graph modifications. A graph production replaces one subgraph by another subgraph. Graph productions can define a graph grammar and graph language, or can directly transform an input graph into an output graph. Graph transformation has been applied in many areas, including the definition of visual languages and their tools, the construction of software development environments, the definition of constraint programming algorithms, the modeling of distributed systems, and the construction of neural networks. One application is presented in detail: the interpretation of mathematical notation in scanned document images. The graph models the set of mathematical symbols, and their spatial and logical relationships. This graph is transformed by productions written in the PROGRES language. Copyright © 1999 John Wiley & Sons, Ltd.     

一种基于图结构分解的图近似查询方法研究

图近似查询能够得到与查询图近似的结果集,相比较精确查询具有更广泛的应用范围。为提高近似查询的查准率和查全率,提出一种基于图结构分解的查询算法。该算法通过对查询图和目标图进行图结构分解,对其建立图分解索引,利用查询图的最小生成树集得到满足阈值的生成树集,通过图标准编码在索引中快速定位,查找出所有可能的近似结果。实验结果表明,该算法能有效得到近似结果,提高查询速度。     

基于攻击图的网络安全度量研究综述

网络安全度量面临的主要挑战之一,即如何准确地识别目标网络系统中入侵者利用脆弱性之间的依赖关系进行威胁传播,量化对网络系统的潜在影响。攻击图由于具备优越的可视化展示能力,是解决该问题的有效途径之一。首先,介绍了安全度量的概念、发展历程和通用测度模型;然后,阐述攻击图构建、分类和应用的相关研究;其次,提出一种基于攻击图的层次化安全度量框架,从关键“点”、攻击“线”和态势“面”3个层次总结归纳了现有网络安全度量方法;最后,阐述了目前研究面临的难点问题与发展趋势。