The following PhD projects offer opportunities for research ranging from theoretical work to implementation work. The projects are examples, I am happy to discuss other ideas for PhD topics.
GP 2 is an experimental rule-based language for problem solving in the domain of graphs [Plump 2012, Plump 2009]. The GP 2 environment consists of a compiler which generates C code [Bak 2015] and a graphical editor for programs and graphs. In addition, there exists a reference interpreter [Bak et al. 2015].
The purpose of this project is to demonstrate that rooted GP 2 programs can match the complexity of graph algorithms in conventional programming languages. Moreover, a methodology for refining unrooted programs to efficient rooted programs should be developed. Rooted programs allow constant-time access to distinguished nodes in the host graph. For example, [Bak 2015] uses a rooted program to check in linear time whether input graphs (of bounded node degree) are 2-colourable. Timing experiments demonstrate that on grid graphs of up to 100,000 nodes, the GP 2 program matches the run time of Sedgewick's tailor-made C program for 2-colourability [Sedgewick 2002]. However, on graphs of unbounded degree, such as star graphs, the program runs in quadratic time.
This project will conduct a range of case studies on graph algorithms in conventional languages, as found in textbooks such as [Sedgewick 2002, Cormen et al. 2014, Skiena 2011], and attempt to design equivalent GP 2 programs of comparable complexity. The run times of these programs should be experimentally compared with published C programs for the algorithms in question. To obtain fast run times on graphs of unbounded degree, the GP 2 compiler should be improved by avoiding redundant search after backtracking.
By evaluating the case studies, it may be possible to develop a methodology for refining unrooted programs to efficient rooted programs. This is desirable because unrooted programs, which may be highly non-deterministic, are often more concise and easier to design than rooted programs.
To test programs (in any language) working on graphs, it is highly desirable to generate graphs randomly within a specified space of graphs that is relevant for a given application. Available graph generators lack the latter feature. On the other hand, random string generators exist that generate strings uniformly at random within a user-defined context-free language. The goal of this project is to develop algorithms that generate graphs uniformly at random within a user-defined graph class. The graph class may be defined by a context-free graph grammar [Drewes et al. 1999], a graph reduction system or even by a graph program [Plump 2009].
In the undergraduate project [Coxon 2013], a tool has been implemented which produces random graphs over context-free graph grammars. The user specifies a hyperedge-replacement grammar [Drewes et al. 1999] and a size range, and the tool generates a sequence of random graphs from the language of that grammar. The hallmark of this generator is that users can specify the shape of the graphs to be generated by means of the graph grammar. For example, one may want to generate trees or flow graphs only.
A limitation of this approach is that it requires an unambiguous grammar as input in order to generate graphs with a uniform distribution. However, many practical examples of graph grammars are ambiguous and in this case many isomorphic copies of already generated graphs may be produced. In contrast, [Santini 2010, Bertoni et al. 2000] generate strings uniformly at random over possibly ambiguous context-free string grammars. This approach should be adapted to context-free graph grammars and possibly to other graph generating formalisms.
Moreover, it would be desirable to generate graphs randomly with non-uniform distributions which may be more appropriate for certain applications.