#!/usr/bin/env python
# coding: utf-8

# # Dominating set.
# 
# **The problem**: Given an undirected graph,
# the dominating set problem is to select a subset of vertices such that each remaining vertex is adjacent
# to some selected vertex, where the number of selected vertices must not exceed a given threshold.
# 
# **An example:**
# The graph $(\{1,2,3,4,5,6\},\{\{1,2\},\{1,3\},\{2,4\},\{3,5\},\{4,5\},\{4,6\}\})$
# has two dominating sets with at most $2$ vertices: $\{1,4\}$ and $\{3,4\}$.
# 
# **Instance format**: We represent such a problem instance by facts as follows.

# In[ ]:


get_ipython().run_cell_magic('file', 'instances/instance-dominating.lp', 'vertex(1). vertex(2). vertex(3). vertex(4). vertex(5). vertex(6).\nedge(1,2). edge(1,3). edge(2,4). edge(3,5). edge(4,5). edge(4,6).\nthreshold(2).\n')


# **The task**: Specify a uniform problem encoding such that atoms over the predicate ``select/1`` within the stable models correspond to dominating sets for arbitrary instances (see the output under **Help** below).

# In[ ]:


get_ipython().run_cell_magic('clingo', '0 instances/instance-dominating.lp -', '\n% your encoding goes here...\n\n% show\n#show select/1.\n')


# The symbol ``-`` in the command call tells ``clingo`` to read the instance file _and_ the content of the cell. 

# **Help**: The next cell contains a hard to read encoding for the problem that
# you can use for testing your solution.
# A readable version of it can be found in the ``solutions`` directory.

# In[4]:


get_ipython().run_cell_magic('clingo', '0 instances/instance-dominating.lp -', '#show select/1.ssdergergergregrefefcerverversodjhoinfeorfioejoi2423onjnfeiegegegegdcsvooi454onro3jfo34oi43o43nfo34oi34iofj43(RJGRORGssdergergergregrefefcerverversodjhoinfeorfioejoi2423onjnfeiegegegegdcsvooi454onro3jfo34oi43o43nfo34oi34iofj43):-select(RJGRORGssdergergergregrefefcerverversodjhoinfeorfioejoi2423onjnfeiegegegegdcsvooi454onro3jfo34oi43o43nfo34oi34iofj43).sodjhoinfeorfioejoi2423onjnfeiooi454onro3jfo34oi43o43nfo34oi34iofj43(R0JER434343rfeferfergerGRORGssdergergergregrefefcerverversodjhoinfeorfioejoi2423onjnfeiegegegegdcsvooi454onro3jfo34oi43o43nfo34oi34iofj43):-threshold(R0JER434343rfeferfergerGRORGssdergergergregrefefcerverversodjhoinfeorfioejoi2423onjnfeiegegegegdcsvooi454onro3jfo34oi43o43nfo34oi34iofj43).:-vertex(RJGRORGssdergergergregrefefcerverversodjhoinfeorfioejoi2423onjnfeiegegegegdcsvooi454onro3jfo34oi43o43nfo34oi34iofj43),not ssdergergergregrefefcerverversodjhoinfeorfioejoi2423onjnfeiegegegegdcsvooi454onro3jfo34oi43o43nfo34oi34iofj43(RJGRORGssdergergergregrefefcerverversodjhoinfeorfioejoi2423onjnfeiegegegegdcsvooi454onro3jfo34oi43o43nfo34oi34iofj43).ssdfefcerverversodjhoinfeorfioejoi2423onjnfeiooi454onro3jfo34oi43o43nfo34oi34iofj43(RJGRORGssdergergergregrefefcerverversodjhoinfeorfioejoi2423onjnfeiegegegegdcsvooi454onro3jfo34oi43o43nfo34oi34iofj43,RJER434343rfeferfergerGRORGssdergergergregrefefcerverversodjhoinfeorfioejoi2423onjnfeiegegegegdcsvooi454onro3jfo34oi43o43nfo34oi34iofj43):-edge(RJGRORGssdergergergregrefefcerverversodjhoinfeorfioejoi2423onjnfeiegegegegdcsvooi454onro3jfo34oi43o43nfo34oi34iofj43,RJER434343rfeferfergerGRORGssdergergergregrefefcerverversodjhoinfeorfioejoi2423onjnfeiegegegegdcsvooi454onro3jfo34oi43o43nfo34oi34iofj43).scerverversodjhoinfeorfioejoi2423onjnfeiooi454onro3jfo34oi43o43nfo34oi34iofj43(RJGRORGssdergergergregrefefcerverversodjhoinfeorfioejoi2423onjnfeiegegegegdcsvooi454onro3jfo34oi43o43nfo34oi34iofj43):-vertex(RJGRORGssdergergergregrefefcerverversodjhoinfeorfioejoi2423onjnfeiegegegegdcsvooi454onro3jfo34oi43o43nfo34oi34iofj43).ssdergergergregrefefcerverversodjhoinfeorfioejoi2423onjnfeiegegegegdcsvooi454onro3jfo34oi43o43nfo34oi34iofj43(RJER434343rfeferfergerGRORGssdergergergregrefefcerverversodjhoinfeorfioejoi2423onjnfeiegegegegdcsvooi454onro3jfo34oi43o43nfo34oi34iofj43):-select(RJGRORGssdergergergregrefefcerverversodjhoinfeorfioejoi2423onjnfeiegegegegdcsvooi454onro3jfo34oi43o43nfo34oi34iofj43),edge(RJER434343rfeferfergerGRORGssdergergergregrefefcerverversodjhoinfeorfioejoi2423onjnfeiegegegegdcsvooi454onro3jfo34oi43o43nfo34oi34iofj43,RJGRORGssdergergergregrefefcerverversodjhoinfeorfioejoi2423onjnfeiegegegegdcsvooi454onro3jfo34oi43o43nfo34oi34iofj43).ssdergergergregrefefcerverversodjhoinfeorfioejoi2423onjnfeiegegegegdcsvooi454onro3jfo34oi43o43nfo34oi34iofj43(RJER434343rfeferfergerGRORGssdergergergregrefefcerverversodjhoinfeorfioejoi2423onjnfeiegegegegdcsvooi454onro3jfo34oi43o43nfo34oi34iofj43):-select(RJGRORGssdergergergregrefefcerverversodjhoinfeorfioejoi2423onjnfeiegegegegdcsvooi454onro3jfo34oi43o43nfo34oi34iofj43),edge(RJGRORGssdergergergregrefefcerverversodjhoinfeorfioejoi2423onjnfeiegegegegdcsvooi454onro3jfo34oi43o43nfo34oi34iofj43,RJER434343rfeferfergerGRORGssdergergergregrefefcerverversodjhoinfeorfioejoi2423onjnfeiegegegegdcsvooi454onro3jfo34oi43o43nfo34oi34iofj43).select(RJGRORGssdergergergregrefefcerverversodjhoinfeorfioejoi2423onjnfeiegegegegdcsvooi454onro3jfo34oi43o43nfo34oi34iofj43):-ssdfefcerverversodjhoinfeorfioejoi2423onjnfeiegegegegdcsvooi454onro3jfo34oi43o43nfo34oi34iofj43(RJGRORGssdergergergregrefefcerverversodjhoinfeorfioejoi2423onjnfeiegegegegdcsvooi454onro3jfo34oi43o43nfo34oi34iofj43).{ssdfefcerverversodjhoinfeorfioejoi2423onjnfeiegegegegdcsvooi454onro3jfo34oi43o43nfo34oi34iofj43(RJGRORGssdergergergregrefefcerverversodjhoinfeorfioejoi2423onjnfeiegegegegdcsvooi454onro3jfo34oi43o43nfo34oi34iofj43):vertex(RJGRORGssdergergergregrefefcerverversodjhoinfeorfioejoi2423onjnfeiegegegegdcsvooi454onro3jfo34oi43o43nfo34oi34iofj43)}R0JER434343rfeferfergerGRORGssdergergergregrefefcerverversodjhoinfeorfioejoi2423onjnfeiegegegegdcsvooi454onro3jfo34oi43o43nfo34oi34iofj43:-threshold(R0JER434343rfeferfergerGRORGssdergergergregrefefcerverversodjhoinfeorfioejoi2423onjnfeiegegegegdcsvooi454onro3jfo34oi43o43nfo34oi34iofj43).\n')