A Prolog library for accessing graphs

title:A Prolog library for accessing graphs
keywords:
topics:Graphs, Algorithms and Data Structures, Logics and semantics
contact:prof.dr.ir. A. Rensink


Description

Many problem domains let themselves be described in terms of graph-like structures; examples are data structures, traffic flows, computer networks, games. The graph transformation tool GROOVE offers an easy and intuitive way to declare how such graphs evolve, on the basis of graph transformation rules, as well as functionality to automatically simulate such rules and model check the resulting state space.

Part of the GROOVE functionality is provided through a built-in PROLOG component, including a number of pre-defined predicates. This library is not well-designed, and moreover, outdated with respect to the current GROOVE version. In this assignment, you are asked to redesign that Prolog libary. As an extension, you can enhance the GROOVE tool by providing access to PROLOG in more ways than currently supported (to be discussed).

Steps that can be foreseen:

  1. Understanding the concept of graph transformation and getting familiar with the GROOVE tool
  2. Designing a library identifying a minimal set of PROLOG predicates sufficient and convenient to define desirable graph characteristics
  3. Implementing and documenting the library in GROOVE
  4. (Possible extension) Enhancing GROOVE by providing more access to PROLOG
  5. Validating the result by demonstrating it on a number of predefined examples

References

  1. Knowledge-based Graph Exploration Analysis (Digital version available here)