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.     

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.     

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.     

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.     

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 -     

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.     

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.     

Rotator graphs: an efficient topology for point-to-pointmultiprocessor networks

Rotator graphs, a set of directed permutation graphs, are proposed as an alternative to star and pancake graphs. Rotator graphs are defined in a way similar to the recently proposed Faber-Moore graphs. They have smaller diameter, n-1 in a graph with n factorial vertices, than either the star or pancake graphs or the k-ary n-cubes. A simple optimal routing algorithm is presented for rotator graphs. The n-rotator graphs are defined as a subset of all rotator graphs. The distribution of distances of vertices in the n-rotator graphs is presented, and the average distance between vertices is found. The n-rotator graphs are shown to be optimally fault tolerant and maximally one-step fault diagnosable. The n-rotator graphs are shown to be Hamiltonian, and an algorithm for finding a Hamiltonian circuit in the graphs is given     

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...     

A fast method to exactly calculate the diameter of incremental disconnected graphs

The breadth of problems requiring graph analytics is growing rapidly. Diameter is one of the most important metrics of a graph. The diameter is important in both designing algorithms for graphs and understanding the nature and evolution of graphs. Besides, the real world graphs are always changing. So detecting diameter in both static and dynamic graphs is very important. We first present an algorithm to calculate the diameter of the static graphs. The main goal of this algorithm is to reduce the number of breadth-first searches required to determine diameter of the graph. In addition, another algorithm is presented for calculating the diameter of incremental graphs. This algorithm uses the proposed static algorithm in its body. Based on experimental results, our proposed algorithm can detect diameter of both static and incremental graphs faster than existing approaches. To the best of our knowledge, the second algorithm is the first one that is able to efficiently determine the diameter of disconnected graphs that will be connected over time by adding new vertices.     

An evaluation of multimodal interaction techniques for 3D layout constraint solver in a desktop-based virtual environment

We propose a new approach to the 3D layout problems based on the integration of constraint programming and virtual reality interaction techniques. Our method uses an open-source constraint solver integrated in a popular 3D game engine. We designed multimodal interaction techniques for the system, based on gesture and voice input. We conducted a user study with an interactive task of laying out room furniture to compare and evaluate the mono- and multimodal interaction techniques. Results showed that voice command provided the best performance and was most preferred by participants, based on the analysis of both objective and subjective data. Results also revealed that there was no significant difference between the voice and multimodal input (voice and gesture). Our original approach opens the way to multidisciplinary theoretical work and promotes the development of high-level applications for the VR applications.