1.1 Getting started

Consider the problem of graph coloring as depicted in Fig. 1.1. Below, we provide a simplistic program with hard-coded constraints and specification of the search method to solve this particular graph coloring problem.


Figure 1.1: An example graph.

import org.jacop.core.*; 
import org.jacop.constraints.*; 
import org.jacop.search.*; 
public class Main { 
    static Main m = new Main (); 
    public static void main (String[] args) { 
        Store store = new Store();  // define FD store 
        int size = 4; 
        // define finite domain variables 
        IntVar[] v = new IntVar[size]; 
        for (int i=0; i<size; i++) 
            v[i] = new IntVar(store, "v"+i, 1, size); 
        // define constraints 
        store.impose( new XneqY(v[0], v[1]) ); 
        store.impose( new XneqY(v[0], v[2]) ); 
        store.impose( new XneqY(v[1], v[2]) ); 
        store.impose( new XneqY(v[1], v[3]) ); 
        store.impose( new XneqY(v[2], v[3]) ); 
        // search for a solution and print results 
        Search<IntVar> search = new DepthFirstSearch<IntVar>(); 
        SelectChoicePoint<IntVar> select = 
            new InputOrderSelect<IntVar>(store, v, 
                                         new IndomainMin<IntVar>()); 
        boolean result = search.labeling(store, select); 
        if ( result ) 
            System.out.println("Solution: " + v[0]+", "+v[1] +", "+ 
                                              v[2] +", "+v[3]); 
            System.out.println("*** No"); 

This program produces the following output indicating that vertices v0, v1 and v3 get different colors (1, 2 and 3 respectively), while vertex v3 is assigned color number 1.

Solution: v0=1, v1=2, v2=3, v3=1