Towards Graph Programs for Graph Algorithms

Detlef Plump; Sandra Steinert

doi:10.1007/978-3-540-30203-2_11

Towards Graph Programs for Graph Algorithms

Detlef Plump, Sandra Steinert

Computer Science

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

Abstract

Graph programs as introduced by Habel and Plump [8] provide a simple yet computationally complete language for computing functions and relations on graphs. We extend this language such that numerical computations on labels can be conveniently expressed. Rather than resorting to some kind of attributed graph transformation, we introduce conditional rule schemata which are instantiated to (conditional) double-pushout rules over ordinary graphs. A guiding principle in our language extension is syntactic and semantic simplicity. As a case study for the use of extended graph programs, we present and analyse two versions of Dijkstra's shortest path algorithm. The first program consists of just three rule schemata and is easily proved to be correct but can be exponential in the number of rule applications. The second program is a refinement of the first which is essentially deterministic and uses at most a quadratic number of rule applications.

Original language	English
Title of host publication	Proceedings 2nd International Conference on Graph Transformation (ICGT 2004)
Editors	H Ehrig, G Engels, F ParisiPresicce, G Rozenberg
Place of Publication	Berlin
Publisher	Springer
Pages	128-143
Number of pages	16
ISBN (Print)	3-540-23207-9
DOIs	https://doi.org/10.1007/978-3-540-30203-2_11
Publication status	Published - 2004
Event	2nd International Conference on Graph Transformations - Rome Duration: 28 Sept 2004 → 2 Oct 2004

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer-Verlag
Volume	3256

Conference

Conference	2nd International Conference on Graph Transformations
City	Rome
Period	28/09/04 → 2/10/04

Keywords

TRANSFORMATION

Access to Document

10.1007/978-3-540-30203-2_11

http://www-users.cs.york.ac.uk/~det/Papers/icgt.04.pdf

Cite this

@inproceedings{8615038937bb4c1abfca277076c79cec,

title = "Towards Graph Programs for Graph Algorithms",

abstract = "Graph programs as introduced by Habel and Plump [8] provide a simple yet computationally complete language for computing functions and relations on graphs. We extend this language such that numerical computations on labels can be conveniently expressed. Rather than resorting to some kind of attributed graph transformation, we introduce conditional rule schemata which are instantiated to (conditional) double-pushout rules over ordinary graphs. A guiding principle in our language extension is syntactic and semantic simplicity. As a case study for the use of extended graph programs, we present and analyse two versions of Dijkstra's shortest path algorithm. The first program consists of just three rule schemata and is easily proved to be correct but can be exponential in the number of rule applications. The second program is a refinement of the first which is essentially deterministic and uses at most a quadratic number of rule applications.",

keywords = "TRANSFORMATION",

author = "Detlef Plump and Sandra Steinert",

year = "2004",

doi = "10.1007/978-3-540-30203-2_11",

language = "English",

isbn = "3-540-23207-9",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "128--143",

editor = "H Ehrig and G Engels and F ParisiPresicce and G Rozenberg",

booktitle = "Proceedings 2nd International Conference on Graph Transformation (ICGT 2004)",

address = "Germany",

note = "2nd International Conference on Graph Transformations ; Conference date: 28-09-2004 Through 02-10-2004",

}

Plump, D & Steinert, S 2004, Towards Graph Programs for Graph Algorithms. in H Ehrig, G Engels, F ParisiPresicce & G Rozenberg (eds), Proceedings 2nd International Conference on Graph Transformation (ICGT 2004). Lecture Notes in Computer Science, vol. 3256, Springer, Berlin, pp. 128-143, 2nd International Conference on Graph Transformations, Rome, 28/09/04. https://doi.org/10.1007/978-3-540-30203-2_11

Towards Graph Programs for Graph Algorithms. / Plump, Detlef; Steinert, Sandra.
Proceedings 2nd International Conference on Graph Transformation (ICGT 2004). ed. / H Ehrig; G Engels; F ParisiPresicce; G Rozenberg. Berlin: Springer, 2004. p. 128-143 (Lecture Notes in Computer Science; Vol. 3256).

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

TY - GEN

T1 - Towards Graph Programs for Graph Algorithms

AU - Plump, Detlef

AU - Steinert, Sandra

PY - 2004

Y1 - 2004

N2 - Graph programs as introduced by Habel and Plump [8] provide a simple yet computationally complete language for computing functions and relations on graphs. We extend this language such that numerical computations on labels can be conveniently expressed. Rather than resorting to some kind of attributed graph transformation, we introduce conditional rule schemata which are instantiated to (conditional) double-pushout rules over ordinary graphs. A guiding principle in our language extension is syntactic and semantic simplicity. As a case study for the use of extended graph programs, we present and analyse two versions of Dijkstra's shortest path algorithm. The first program consists of just three rule schemata and is easily proved to be correct but can be exponential in the number of rule applications. The second program is a refinement of the first which is essentially deterministic and uses at most a quadratic number of rule applications.

AB - Graph programs as introduced by Habel and Plump [8] provide a simple yet computationally complete language for computing functions and relations on graphs. We extend this language such that numerical computations on labels can be conveniently expressed. Rather than resorting to some kind of attributed graph transformation, we introduce conditional rule schemata which are instantiated to (conditional) double-pushout rules over ordinary graphs. A guiding principle in our language extension is syntactic and semantic simplicity. As a case study for the use of extended graph programs, we present and analyse two versions of Dijkstra's shortest path algorithm. The first program consists of just three rule schemata and is easily proved to be correct but can be exponential in the number of rule applications. The second program is a refinement of the first which is essentially deterministic and uses at most a quadratic number of rule applications.

KW - TRANSFORMATION

U2 - 10.1007/978-3-540-30203-2_11

DO - 10.1007/978-3-540-30203-2_11

M3 - Conference contribution

SN - 3-540-23207-9

T3 - Lecture Notes in Computer Science

SP - 128

EP - 143

BT - Proceedings 2nd International Conference on Graph Transformation (ICGT 2004)

A2 - Ehrig, H

A2 - Engels, G

A2 - ParisiPresicce, F

A2 - Rozenberg, G

PB - Springer

CY - Berlin

T2 - 2nd International Conference on Graph Transformations

Y2 - 28 September 2004 through 2 October 2004

ER -