//Implementation of the rules to build level-(k+1) generators from level-k generators
//Based on the code by Steven Kelk http://homepages.cwi.nl/~kelk/lev3gen/
//Philippe Gambette - http://www.lirmm.fr/~gambette/ProgramGenerators

import java.io.*;
import java.util.*;
import java.lang.*;

import java.math.BigInteger;

public class Generators
{
	public static final boolean DEBUG = false;
	public static Vector currentLevel;
	public static Vector previousLevel;
	public static int perm[][][];
	public static int mycount;
	public static int countTested;	
	public static int countPrev;	
	public static int l;
	public static FileWriter output;
	public static int myfac(int f)
	{
		if( f <= 2 ) return f;
		else return f * myfac(f-1);
	}	
	public static void makePerms()
	{
		int top = 8;
		perm = new int [top+1][][];
		for( int x=1; x<=top; x++ ){
			PermutationGenerator pg = new PermutationGenerator(x);
			int t = myfac(x);
			perm[x] = new int[t][x];

			int at = 0;

			while( pg.hasMore() ){
				int v[] = pg.getNext();
				for( int l=0; l < x; l++ ) perm[x][at][l] = v[l];
				at++;
			}
		}	

		/*
		for(int s=1; s<=top; s++ ){
			System.out.println("Permutations on "+s+" elements:");
			int todo = perm[s].length;
			for( int k=0; k < todo; k++ ){
				for( int t=0; t<s; t++ ){
					System.out.print(perm[s][k][t]);
					}
				System.out.println();
				}

			}
		 */
	}


	public static void main( String[] args )
	{
		l=4;
		countPrev=0;
		countTested=0;
		mycount=0;
		try{
			output = new FileWriter("C:\\These\\Generateurs\\Output.txt"); 
			output.write("# Beginning of level-1 generators !\n");
        } catch (FileNotFoundException e) {
             e.printStackTrace();
        } catch (IOException e) {
             e.printStackTrace();
        }
		buildGenerators(l);
		try{
			output.write("# End of level-"+l+" generators !");
			output.close();
        } catch (FileNotFoundException e) {
             e.printStackTrace();
        } catch (IOException e) {
             e.printStackTrace();
        }

	}

	//Build generators of level l (recursively by building generators of level l-1).
	public static Vector buildGenerators(int l)
	{
		int etape=0;
		if (l==1){
			Graph G1 = new Graph(2);
			G1.adj[0][1]=2;
			G1.v20=1;
			G1.v21=0;
			G1.dumpGraph(mycount++);
			countTested++;

			previousLevel = new Vector();	
			previousLevel.add(G1);
			return previousLevel;
		} else {
			makePerms();
			int nbPreviousLevel=0;
			//System.out.println("Beginning of level-"+l-1+" generators :");
			previousLevel=buildGenerators(l-1);
			System.out.println("End of level-"+(l-1)+" generators !");
			System.out.println("===================================");
			System.out.println("Beginning of level-"+l+" generators :");
			try{
				output.write("# End of level-"+(l-1)+" generators !\n\n# Beginning of level-"+l+" generators :\n");
	        } catch (FileNotFoundException e) {
	             e.printStackTrace();
	        } catch (IOException e) {
	             e.printStackTrace();
	        }

			currentLevel = new Vector();
			Enumeration prevLevel = previousLevel.elements();
			//For any level-(k-1) generator:
			while( prevLevel.hasMoreElements() ){
				Graph prevGraph=(Graph) prevLevel.nextElement();
				if( !prevGraph.biconnected() ){
					System.out.println("Problem: the graph is not biconnected!");
				} else {
					//For any couple of arcs apply R1:
					for(int e1i=0;e1i<prevGraph.v;e1i++){
						for(int e1j=0;e1j<prevGraph.v;e1j++){

							if (prevGraph.adj[e1i][e1j]>0) {
								for(int e2i=0;e2i<prevGraph.v;e2i++){
									for(int e2j=0;e2j<prevGraph.v;e2j++){

										if ((prevGraph.adj[e2i][e2j]>0)) {
											if ((e2i==e1i) && (e2j==e1j) && (prevGraph.adj[e1i][e1j]==2)){
												//Create a copy of prevGraph with three more nodes
												Graph newGraph=prevGraph.augment(3);
												newGraph.v20=prevGraph.v20+1;
												String theName="R1m(G_"+(countPrev+nbPreviousLevel)+",("+e1i+","+e1j+"),("+e2i+","+e2j+"))";
												if (DEBUG)
													System.out.println(mycount+"/"+countTested+":"+theName);
												newGraph.ruleR1multi(e1i,e1j,e2i,e2j);
												countTested++;
												
												if( !newGraph.containedIn(currentLevel) ){
													currentLevel.addElement(newGraph);
													newGraph.dumpGraph(mycount++,theName);
												}

												//Create a copy of prevGraph with two more nodes
												newGraph=prevGraph.augment(2);
												newGraph.v21=prevGraph.v21+1;
												theName="R2m(G_"+(countPrev+nbPreviousLevel)+",("+e1i+","+e1j+"),("+e2i+","+e2j+"))";
												if (DEBUG)
													System.out.println(mycount+"/"+countTested+":"+theName);
												newGraph.ruleR2multi(e1i,e1j,e2i,e2j);
												countTested++;
												
												if( !newGraph.containedIn(currentLevel) ){
													currentLevel.addElement(newGraph);
													newGraph.dumpGraph(mycount++,theName);
												}

											}

											if ((e2i*prevGraph.v+e2j)<=(e1i*prevGraph.v+e1j))
											{
												etape++;
												//Create a copy of prevGraph with three more nodes
												Graph newGraph=prevGraph.augment(3);
												newGraph.v20=prevGraph.v20+1;
												String theName="R1(G_"+(countPrev+nbPreviousLevel)+",("+e1i+","+e1j+"),("+e2i+","+e2j+"))";
												if (DEBUG)
													System.out.println(mycount+"/"+countTested+":"+theName);
												newGraph.ruleR1(e1i,e1j,e2i,e2j);
												countTested++;

												if( !newGraph.containedIn(currentLevel) )
												{
													currentLevel.addElement(newGraph);
													newGraph.dumpGraph(mycount++,theName);
												}
											}

											//Apply R2 if you can
											if (!prevGraph.directedPath(e2j,e1i)){
												//Create a copy of prevGraph with one more node
												Graph newGraph=prevGraph.augment(2);
												newGraph.v21=prevGraph.v21+1;
												String theName="R2(G_"+(countPrev+nbPreviousLevel)+",("+e1i+","+e1j+"),("+e2i+","+e2j+"))";
												if (DEBUG)
													System.out.println(mycount+"/"+countTested+":"+theName);
												newGraph.ruleR2(e1i,e1j,e2i,e2j);
												countTested++;

												if( !newGraph.containedIn(currentLevel)){
													currentLevel.addElement(newGraph);
													newGraph.dumpGraph(mycount++,theName);
												}
											}

										}
									}
								}
							}
						}
					}
					//For any couple (hybrid node,arc) apply R1 & R2:
					for(int i=0;i<prevGraph.v;i++){
						if ((prevGraph.getInDegree(i)>1) && (prevGraph.getOutDegree(i)==0)){
							for(int e1i=0;e1i<prevGraph.v;e1i++){
								for(int e1j=0;e1j<prevGraph.v;e1j++){
									if (prevGraph.adj[e1i][e1j]>0) {
										//Create a copy of prevGraph with two more nodes
										Graph newGraph=prevGraph.augment(2);
										newGraph.v21=prevGraph.v21+1;
										String theName="R1(G_"+(countPrev+nbPreviousLevel)+","+i+",("+e1i+","+e1j+"))";
										if (DEBUG)
											System.out.println(mycount+"/"+countTested+":"+theName);
										newGraph.ruleR1(i,e1i,e1j);
										countTested++;
										if( !newGraph.containedIn(currentLevel) ){
											currentLevel.addElement(newGraph);
											newGraph.dumpGraph(mycount++,theName);
										}

										//Apply R2 if you can
										if (!prevGraph.directedPath(e1j,i)){
											//Create a copy of prevGraph with one more node
											newGraph=prevGraph.augment(1);
											newGraph.v20=prevGraph.v20-1;
											newGraph.v21=prevGraph.v21+2;
											theName="R2(G_"+(countPrev+nbPreviousLevel)+","+i+",("+e1i+","+e1j+"))";
											if (DEBUG)
												System.out.println(mycount+"/"+countTested+":"+theName);
											newGraph.ruleR2(i,e1i,e1j);
											countTested++;

											if( !newGraph.containedIn(currentLevel) ){
												currentLevel.addElement(newGraph);
												newGraph.dumpGraph(mycount++,theName);
											}
										}
									}								
								}
							}						
						}
					}

					//For any couple (hybrid node,hybrid node) apply R1:
					for(int i=0;i<prevGraph.v;i++){
						if ((prevGraph.getInDegree(i)>1) && (prevGraph.getOutDegree(i)==0)){
							for(int j=i+1;j<prevGraph.v;j++){
								if ((prevGraph.getInDegree(j)>1) && (prevGraph.getOutDegree(j)==0)){
									//Create a copy of prevGraph with one more node
									Graph newGraph=prevGraph.augment(1);
									newGraph.v20=prevGraph.v20-1;
									newGraph.v21=prevGraph.v21+2;
									String theName="R1(G_"+(countPrev+nbPreviousLevel)+","+i+","+j+")";
									if (DEBUG)
										System.out.println(mycount+"/"+countTested+":"+theName);
									newGraph.ruleR1(i,j);
									countTested++;
									
									if( !newGraph.containedIn(currentLevel) ){
										currentLevel.addElement(newGraph);
										newGraph.dumpGraph(mycount++,theName);
									}								
								}	
							}						
						}
					}

				}
				nbPreviousLevel++;
			}
			
			countPrev+=nbPreviousLevel;
			System.out.println("Nb:"+countTested);
			return currentLevel;
		}
	}
}