Compiling Graph Programs to C

Christopher Peter Bak; Detlef  Plump

doi:10.1007/978-3-319-40530-8_7

Compiling Graph Programs to C

Christopher Peter Bak, Detlef Plump

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We show how to generate efficient C code for a high-level domain-specific language for graphs. The experimental language GP 2 is based on graph transformation rules and aims to facilitate formal reasoning on programs. Implementing graph programs is challenging because rule matching is expensive in general. GP 2 addresses this problem by providing rooted rules which under mild conditions can be matched in constant time. Using a search plan, our compiler generates C code for matching rooted graph transformation rules. We present run-time experiments with our implementation in a case study on checking graphs for two-colourability: on grid graphs of up to 100,000 nodes, the compiled GP 2 program is as fast as the tailor-made C program given by Sedgewick.

Original language	English
Title of host publication	Proceedings 9th International Conference on Graph Transformation (ICGT 2016)
Editors	Rachid Echahed, Mark Minas
Publisher	Springer
Pages	102-117
Number of pages	16
ISBN (Electronic)	978-3-319-40530-8
ISBN (Print)	978-3-319-40529-2
DOIs	https://doi.org/10.1007/978-3-319-40530-8_7
Publication status	Published - 2016
Event	9th International Conference on Graph Transformation (ICGT 2016) - Vienna, Austria Duration: 5 Jul 2016 → 6 Jul 2016

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	9761

Conference

Conference	9th International Conference on Graph Transformation (ICGT 2016)
Country/Territory	Austria
City	Vienna
Period	5/07/16 → 6/07/16

Bibliographical note

© C. Bak, G. Faulkner, D. Plump & C. Runciman. This is an author-produced version of the published article. Uploaded in accordance with the publisher’s self-archiving policy. Further copying may not be permitted; contact the publisher for details.

Access to Document

10.1007/978-3-319-40530-8_7Licence: Unspecified

paperAccepted author manuscript, 282 KBLicence: Unspecified

http://www.cs.york.ac.uk/plasma/publications/pdf/BakPlump.ICGT.16.pdf Licence: Unspecified

Cite this

@inproceedings{cef1951b86a241bb91bf3195b3dc50fa,

title = "Compiling Graph Programs to C",

abstract = "We show how to generate efficient C code for a high-level domain-specific language for graphs. The experimental language GP 2 is based on graph transformation rules and aims to facilitate formal reasoning on programs. Implementing graph programs is challenging because rule matching is expensive in general. GP 2 addresses this problem by providing rooted rules which under mild conditions can be matched in constant time. Using a search plan, our compiler generates C code for matching rooted graph transformation rules. We present run-time experiments with our implementation in a case study on checking graphs for two-colourability: on grid graphs of up to 100,000 nodes, the compiled GP 2 program is as fast as the tailor-made C program given by Sedgewick.",

author = "Bak, {Christopher Peter} and Detlef Plump",

note = "{\textcopyright} C. Bak, G. Faulkner, D. Plump & C. Runciman. This is an author-produced version of the published article. Uploaded in accordance with the publisher{\textquoteright}s self-archiving policy. Further copying may not be permitted; contact the publisher for details. ; 9th International Conference on Graph Transformation (ICGT 2016) ; Conference date: 05-07-2016 Through 06-07-2016",

year = "2016",

doi = "10.1007/978-3-319-40530-8_7",

language = "English",

isbn = "978-3-319-40529-2",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "102--117",

editor = "Rachid Echahed and Mark Minas",

booktitle = "Proceedings 9th International Conference on Graph Transformation (ICGT 2016)",

address = "Germany",

}

TY - GEN

T1 - Compiling Graph Programs to C

AU - Bak, Christopher Peter

AU - Plump, Detlef

N1 - © C. Bak, G. Faulkner, D. Plump & C. Runciman. This is an author-produced version of the published article. Uploaded in accordance with the publisher’s self-archiving policy. Further copying may not be permitted; contact the publisher for details.

PY - 2016

Y1 - 2016

N2 - We show how to generate efficient C code for a high-level domain-specific language for graphs. The experimental language GP 2 is based on graph transformation rules and aims to facilitate formal reasoning on programs. Implementing graph programs is challenging because rule matching is expensive in general. GP 2 addresses this problem by providing rooted rules which under mild conditions can be matched in constant time. Using a search plan, our compiler generates C code for matching rooted graph transformation rules. We present run-time experiments with our implementation in a case study on checking graphs for two-colourability: on grid graphs of up to 100,000 nodes, the compiled GP 2 program is as fast as the tailor-made C program given by Sedgewick.

AB - We show how to generate efficient C code for a high-level domain-specific language for graphs. The experimental language GP 2 is based on graph transformation rules and aims to facilitate formal reasoning on programs. Implementing graph programs is challenging because rule matching is expensive in general. GP 2 addresses this problem by providing rooted rules which under mild conditions can be matched in constant time. Using a search plan, our compiler generates C code for matching rooted graph transformation rules. We present run-time experiments with our implementation in a case study on checking graphs for two-colourability: on grid graphs of up to 100,000 nodes, the compiled GP 2 program is as fast as the tailor-made C program given by Sedgewick.

UR - http://www.scopus.com/inward/record.url?scp=84977530434&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-40530-8_7

DO - 10.1007/978-3-319-40530-8_7

M3 - Conference contribution

SN - 978-3-319-40529-2

T3 - Lecture Notes in Computer Science

SP - 102

EP - 117

BT - Proceedings 9th International Conference on Graph Transformation (ICGT 2016)

A2 - Echahed, Rachid

A2 - Minas, Mark

PB - Springer

T2 - 9th International Conference on Graph Transformation (ICGT 2016)

Y2 - 5 July 2016 through 6 July 2016

ER -

Compiling Graph Programs to C

Abstract

Publication series

Conference

Bibliographical note

Access to Document

Other files and links

Cite this