/* Diamond free sequence (CSPLib #50) in Picat. http://www.csplib.org/Problems/prob050/ """ Proposed by Alice Miller, Patrick Prosser Given a simple undirected graph G=(V,E), where V is the set of vertices and E the set of undirected edges, the edge {u,v} is in E if and only if vertex u is adjacent to vertex v∈G. The graph is simple in that there are no loop edges, i.e. we have no edges of the form {v,v}. Each vertex v∈V has a degree dv i.e. the number of edges incident on that vertex. Consequently a graph has a degree sequence d1,…,dn, where di>=di+1. A diamond is a set of four vertices in V such that there are at least five edges between those vertices. Conversely, a graph is diamond-free if it has no diamond as an induced subgraph, i.e. for every set of four vertices the number of edges between those vertices is at most four. In our problem we have additional properties required of the degree sequences of the graphs, in particular that the degree of each vertex is greater than zero (i.e. isolated vertices are disallowed), the degree of each vertex is modulo 3, and the sum of the degrees is modulo 12 (i.e. |E| is modulo 6). The problem is then for a given value of n, produce all unique degree sequences d1,…,dn such that * di≥di+1 * each degree di>0 and di is modulo 3 * the sum of the degrees is modulo 12 * there exists a simple diamond-free graph with that degree sequence Below, as an example, is the unique degree sequence forn=10 along with the adjacency matrix of a diamond-free graph with that degree sequence. n = 10 6 6 3 3 3 3 3 3 3 3 0 0 0 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 1 1 0 0 0 1 1 0 1 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 """ Result for go2/0: 8 = [[3,3,3,3,3,3,3,3]] 9 = [[6,6,6,3,3,3,3,3,3]] 10 = [[6,6,3,3,3,3,3,3,3,3]] 11 = [[6,3,3,3,3,3,3,3,3,3,3]] 12 = [[3,3,3,3,3,3,3,3,3,3,3,3],[6,6,6,6,3,3,3,3,3,3,3,3],[6,6,6,6,6,6,6,6,6,6,6,6],[9,6,6,3,3,3,3,3,3,3,3,3]] 13 = [[6,6,6,3,3,3,3,3,3,3,3,3,3]] 14 = [[6,6,3,3,3,3,3,3,3,3,3,3,3,3],[6,6,6,6,6,6,6,6,6,6,6,6,6,6],[9,6,6,6,6,3,3,3,3,3,3,3,3,3],[9,9,6,6,3,3,3,3,3,3,3,3,3,3],[9,9,9,3,3,3,3,3,3,3,3,3,3,3]] 15 = [[6,3,3,3,3,3,3,3,3,3,3,3,3,3,3],[6,6,6,6,6,3,3,3,3,3,3,3,3,3,3],[6,6,6,6,6,6,6,6,6,6,6,6,6,3,3],[9,6,6,6,3,3,3,3,3,3,3,3,3,3,3],[9,9,6,3,3,3,3,3,3,3,3,3,3,3,3],[9,9,9,9,9,9,6,6,6,6,6,6,6,6,6],[12,12,12,3,3,3,3,3,3,3,3,3,3,3,3]] 16 = [[3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3],[6,6,6,6,3,3,3,3,3,3,3,3,3,3,3,3],[6,6,6,6,6,6,6,6,6,6,6,6,3,3,3,3],[6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6],[9,6,6,3,3,3,3,3,3,3,3,3,3,3,3,3],[9,6,6,6,6,6,6,3,3,3,3,3,3,3,3,3],[9,6,6,6,6,6,6,6,6,6,6,3,3,3,3,3],[9,9,3,3,3,3,3,3,3,3,3,3,3,3,3,3],[9,9,9,6,6,3,3,3,3,3,3,3,3,3,3,3],[9,9,9,9,3,3,3,3,3,3,3,3,3,3,3,3],[12,9,9,6,3,3,3,3,3,3,3,3,3,3,3,3]] This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com See also my Picat page: http://www.hakank.org/picat/ */ import cp. main => go. go => garbage_collect(200_000_000), N = 10, All = findall(Degrees, diamond_free_sequence(N, _, Degrees)).sort_remove_dups(), println(all=All), println(len=All.len), nl. % % the different degrees % go2 => garbage_collect(200_000_000), Map = get_global_map(), foreach(N in 1..15) println(n=N), diamond_free_sequence(N, _, Degrees), if not Map.has_key(Degrees) then Map.put(Degrees,1) end, fail ; true end, Lens = new_map(), foreach(Degrees=_ in Map) Len = Degrees.len, Lens.put(Len,Lens.get(Len,[]) ++ [Degrees]) end, foreach(Key in keys(Lens).sort()) println(Key=Lens.get(Key)) end, nl. % % This takes too much RAM for N >= 15 % go2b => garbage_collect(200_000_000), Num = [], foreach(N in 1..16) println(n=N), All = findall(Degrees, diamond_free_sequence(N, _, Degrees)).sort_remove_dups(), println(all=All), println(len=All.len), Num := Num ++ [All.len], nl end, println(num=Num), nl. % % count the number of different graphs (X) % go3 ?=> garbage_collect(200_000_000), N = 15, println(n=N), M = get_global_map(), M.put(count,0), diamond_free_sequence(N, _X, _Degrees), M.put(count,M.get(count)+1), fail, nl. go3 => println(num=get_global_map().get(count)). diamond_free_sequence(N, X, Degrees) => X = new_array(N,N), X :: 0..1, Degrees = new_list(N), Degrees :: 1..N, % diamond free foreach(I in 1..N, J in 1..N, K in 1..N, L in 1..N, I < J, J < K, K < L) X[I,J] + X[I,K] + X[I,L] + X[J,K] + X[J,L] + X[K,L] #<= 4 end, % undirected graph foreach(I in 1..N, J in 1..N) X[I,J] #= X[J,I] end, foreach(I in 1..N) % the degrees (rows = columns since it's an undirected graph) Degrees[I] #= sum([X[I,J] : J in 1..N]), % degrees modulo 3 Degrees[I] mod 3 #= 0, % no loops X[I,I] #= 0 end, % sum degrees modulo 12 sum(Degrees) mod 12 #= 0, % symmetry breaking decreasing(Degrees), lex2eq(X), Vars = Degrees ++ X.vars(), solve([split],Vars). decreasing(List) => foreach(I in 2..List.length) List[I-1] #>= List[I] end. lex2eq(X) => Len = X[1].length, foreach(I in 2..X.length) lex_le([X[I-1,J] : J in 1..Len], [X[I,J] : J in 1..Len]) end.