Grammatica

An Implementation of Algebraic Graph Transformation on Mathematica

© 1998 Gabriel Valiente

Abstract

Grammatica is a prototype implementation of double-pushout algebraic graph transformation based on relation algebra.
It has been implemented using Mathematica on top of the Combinatorica package, and runs therefore on most platforms.
It consists of Mathematica functions for representing, manipulating, displaying and transforming graphs, as well as functions implementing some relation algebra-theoretic operations on graphs.
It supports both interactive and automatic application of double-pushout graph productions, being therefore both a teaching aid and a research tool for algebraic graph transformation.

Tutorial

This is a brief tour on Grammatica, targeted at people who are familiar with the double-pushout algebraic approach to graph transformation. Some working knowledge of Mathematica and the Combinatorica package will also be useful to better follow this tutorial.
Grammatica has been conceived as a direct extension of the Combinatorica package. Although several graph layout algorithms are already encoded in Combinatorica, however, some effort is still needed to better coordinate graph transformation and graph layout. Furthermore, self-loops are not displayed in Combinatorica, because low-level drawing in Mathematica is mostly straight-line based. These issues will be addressed in a future release of Grammatica.
A word of warning: The current release of Grammatica implements the double-pushout approach to the transformation of simple graphs, called 1-graphs in the literature on relation algebra because at most one arc is allowed between an ordered pair of nodes. Although counter-parallel arcs are still allowed, the absence of parallel arcs implies some differencies with respect to the more usual double-pushout transformation of directed multigraphs.

This loads the Grammatica package.

<<Grammatica`

This loads the Combinatorica package.

<< DiscreteMath`Combinatorica`

Graph Matching in Grammatica

Grammatica includes a simple graph matching algorithm, which essentially consists of enumerating the leaves of a search tree and testing them for graph homomorphism.

Grammatica functions for graph matching.

The test for graph homomorphism assumes the candidate matrix to be of the right dimensions and to have exactly one 1 in each row.

MatrixForm[ m = IdentityMatrix[6] ]

\(Print[\ MatrixForm[\ Edges[\ L = CompleteGraph[3, 3]\ ]\ ]\ ]; 

    ShowLabeledGraph[\ L\ ]; \)

\(Print[\ MatrixForm[\ Edges[\ G = CompleteGraph[6]\ ]\ ]\ ]; 

    ShowLabeledGraph[\ G\ ]; \)

IsMorphism[ m, G, L ]

IsMorphism[ m, L, G ]

There is always an occurrence of a complete graph in another complete graph.

MatrixForm[
RandomMorphism[CompleteGraph[3],
CompleteGraph[5]]]

There are, in fact, many occurrences of a complete graph in another complete graph.

Map[MatrixForm,
AllMorphisms[CompleteGraph[3],
CompleteGraph[5]]]

Not every graph homomorphism is also a graph monomorphism.

IsMorphism[m=(({{1, 0, 0, 0}, {1, 0, 0, 0}, {0, 1, 0, 0}})),
	L = CompleteGraph[3],
	G = AddEdge[CompleteGraph[4], {1, 1}, Directed]]

IsMonomorphism[m, L, G]

MatrixForm[RandomMonomorphism[L, G]]

Actually, there are 34 graph homomorphisms from L to G, of which only 24 are graph monomorphisms.

Length[AllMorphisms[L, G]]

Length[AllMonomorphisms[L, G]]

Grammatica functions for graph matching.

Graph Transformation in Grammatica

Grammatica implements the double-pushout algebraic approach to graph transformation. It handles simple, directed graphs (called 1-graphs in the literature on relation algebra) and also simple, undirected graphs as a special case.

Grammatica functions for graph transformation.

Several functions provided by Combinatorica for generating graphs can be used in Grammatica to build graph productions.

The following set of five graph productions allow to generate all Eulerian graphs.

\(p1 = {
		CompleteGraph[1], 
		CompleteGraph[1], 
		
          Graph[{{1}}, {{0, 0}}], 
		IdentityMatrix[1], 
		
          IdentityMatrix[1]\ }\);
p2={
		CompleteGraph[1],
		CompleteGraph[1],
		AddEdge[EmptyGraph[2], {1, 2}, Directed],
		IdentityMatrix[1],
		(({{1, 0}})) };
\(p3 = {
		EmptyGraph[2], 
		EmptyGraph[2], 
		
          AddEdge[EmptyGraph[2], {1, 2}, Directed], 
		IdentityMatrix[2], 
          
		IdentityMatrix[2]\ }\);
p4={
		DeleteEdge[CompleteGraph[2], {2, 1}, Directed],
		EmptyGraph[2],
		\(AddEdge[
			
              AddEdge[
				EmptyGraph[3], 
				{1, 3}, Directed], 

              			{3, 2}, Directed]\),
		IdentityMatrix[2],(({{1, 0, 0}, {0, 1, 0}})) };
\(p5 = {
		AddEdge[
			EmptyGraph[3], 
			{1, 2}, Directed], 
          
		EmptyGraph[3], 
		
          AddEdge[AddEdge[EmptyGraph[3], {1, 3}, Directed], {3, 2}, 
            Directed], 
		IdentityMatrix[3], 
		IdentityMatrix[3]\ }\);

Together with a start graph with just one node and no arcs, these graph productions form a graph grammar for generating all Eulerian graphs.

G=CompleteGraph[1]

Not all these graph productions can be applied to the start graph.

RandomRedex[p1,G]//MatrixForm
RandomRedex[p2,G]//MatrixForm
RandomRedex[p3,G]//MatrixForm
RandomRedex[p4,G]//MatrixForm
RandomRedex[p5,G]//MatrixForm

Actually, there is only one redex (up to isomorphism) for production (Subscript[p, 3]) and graph G .

Map[MatrixForm,AllRedexes[p3,G]]

There may be several redexes for a production and a graph.

Map[MatrixForm,
AllRedexes[p3,CompleteGraph[4]]]

A graph can be transformed (rewritten) by applying a production at a redex. The result consists of two graphs and four graph homomorphisms. Together with the production, the graph and the redex, they allow to build a pretty double-pushout diagram, as we will see later in this tutorial.

RewriteProductionGraphRandomRedex[p1,G]

All direct transformations of a graph by applying a production at different redexes can also be obtained.

RewriteProductionGraphAllRedexes[p3,
CompleteGraph[4]]

These graph productions always generate Eulerian graphs when applied to the start graph of this graph grammar, or when applied to an Eulerian graph.

RewriteGraph[{p1,p2,p3,p4,p5},G]

For instance, a derivation sequence of Eulerian graphs having up to 10 nodes can be easily generated by iterative application of these graph productions to the result of each previous rewrite step, starting off with the start graph of this graph grammar.

\(Module[{H = G}, 
	
      While[V[H] < 10, 
		
        H = \(RewriteGraph[{p1, p2, p3, p4, p5}, H]\)[\([4]\)]; 
		
        Print[MatrixForm[Edges[H]]]
	]
]\)

The inverses to these graph productions allow to recognize Eulerian graphs.

q1=InverseProduction[p1];
q2=InverseProduction[p2];
q3=InverseProduction[p3];
q4=InverseProduction[p4];
q5=InverseProduction[p5];

Eulerian graphs cannot always be recognized by reducing them to (a graph isomorphic to) the start graph of the graph grammar using these inverse graph productions, however, because the inverse graph productions disconnect the graph to be recognized.

ReduceGraph[{q1,q2,q3,q4,q5},
CompleteGraph[2,2]]

Grammatica functions for graph transformation.

Graph Visualization in Grammatica

Since Grammatica has been conceived as a direct extension of Combinatorica, it does not offer much more than the graph layout algorithms that are already encoded in Combinatorica.

Grammatica functions for graph visualization.

ShowGraph[  MinCrossEmbedding[GridGraph[4, 5]] ]

AllEmbeddings[GridGraph[4, 5]]

Grammatica functions for graph visualization.

Visualization of Graph Transformation in Grammatica

Graph transformations can be visualized in Grammatica in the usual form of pretty double-pushout diagrams. Graph productions can be visualized in a similar form as well.

Grammatica functions for visualization of graph transformation.

Graph productions can be visualized in matrix form.

ShowMatrixProduction[p1]ShowMatrixProduction[p2]ShowMatrixProduction[p3]ShowMatrixProduction[p4]ShowMatrixProduction[p5]

Graph productions can also be visualized in graphical form.

ShowProduction[p1]ShowProduction[p2]ShowProduction[p3]ShowProduction[p4]ShowProduction[p5]

A graph transformation step can be visualized in matrix form.

\(ShowMatrixRewriteStep[p2, G = CompleteGraph[4], 
	
      m = RandomRedex[p2, G]]\)

As expected, a graph transformation step can also be visualized in graphical form.

ShowRewriteStep[p2, G, m]

Grammatica functions for visualization of graph transformation.