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.     

混合群体增量学习算法求解闭环布局问题

闭环布局问题（CLLP）是一种NP-困难的混合优化问题,它在大小可调的矩形环上寻找设施最佳放置次序,目标是最小化设施之间物料流的运输成本。现有方法均采用元启发式算法来寻找最优的设施放置次序,并且通过枚举方法来获得最优的矩形环大小,而枚举方法的计算效率不高。为了解决这个问题,提出了求解CLLP的混合群体增量学习（HPBIL）算法,分别使用离散群体增量学习（DPBIL）算子和连续PBIL（CPBIL）算子同时对设施放置次序和矩形环大小进行优化,提高了搜索效率;同时还设计了一个局部搜索算法来优化每代中的部分优质解,以提高算法的求精能力。在13个CLLP测试实例上进行实验,结果表明HPBIL算法在9个测试实例上找到了新的最优布局,它对CLLP的寻优能力明显优于对比算法。     

Secant structural solution strategies under element constraint for incremental damage

Two major difficulties in the nonlinear analysis of post-peak structural behavior are the occurrence of an ill-conditioned tangent stiffness matrix around critical points, namely limit and bifurcation points, and the selection of a suitable constrain on the solution path. As an attempt to make failure prediction available in a routine manner, new solution strategies are proposed in which a secant structural stiffness matrix is formulated for incremental damage models, and the solution path is controlled through a suitable measure of failure at the most severely damaged point in the body. Numerical solutions are given for plane strain and plane stress problems to show that snap-back and snap-through associated with shear band formation can be inexpensively predicted.     

An incremental algorithm for DLO quantifier elimination via constraint propagation

The first-order logical theory of dense linear order has long been known to admit quantifier elimination. This paper develops an explicit algorithm that yields an equivalent quantifier free form of its input formula. This algorithm performs existential quantifier elimination via constraint propagation. The result is computed incrementally using functional programming techniques. This approach may be of interest in implementing query languages for constraint databases.     

Network layout procedure for printed - circuit design

This paper describes a heuristic solution procedure for laying out the conductors of a printed circuit on the two sides of a plate of nonconducting material. There must be no overlap between conductors on the same side of the plate as they are uninsulated. For certain layouts it is necessary to drill holes in the plate and pass conductors through the holes to avoid overlap. The problem is to identify the layout which requires the minimum number of holes. The solution procedure uses a computer subroutine in conjunction with an iconic model of the plate. The subroutine is based on a method of Nicholson¹ which attempts to lay out a given circuit on one side of a plate to minimize the number of overlaps. The iconic model of the plate used in this research consisted of a pair of plastic sheets, representing the two sides of the plate, overlaid one on top of the other. The nodes and connections were drawn on them with felt-tip pens. The procedure is iterative and takes advantage of the fact that the problem can be viewed in terms of graph theory. The procedure is suitable for an interactive computer terminal system. Computational experience is limited but encouraging. However there is no guarantee that solutions produced by the procedure will be optimal in the sense that an absolute minimum number of holes will be required to be drilled.     

Efficiency of partial-order graphs and an opdering procedure for a numerical data array

Cybernetics and Systems Analysis -     

Revisiting decomposition analysis of geometric constraint graphs

Geometric problems defined by constraints can be represented by geometric constraint graphs whose nodes are geometric elements and whose arcs represent geometric constraints. Reduction and decomposition are techniques commonly used to analyze geometric constraint graphs in geometric constraint solving.In this paper we first introduce the concept of deficit of a constraint graph. Then we give a new formalization of the decomposition algorithm due to Owen. This new formalization is based on preserving the deficit rather than on computing triconnected components of the graph and is simpler. Finally we apply tree decompositions to prove that the class of problems solved by the formalizations studied here and other formalizations reported in the literature is the same.     

带平衡约束矩形布局优化问题的深度强化学习算法

带平衡约束的矩形布局问题源于卫星舱设备布局设计,属于组合优化问题。深度强化学习利用奖赏机制,通过数据训练实现高性能决策优化。针对布局优化问题,提出一种基于深度强化学习的新算法DAR及其扩展算法IDAR。DAR用指针网络输出定位顺序,再利用定位机制给出布局结果,算法的时间复杂度是O（n³）;IDAR算法在DAR的基础上引入迭代机制,算法时间复杂度是O（n⁴）,但能给出更好的结果。测试表明DAR算法具有较好的学习能力,用小型布局问题进行求解训练所获得的模型,能有效应用在大型问题上。在两个大规模典型算例的对照实验中,提出算法分别超出和接近目前最优解,具有时间和质量上的优势。     

A simulated annealing heuristic for the dynamic layout problem with budget constraint

Facility layout problem has been extensively studied in the literature because the total material handling cost can be a significant portion in the operational costs for a company and in the manufacturing cost of a product. Today’s severe global competition, rapid changes in technology and shortening life cycle of products force companies to evaluate and modify their facility layout in a periodic fashion. This type of layout problems is categorized as the dynamic facility layout problem (DFLP). As a realistic dimension of the problem, one has to consider also the limited budget to cover the cost of changing the layout. In this study, we propose a simulated annealing heuristic for the DFLP with budget constraint, and show the effectiveness of this heuristic on a set of numerical experiments.     

X-tron: an incremental connectionist model for category perception

A connectionist model for categorization (self-organization) even in the presence of multiple or mixed patterns has been presented. During self-organization, the network automatically adjusts the number of nodes in the hidden and output layers, depending on the complexity or nature of overlap between the patterns. An ambiguity measure is given based on how well the features are being interpreted by the network. From the ambiguity measure a certainty factor about the decision of the network is derived. The effect of noise on the certainty factor is investigated. A vigilance threshold is used to decide whether the network's decision is correct or not. Functionally the network consists of two parts, one of them categorizes the incoming patterns and the other monitors the performance of categorization. The characteristics of the model has also been demonstrated experimentally on both 1D binary strings and image patterns even when they are corrupted by additive, subtractive, and mixed noise.     

Verifying traits: an incremental proof system for fine-grained reuse

Traits have been proposed as a more flexible mechanism than class inheritance for structuring code in object-oriented programming, to achieve fine-grained code reuse. A trait originally developed for one purpose can be adapted and reused in a completely different context. Formalizations of traits have been extensively studied, and implementations of traits have started to appear in programming languages. So far, work on formally establishing properties of trait-based programs has mostly concentrated on type systems. This paper presents the first deductive proof system for a trait-based object-oriented language. If a specification of a trait can be given a priori, covering all actual usage of that trait, our proof system is modular as each trait is analyzed only once. However, imposing such a restriction may in many cases unnecessarily limit traits as a mechanism for flexible code reuse. In order to reflect the flexible reuse potential of traits, our proof system additionally allows new specifications to be added to a trait in an incremental way which does not violate established proofs. We formalize and show the soundness of the proof system.     

iGraph: an incremental data processing system for dynamic graph

With the popularity of social network, the demand for real-time processing of graph data is increasing. However, most of the existing graph systems adopt a batch processing mode, therefore the overhead of maintaining and processing of dynamic graph is significantly high. In this paper, we design iGraph, an incremental graph processing system for dynamic graph with its continuous updates. The contributions of iGraph include: 1) a hash-based graph partition strategy to enable fine-grained graph updates; 2) a vertexbased graph computing model to support incremental data processing; 3) detection and rebalance methods of hotspot to address the workload imbalance problem during incremental processing. Through the general-purpose API, iGraph can be used to implement various graph processing algorithms such as PageRank. We have implemented iGraph on Apache Spark, and experimental results show that for real life datasets, iGraph outperforms the original GraphX in respect of graph update and graph computation.     

Fast procedure for Non-uniform optimum design of stiffened shells under buckling constraint

For tailoring the non-uniform axial compression, each sub-panel of stiffened shells should be designed separately to achieve a high load-carrying efficiency. Motivated by the challenge caused by numerous variables and high computational cost, a fast procedure for the minimum weight design of non-uniform stiffened shells under buckling constraint is proposed, which decomposes a hyper multi-dimensional problem into a hierarchical optimization with two levels. To facilitate the post-buckling optimization, an efficient equivalent analysis model of stiffened shells is developed based on the Numerical Implementation of Asymptotic Homogenization Method. In particular, the effects of non-uniform load, internal pressure and geometric imperfections are taken into account during the optimization. Finally, a typical fuel tank of launch vehicle is utilized to demonstrate the effectiveness of the proposed procedure, and detailed comparison with other optimization methodologies is made.

     

A learning procedure for multisurface method of pattern separation

Mangasarian⁽⁵⁾ has proposed an interesting method of pattern separation, which is called “multisurface method”. In the method, linear programming problems are recursively solved, and the correct classification of any disjoint pattern sets is basically possible. However the fact that linear programming problems are recursively solved leads to the result that it takes long computation times and requires much memory space of computer in use. This paper describes a learning procedure for multi-surface method instead of linear programming to avoid drawbacks above. The proposed learning algorithm requires only repetitive simple calculations. Experimental results show that computation times required by learning procedure proposed are shorter than those by linear programming.     

AnO(n 2) incremental algorithm for modular decomposition of graphs and 2-structures

This paper gives anO(n ²) incremental algorithm for computing the modular decomposition of 2-structures [1], [2]. A 2-structure is a type of edge-colored graph, and its modular decomposition is also known as the prime tree family. Modular decomposition of 2-structures arises in the study of relational systems. The modular decomposition of undirected graphs and digraphs is a special case, and has applications in a number of combinatorial optimization problems. This algorithm generalizes elements of a previousO(n ²) algorithm of Muller and Spinrad [3] for the decomposition of undirected graphs. However, Muller and Spinrad's algorithm employs a sophisticated data structure that impedes its generalization to digraphs and 2-structures, and limits its practical use. We replace this data structure with a scheme that labels each edge with at most one node, thereby obtaining an algorithm that is both practical and general to 2-structures.     

GUIDE: an interactive and incremental approach for crawling Web applications

The Journal of Supercomputing - The Internet, having a sea of Web applications, is one of the largest data stores for big data analysis. To explore and retrieve the states (pages) from Web...