Graph Completion

Via this site we provide the framework for hypergraph completion presented at ICGT 2008. The corresponding paper is

Given a hyperedge replacement grammar and a hypergraph it computes possible completions of this hypergraph. A completion either adds new edges or glues existing nodes in a way that the resulting graph is a member of the grammar's language.

News: We have developed an improved version of the library that includes some bugfixes and is much more efficient. Among others it is multi-threaded, which gives a factor 2 on quadcore computers. This version is not free software, though. Contact me for further information.


Copyright (C) 2008 Steffen Mazanek

This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program. If not, see


You can download the framework as follows:

We also provide the corresponding javadoc. And we also provide the NSD grammar as an example.

Note that you do not have to use the provided EdgeImpl and NodeImpl implementation classes. Rather you can make your own classes for edges and nodes implement the interfaces Edge and Node. Then you just have to provide edge and node factories for your data structures and are done.


Please, tell me how you use this framework, so that I can add a reference to your project here.

We use this framework in the DiaGen system in order to realize content assist. Further details about this important application are described in

  • S. Mazanek, S. Maier, M. Minas. Auto-completion for Diagram Editors based on Graph Grammars. Proc. of the 2008 IEEE Symposium on Visual Languages and Human-Centric Computing (VL/HCC 2008), 2008. IEEE Computer Society Press, pages 242-245.
Example DiaGen editors with completion are described in the following blog posts (there are also links for download):


You can contact me in case of any problems with the library. Please also report bugs if you meet them. And please tell me your applications!

Related Work

Limited support for graph completion is also possible with our graph parser combinators framework.

Tell me further related work if you know and like.

Steffen Mazanek

Institut für Softwaretechnologie
Fakultät für Informatik

Tel: +49 176 24265704