Declarative problem solving involves writing constraints as logic rules. For example, the following two logic rules solve the problem of checking whether a graph can be colored with only two colors: The first rule assigns either red or blue to a node X, while the second rule filters out failed candidate solutions, i.e., having two neighboring nodes X and Y with the same color:
color(X,red) v color(X,blue) ← node(X). % Generate ..
false ← edge(X,Y), color(X,C), color(Y,C). % .. and test
For example the utility graph K3,3 can be colored in this way (houses are red, utilities blue or vice versa), while K5 (cf. Kuratowski's theorem) cannot. Graphs that can be two-colored are also called bipartite. A well-known example of bipartite graphs are Petri nets which consist of places and transitions and are used to model and analyze concurrency in distributed systems. In social network analysis, affiliation networks and folksonomies can be modeled as bipartite and tripartite graphs, respectively.
The goal of the project is to visualize and analyze declarative solutions obtained from constraint-based specifications similar to the example above (this includes scheduling problems, optimizations problems, etc.)
Visualizing Declarative Solutions
In this project you will apply information visualization techniques to display (i) problem instances, (ii) candidate solutions, (iii) failed candidates, and (iv) successful solutions in graph form. The goal is to come up with simple and intuitive renderings for a number of declarative problems and solutions.
Required skills: Programming skills in Python
Desired skills: Experience with Jupyter notebooks and databases (e.g. SQL)
Helpful skills: Experience in information visualization; interest in graph theory or combinatorics