Graph grammar engineering: A software specification method

Graphs as conceptual data models are accepted and used in a wide range of different problem areas. Giving some examples we outline common aspects for modeling complex structures by graphs. We present a formal frame-work based on graph grammars to specify graph classes and the corresponding graph manipulations. We show that such a specification can be written in a systematic, engineering-like manner. This is achieved by an extension of the known programmed, attributed graph grammars. Node-set operators are introduced to facilitate graph queries. Concepts like abstraction, decomposition, refinement, parameterization, and integration have been adopted from software engineering to yield a compr…