/* 

  Map coloring in Picat.

  Ported from the B-Prolog model
  http://www.probp.com/cp_sat_lp/color.pl
  """
  by Neng-Fa Zhou, Jan. 2012
  """


  This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/


% import sat. % 1.38s
import cp. % 0.75s


main => go.

% color/2
go =>
    time2(color_cp(125,5)).

% color_cp/2
go2 =>
    time2(color(125,5)).

% color2/1
go3 =>
    time2(color2(5)).

% random instances
go4 =>
  N = 100,
  Pct = 7,
  Graph = generate(N,Pct),
  println(generated),
  time2(color3(Graph,A)),
  println(A),
  nl.


% CP: using labeling
color_cp(NV,NC) =>
    println((nv=NV,nc=NC)),
    A = new_list(NV),
    A :: 1..NC,
    foreach(I in 1..NV-1, J in I+1..NV)
       if edge(I,J); edge(J,I) then
          A[I] #!= A[J]
       end
    end,

    % symmetry breaking
    % foreach(I in 1..NC) 
    %   A[I] #<= I
    % end, 

    % solve([ffc,split], A), % 0.748s (0 backtracks)
    solve([ffc,updown], A), % 0.17s (29952 backtracks)
    println(A).


% for sat (no labeling)
color(NV,NC) =>
    A = new_list(NV),
    A :: 1..NC,
    foreach(I in 1..NV-1, J in I+1..NV)
       if edge(I,J); edge(J,I) then
          A[I] #!= A[J]
       end
    end,
    solve(A),
    println(A).

%
% This is a slightly different (and easier) problem instance, using
% the neighbour/2 data (110 nodes).
%
% Time: 0.004s/0 backtracks
%
color2(NC) =>
    AllNeighbors = findall([I,N], (neighbors(I,N))),
    A = new_list(AllNeighbors.length),
    A :: 1..NC,
    foreach([I,Neighbors] in AllNeighbors)
       foreach(J in Neighbors)
          A[I] #!= A[J]
       end
    end,
    solve(A),
    println(A).


% for random generated instances (go4/0)
color3(Graph, A) =>
  N = Graph.len,
  MaxDegree = max([len(Neighbours) : [_,Neighbours] in Graph]),

  A = new_list(N),
  A :: 1..MaxDegree+1,

  println(maxDegree=MaxDegree),

  MaxColor #= max(A),

  % symmetry breaking
  % foreach(I in 1..MaxDegree)
  %   A[I] #<= I
  % end,
  % value_precede_chain(1..MaxDegree+1, A),

  % Neqs = [],
  foreach([I,Neighbors] in Graph)
    foreach(J in Neighbors)
      A[I] #!= A[J]
      % , Neqs := Neqs ++ [A[I] #!= A[J]]
    end
  end,
  % value_precede_chain(1..MaxDegree+1, A),
  % neqs(Neqs),
  println(maxColor=MaxColor),

  solve($[constr,ff,split,min(MaxColor),report(printf("MaxColor: %d\n",MaxColor))], A).


%
% generate a list of neighbours
%
generate(NumNodes,Pct) = Graph =>
   Graph1 = new_array(NumNodes),
   foreach(I in 1..NumNodes)
      Neighbours = [],
      foreach(J in 1..NumNodes, I != J)
        Rand = (1+random() mod 100),
        if Rand <= Pct then
           Neighbours := Neighbours ++ [J]
        end
      end,
      if Neighbours == [] then
        Rand = 1 + random() mod NumNodes,
        while (Rand == I) Rand := 1 + random() mod NumNodes end,
        Neighbours := [Rand]
      end,
      Graph1[I] := [I,Neighbours]
   end,
   Graph = Graph1.to_list().


value_precede_chain(C, X) =>
  foreach(I in 2..C.length)
    value_precede(C[I-1], C[I], X)
  end.


% This definition is inspired by 
% MiniZinc definition value_precede_int.mzn
value_precede(S,T,X) =>
   XLen = X.length,
   B = new_list(XLen+1),
   B :: 0..1,
   foreach(I in 1..XLen)
     % Xis :: 0..1,
     Xis #= (X[I] #= S),
     (Xis #=> (B[I+1] #= 1))
     #/\ ((#~ Xis #= 1) #=> (B[I] #= B[I+1]))
     #/\ ((#~ B[I] #= 1) #=> (X[I] #!= T))
   end,
   B[1] #= 0.




%
% Instance from the B-Prolog model
% http://www.probp.com/cp_sat_lp/color.pl
% 125 nodes.
%
index(-,-)	
edge(1,17).
edge(17,1).
edge(1,25).
edge(25,1).
edge(1,27).
edge(27,1).
edge(1,39).
edge(39,1).
edge(1,45).
edge(45,1).
edge(1,62).
edge(62,1).
edge(1,70).
edge(70,1).
edge(1,77).
edge(77,1).
edge(1,93).
edge(93,1).
edge(1,95).
edge(95,1).
edge(1,96).
edge(96,1).
edge(1,103).
edge(103,1).
edge(1,108).
edge(108,1).
edge(1,125).
edge(125,1).
edge(2,6).
edge(6,2).
edge(2,16).
edge(16,2).
edge(2,18).
edge(18,2).
edge(2,30).
edge(30,2).
edge(2,49).
edge(49,2).
edge(2,51).
edge(51,2).
edge(2,52).
edge(52,2).
edge(2,78).
edge(78,2).
edge(2,82).
edge(82,2).
edge(2,109).
edge(109,2).
edge(3,5).
edge(5,3).
edge(3,6).
edge(6,3).
edge(3,15).
edge(15,3).
edge(3,20).
edge(20,3).
edge(3,24).
edge(24,3).
edge(3,28).
edge(28,3).
edge(3,40).
edge(40,3).
edge(3,42).
edge(42,3).
edge(3,71).
edge(71,3).
edge(3,79).
edge(79,3).
edge(3,80).
edge(80,3).
edge(3,86).
edge(86,3).
edge(3,94).
edge(94,3).
edge(3,101).
edge(101,3).
edge(3,102).
edge(102,3).
edge(3,125).
edge(125,3).
edge(4,15).
edge(15,4).
edge(4,37).
edge(37,4).
edge(4,52).
edge(52,4).
edge(4,63).
edge(63,4).
edge(4,66).
edge(66,4).
edge(4,70).
edge(70,4).
edge(4,97).
edge(97,4).
edge(4,112).
edge(112,4).
edge(4,122).
edge(122,4).
edge(5,18).
edge(18,5).
edge(5,20).
edge(20,5).
edge(5,27).
edge(27,5).
edge(5,29).
edge(29,5).
edge(5,37).
edge(37,5).
edge(5,39).
edge(39,5).
edge(5,56).
edge(56,5).
edge(5,73).
edge(73,5).
edge(5,74).
edge(74,5).
edge(5,76).
edge(76,5).
edge(5,87).
edge(87,5).
edge(5,88).
edge(88,5).
edge(5,105).
edge(105,5).
edge(5,115).
edge(115,5).
edge(5,124).
edge(124,5).
edge(6,15).
edge(15,6).
edge(6,35).
edge(35,6).
edge(6,59).
edge(59,6).
edge(6,61).
edge(61,6).
edge(6,68).
edge(68,6).
edge(6,77).
edge(77,6).
edge(6,81).
edge(81,6).
edge(6,99).
edge(99,6).
edge(6,102).
edge(102,6).
edge(6,104).
edge(104,6).
edge(6,113).
edge(113,6).
edge(6,120).
edge(120,6).
edge(7,36).
edge(36,7).
edge(7,58).
edge(58,7).
edge(7,60).
edge(60,7).
edge(7,61).
edge(61,7).
edge(7,66).
edge(66,7).
edge(7,70).
edge(70,7).
edge(7,90).
edge(90,7).
edge(7,95).
edge(95,7).
edge(7,104).
edge(104,7).
edge(7,125).
edge(125,7).
edge(8,23).
edge(23,8).
edge(8,24).
edge(24,8).
edge(8,26).
edge(26,8).
edge(8,65).
edge(65,8).
edge(8,70).
edge(70,8).
edge(8,102).
edge(102,8).
edge(8,103).
edge(103,8).
edge(8,115).
edge(115,8).
edge(8,116).
edge(116,8).
edge(8,117).
edge(117,8).
edge(9,21).
edge(21,9).
edge(9,41).
edge(41,9).
edge(9,43).
edge(43,9).
edge(9,56).
edge(56,9).
edge(9,93).
edge(93,9).
edge(9,113).
edge(113,9).
edge(10,12).
edge(12,10).
edge(10,49).
edge(49,10).
edge(10,55).
edge(55,10).
edge(10,58).
edge(58,10).
edge(10,68).
edge(68,10).
edge(10,72).
edge(72,10).
edge(10,76).
edge(76,10).
edge(10,99).
edge(99,10).
edge(10,111).
edge(111,10).
edge(10,119).
edge(119,10).
edge(11,20).
edge(20,11).
edge(11,27).
edge(27,11).
edge(11,30).
edge(30,11).
edge(11,38).
edge(38,11).
edge(11,57).
edge(57,11).
edge(11,67).
edge(67,11).
edge(11,68).
edge(68,11).
edge(11,71).
edge(71,11).
edge(11,75).
edge(75,11).
edge(11,77).
edge(77,11).
edge(11,86).
edge(86,11).
edge(11,112).
edge(112,11).
edge(11,123).
edge(123,11).
edge(11,124).
edge(124,11).
edge(12,20).
edge(20,12).
edge(12,47).
edge(47,12).
edge(12,55).
edge(55,12).
edge(12,64).
edge(64,12).
edge(12,69).
edge(69,12).
edge(12,70).
edge(70,12).
edge(12,86).
edge(86,12).
edge(12,90).
edge(90,12).
edge(12,101).
edge(101,12).
edge(12,112).
edge(112,12).
edge(13,27).
edge(27,13).
edge(13,28).
edge(28,13).
edge(13,31).
edge(31,13).
edge(13,41).
edge(41,13).
edge(13,44).
edge(44,13).
edge(13,48).
edge(48,13).
edge(13,54).
edge(54,13).
edge(13,62).
edge(62,13).
edge(13,65).
edge(65,13).
edge(13,67).
edge(67,13).
edge(13,70).
edge(70,13).
edge(13,87).
edge(87,13).
edge(13,118).
edge(118,13).
edge(13,122).
edge(122,13).
edge(14,46).
edge(46,14).
edge(14,48).
edge(48,14).
edge(14,54).
edge(54,14).
edge(14,62).
edge(62,14).
edge(14,72).
edge(72,14).
edge(14,75).
edge(75,14).
edge(14,76).
edge(76,14).
edge(14,87).
edge(87,14).
edge(14,89).
edge(89,14).
edge(14,104).
edge(104,14).
edge(14,105).
edge(105,14).
edge(14,114).
edge(114,14).
edge(14,123).
edge(123,14).
edge(15,40).
edge(40,15).
edge(15,53).
edge(53,15).
edge(15,68).
edge(68,15).
edge(15,81).
edge(81,15).
edge(15,83).
edge(83,15).
edge(15,90).
edge(90,15).
edge(15,96).
edge(96,15).
edge(15,99).
edge(99,15).
edge(15,106).
edge(106,15).
edge(15,118).
edge(118,15).
edge(16,31).
edge(31,16).
edge(16,35).
edge(35,16).
edge(16,37).
edge(37,16).
edge(16,49).
edge(49,16).
edge(16,66).
edge(66,16).
edge(16,67).
edge(67,16).
edge(16,71).
edge(71,16).
edge(16,80).
edge(80,16).
edge(16,89).
edge(89,16).
edge(16,102).
edge(102,16).
edge(16,120).
edge(120,16).
edge(17,28).
edge(28,17).
edge(17,29).
edge(29,17).
edge(17,45).
edge(45,17).
edge(17,49).
edge(49,17).
edge(17,81).
edge(81,17).
edge(17,84).
edge(84,17).
edge(17,96).
edge(96,17).
edge(17,98).
edge(98,17).
edge(17,111).
edge(111,17).
edge(17,112).
edge(112,17).
edge(18,34).
edge(34,18).
edge(18,35).
edge(35,18).
edge(18,49).
edge(49,18).
edge(18,71).
edge(71,18).
edge(18,78).
edge(78,18).
edge(18,81).
edge(81,18).
edge(18,86).
edge(86,18).
edge(18,98).
edge(98,18).
edge(18,99).
edge(99,18).
edge(18,119).
edge(119,18).
edge(18,123).
edge(123,18).
edge(19,36).
edge(36,19).
edge(19,46).
edge(46,19).
edge(19,48).
edge(48,19).
edge(19,61).
edge(61,19).
edge(19,64).
edge(64,19).
edge(19,77).
edge(77,19).
edge(19,78).
edge(78,19).
edge(19,97).
edge(97,19).
edge(19,102).
edge(102,19).
edge(19,103).
edge(103,19).
edge(19,107).
edge(107,19).
edge(19,108).
edge(108,19).
edge(19,118).
edge(118,19).
edge(20,60).
edge(60,20).
edge(20,70).
edge(70,20).
edge(20,71).
edge(71,20).
edge(20,74).
edge(74,20).
edge(20,76).
edge(76,20).
edge(20,94).
edge(94,20).
edge(20,114).
edge(114,20).
edge(20,124).
edge(124,20).
edge(21,25).
edge(25,21).
edge(21,26).
edge(26,21).
edge(21,31).
edge(31,21).
edge(21,33).
edge(33,21).
edge(21,34).
edge(34,21).
edge(21,47).
edge(47,21).
edge(21,80).
edge(80,21).
edge(21,90).
edge(90,21).
edge(21,103).
edge(103,21).
edge(21,119).
edge(119,21).
edge(22,33).
edge(33,22).
edge(22,51).
edge(51,22).
edge(22,58).
edge(58,22).
edge(22,60).
edge(60,22).
edge(22,83).
edge(83,22).
edge(22,90).
edge(90,22).
edge(22,99).
edge(99,22).
edge(22,108).
edge(108,22).
edge(22,119).
edge(119,22).
edge(22,121).
edge(121,22).
edge(22,122).
edge(122,22).
edge(23,27).
edge(27,23).
edge(23,34).
edge(34,23).
edge(23,42).
edge(42,23).
edge(23,46).
edge(46,23).
edge(23,50).
edge(50,23).
edge(23,59).
edge(59,23).
edge(23,74).
edge(74,23).
edge(23,90).
edge(90,23).
edge(23,110).
edge(110,23).
edge(23,121).
edge(121,23).
edge(24,28).
edge(28,24).
edge(24,31).
edge(31,24).
edge(24,43).
edge(43,24).
edge(24,44).
edge(44,24).
edge(24,48).
edge(48,24).
edge(24,52).
edge(52,24).
edge(24,55).
edge(55,24).
edge(24,57).
edge(57,24).
edge(24,97).
edge(97,24).
edge(24,99).
edge(99,24).
edge(24,101).
edge(101,24).
edge(24,102).
edge(102,24).
edge(24,109).
edge(109,24).
edge(24,112).
edge(112,24).
edge(24,125).
edge(125,24).
edge(25,36).
edge(36,25).
edge(25,37).
edge(37,25).
edge(25,41).
edge(41,25).
edge(25,52).
edge(52,25).
edge(25,67).
edge(67,25).
edge(25,70).
edge(70,25).
edge(25,77).
edge(77,25).
edge(25,83).
edge(83,25).
edge(25,91).
edge(91,25).
edge(25,92).
edge(92,25).
edge(25,93).
edge(93,25).
edge(25,100).
edge(100,25).
edge(25,114).
edge(114,25).
edge(25,125).
edge(125,25).
edge(26,48).
edge(48,26).
edge(26,51).
edge(51,26).
edge(26,75).
edge(75,26).
edge(26,92).
edge(92,26).
edge(26,95).
edge(95,26).
edge(26,109).
edge(109,26).
edge(26,112).
edge(112,26).
edge(26,113).
edge(113,26).
edge(26,114).
edge(114,26).
edge(27,28).
edge(28,27).
edge(27,30).
edge(30,27).
edge(27,53).
edge(53,27).
edge(27,81).
edge(81,27).
edge(27,82).
edge(82,27).
edge(27,88).
edge(88,27).
edge(27,92).
edge(92,27).
edge(27,103).
edge(103,27).
edge(27,108).
edge(108,27).
edge(27,113).
edge(113,27).
edge(27,123).
edge(123,27).
edge(28,33).
edge(33,28).
edge(28,34).
edge(34,28).
edge(28,52).
edge(52,28).
edge(28,62).
edge(62,28).
edge(28,63).
edge(63,28).
edge(28,74).
edge(74,28).
edge(28,77).
edge(77,28).
edge(28,89).
edge(89,28).
edge(28,93).
edge(93,28).
edge(28,95).
edge(95,28).
edge(29,30).
edge(30,29).
edge(29,39).
edge(39,29).
edge(29,43).
edge(43,29).
edge(29,51).
edge(51,29).
edge(29,92).
edge(92,29).
edge(29,97).
edge(97,29).
edge(29,108).
edge(108,29).
edge(30,36).
edge(36,30).
edge(30,45).
edge(45,30).
edge(30,53).
edge(53,30).
edge(30,54).
edge(54,30).
edge(30,67).
edge(67,30).
edge(30,92).
edge(92,30).
edge(30,105).
edge(105,30).
edge(30,106).
edge(106,30).
edge(30,114).
edge(114,30).
edge(30,118).
edge(118,30).
edge(31,36).
edge(36,31).
edge(31,44).
edge(44,31).
edge(31,51).
edge(51,31).
edge(31,55).
edge(55,31).
edge(31,65).
edge(65,31).
edge(31,69).
edge(69,31).
edge(31,70).
edge(70,31).
edge(31,86).
edge(86,31).
edge(31,87).
edge(87,31).
edge(31,121).
edge(121,31).
edge(32,33).
edge(33,32).
edge(32,84).
edge(84,32).
edge(32,85).
edge(85,32).
edge(32,113).
edge(113,32).
edge(33,35).
edge(35,33).
edge(33,46).
edge(46,33).
edge(33,72).
edge(72,33).
edge(33,82).
edge(82,33).
edge(33,86).
edge(86,33).
edge(33,88).
edge(88,33).
edge(33,91).
edge(91,33).
edge(33,96).
edge(96,33).
edge(33,97).
edge(97,33).
edge(34,40).
edge(40,34).
edge(34,50).
edge(50,34).
edge(34,55).
edge(55,34).
edge(34,57).
edge(57,34).
edge(34,62).
edge(62,34).
edge(34,76).
edge(76,34).
edge(34,91).
edge(91,34).
edge(34,112).
edge(112,34).
edge(35,43).
edge(43,35).
edge(35,71).
edge(71,35).
edge(35,81).
edge(81,35).
edge(35,94).
edge(94,35).
edge(35,95).
edge(95,35).
edge(35,103).
edge(103,35).
edge(35,109).
edge(109,35).
edge(35,120).
edge(120,35).
edge(36,87).
edge(87,36).
edge(36,102).
edge(102,36).
edge(36,118).
edge(118,36).
edge(36,120).
edge(120,36).
edge(36,122).
edge(122,36).
edge(37,44).
edge(44,37).
edge(37,83).
edge(83,37).
edge(37,88).
edge(88,37).
edge(37,90).
edge(90,37).
edge(37,93).
edge(93,37).
edge(37,96).
edge(96,37).
edge(37,111).
edge(111,37).
edge(37,122).
edge(122,37).
edge(37,123).
edge(123,37).
edge(37,125).
edge(125,37).
edge(38,43).
edge(43,38).
edge(38,50).
edge(50,38).
edge(38,52).
edge(52,38).
edge(38,59).
edge(59,38).
edge(38,64).
edge(64,38).
edge(38,87).
edge(87,38).
edge(38,90).
edge(90,38).
edge(38,101).
edge(101,38).
edge(38,113).
edge(113,38).
edge(39,46).
edge(46,39).
edge(39,61).
edge(61,39).
edge(39,64).
edge(64,39).
edge(39,82).
edge(82,39).
edge(39,103).
edge(103,39).
edge(39,113).
edge(113,39).
edge(39,119).
edge(119,39).
edge(40,46).
edge(46,40).
edge(40,49).
edge(49,40).
edge(40,51).
edge(51,40).
edge(40,55).
edge(55,40).
edge(40,109).
edge(109,40).
edge(40,116).
edge(116,40).
edge(41,42).
edge(42,41).
edge(41,61).
edge(61,41).
edge(41,75).
edge(75,41).
edge(41,89).
edge(89,41).
edge(41,105).
edge(105,41).
edge(41,108).
edge(108,41).
edge(41,113).
edge(113,41).
edge(41,115).
edge(115,41).
edge(41,121).
edge(121,41).
edge(42,47).
edge(47,42).
edge(42,76).
edge(76,42).
edge(42,103).
edge(103,42).
edge(42,110).
edge(110,42).
edge(42,113).
edge(113,42).
edge(42,119).
edge(119,42).
edge(42,123).
edge(123,42).
edge(43,49).
edge(49,43).
edge(43,65).
edge(65,43).
edge(43,67).
edge(67,43).
edge(43,68).
edge(68,43).
edge(43,74).
edge(74,43).
edge(43,80).
edge(80,43).
edge(43,112).
edge(112,43).
edge(44,90).
edge(90,44).
edge(44,94).
edge(94,44).
edge(44,106).
edge(106,44).
edge(44,107).
edge(107,44).
edge(44,114).
edge(114,44).
edge(44,117).
edge(117,44).
edge(45,56).
edge(56,45).
edge(45,60).
edge(60,45).
edge(45,71).
edge(71,45).
edge(45,77).
edge(77,45).
edge(45,87).
edge(87,45).
edge(45,101).
edge(101,45).
edge(46,67).
edge(67,46).
edge(46,79).
edge(79,46).
edge(47,57).
edge(57,47).
edge(47,63).
edge(63,47).
edge(47,107).
edge(107,47).
edge(47,111).
edge(111,47).
edge(47,120).
edge(120,47).
edge(48,53).
edge(53,48).
edge(48,61).
edge(61,48).
edge(48,65).
edge(65,48).
edge(48,68).
edge(68,48).
edge(48,80).
edge(80,48).
edge(48,84).
edge(84,48).
edge(48,98).
edge(98,48).
edge(48,99).
edge(99,48).
edge(48,114).
edge(114,48).
edge(49,53).
edge(53,49).
edge(49,94).
edge(94,49).
edge(50,51).
edge(51,50).
edge(50,52).
edge(52,50).
edge(50,58).
edge(58,50).
edge(50,72).
edge(72,50).
edge(50,92).
edge(92,50).
edge(50,95).
edge(95,50).
edge(50,108).
edge(108,50).
edge(50,109).
edge(109,50).
edge(50,113).
edge(113,50).
edge(50,117).
edge(117,50).
edge(50,119).
edge(119,50).
edge(50,123).
edge(123,50).
edge(51,56).
edge(56,51).
edge(51,101).
edge(101,51).
edge(51,105).
edge(105,51).
edge(51,106).
edge(106,51).
edge(51,115).
edge(115,51).
edge(51,116).
edge(116,51).
edge(51,118).
edge(118,51).
edge(52,63).
edge(63,52).
edge(52,91).
edge(91,52).
edge(52,103).
edge(103,52).
edge(52,108).
edge(108,52).
edge(52,111).
edge(111,52).
edge(52,112).
edge(112,52).
edge(53,70).
edge(70,53).
edge(53,80).
edge(80,53).
edge(53,98).
edge(98,53).
edge(53,118).
edge(118,53).
edge(53,120).
edge(120,53).
edge(54,88).
edge(88,54).
edge(54,92).
edge(92,54).
edge(54,104).
edge(104,54).
edge(54,114).
edge(114,54).
edge(54,115).
edge(115,54).
edge(55,75).
edge(75,55).
edge(55,82).
edge(82,55).
edge(55,96).
edge(96,55).
edge(55,99).
edge(99,55).
edge(55,103).
edge(103,55).
edge(55,115).
edge(115,55).
edge(55,125).
edge(125,55).
edge(56,59).
edge(59,56).
edge(56,64).
edge(64,56).
edge(56,66).
edge(66,56).
edge(56,75).
edge(75,56).
edge(56,76).
edge(76,56).
edge(56,77).
edge(77,56).
edge(56,104).
edge(104,56).
edge(56,105).
edge(105,56).
edge(56,106).
edge(106,56).
edge(56,109).
edge(109,56).
edge(56,112).
edge(112,56).
edge(56,119).
edge(119,56).
edge(57,63).
edge(63,57).
edge(57,65).
edge(65,57).
edge(57,66).
edge(66,57).
edge(57,75).
edge(75,57).
edge(57,80).
edge(80,57).
edge(57,87).
edge(87,57).
edge(57,89).
edge(89,57).
edge(57,95).
edge(95,57).
edge(57,100).
edge(100,57).
edge(58,76).
edge(76,58).
edge(58,77).
edge(77,58).
edge(58,79).
edge(79,58).
edge(58,81).
edge(81,58).
edge(58,91).
edge(91,58).
edge(58,94).
edge(94,58).
edge(58,97).
edge(97,58).
edge(58,108).
edge(108,58).
edge(58,113).
edge(113,58).
edge(59,70).
edge(70,59).
edge(59,74).
edge(74,59).
edge(59,95).
edge(95,59).
edge(59,113).
edge(113,59).
edge(59,124).
edge(124,59).
edge(60,64).
edge(64,60).
edge(60,96).
edge(96,60).
edge(60,98).
edge(98,60).
edge(60,115).
edge(115,60).
edge(60,124).
edge(124,60).
edge(61,63).
edge(63,61).
edge(61,71).
edge(71,61).
edge(61,92).
edge(92,61).
edge(61,94).
edge(94,61).
edge(61,100).
edge(100,61).
edge(61,108).
edge(108,61).
edge(61,115).
edge(115,61).
edge(61,124).
edge(124,61).
edge(62,68).
edge(68,62).
edge(62,69).
edge(69,62).
edge(62,93).
edge(93,62).
edge(62,94).
edge(94,62).
edge(62,105).
edge(105,62).
edge(62,110).
edge(110,62).
edge(62,112).
edge(112,62).
edge(62,120).
edge(120,62).
edge(62,124).
edge(124,62).
edge(62,125).
edge(125,62).
edge(63,65).
edge(65,63).
edge(63,68).
edge(68,63).
edge(63,73).
edge(73,63).
edge(63,86).
edge(86,63).
edge(63,89).
edge(89,63).
edge(63,90).
edge(90,63).
edge(63,96).
edge(96,63).
edge(63,105).
edge(105,63).
edge(63,106).
edge(106,63).
edge(63,112).
edge(112,63).
edge(64,68).
edge(68,64).
edge(64,72).
edge(72,64).
edge(64,77).
edge(77,64).
edge(64,85).
edge(85,64).
edge(64,95).
edge(95,64).
edge(64,110).
edge(110,64).
edge(64,113).
edge(113,64).
edge(64,115).
edge(115,64).
edge(64,117).
edge(117,64).
edge(65,78).
edge(78,65).
edge(65,97).
edge(97,65).
edge(65,102).
edge(102,65).
edge(66,68).
edge(68,66).
edge(66,70).
edge(70,66).
edge(66,71).
edge(71,66).
edge(66,76).
edge(76,66).
edge(66,82).
edge(82,66).
edge(66,88).
edge(88,66).
edge(66,91).
edge(91,66).
edge(66,122).
edge(122,66).
edge(67,68).
edge(68,67).
edge(67,69).
edge(69,67).
edge(67,91).
edge(91,67).
edge(67,125).
edge(125,67).
edge(68,71).
edge(71,68).
edge(68,83).
edge(83,68).
edge(68,102).
edge(102,68).
edge(68,104).
edge(104,68).
edge(69,74).
edge(74,69).
edge(69,118).
edge(118,69).
edge(70,81).
edge(81,70).
edge(70,82).
edge(82,70).
edge(70,83).
edge(83,70).
edge(70,96).
edge(96,70).
edge(70,119).
edge(119,70).
edge(71,95).
edge(95,71).
edge(71,101).
edge(101,71).
edge(71,109).
edge(109,71).
edge(71,110).
edge(110,71).
edge(72,76).
edge(76,72).
edge(72,81).
edge(81,72).
edge(72,82).
edge(82,72).
edge(72,84).
edge(84,72).
edge(72,111).
edge(111,72).
edge(72,117).
edge(117,72).
edge(73,92).
edge(92,73).
edge(73,112).
edge(112,73).
edge(74,92).
edge(92,74).
edge(74,97).
edge(97,74).
edge(74,121).
edge(121,74).
edge(74,123).
edge(123,74).
edge(75,78).
edge(78,75).
edge(75,79).
edge(79,75).
edge(75,86).
edge(86,75).
edge(75,103).
edge(103,75).
edge(75,104).
edge(104,75).
edge(75,107).
edge(107,75).
edge(75,110).
edge(110,75).
edge(75,120).
edge(120,75).
edge(76,80).
edge(80,76).
edge(76,93).
edge(93,76).
edge(76,102).
edge(102,76).
edge(76,103).
edge(103,76).
edge(76,109).
edge(109,76).
edge(77,78).
edge(78,77).
edge(77,85).
edge(85,77).
edge(77,88).
edge(88,77).
edge(77,106).
edge(106,77).
edge(77,107).
edge(107,77).
edge(77,116).
edge(116,77).
edge(77,120).
edge(120,77).
edge(78,81).
edge(81,78).
edge(78,101).
edge(101,78).
edge(78,107).
edge(107,78).
edge(79,88).
edge(88,79).
edge(79,99).
edge(99,79).
edge(79,119).
edge(119,79).
edge(80,88).
edge(88,80).
edge(80,93).
edge(93,80).
edge(80,103).
edge(103,80).
edge(80,113).
edge(113,80).
edge(80,124).
edge(124,80).
edge(81,83).
edge(83,81).
edge(81,92).
edge(92,81).
edge(81,101).
edge(101,81).
edge(81,104).
edge(104,81).
edge(81,114).
edge(114,81).
edge(82,97).
edge(97,82).
edge(82,103).
edge(103,82).
edge(82,120).
edge(120,82).
edge(83,96).
edge(96,83).
edge(83,112).
edge(112,83).
edge(83,121).
edge(121,83).
edge(84,108).
edge(108,84).
edge(84,112).
edge(112,84).
edge(85,95).
edge(95,85).
edge(85,109).
edge(109,85).
edge(85,114).
edge(114,85).
edge(85,117).
edge(117,85).
edge(85,118).
edge(118,85).
edge(85,121).
edge(121,85).
edge(86,91).
edge(91,86).
edge(86,106).
edge(106,86).
edge(87,118).
edge(118,87).
edge(88,90).
edge(90,88).
edge(88,92).
edge(92,88).
edge(88,96).
edge(96,88).
edge(88,101).
edge(101,88).
edge(88,103).
edge(103,88).
edge(88,105).
edge(105,88).
edge(88,118).
edge(118,88).
edge(88,122).
edge(122,88).
edge(89,97).
edge(97,89).
edge(89,98).
edge(98,89).
edge(89,99).
edge(99,89).
edge(89,108).
edge(108,89).
edge(90,96).
edge(96,90).
edge(90,98).
edge(98,90).
edge(90,110).
edge(110,90).
edge(90,125).
edge(125,90).
edge(91,95).
edge(95,91).
edge(91,105).
edge(105,91).
edge(91,109).
edge(109,91).
edge(91,116).
edge(116,91).
edge(91,124).
edge(124,91).
edge(92,93).
edge(93,92).
edge(92,98).
edge(98,92).
edge(92,101).
edge(101,92).
edge(92,102).
edge(102,92).
edge(92,107).
edge(107,92).
edge(92,123).
edge(123,92).
edge(93,102).
edge(102,93).
edge(93,115).
edge(115,93).
edge(93,117).
edge(117,93).
edge(93,118).
edge(118,93).
edge(94,95).
edge(95,94).
edge(94,114).
edge(114,94).
edge(94,121).
edge(121,94).
edge(95,102).
edge(102,95).
edge(95,115).
edge(115,95).
edge(95,117).
edge(117,95).
edge(96,97).
edge(97,96).
edge(96,101).
edge(101,96).
edge(96,112).
edge(112,96).
edge(96,115).
edge(115,96).
edge(97,98).
edge(98,97).
edge(97,100).
edge(100,97).
edge(97,102).
edge(102,97).
edge(97,123).
edge(123,97).
edge(98,110).
edge(110,98).
edge(99,101).
edge(101,99).
edge(99,113).
edge(113,99).
edge(99,119).
edge(119,99).
edge(100,112).
edge(112,100).
edge(100,125).
edge(125,100).
edge(101,102).
edge(102,101).
edge(101,123).
edge(123,101).
edge(101,124).
edge(124,101).
edge(102,104).
edge(104,102).
edge(102,107).
edge(107,102).
edge(102,114).
edge(114,102).
edge(102,122).
edge(122,102).
edge(102,123).
edge(123,102).
edge(103,109).
edge(109,103).
edge(103,112).
edge(112,103).
edge(103,125).
edge(125,103).
edge(104,118).
edge(118,104).
edge(104,121).
edge(121,104).
edge(105,109).
edge(109,105).
edge(105,116).
edge(116,105).
edge(105,123).
edge(123,105).
edge(106,107).
edge(107,106).
edge(106,116).
edge(116,106).
edge(107,108).
edge(108,107).
edge(107,120).
edge(120,107).
edge(109,112).
edge(112,109).
edge(109,114).
edge(114,109).
edge(109,123).
edge(123,109).
edge(110,111).
edge(111,110).
edge(110,113).
edge(113,110).
edge(110,121).
edge(121,110).
edge(111,115).
edge(115,111).
edge(111,117).
edge(117,111).
edge(111,124).
edge(124,111).
edge(112,117).
edge(117,112).
edge(113,116).
edge(116,113).
edge(114,124).
edge(124,114).
edge(115,117).
edge(117,115).
edge(115,118).
edge(118,115).
edge(115,120).
edge(120,115).
edge(115,122).
edge(122,115).
edge(115,125).
edge(125,115).
edge(117,122).
edge(122,117).
edge(118,124).
edge(124,118).
edge(119,123).
edge(123,119).
edge(120,122).
edge(122,120).
edge(121,125).
edge(125,121).
edge(122,125).
edge(125,122).

%
% From the B-Prolog program 
% examples/clpfd/color.pi
%
% (It's a slightly smaller instance than the one above: 110 nodes instead of 125 nodes)
%
index(-,-)
neighbors(1,[]).
neighbors(2,[1]).
neighbors(3,[1,2]).
neighbors(4,[1,3]).
neighbors(5,[1,4]).
neighbors(6,[1,5]).
neighbors(7,[1,6]).
neighbors(8,[1,7]).
neighbors(9,[1,8]).
neighbors(10,[1,9]).
neighbors(11,[1,10]).
neighbors(12,[2,3]).
neighbors(13,[3,4,12]).
neighbors(14,[4,5,13]).
neighbors(15,[5,6,14]).
neighbors(16,[6,7,15]).
neighbors(17,[7,8,16]).
neighbors(18,[8,9,17]).
neighbors(19,[9,10,18]).
neighbors(20,[1,10,11,19]).
neighbors(21,[12,13]).
neighbors(22,[13,14,21]).
neighbors(23,[14,15,22]).
neighbors(24,[15,16,23]).
neighbors(25,[16,17,24]).
neighbors(26,[17,18,25]).
neighbors(27,[18,19,26]).
neighbors(28,[19,20,27]).
neighbors(29,[21,22]).
neighbors(30,[22,23,29]).
neighbors(31,[23,24,30]).
neighbors(32,[24,25,31]).
neighbors(33,[25,26,32]).
neighbors(34,[26,27,33]).
neighbors(35,[27,28,34]).
neighbors(36,[29,30]).
neighbors(37,[30,31,36]).
neighbors(38,[31,32,37]).
neighbors(39,[32,33,38]).
neighbors(40,[33,34,39]).
neighbors(41,[34,35,40]).
neighbors(42,[36,37]).
neighbors(43,[37,38,42]).
neighbors(44,[38,39,43]).
neighbors(45,[39,40,44]).
neighbors(46,[40,41,45]).
neighbors(47,[42,43]).
neighbors(48,[43,44,47]).
neighbors(49,[44,45,48]).
neighbors(50,[45,46,49]).
neighbors(51,[47,48]).
neighbors(52,[48,49,51]).
neighbors(53,[49,50,52]).
neighbors(54,[51,52]).
neighbors(55,[52,53,54]).
neighbors(56,[54,55]).
neighbors(57,[2,12]).
neighbors(58,[12,21,57]).
neighbors(59,[21,29,58]).
neighbors(60,[29,36,59]).
neighbors(61,[36,42,60]).
neighbors(62,[42,47,61]).
neighbors(63,[47,51,62]).
neighbors(64,[51,54,63]).
neighbors(65,[54,56,64]).
neighbors(66,[55,56,65]).
neighbors(67,[53,55,66]).
neighbors(68,[50,53,67]).
neighbors(69,[46,50,68]).
neighbors(70,[41,46,69]).
neighbors(71,[35,41,70]).
neighbors(72,[28,35,71]).
neighbors(73,[1,20,28,72]).
neighbors(74,[64,65,66,67]).
neighbors(75,[63,64,74]).
neighbors(76,[67,68,74,75]).
neighbors(77,[62,63,75]).
neighbors(78,[75,76,77]).
neighbors(79,[68,69,76,78]).
neighbors(80,[61,62,77]).
neighbors(81,[77,78,80]).
neighbors(82,[78,79,81]).
neighbors(83,[69,70,79,82]).
neighbors(84,[60,61,80]).
neighbors(85,[80,81,84]).
neighbors(86,[81,82,85]).
neighbors(87,[82,83,86]).
neighbors(88,[70,71,83,87]).
neighbors(89,[59,60,84]).
neighbors(90,[84,85,89]).
neighbors(91,[85,86,90]).
neighbors(92,[86,87,91]).
neighbors(93,[87,88,92]).
neighbors(94,[71,72,88,93]).
neighbors(95,[58,59,89]).
neighbors(96,[89,90,95]).
neighbors(97,[90,91,96]).
neighbors(98,[91,92,97]).
neighbors(99,[92,93,98]).
neighbors(100,[93,94,99]).
neighbors(101,[72,73,94,100]).
neighbors(102,[2,57,58,95]).
neighbors(103,[2,95,96,102]).
neighbors(104,[2,96,97,103]).
neighbors(105,[2,97,98,104]).
neighbors(106,[2,98,99,105]).
neighbors(107,[99,100,106]).
neighbors(108,[100,101,107]).
neighbors(109,[1,73,101,108]).
neighbors(110,[1,2,106,107,108,109]).