White Rose University Consortium logo
University of Leeds logo University of Sheffield logo York University logo

GP 2: Efficient Implementation of a Graph Programming Language

Bak, Christopher (2015) GP 2: Efficient Implementation of a Graph Programming Language. PhD thesis, University of York.

Text (PDF)
Available under License Creative Commons Attribution-Noncommercial-No Derivative Works 2.0 UK: England & Wales.

Download (1056Kb) | Preview


The graph programming language GP (Graph Programs) 2 and its implementation is the subject of this thesis. The language allows programmers to write visual graph programs at a high level of abstraction, bringing the task of solving graph-based problems to an environment in which the user feels comfortable and secure. Implementing graph programs presents two main challenges. The first challenge is translating programs from a high-level source code representation to executable code, which involves bridging the gap from a non-deterministic program to deterministic machine code. The second challenge is overcoming the theoretically impractical complexity of applying graph transformation rules, the basic computation step of a graph program. The work presented in this thesis addresses both of these challenges. We tackle the first challenge by implementing a compiler that translates GP 2 graph programs directly to C code. Implementation strategies concerning the storage and access of internal data structures are empirically compared to determine the most efficient approach for executing practical graph programs. The second challenge is met by extending the double-pushout approach to graph transformation with root nodes to support fast execution of graph transformation rules by restricting the search to the local neighbourhood of the root nodes in the host graph. We add this theoretical construct to the GP 2 language in order to support rooted graph transformation rules, and we identify a class of rooted rules that are applicable in constant time on certain classes of graphs. Finally, we combine theory and practice by writing rooted graph programs to solve two common graph algorithms, and demonstrate that their execution times are capable of matching the execution times of tailored C solutions.

Item Type: Thesis (PhD)
Related URLs:
Keywords: Graph programming, code generation, rooted graph transformation, domain-specific languages
Academic Units: The University of York > Computer Science (York)
Identification Number/EthosID: uk.bl.ethos.684629
Depositing User: Mr Christopher Bak
Date Deposited: 06 May 2016 11:57
Last Modified: 08 Sep 2016 13:34
URI: http://etheses.whiterose.ac.uk/id/eprint/12586

You do not need to contact us to get a copy of this thesis. Please use the 'Download' link(s) above to get a copy.
You can contact us about this thesis. If you need to make a general enquiry, please see the Contact us page.

Actions (repository staff only: login required)