We introduce a notion of probability to the graph programming language GP 2 which resolves nondeterministic choices of graph transformation rules and their matches. With our programming model Probabilistic GP 2 (P-GP 2), rule and match decisions are assigned uniform distributions over their domains. In this paper, we present an implementation of P-GP 2 as an extension of an existing GP 2 compiler. As an example application, we analyse a (polynomial-time) nondeterministic vertex colouring program which may produce one of many possible colourings. The uniform implementation of P-GP 2 is shown, by sampling, to produce different colourings with different probabilities, allowing quantities such as expected colouring and likelihood of optimal colouring to be considered.
full paper : pdf
@inproceedings(Atkinson2017:GCM:pgp, author = "Timothy Atkinson and Detlef Plump and Susan Stepney", title = "Probabilistic Graph Programming", crossref = "GCM-2017" ) @proceedings(GCM-2017, title = "Electronic pre-proceedings, GCM 2017, Marburg, Germany, July 2017", booktitle = "Electronic pre-proceedings, GCM 2017, Marburg, Germany, July 2017", year = 2017 )