| Titre : | Design and Implementation of a Graph Transformation Engine |
| Auteurs : | Maroua Guerfi, Auteur ; Fayçal Guerrouf, Directeur de thèse |
| Type de document : | Monographie imprimée |
| Editeur : | Biskra [Algérie] : Faculté des Sciences Exactes et des Sciences de la Nature et de la Vie, Université Mohamed Khider, 2019 |
| Format : | 1 vol. (56 p.) / ill. / 29 cm |
| Langues: | Anglais |
| Résumé : |
Graphs are used in a wide range of computer science domain to express complex statuses of systems. Graph transformation is used to model statuses changes of these systems.There are many tools to transform graphs. These tools do not separate their graph transformation engine from its graphical interface. This inhibits reuses their engine in other software. The aim of our work is to develop a graph transformation engine easily integrated into other software. Our engine follows the double pushout approach which is an algebraic approach of graph transformation. To demonstrate the use of our work we developed an application that uses the APIs and packages de?ned by our engine. |
| Sommaire : |
General Introduction 1 1 Fundamentals of Graph Transformation 3 1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Graph Transformation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Graph, Typed Graph, and Their Morphisms . . . . . . . . . . . . . . . . . 4 1.3.1 Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.3.2 Graph Morphism . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3.3 Typed Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.3.4 Typed Graph Morphism . . . . . . . . . . . . . . . . . . . . . . . . 7 1.4 Category . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.5 Gluing Relation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.6 Pushout . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.7 Graph Production . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.8 Graph Match . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.8.1 Constraint Satisfaction Problems . . . . . . . . . . . . . . . . . . . 12 1.8.2 Graph Matching as a CSP . . . . . . . . . . . . . . . . . . . . . . . 13 1.9 Graph Transformation Systems . . . . . . . . . . . . . . . . . . . . . . . . 14 1.9.1 graph transformation . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.9.2 graph transformation system . . . . . . . . . . . . . . . . . . . . . . 14 1.9.3 ( Typed) graph grammar . . . . . . . . . . . . . . . . . . . . . . . 14 1.10 Construction of Graph Transformations . . . . . . . . . . . . . . . . . . . . 15 1.10.1 Applicability of Productions . . . . . . . . . . . . . . . . . . . . . . 15 1.10.2 gluing condition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.10.3 construction of direct (typed) graph transformations . . . . . . . . 16 1.11 Application Condition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.11.1 Application Condition . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.11.2 Negative Application Condition . . . . . . . . . . . . . . . . . . . . 17 1.11.3 application condition for a production . . . . . . . . . . . . . . . . 18 1.12 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.12.1 Fujaba . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.12.2 AGG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.12.3 VIATRA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.13 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2 System Design 20 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.2 Global Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.2.1 Graph Grammar . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.2.2 Graph Transformation . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.3 Detailed Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.3.1 Graph Grammar Class Diagram . . . . . . . . . . . . . . . . . . . . 24 2.3.2 Direct graph transformation activity diagram . . . . . . . . . . . . 27 2.3.3 Non-deterministic Graph transformation activity diagram . . . . . . 27 2.3.4 Graph transformation by rule priority activity diagram . . . . . . . 28 2.3.5 Find matches algorithm . . . . . . . . . . . . . . . . . . . . . . . . 29 2.3.6 Check the applicability of rule algorithm . . . . . . . . . . . . . . . 30 2.3.7 Double Pushout algorithm . . . . . . . . . . . . . . . . . . . . . . . 30 2.3.8 Conform Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3 Implementation 32 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.2 Development Tools and Languages . . . . . . . . . . . . . . . . . . . . . . 32 3.2.1 Go programming language . . . . . . . . . . . . . . . . . . . . . . . 32 3.2.2 Visual Studio Code . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 3.2.3 JavaScript Object Notation . . . . . . . . . . . . . . . . . . . . . . 33 3.3 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 3.3.1 Data Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 3.3.2 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 3.3.3 Usage of the APIs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 4 Use Case: Implementing A Graph Transformation Tool 40 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 4.2 REST architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 4.3 Global Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 4.3.1 Front-end . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 4.3.2 Back-end . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 4.4 Detailed Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 4.4.1 The sequence diagram of Single rule application . . . . . . . . . . . 43 4.4.2 The sequence diagram of rule set application . . . . . . . . . . . . . 44 4.4.3 List of APIs o?ered by the REST server . . . . . . . . . . . . . . . 46 4.5 Example of Application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 4.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 General Conclusion 53 |
| Type de document : | Mémoire master |
Disponibilité (1)
| Cote | Support | Localisation | Statut |
|---|---|---|---|
| MINF/484 | Mémoire master | bibliothèque sciences exactes | Consultable |
