workflow

Process
Problem
Modeling
- Problem instance
  - Commands
- Problem class
  - Commands
Grounding
- NB: You may as well want to try gringo 3 for more options:
Solving
Miscellaneous
- Alternative encoding
- clingo versus gringo+clasp

The ASP solving process Graph coloring

Torsten Schaub, torsten@cs.uni-potsdam.de

http://potassco.sourceforge.net/videos.html

1 Process

okular –presentation asp-solving.pdf

2 Problem

http://en.wikipedia.org/wiki/Graph_coloring
Example: Graph coloring, Section 3.1 in ¹
Given a graph consisting of nodes and edges, assign each node one color such that no two nodes connected by an edge have the same color

3 Modeling

3.1 Problem instance

A graph consisting of nodes and edges, along with some colors, is represented as

facts formed by predicates node/1 and edge/2
facts formed by predicate col/1

3.1.1 Commands

view-file graph.lp

3.2 Problem class

Assign each node one color such that no two nodes connected by an edge have the same color

In other words:

Each node has a unique color
Two connected nodes must not have the same color

3.2.1 Commands

view-file color.lp4 ²

okular –presentation methodology.pdf

4 Grounding

gringo4 –version

human-readable output gringo4 color.lp4 graph.lp –text
machine-readable output (see Table 7.1 in ¹) gringo4 color.lp4 graph.lp

4.1 NB: You may as well want to try gringo 3 for more options:

view-file color.lp4 ² view-file color.lp

gringo3 color.lp graph.lp –text

gringo3 color.lp4 graph.lp –text gringo4 color.lp4 graph.lp –text

5 Solving

clasp3 –version

gringo4 color.lp4 graph.lp | clasp3 gringo4 color.lp4 graph.lp | clasp3 0

gringo4 color.lp4 graph.lp | clasp3 0 –stats

6 Miscellaneous

6.1 Alternative encoding

view-file colorD.lp4 ²

gringo4 colorD.lp4 graph.lp –text gringo4 colorD.lp4 graph.lp | clasp3 0

6.2 clingo versus gringo+clasp

clingo4 –version

clingo4 color.lp4 graph.lp

clingo4 –help

"–help=3" clingo4 –help=3
"–mode" clingo4 –mode=gringo color.lp4 graph.lp | clingo4 –mode=clasp

Footnotes:

M. Gebser, R. Kaminski, B. Kaufmann, and T. Schaub. Answer Set Solving in Practice. Synthesis Lectures on Artificial Intelligence and Machine Learning, Morgan and Claypool December 2012, 238 pages, 10.2200/S00457ED1V01Y201211AIM019

We use extension lp4 to indicate encodings for gringo 4 (along the ASP-Core-2 standard ³)

F. Calimeri, W. Faber, M. Gebser, G. Ianni, R. Kaminski, T. Krennwallner, N. Leone, F. Ricca, and T. Schaub: ASP-Core-2: Input language format. 2012. Available at https://www.mat.unical.it/aspcomp2013/files/ASP-CORE-2.0.pdf.