Maximal independent set graph partitions for representations of body-centered cubic lattices

A maximal independent set graph data structure for a body-centered cubic lattice is presented. Refinement and coarsening operations are defined in terms of set-operations resulting in robust and easy implementation compared to a quad-tree-based implementation. The graph only stores information corresponding to the leaves of a quad-tree thus has a smaller memory foot-print. The adjacency information in the graph relieves one from going up and down the quad-tree when searching for neighbors. This results in constant time complexities for refinement and coarsening operations.     

Automatic learning of cost functions for graph edit distance

Graph matching and graph edit distance have become important tools in structural pattern recognition. The graph edit distance concept allows us to measure the structural similarity of attributed graphs in an error-tolerant way. The key idea is to model graph variations by structural distortion operations. As one of its main constraints, however, the edit distance requires the adequate definition of edit cost functions, which eventually determine which graphs are considered similar. In the past, these cost functions were usually defined in a manual fashion, which is highly prone to errors. The present paper proposes a method to automatically learn cost functions from a labeled sample set of graphs. To this end, we formulate the graph edit process in a stochastic context and perform a maximum likelihood parameter estimation of the distribution of edit operations. The underlying distortion model is learned using an Expectation Maximization algorithm. From this model we finally derive the desired cost functions. In a series of experiments we demonstrate the learning effect of the proposed method and provide a performance comparison to other models.     

Behavioral Refinement of Graph Transformation-Based Models

Model-driven software engineering requires the refinement of abstract models into more concrete, platform-specific ones. To create and verify such refinements, behavioral models capturing recon- figuration or communication scenarios are presented as instances of a dynamic meta-model, i.e., a typed graph transformation system specifying the concepts and basic operations scenarios may be composed of. Possible refinement relations between models can now be described based on the corresponding meta-models.In contrast to previous approaches, refinement relations on graph transformation systems are not defined as fixed syntactic mappings between abstract transformation rules and, e.g., concrete rule expressions, but allow for a more loose, semantically defined relation between the transformation systems, resulting in a more flexible notion of refinement.     

Context-free graph grammars and concatenation of graphs

An operation of concatenation is defined for graphs. This allows strings to be viewed as expressions denoting graphs, and string languages to be interpreted as graph languages. For a class of string languages, is the class of all graph languages that are interpretations of languages from . For the classes REG and LIN of regular and linear context-free languages, respectively, . is the smallest class of graph languages containing all singletons and closed under union, concatenation and star (of graph languages). equals the class of graph languages generated by linear HR (= Hyperedge Replacement) grammars, and is generated by the corresponding -controlled grammars. Two characterizations are given of the largest class such that . For the class CF of context-free languages, lies properly inbetween and the class of graph languages generated by HR grammars. The concatenation operation on graphs combines nicely with the sum operation on graphs. The class of context-free (or equational) graph languages, with respect to these two operations, is the class of graph languages generated by HR grammars. Received 16 October 1995 / 18 September 1996     

基于FF—FC有向树结构的GKS图段管理

本文从图论的角度出发对GKS的图段状态与操作进行描述,提出了适用于图段管理的FF-FC有向树结构,阐述了这种有向树的一些性质及其图段操作应用,并建立了相应的图段存储方法和数据类型。最后指出,FF-FC有向树结构适用于任何一级别的GKS实现。     

Recent advances in graph-based pattern recognition with applications in document analysis

Graphs are a powerful and popular representation formalism in pattern recognition. Particularly in the field of document analysis they have found widespread application. From the formal point of view, however, graphs are quite limited in the sense that the majority of mathematical operations needed to build common algorithms, such as classifiers or clustering schemes, are not defined. Consequently, we observe a severe lack of algorithmic procedures that can directly be applied to graphs. There exists recent work, however, aimed at overcoming these limitations. The present paper first provides a review of the use of graph representations in document analysis. Then we discuss a number of novel approaches suitable for making tools from statistical pattern recognition available to graphs. These novel approaches include graph kernels and graph embedding. With several experiments, using different data sets from the field of document analysis, we show that the new methods have great potential to outperform traditional procedures applied to graph representations.     

云环境下图数据库建模技术及其应用研究

针对云环境下传统关系型数据库在大数据库建模方面存在的诸多问题,描述了一种全新的能适应云计算环境建模的图数据库,定义了图数据库模型的基本概念,给出了图数据库建模元素及组织形式,在关系型数据库概念模型建模理论及方法的基础上提出了图数据库建模的若干规则和方法。以图数据库Neo4j为例,详细描述了现代物料入库管理图数据库的建模过程,并应用Cypher语言实现该系统模型的增加、删除、更改、查询及统计功能。实践结果表明：利用图数据库建模技术构造的模型具有语义表达更丰富、更具简易性和可扩展性等优点,对开发基于图模型的智能管理信息系统能够提供一定的参考依据。     

An extended dominating node approach to broadcast and globalcombine in multiport wormhole-routed mesh networks

A new approach to the design of collective communication operations in wormhole-routed mesh networks is described. The approach extends the concept of dominating sets in graph theory by accounting for the relative distance-insensitivity of the wormhole switching strategy and by taking advantage of a multiport communication architecture, which allows each node to simultaneously transmit messages on different outgoing channels. Collective communication operations are defined in terms of sets of extended dominating nodes (EDNs). The nodes in a set of EDNs can deliver (receive) messages to (from) a different, larger set of nodes in a single message-passing step under dimension-ordered wormhole routing and without channel contention among messages. The EDN model can be applied to different collective operations in 2D and 3D mesh networks. The authors focus on EDN-based broadcast and global combine operations. Performance evaluation results are presented that confirm the advantage of this approach over other methods     

区间值模糊图的分解性质

给出了区间值模糊图在笛卡尔积与合成运算下分解的充要条件,证明了区间值模糊图能够在并与联运算下分解。     

A comparison of the stability characteristics of some graph theoretic clustering methods

Assessing the stability of a clustering method involves the measurement of the extent to which the generated clusters are affected by perturbations in the input data. A measure which specifies the disturbance in a set of clusters as the minimum number of operations required to restore the set of modified clusters to the original ones is adopted. A number of well-known graph theoretic clustering methods are compared in terms of their stability as determined by this measure. Specifically, it is shown that among the clustering methods in any of several families of graph theoretic methods, clusters defined as the connected components are the most stable and the clusters specified as the maximal complete subgraphs are the least stable. Furthermore, as one proceeds from the method producing the most narrow clusters (maximal complete subgraphs) to those producing relatively broader clusters, the clustering process is shown to remain at least as stable as any method in the previous stages. Finally, the lower and the upper bounds for the measure of stability, when clusters are defined as the connected components, are derived.     

Towards an Integrated Graph Based Semantics for UML

Recently, we proposed an integrated formal semantics based on graph transformation for central aspects of UML class, object and state diagrams. In this paper, we explain the basic ideas of that approach and show how two more UML diagram types, sequence and collaboration diagrams, can be captured. For UML models consisting of a class diagram and particular state diagrams, a graph transformation system can be defined. Its graphs are associated with system states and its rules with operations in the class diagram and transitions in the state diagrams. Sequence and collaboration diagrams then characterize sequences of operation applications and therefore sequences of transformation rule applications. Thus valid sequence and collaboration diagrams correspond to derivations induced by the graph transformation system. Proceeding this way, it can be checked for example whether such an operation application sequence may be applied in a specific system state.     

Architecting and implementing distributed Web applications using the graph‐oriented approach

This paper presents a graph‐oriented framework, called WebGOP, for architecture modeling and programming of Web‐based distributed applications. WebGOP is based on the graph‐oriented programming (GOP) model, under which the components of a distributed program are configured as a logical graph and implemented using a set of operations defined over the graph. WebGOP reshapes GOP with a reflective object‐oriented design, which provides powerful architectural support in the World Wide Web environment. In WebGOP, the architecture graph is reified as an explicit object which itself is distributed over the network, providing a graph‐oriented context for the execution of distributed applications. The programmer can specialize the type of graph to represent a particular architecture style tailored for an application. WebGOP also has built‐in support for flexible and dynamic architectures, including both planned and unplanned dynamic reconfiguration of distributed applications. We describe the WebGOP framework, a prototypical implementation of the framework on top of SOAP, and a performance evaluation of the prototype. The prototype demonstrated the feasibility of our approach. Results of the performance evaluation showed that the overhead introduced by WebGOP over SOAP is reasonable and acceptable. Copyright © 2003 John Wiley & Sons, Ltd.     

基于组件的分布式软件的动态配置和容错

论文提出一种结构化新方法,它能通过动态配置支持基于组件的分布式软件的容错。采用面向图形的编程模型,基于组件的分布式软件的软件体系结构可用一个逻辑图来表示,该逻辑图可以精化为一个明确的对象并分布到网络中,软件的动态配置通过执行定义在图上的一系列操作来实现,发生错误时通过动态重配置软件来支持容错。论文描述了该方法的基本模型、系统结构及其在CORBA上的实现原型。     

A tabu search algorithm for the job shop problem with sequence dependent setup times

This paper addresses the classic job shop scheduling problem where sequence dependent setup times are present. Based on a modified disjunctive graph, we further investigate and generalize structural properties for the problem under study. A tabu search algorithm with a sophisticated neighbourhood structure is then developed. Compared to most studies in this research area, we are interested in moving internal critical operations rather than merely focusing on non-internal ones. Moreover, neighbourhood functions are defined using insertion techniques instead of simple swaps. Test results show that our algorithm outperforms a simulated annealing algorithm which is recently published. We have also conducted experiments considering the efficiency of developed propositions.     

面向图结构的分布式程序设计模型GOM

很多分布式程序由一组分散在不同处理器结点上的松散耦合的进程协作完成某项任务。这些进程底层的逻辑结构可以用一个图来表示，进程间的通信和同步关系可以用图上的操作来表示。该文描述面向图结构的模型ＧＯＭ以及它的实现ＧＯＳ。在ＧＯＭ层，一个分布式程序由一个概念图以及由消息激活的若干函数构成。     

Detecting Data-flow Errors Based on Petri Nets With Data Operations

In order to guarantee the correctness of business processes, not only control-flow errors but also data-flow errors should be considered. The control-flow errors mainly focus on deadlock, livelock, soundness, and so on. However, there are not too many methods for detecting data-flow errors. This paper defines Petri nets with data operations (PN-DO) that can model the operations on data such as read, write and delete. Based on PN-DO, we define some data-flow errors in this paper. We construct a reachability graph with data operations for each PN-DO, and then propose a method to reduce the reachability graph. Based on the reduced reachability graph, data-flow errors can be detected rapidly. A case study is given to illustrate the effectiveness of our methods.      

A graph theoretical approach to determine a join reducer sequencein distributed query processing

Semijoin has traditionally been relied upon to reduce the cost of data transmission for distributed query processing. However, judiciously applying join operations as reducers can lead to further reduction in the amount of data transmission required. In view of this fact, we explore the approach of using join operations as reducers in distributed query processing. We first show that the problem of determining a sequence of join operations for a query can be transformed to that of finding a specific type of set of cuts to the corresponding query graph, where a cut to a graph is a partition of nodes in that graph. Then, in light of this concept, we prove that the problem of determining the optimal sequence of join operations for a given query graph is of exponential complexity, thus justifying the necessity of applying heuristic approaches to solve this problem. By mapping the problem of determining a sequence of join reducers into the one of finding a set of cuts, we develop (for tree and general query graphs, respectively) efficient heuristic algorithms to determine a join reducer sequence for distributed query processing. The algorithms developed are based on the concept of divide and conquer and are of polynomial time complexity. Simulation is performed to evaluate these algorithms     

基于规则推导的特权隐式授权分析

介绍了一种研究系统特权安全问题的方法.由于其特有的迁移系统安全状态的能力,使得分析及保护系统特权都很困难,因此,传统访问控制研究中所采用的技术无法复制到该领域.在访问控制空间理论下,检查了系统特权的来源问题及其特点,从而将系统规则划分为约束规则与执行规则两类,分别描述授权的限制与效果.进一步对规则逻辑形式进行推导,发现特权操作问的特殊授权关系以及相关属性,并设计了一种快速构造授权推导图的算法.在此基础上,分析隐式授权安全问题可能存在的滥用特权威胁.最后对POSIX(portable operating system interface)标准的权能机制进行形式化描述,计算并构造其授权推导图.对标准设计中存在的滥用威胁提供了对策,有效地实现了与最小特权原则的一致性.