/* 

  Graph degree sequence  in Picat.

  Given a (directed) graph as matrix gives the degree sequence.
  
  Reference:
  http://mathworld.wolfram.com/DegreeSequence.html

  If both d and graph are uninitialized we see that for n = 4 there are 
  65536 possible (directed) graphs (65536 = 2^16).



  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.

%
% matrix version, unknown degree sequence
%
go ?=>

  data(matrix,Graph,_DD),
  N = Graph.len,

  % Graph, matrix version, directed
  Graph = new_array(N,N),
  Graph :: 0..1,

  % degree sequence
  D = new_list(N),
  D :: 0..N, 

  degree_sequence_matrix(D, Graph),

  Vars = Graph.vars ++ D,
  solve(Vars),

  println(graph=Graph),
  println(d=D),
  nl,
  fail,

  nl.

go => true.

%
% matrix version, unknown graph
% (generate graph from degree sequence)
%
go2 ?=>

  data(matrix,_GGraph,D),
  N = D.len,

  % Graph, matrix version, directed
  Graph = new_array(N,N),
  Graph :: 0..1,

  % degree sequence
  D = new_list(N),
  D :: 0..N, 

  degree_sequence_matrix(D, Graph),

  Vars = Graph.vars ++ D,
  solve(Vars),

  println(graph=Graph),
  println(d=D),
  nl,
  fail,

  nl.

go2 => true.



%
% Edges version, unknown degree sequence
%
go3 ?=>

  data(edge,Graph,D),
  NumEdges = Graph.len, % number of edges
  N = D.len, % number of nodes
  
  % Graph, edges version, directed
  Graph = new_array(NumEdges,2),
  Graph :: 0..N,
  
  % degree sequence
  D = new_list(N),
  D :: 0..N, 

  degree_sequence_edges(D, Graph),

  Vars = Graph.vars ++ D,
  println(vars=Vars),
  solve(Vars),

  println(graph=Graph),
  println(d=D),
  nl,
  fail,

  nl.

go3 => true.


%
% Matrix version
%
degree_sequence_matrix(D, G) =>
  if var(G) then
    N = G.len
  else
    N = D.len
  end,
  foreach(I in 1..N)
    D[I] #= sum([G[I,J] #= 1 : J in 1..N])
  end.


%
% Edge versionq
%
degree_sequence_edges(D, G) =>
  foreach(I in 1..D.len) 
    D[I] #= sum([G[J,1] #= I : J in 1..G.len])
  end.


data(matrix,Graph,D) =>
  Graph = {{1,0,1,0},
           {1,1,0,1},
           {0,1,1,0},
           {0,0,1,1}},
  D = [2,3,2,2].


data(edge,Graph,D) =>
  Graph = {{1,2},
           {1,3},
           {1,4},
           {2,3},
           {2,4},
           {3,4}},
  D = [3,2,1,0].