Document Open Access Logo

Linear-Time Graph Algorithms in GP 2

Authors Graham Campbell , Brian Courtehoute , Detlef Plump

PDF
Thumbnail PDF

File

LIPIcs.CALCO.2019.16.pdf
  • Filesize: 0.53 MB
  • 23 pages

Document Identifiers

Author Details

Graham Campbell
  • Department of Computer Science, University of York, United Kingdom
Brian Courtehoute
  • Department of Computer Science, University of York, United Kingdom
Detlef Plump
  • Department of Computer Science, University of York, United Kingdom

Cite As Get BibTex

Graham Campbell, Brian Courtehoute, and Detlef Plump. Linear-Time Graph Algorithms in GP 2. In 8th Conference on Algebra and Coalgebra in Computer Science (CALCO 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 139, pp. 16:1-16:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.CALCO.2019.16

Abstract

GP 2 is an experimental programming language based on graph transformation rules which aims to facilitate program analysis and verification. However, implementing graph algorithms efficiently in a rule-based language is challenging because graph pattern matching is expensive. GP 2 mitigates this problem by providing rooted rules which, under mild conditions, can be matched in constant time. In this paper, we present linear-time GP 2 programs for three problems: tree recognition, binary directed acyclic graph (DAG) recognition, and topological sorting. In each case, we show the correctness of the program, prove its linear time complexity, and also give empirical evidence for the linear run time. For DAG recognition and topological sorting, the linear behaviour is achieved by implementing depth-first search strategies based on an encoding of stacks in graphs.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Graph transformation
  • rooted graph programs
  • GP 2
  • linear-time algorithms
  • depth-first search
  • topological sorting

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Aditya Agrawal, Gabor Karsai, Sandeep Neema, Feng Shi, and Attila Vizhanyo. The design of a language for model transformations. Software and System Modeling, 5(3):261-288, 2006. URL: https://doi.org/10.1007/s10270-006-0027-7.
  2. Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974. Google Scholar
  3. Thorsten Arendt, Enrico Biermann, Stefan Jurack, Christian Krause, and Gabriele Taentzer. Henshin: Advanced Concepts and Tools for In-Place EMF Model Transformations. In Model Driven Engineering Languages and Systems (MODELS 2010), volume 6394 of Lecture Notes in Computer Science, pages 121-135. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-16145-2_9.
  4. Christopher Bak. GP 2: Efficient Implementation of a Graph Programming Language. PhD thesis, Department of Computer Science, University of York, 2015. URL: http://etheses.whiterose.ac.uk/12586/.
  5. Christopher Bak and Detlef Plump. Rooted Graph Programs. In Proc. International Workshop on Graph Based Tools (GraBaTs 2012), volume 54 of Electronic Communications of the EASST, 2012. URL: https://doi.org/10.14279/tuj.eceasst.54.780.
  6. Christopher Bak and Detlef Plump. Compiling Graph Programs to C. In Proc. International Conference on Graph Transformation (ICGT 2016), volume 9761 of LNCS, pages 102-117. Springer, 2016. URL: https://doi.org/10.1007/978-3-319-40530-8_7.
  7. Heiko Dörr. Efficient Graph Rewriting and its Implementation, volume 922 of Lecture Notes in Computer Science. Springer, 1995. URL: https://doi.org/10.1007/BFb0031909.
  8. Hartmut Ehrig, Claudia Ermel, Ulrike Golas, and Frank Hermann. Graph and Model Transformation. Monographs in Theoretical Computer Science. Springer, 2015. URL: https://doi.org/10.1007/978-3-662-47980-3.
  9. Maribel Fernández, Hélène Kirchner, Ian Mackie, and Bruno Pinaud. Visual Modelling of Complex Systems: Towards an Abstract Machine for PORGY. In Proc. Computability in Europe (CiE 2014), volume 8493 of Lecture Notes in Computer Science, pages 183-193. Springer, 2014. URL: https://doi.org/10.1007/978-3-319-08019-2_19.
  10. Amir Hossein Ghamarian, Maarten de Mol, Arend Rensink, Eduardo Zambon, and Maria Zimakova. Modelling and analysis using GROOVE. International Journal on Software Tools for Technology Transfer, 14(1):15-40, 2012. URL: https://doi.org/10.1007/s10009-011-0186-x.
  11. Annegret Habel and Detlef Plump. Relabelling in Graph Transformation. In Proc. International Conference on Graph Transformation (ICGT 2002), volume 2505 of Lecture Notes in Computer Science, pages 135-147. Springer, 2002. URL: https://doi.org/10.1007/3-540-45832-8_12.
  12. Ivaylo Hristakiev and Detlef Plump. Checking Graph Programs for Confluence. In Software Technologies: Applications and Foundations - STAF 2017 Collocated Workshops, Revised Selected Papers, volume 10748 of Lecture Notes in Computer Science, pages 92-108. Springer, 2018. URL: https://doi.org/10.1007/978-3-319-74730-9_8.
  13. Edgar Jakumeit, Sebastian Buchwald, and Moritz Kroll. GrGen.NET - the expressive, convenient and fast graph rewrite system. International Journal on Software Tools for Technology Transfer, 12(3-4):263-271, 2010. URL: https://doi.org/10.1007/s10009-010-0148-8.
  14. Detlef Plump. The Design of GP 2. In Proc. Workshop on Reduction Strategies in Rewriting and Programming (WRS 2011), volume 82 of Electronic Proceedings in Theoretical Computer Science, pages 1-16, 2012. URL: https://doi.org/10.4204/EPTCS.82.1.
  15. Detlef Plump. From Imperative to Rule-based Graph Programs. Journal of Logical and Algebraic Methods in Programming, 88:154-173, 2017. URL: https://doi.org/10.1016/j.jlamp.2016.12.001.
  16. Christopher M. Poskitt and Detlef Plump. Hoare-style verification of graph programs. Fundamenta Informaticae, 118(1-2):135-175, 2012. URL: https://doi.org/10.3233/FI-2012-708.
  17. Christopher M. Poskitt and Detlef Plump. Verifying Monadic Second-Order Properties of Graph Programs. In Proc. International Conference on Graph Transformation (ICGT 2014), volume 8571 of Lecture Notes in Computer Science, pages 33-48. Springer, 2014. URL: https://doi.org/10.1007/978-3-319-09108-2_3.
  18. Olga Runge, Claudia Ermel, and Gabriele Taentzer. AGG 2.0 - new features for specifying and analyzing algebraic graph transformations. In Proc. Applications of Graph Transformations with Industrial Relevance (AGTIVE 2011), volume 7233 of Lecture Notes in Computer Science, pages 81-88. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-34176-2_8.
  19. Robert Sedgewick. Algorithms in C. Part 5: Graph Algorithms. Addison-Wesley, third edition, 2002. Google Scholar
  20. Steven Skiena. The Algorithm Design Manual. Springer, second edition, 2008. URL: https://doi.org/10.1007/978-1-84800-070-4.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact