/** 
Generator - generates uniform random binary constraint satisfaction problems
<br> by Zheying Yang
<br> Department of Computer Science and Engineering,
<br> University of Nebraska-Lincoln 
<br> October 12, 2002
<br>
<br> SUMMARY OF CLASS MEMBER VARIABLES
<br> int			N=number of varibles
<br> int			D=max domain size
<br> int			C=number of constraint
<br> int			T=number of allowed tuples
<br> int			sol[]=build_in solution for CSP (at least one solution)
<br> GConstraint	constr[]=objects of class GConstraint @see GConstraint
@author ZheYing (Jane) YANG
@version 2002.10	No furture revisionns planned
*/
 
import java.util.*;     
public class Generator{
	int N,D,C,T;
	int [] sol;
	GConstraint [] constr;
/**
Creates a new Generator object and insert a randomly generated solution 
@param int			N number of varibles
@param int			D max domain size
@param int			C number of constraint
@param int			T number of allowed tuples
@return Generator object which is a CSP instance
*/	
public	Generator(int n, int d, int c, int t){
		N=n;
		D=d;
		C=c;
		T=t;	
		sol=new int[n];
		constr=new GConstraint[c];
		for(int i=0; i<C; i++){
			constr[i]=new GConstraint(t);
			}
			
		setSolution();
		setConstraints();
		adjustConstraints();
		}
/**
Generate a solution, which can be inserted in CSP to guarantee at least one solution  
<br>solution is randomly generated
*/		
    public void	setSolution(){
   		Random r=new Random(System.currentTimeMillis());    	
    	for(int i=0; i<N; i++){
    		sol[i]=(int) (r.nextDouble()*(double)D);	    	
    			}
    		}
/**
Check if constraint Cij exists or not 
@param c1 index i in Cij
@param c2 index j in Cij
@return false if Cij exists, true otherwise
*/    
    private boolean checkConstraint(int c1, int c2){
    	boolean flg=true;
    	for(int i=0;i<C;i++){
    		if(c1==constr[i].I && c2==constr[i].J) {flg=false; break;}
    		}
    	return flg;   	
    	}	
/**
Set a set of constraints randomly
<br>Make sure i &lt j in Cij and no Cji in the same set
*/    	
    public void setConstraints(){
    	int c1, c2;
    	Random r=new Random(System.currentTimeMillis());    	
    	for(int i=0; i<C; i++){
    	    while(true){
	    		c1=(int) (r.nextDouble()*(double)N);	
    			c2=(int) (r.nextDouble()*(double)N);	
    			if(c1 < c2 && checkConstraint(c1, c2)) break;
    			}
    	constr[i].I=c1;	
    	constr[i].J=c2;
    		
    	for(int j=0; j<T; j++){
    			constr[i].p1[j]=(int) (r.nextDouble()*(double)D);
    			constr[i].p2[j]=(int) (r.nextDouble()*(double)D);
    			}
    		}	
    	}
/**
Adjust constraint set to insert a solution
*/    	
    public void adjustConstraints(){
    	Random r=new Random(System.currentTimeMillis());    	
        int s1, s2, p;
    	for(int i=0; i<C; i++){
    		s1=sol[constr[i].I];
    		s2=sol[constr[i].J];
    		p=(int) (r.nextDouble()*(double)T);
    		constr[i].p1[p]=s1;
    		constr[i].p2[p]=s2;
    		}
    	}
    	
/**
Show solution on standard output (Monitor)
*/    	    	
    public void showSolution(){
    	for(int i=0; i<N; i++)
    		System.out.print(sol[i]+" ");
    		
    	}
    	
/**
Show generated CSP on standard output (Monitor)
<br>number of variables
<br>variable &#43 domain content
<br>&#126
<br>i,j (in constriant Cij) &#43 constriant content 
<br>&#126
*/    	
    public void show(){
    	System.out.println(""+N);
    	for (int i=0; i<N; i++){
    		System.out.print(""+i+" ");
    		for(int j=0; j<D; j++){    			
    			if(j==D-1) System.out.print(""+j+"\n");
    			else System.out.print(""+j+" ");
    			}    		
    		}
    	
    	for(int i=0; i<C; i++){
    		System.out.print(""+constr[i].I+" "+constr[i].J+" ");
    		for(int j=0; j<T; j++){
    			if(j==T-1) System.out.print(""+constr[i].p1[j]+" "+constr[i].p2[j]+"\n");
    			else System.out.print(""+constr[i].p1[j]+" "+constr[i].p2[j]+" ");
    			}    		
    		}
    	}	
/**
main function
*/    		
    public static void main(String args[]){
    	if(args.length != 4) System.out.println("Usage: java Generator N D C T");
    	int N, D, C, T;
    	N=Integer.parseInt(args[0]);
    	D=Integer.parseInt(args[1]);
    	C=Integer.parseInt(args[2]);
    	T=Integer.parseInt(args[3]);
    	
    	Generator g=new Generator(N,D,C,T);
    	g.show();
    //	g.showSolution();    	
    	}
    	    			    		
	}//end class Generator
	
/**
 * Data structure for constraint
 * <br> SUMMARY OF CLASS MEMBER VARIABLES
 * <br> int	I=index i in Cij
 * <br> int	J=index j in Cij
 * <br> int p1[]=first value in constraint pair 
 * <br> int	p2[]=second value in constrant pair
 */		
class GConstraint{
	public int I,J;
	public int [] p1;
	public int [] p2;
	
	GConstraint(int t){
		p1=new int[t];
		p2=new int[t];		
		}	
	}//end class Constraint