h-graphs: A new representation for tree decompositions of graphs

In geometric constraint solving, 2D well constrained geometric problems can be abstracted as Laman graphs. If the graph is tree decomposable, the constraint-based geometric problem can be solved by a Decomposition–Recombination planner based solver. In general decomposition and recombination steps can be completed only when steps on which they are dependent have already been completed. This fact naturally defines a hierarchy in the decomposition–recombination steps that traditional tree decomposition representations do not capture explicitly.In this work we introduce h-graphs, a new representation for decompositions of tree decomposable Laman graphs, which captures dependence relations between different tree decomposition steps. We show how h-graphs help in efficiently computing parameter ranges for which solution instances to well constrained, tree decomposable geometric constraint problems with one degree of freedom can actually be constructed.     

三维几何约束系统的等价性分析

针对过约束、完整约束和欠约束三维几何约束系统的求解问题,提出了等价性分析方法.该方法基于三维几何约束系统的内在等价性,充分挖掘几何领域知识,依据拆解约束闭环、缩减约束闭环和析出约束闭环等原则,采用等价约束替换来处理几何约束闭环问题,优化几何约束图的结构,实现几何约束系统的优化分解.最后用多个实例验证了该方法的正确性和有...     

用连杆机构几何约束求解

在这篇文章里,我们引入连杆机构作为新的工具,且证明这是完备的,也就是说,所有能构造性描述的图形能被连杆机构作出,这一类包括了所有只含距离约束的约束问题.作为一个应用,我们说明了超出Owen和Hoffmann的三角分解方法之外的最简单的约束图能被转化为纯几何构造形式.为了求解起源于连杆构造的方程,我们提出了一种基于动态轨迹生成的几何方法.     

一类闭环约束的装配约束问题求解

分析了一种可以拆分为等价的开环约束的装配闭环约束问题.给出了等价性的定义,并提出一种该类闭环约束拆分为等价开环约束的方法.首先确定装配几何约束图上的闭环,然后对该闭环利用自由度归约加扰动判定是否从某一条边拆开.该方法能够较好的简化CAD软件中用户添加的装配约束,避免了因闭环约束造成的求解复杂度增加的情况,同时可以更好的表达实际装配的过程.     

Dealing with redundancy and inconsistency in constructive geometric constraint solving

General constructive geometric constraint solvers are pre-processed by a degree-of-freedom analysis, which enables efficient graph decomposition and recombination. However, all these methods are based on the assumption that structural rigidity automatically assures solvability. In this paper, we show that this assumption fails in numerous, even the most basic, configurations. We introduce several simple but efficient rules aimed to additionally analyse solvability in such cases. Another novelty addresses conditional constraints between three or more geometric parts, rules for their simplification and a redundancy check. All these functionalities are built into our original 2D geometric constraint solver, based on concepts of rigid clusters and constrained-angle (CA) sets.     

Formalization of Workflows and Correctness Issues in the Presence of Concurrency

In this paper, main components of a workflow system that are relevant to the correctness in the presence of concurrency are formalized based on set theory and graph theory. The formalization which constitutes the theoretical basis of the correctness criterion provided can be summarized as follows:-Activities of a workflow are represented through a notation based on set theory to make it possible to formalize the conceptual grouping of activities.-Control-flow is represented as a special graph based on this set definition, and it includes serial composition, parallel composition, conditional branching, and nesting of individual activities and conceptual activities themselves.-Data-flow is represented as a directed acyclic graph in conformance with the control-flow graph.The formalization of correctness of concurrently executing workflow instances is based on this framework by defining two categories of constraints on the workflow environment with which the workflow instances and their activities interact. These categories are:-Basic constraints that specify the correct states of a workflow environment.-Inter-activity constraints that define the semantic dependencies among activities such as an activity requiring the validity of a constraint that is set or verified by a preceding activity.Basic constraints graph and inter-activity constraints graph which are in conformance with the control-flow and data-flow graphs are then defined to represent these constraints. These graphs are used in formalizing the intervals among activities where an inter-activity constraint should be maintained and the intervals where a basic constraint remains invalid.A correctness criterion is defined for an interleaved execution of workflow instances using the constraints graphs. A concurrency control mechanism, namely Constraint Based Concurrency Control technique is developed based on the correctness criterion. The performance analysis shows the superiority of the proposed technique. Other possible approaches to the problem are also presented.     

面向集成变量化设计的三维几何约束求解方法

针对集成变量化设计中三维几何约束和装配几何约束的混合建模与求解问题,提出改进的有向图方法.该方法采用几何约束的基本约束表达和几何实体的抽象对偶实体表达,引入定向弧表达实体之间的内在依赖关系建立混合几何约束有向图模型;结合约束有向图的优化处理,实现了几何约束系统的细粒度分解和高效并行求解.最后用实例验证了文中方法的正确性和有效性.     

Geometric constraint solving with conics and linkages

Most geometric construction methods of geometric constraint solving systems use line and circle (rule and compass) as basic drawing tools. In this paper, by introducing conics and linkages, we provide a set of complete drawing tools for the construction approach of geometric constraint solving. Using these tools, we may enlarge the drawing scope of the construction approach and still keep the elegant style of geometric solutions to geometric constraint solving. As applications, we obtain pure geometric solutions to three sets of well-known constraint problems: the 10 Apollonian drawing problems, the 13 cases of a smallest tri-connected constraint graph, and constraint problems with distance constraints only.     

通用几何约束系统统一建模研究

在几何约束和几何实体的基本约束和欧拉参数表达的基础上,研究了通用几何约束系统的统一建模问题。通过对三维几何实体姿态约束和位置约束解耦性的分析,抽象出球实体、盒体和球盒体三种基本几何实体表达空间几何实体,并以基本约束的组合表达几何约束,形成几何约束模型特有的层次结构;并以有向图管理几何约束系统,可以清晰地反映姿态约束和位置约束的解耦性,实现约束系统的细粒度分解,得到规模更小的求解序列,实现高效求解。方法实现于原型系统WhutVAS中。     

Optimality Theory as a Family of Cumulative Logics

We investigate two formalizations of Optimality Theory, a successful paradigm in linguistics.We first give an order-theoretic counterpart for the data and processinvolved in candidate evaluation.Basically, we represent each constraint as a function that assigns every candidate a degree of violation.As for the second formalization, we define (after Samek-Lodovici and Prince) constraints as operations that select the best candidates out of a set of candidates.We prove that these two formalizations are equivalent (accordingly, there is no loss of generality with using violation marks and dispensing with them is only apparent).Importantly, we show that the second formalization is equivalent with a class of operations over sets of formulas in a given logical language.As a result, we prove that Optimality Theory can be characterized by certain cumulative logics.So, applying Optimality Theory is shown to be reasoning by the rules of cumulative logics.     

On the maximum acyclic subgraph problem under disjunctive constraints

Disjunctively constrained versions of classic problems in graph theory such as shortest paths, minimum spanning trees and maximum matchings were recently studied. In this article we introduce disjunctive constrained versions of the Maximum Acyclic Subgraph problem. Negative disjunctive constraints state that a certain pair of edges cannot be contained simultaneously in a feasible solution. Positive disjunctive constraints enforces that at least one arc for the underlying pair is in a feasible solution. It is convenient to represent these disjunctive constraints in terms of an undirected graph, called constraint graph, whose vertices correspond to the arcs of the original graph, and whose edges encode the disjunctive constraints. For the Maximum Acyclic Subgraph problem under Negative Disjunctive Constraints we develop 1/2-approximative algorithms that are polynomial for certain classes of constraint graphs. We also show that determining if a feasible solution exists for an instance of the Maximum Acyclic Subgraph problem under Positive Disjunctive Constraints is an NP-Complete problem.     

几何约束有向图的规划分解研究

在基于有向图表达的几何约束系统中,几何约束的匹配方向、分布状态以及有向图中强连通分量的规模直接影响到整个约束系统的求解;如何对几何约束系统进行合理规划,得到正确有效的求解序列,是目前约束分解研究的重要内容。该文提出了一个规划分解算法,它针对欠约束几何系统的特点,能够优化约束的初始匹配方向,对于约束匹配过程中生成的强连通子图,通过调整约束匹配方向,自适应地改善约束分布,从而减小强连通子图的规模,以求得到几何约束系统正确而高效的求解序列。同时,基于规划分解算法,完成了约束的奇异性分析,提供了面向分解的奇异性分析算法。     

New applications of clique separator decomposition for the Maximum Weight Stable Set problem

Graph decompositions such as decomposition by clique separators and modular decomposition are of crucial importance for designing efficient graph algorithms. Clique separators in graphs were used by Tarjan as a divide-and-conquer approach for solving various problems such as the Maximum Weight Stable Set (MWS) problem, Colouring and Minimum Fill-in. The basic tool is a decomposition tree of the graph whose leaves have no clique separator (so-called atoms), and the problem can be solved efficiently on the graph if it is efficiently solvable on its atoms. We give new examples where the clique separator decomposition works well for the MWS problem; our results improve and extend various recently published results. In particular, we describe the atom structure for some new classes of graphs whose atoms are P₅-free (the P₅ is the induced path with five vertices) and obtain new polynomial time results for the MWS problem. The complexity of this problem on the class of P₅-free graphs is still unknown.     

A Dichotomy for Real Weighted Holant Problems

Holant is a framework of counting characterized by local constraints. It is closely related to other well-studied frameworks such as the counting constraint satisfaction problem (#CSP) and graph homomorphism. An effective dichotomy for such frameworks can immediately settle the complexity of all combinatorial problems expressible in that framework. Both #CSP and graph homomorphism can be viewed as subfamilies of Holant with the additional assumption that the equality constraints are always available. Other subfamilies of Holant such as Holant^* and Holant ^c problems, in which we assume some specific sets of constraints to be freely available, were also studied. The Holant framework becomes more expressive and contains more interesting tractable cases with less or no freely available constraint functions, while, on the other hand, it also becomes more challenging to obtain a complete characterization of its time complexity. Recently, a complexity dichotomy for a variety of subfamilies of Holant such as #CSP, graph homomorphism, Holant^*, and Holant ^c for Boolean domain was proved. In this paper, we prove a dichotomy for the general Holant framework where all the constraints are real symmetric functions on Boolean inputs. This setting already captures most of the interesting combinatorial counting problems defined by local constraints, such as (perfect) matching. This is the first time a dichotomy is obtained for general Holant problems without any auxiliary functions. One benefit of working with the Holant framework is some powerful new reduction technique such as the holographic reduction. Along the proof of our dichotomy, we introduce a new reduction technique, namely realizing a constraint function by approximating it. This new technique is employed in our proof in a situation where it seems that all previous reduction techniques fail; thus, this new idea of reduction might also be of independent interest. Besides proving a dichotomy and developing a new technique, we also obtained some interesting by-products. We prove a dichotomy for #CSP, restricting to instances where each variable appears a multiple of d times for any d. We also prove that counting the number of Eulerian orientations on 2k-regular graphs is #P-hard for any \({k \geq 2}\).     

基于图的参数化设计方法

参数化系统中约束的表达和约束的求解是两大关键性技术问题。作者提出的基于图的参数化方法是将约束分成拓扑约束和几何约束,并以图结构表达这两类约束,然后对约束网络图进行拓扑排序、分解,以确定求解序列和检测约束一致性,最后按照几何约束网中的约束关系进行“几何参数驱动”,以实现参数化。     

A formalization of geometric constraint systems and their decomposition

For more than a decade, the trend in geometric constraint systems solving has been to use a geometric decomposition/recombination approach. These methods are generally grounded on the invariance of systems under rigid motions. In order to decompose further, other invariance groups (e.g., scalings) have recently been considered. Geometric decomposition is grounded on the possibility to replace a solved subsystem with a smaller system called boundary. This article shows the central property that justifies decomposition, without assuming specific types of constraints or invariance groups. The exact nature of the boundary system is given. This formalization brings out the elements of a general and modular implementation.     

Predicting phase transitions of binary constraint satisfaction problems with constraint graph information

Constraint satisfaction is at the core of many applications, such as scheduling. The study of phase transition has benefited algorithm selection and algorithm development in constraint satisfaction. Recent research provides evidence that constraint graph topology affects where phase transitions occur in constraint satisfaction problems. In this article, a new phase transition predictor which takes constraint graph information into consideration is proposed. The new predictor allows variation in the tightness of individual constraints and node degree variation in constraint graph. Experiments were conducted to study the usefulness of the new predictor on random binary constraint satisfaction problems. Results show that the new predictor is able to produce predictions as good as the state-of-the-art predictor in general, but do considerably better in sparsely constrained problems, particularly when the node degree variation in their constraint graphs is high.     

图依赖研究与应用综述

图依赖是用于解决图数据的数据一致性问题的数据质量规则。基于图依赖提升数据一致性的过程通常分为图依赖定义与形式化、图依赖自动挖掘、基于图依赖的数据一致性提升三步。介绍了针对数据一致性的图依赖理论,并根据拓展类型将图依赖分为基于结构约束拓展、基于语义约束拓展和基于外部约束拓展的图依赖;综述并对比了从图数据中自动挖掘图依赖及其拓展的算法;分析了应用图依赖提高数据一致性的研究现状;总结了当前研究中仍存在的问题,并依据问题展望了图依赖在数据质量领域的应用前景。     

Online promise problems with online width metrics

In this article we consider the application of ideas from parameterized complexity, and topological graph theory, to online problems. We focus on parameterized promise problems, where we are promised that the problem input obeys certain properties, or is presented in a certain fashion.We explore the effects of using graph width metrics as restrictions on the input to online problems. It seems natural to suppose that, for graphs having some form of bounded width, good online algorithms may exist for a number of natural problems. In the work presented we concentrate on online graph coloring problems, where we restrict the allowed input to instances having some form of bounded treewidth or pathwidth.We also consider the effects of restricting the presentation of the input to some form of bounded width decomposition or layout. A consequence of this part of the work is the clarification of a new parameter for graphs, persistence, which arises naturally in the online setting, and is of interest in its own right. We present some basic results regarding the general recognition of graphs having bounded persistence path decompositions.     

Searching the Solution Space in Constructive Geometric Constraint Solving with Genetic Algorithms

Geometric problems defined by constraints have an exponential number of solution instances in the number of geometric elements involved. Generally, the user is only interested in one instance such that besides fulfilling the geometric constraints, exhibits some additional properties. Selecting a solution instance amounts to selecting a given root every time the geometric constraint solver needs to compute the zeros of a multi valuated function. The problem of selecting a given root is known as the Root Identification Problem.In this paper we present a new technique to solve the root identification problem. The technique is based on an automatic search in the space of solutions performed by a genetic algorithm. The user specifies the solution of interest by defining a set of additional constraints on the geometric elements which drive the search of the genetic algorithm. The method is extended with a sequential niche technique to compute multiple solutions. A number of case studies illustrate the performance of the method.