<commit_before>import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;

public class Graphe {
	private int nbSommets;
	private boolean arcs[][];
	
	/**
	 * Constructeur vide d'un {@link Graphe}
	 */
	public Graphe() {
		nbSommets = 0;
		arcs = new boolean[nbSommets][nbSommets];
	}
	
	/**
	 * Constructeur d'un {@link Graphe} à partir du nombre de de sommets
	 * @param nbSommets : int
	 */
	public Graphe(int nbSommets) {
		this.nbSommets = nbSommets;
		arcs = new boolean[nbSommets][nbSommets];
	}
	
	/**
	 * Constructeur d'un {@link Graphe} à partir d'un fichier
	 * @param filename : String
	 */
	public Graphe(String filename) {
		int nbSommets = 0;
		try{
			FileInputStream fis 	=	new FileInputStream(filename); 
			InputStreamReader ipsr 	= 	new InputStreamReader(fis);
			BufferedReader br 		=	new BufferedReader(ipsr);
			String ligne;
			// Récupération du nombre de sommets
			while ((ligne=br.readLine())!=null){
				if(ligne.startsWith("p")) {
					String[] split_line = ligne.split(" ");
					nbSommets = Integer.parseInt(split_line[2]);
					break;
				}
			}
			this.nbSommets = nbSommets;
			arcs = new boolean[nbSommets][nbSommets];
			init();
			// Récupération des arcs
			while ((ligne=br.readLine())!=null){
				if(ligne.startsWith("e")) {
					String[] split_ligne = ligne.split(" ");
					int from = Integer.parseInt(split_ligne[1]);
					int to = Integer.parseInt(split_ligne[2]);
					// System.out.print("From " + from + " To " + to + "\n");
					arcs[from-1][to-1] = true;
					arcs[to-1][from-1] = true;
				}
			}
			br.close();
			ipsr.close();
			fis.close();
		} catch (Exception e) {
			System.out.println(e.toString());
		}
	}
	
	//	GETTERS
	public int getNbSommets() {
		return nbSommets;
	}
	
	public boolean[][] getArcs() {
		return arcs;
	}
	
	public boolean[] getArcs(int sommet) {
		return this.arcs[sommet];
	}
	
	//	SETTERS
	public void setNbSommets(int nbSommets) {
		this.nbSommets = nbSommets;
	}
	
	public void setArcs(boolean[][] arcs) {
		this.arcs = arcs;
	}
	
	public void setArcs(boolean[] arcs, int sommet) {
		this.arcs[sommet] = arcs;
	}
	
	@Override
	public String toString() {
		super.toString();
		String ch = "Sommets  : " + nbSommets + "\n" +
					"Arcs : " + getNbArcs() + "\n";
		for(int i=0 ; i<nbSommets ; i++) {
			ch += "| ";
			for(int j=0 ; j<nbSommets ; j++) {
				ch += (arcs[i][j] ? 1 : 0) + " | ";
			}
			ch += "\n";
		}
		return ch;
	}
	
	//	METHODES
	/**
	 * Initialise la matrice d'arcs à false
	 */
	public void init() {
		for(int i=0 ; i<nbSommets ; i++) {
			Arrays.fill(arcs[i], false);
		}
	}
	
	/**
	 * Teste si le {@link Graphe} courant est une clique
	 * @return <code>true</code> si le Graphe est une clique, <code>false</code> sinon
	 */
	public boolean isClique() {
		for(int i=0 ; i<nbSommets ; i++) {
			for(int j=0 ; j<nbSommets ; j++) { 
				if((i != j && arcs[i][j] == false))
					return false;
			}
		}
		return true;
	}
	
	/**
	 * Retourne le nombre d'arcs du {@link Graphe} courant
	 * @return int
	 */
	public int getNbArcs() {
		int nbArcs = 0;
		for(int i=0 ; i<nbSommets ; i++) {
			for(int j=0 ; j<nbSommets ; j++) {
				if(arcs[i][j] == true) nbArcs++;
			}
		}
		return (nbArcs/2);
	}
	
	/**
	 * Retourne le nombre d'arcs partant du sommet passé en paramètre
	 * @param sommet : int
	 * @return int
	 */
	public int getNbArcsFrom(int sommet) {
		int nbArcs = 0;
		for(int i=0 ; i< nbSommets ; i++) {
			if(arcs[sommet][i] == true) nbArcs++;
		}
		return nbArcs;
	}
	
	/**
	 * Retourne le nombre d'arcs absent du sommet passé en paramètre
	 * @param sommet : int
	 * @return int
	 */
	public int getNotNbArcsFrom(int sommet) {
		int notNbArcs = 0;
		for(int i=0 ; i< nbSommets ; i++) {
			if(i != sommet && arcs[sommet][i] == false) notNbArcs++;
		}
		return notNbArcs;
	}
	
	/**
	 * Retoune un graphe sans le sommet passé en paramètre
	 * @param sommet : int
	 * @return {@link Graphe}
	 */
	public Graphe getGrapheWithout(int sommet) {
		Graphe G = new Graphe(this.nbSommets-1);
		boolean new_arcs[][] = new boolean[G.nbSommets][G.nbSommets];
		/*
		int i;
		for(i=0 ; i<sommet ; i++) {
			new_arcs[i] = this.arcs[i];
		}
		// On saute le sommet et continue le traitement (si il y en a encore)
		for(i = sommet+1 ; i<this.nbSommets ; i++) {
			new_arcs[i-1] = this.arcs[i];
		} */
		for(int i=0 ; i<this.nbSommets ; i++) {
			for(int j=0 ; j<this.nbSommets ; j++) {
				if(i != sommet && j != sommet) {
					if (i > sommet) {
						if(j > sommet)
							new_arcs[i-1][j-1] = this.arcs[i][j];
						else 
							new_arcs[i-1][j] = this.arcs[i][j];
					} else {
						if(j > sommet)
							new_arcs[i][j-1] = this.arcs[i][j];
						else
							new_arcs[i][j] = this.arcs[i][j];
					}
				}
			}
		}
		G.setArcs(new_arcs);
		return G;
	}
	
	/**
	 * Retourne le sommet ayant le moins d'arcs
	 * @return sommet : int
	 */
	public int getWithLessArcs() {
		int sommet = -1;
		int min = 0;

		for(int i=0 ; i<nbSommets ; i++) {
			int nbNotArcs = getNotNbArcsFrom(i);
			if(nbNotArcs > min) {
				min = nbNotArcs;
				sommet = i;
			}
		}
		return sommet;
	}
	
	/**
	 * Retourne le sommet ayant le plus d'arcs
	 * @return sommet : int
	 */
	public int getWithMostArcs() {
		int sommet = -1;
		int max = 0;
		for(int i=0 ; i<nbSommets ; i++) {
			int nbArcs = getNbArcsFrom(i);
			if(nbArcs > max) {
				max = nbArcs;
				sommet = i;
			}
		}
		return sommet;
	}
	
	/**
	 * Retourne le sommet ayant le plus d'arcs parmi la liste de sommets passée en paramètre
	 * @param sommets : ArrayList<Integer>
	 * @return sommet : int
	 */
	public int getWithMostArcs(ArrayList<Integer> sommets) {
		int sommet = -1;
		int max = 0;
		for(int s : sommets) {
			int nbArcs = getNbArcsFrom(s);
			if(nbArcs > max) {
				max = nbArcs;
				sommet = s;
			}
		}
		return sommet;
	}
	
	/**
	 * Retourne les sommets voisins du sommet passé en paramètre
	 * @param sommet : int
	 * @return ArrayList<Integer>
	 */
	public ArrayList<Integer> getNeightbors(int sommet) {
		ArrayList<Integer> voisins = new ArrayList<>();
		for(int i=0 ; i<nbSommets ; i++) {
			if(arcs[sommet][i] == true) voisins.add(i);
		}
		return voisins;
	}
	
	/**
	 * Retoune un {@link Graphe} etant une clique à partir du {@link Graphe} G
	 * @param G : {@link Graphe}
	 * @return {@link Graphe}
	 */
	public static Graphe getClique(Graphe G) {
		if(G.isClique()) return G;
		else {
			Graphe Gaux = getClique(G.getGrapheWithout(G.getWithLessArcs()));
			return Gaux;
		}
	}
	
	public boolean isClique(ArrayList<Integer> sommets){
		for(Integer s1 : sommets){
			for(Integer s2 : sommets){
				if((s1 != s2 && arcs[s1][s2] == false)) 
					return false;
			}
		}
		return true;
	}
	
	// TODO Le traitement ne se fait que dans un seul sens, traiter les autres ?
	public boolean existingClique(int nbSom){
		System.out.println("Sommet : " + nbSom);
		for(int i = 0 ; i < nbSom ; ++i){ //i est le sommet qu'on ne comptabilise pas pour le moment
			ArrayList<Integer> sommets = new ArrayList<Integer>();
			for(int j = 0; j < nbSom; ++j){ // tous les sommets sauf i
				if(j != i) sommets.add(j);
			}
			if(isClique(sommets)) return true;
		}
		return false;
	}
	
	public int cliqueMax(){
		if(isClique()) return nbSommets; // Pas besoin de tester toute la matrice si le graphe d'origine est une clique
		for(int i = nbSommets ; i > 0 ; --i){	// Le traitement ne s'effectue pas sur tous les sommets ?
			if(existingClique(i)) return i;
			// TODO Attention on renvoie le sommet et non la taille de la Clique Maximale
		}
		return 0;
	}
	
	public static void traitement(Graphe G) {
		// Liste des sommets déjà compris comme partie de la clique
		ArrayList<Integer> compsub = new ArrayList<>(); 
		// Liste des sommets candidats, connectés avec tous les noeuds de compsub
		ArrayList<Integer> candidats = new ArrayList<>();
		// Liste des sommets déjà analysés, menant à une extension valide de compsub et qui ne devraient pas être utilisées
		ArrayList<Integer> not = new ArrayList<>();
		// On prend le premier sommet avec le plus de voisin
		int sommet;
		
		sommet = G.getWithMostArcs();
		System.out.println("Sommet avec le plus de voisins : " + sommet);
		// On l'ajoute à compsub
		compsub.add(sommet);
		
		// Voisins du sommet courant
		ArrayList<Integer> neightbors;
		neightbors = G.getNeightbors(sommet);
		System.out.println("Voisins de " + sommet + " : " + neightbors);
		// Les candidats susceptibles de former une clique sont les voisins du sommet
		candidats = neightbors;
		
		sommet = G.getWithMostArcs(candidats);
		compsub.add(sommet);
		
		System.out.println("Sommet avec le plus de voisins de " + candidats + " : " + sommet);
		neightbors = G.getNeightbors(sommet);
		candidats = intersection(candidats, neightbors);
		System.out.println("Voisins de " + sommet + " : " + neightbors);
		System.out.println("Intersection : " + candidats);
		
		sommet = G.getWithMostArcs(candidats);
		compsub.add(sommet);
		
		System.out.println("Sommet avec le plus de voisins de " + candidats + " : " + sommet);
		neightbors = G.getNeightbors(sommet);
		candidats = intersection(candidats, neightbors);
		System.out.println("Voisins de " + sommet + " : " + neightbors);
		System.out.println("Intersection : " + candidats);
		
		sommet = G.getWithMostArcs(candidats);
		compsub.add(sommet);
		
		/**
		 * Une clique est trouvée si :
		 * 	il n'y a pas plus de candidats ET
		 * 	il n'y a plus de sommets dans not (sinon ce n'est pas une clique maximale)
		 */
	}
	
	public static void traitement_recursif(Graphe G, ArrayList<Integer> P, ArrayList<Integer> X) {
		// Liste des sommets déjà compris comme partie de la clique
		ArrayList<Integer> compsub = new ArrayList<>(); 
		// Liste des sommets candidats, connectés avec tous les noeuds de compsub
		ArrayList<Integer> candidats = new ArrayList<>();
		// Liste des sommets déjà analysés, menant à une extension valide de compsub et qui ne devraient pas être utilisées
		ArrayList<Integer> not = new ArrayList<>();
		
		int sommet;
		
		if(P == null && X == null) {		// Premier tour de procédure	
			sommet = G.getWithMostArcs(); 	// On prend le sommet avec le plus de voisins<commit_msg>Traitement itératif<commit_after>import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;

public class Graphe {
	private int nbSommets;
	private boolean arcs[][];
	
	/**
	 * Constructeur vide d'un {@link Graphe}
	 */
	public Graphe() {
		nbSommets = 0;
		arcs = new boolean[nbSommets][nbSommets];
	}
	
	/**
	 * Constructeur d'un {@link Graphe} à partir du nombre de de sommets
	 * @param nbSommets : int
	 */
	public Graphe(int nbSommets) {
		this.nbSommets = nbSommets;
		arcs = new boolean[nbSommets][nbSommets];
	}
	
	/**
	 * Constructeur d'un {@link Graphe} à partir d'un fichier
	 * @param filename : String
	 */
	public Graphe(String filename) {
		int nbSommets = 0;
		try{
			FileInputStream fis 	=	new FileInputStream(filename); 
			InputStreamReader ipsr 	= 	new InputStreamReader(fis);
			BufferedReader br 		=	new BufferedReader(ipsr);
			String ligne;
			// Récupération du nombre de sommets
			while ((ligne=br.readLine())!=null){
				if(ligne.startsWith("p")) {
					String[] split_line = ligne.split(" ");
					nbSommets = Integer.parseInt(split_line[2]);
					break;
				}
			}
			this.nbSommets = nbSommets;
			arcs = new boolean[nbSommets][nbSommets];
			init();
			// Récupération des arcs
			while ((ligne=br.readLine())!=null){
				if(ligne.startsWith("e")) {
					String[] split_ligne = ligne.split(" ");
					int from = Integer.parseInt(split_ligne[1]);
					int to = Integer.parseInt(split_ligne[2]);
					// System.out.print("From " + from + " To " + to + "\n");
					arcs[from-1][to-1] = true;
					arcs[to-1][from-1] = true;
				}
			}
			br.close();
			ipsr.close();
			fis.close();
		} catch (Exception e) {
			System.out.println(e.toString());
		}
	}
	
	//	GETTERS
	public int getNbSommets() {
		return nbSommets;
	}
	
	public boolean[][] getArcs() {
		return arcs;
	}
	
	public boolean[] getArcs(int sommet) {
		return this.arcs[sommet];
	}
	
	//	SETTERS
	public void setNbSommets(int nbSommets) {
		this.nbSommets = nbSommets;
	}
	
	public void setArcs(boolean[][] arcs) {
		this.arcs = arcs;
	}
	
	public void setArcs(boolean[] arcs, int sommet) {
		this.arcs[sommet] = arcs;
	}
	
	@Override
	public String toString() {
		super.toString();
		String ch = "Sommets  : " + nbSommets + "\n" +
					"Arcs : " + getNbArcs() + "\n";
		for(int i=0 ; i<nbSommets ; i++) {
			ch += "| ";
			for(int j=0 ; j<nbSommets ; j++) {
				ch += (arcs[i][j] ? 1 : 0) + " | ";
			}
			ch += "\n";
		}
		return ch;
	}
	
	//	METHODES
	/**
	 * Initialise la matrice d'arcs à false
	 */
	public void init() {
		for(int i=0 ; i<nbSommets ; i++) {
			Arrays.fill(arcs[i], false);
		}
	}
	
	/**
	 * Teste si le {@link Graphe} courant est une clique
	 * @return <code>true</code> si le Graphe est une clique, <code>false</code> sinon
	 */
	public boolean isClique() {
		for(int i=0 ; i<nbSommets ; i++) {
			for(int j=0 ; j<nbSommets ; j++) { 
				if((i != j && arcs[i][j] == false))
					return false;
			}
		}
		return true;
	}
	
	/**
	 * Retourne le nombre d'arcs du {@link Graphe} courant
	 * @return int
	 */
	public int getNbArcs() {
		int nbArcs = 0;
		for(int i=0 ; i<nbSommets ; i++) {
			for(int j=0 ; j<nbSommets ; j++) {
				if(arcs[i][j] == true) nbArcs++;
			}
		}
		return (nbArcs/2);
	}
	
	/**
	 * Retourne le nombre d'arcs partant du sommet passé en paramètre
	 * @param sommet : int
	 * @return int
	 */
	public int getNbArcsFrom(int sommet) {
		int nbArcs = 0;
		for(int i=0 ; i< nbSommets ; i++) {
			if(arcs[sommet][i] == true) nbArcs++;
		}
		return nbArcs;
	}
	
	/**
	 * Retourne le nombre d'arcs absent du sommet passé en paramètre
	 * @param sommet : int
	 * @return int
	 */
	public int getNotNbArcsFrom(int sommet) {
		int notNbArcs = 0;
		for(int i=0 ; i< nbSommets ; i++) {
			if(i != sommet && arcs[sommet][i] == false) notNbArcs++;
		}
		return notNbArcs;
	}
	
	/**
	 * Retoune un graphe sans le sommet passé en paramètre
	 * @param sommet : int
	 * @return {@link Graphe}
	 */
	public Graphe getGrapheWithout(int sommet) {
		Graphe G = new Graphe(this.nbSommets-1);
		boolean new_arcs[][] = new boolean[G.nbSommets][G.nbSommets];
		/*
		int i;
		for(i=0 ; i<sommet ; i++) {
			new_arcs[i] = this.arcs[i];
		}
		// On saute le sommet et continue le traitement (si il y en a encore)
		for(i = sommet+1 ; i<this.nbSommets ; i++) {
			new_arcs[i-1] = this.arcs[i];
		} */
		for(int i=0 ; i<this.nbSommets ; i++) {
			for(int j=0 ; j<this.nbSommets ; j++) {
				if(i != sommet && j != sommet) {
					if (i > sommet) {
						if(j > sommet)
							new_arcs[i-1][j-1] = this.arcs[i][j];
						else 
							new_arcs[i-1][j] = this.arcs[i][j];
					} else {
						if(j > sommet)
							new_arcs[i][j-1] = this.arcs[i][j];
						else
							new_arcs[i][j] = this.arcs[i][j];
					}
				}
			}
		}
		G.setArcs(new_arcs);
		return G;
	}
	
	/**
	 * Retourne le sommet ayant le moins d'arcs
	 * @return sommet : int
	 */
	public int getWithLessArcs() {
		int sommet = -1;
		int min = 0;

		for(int i=0 ; i<nbSommets ; i++) {
			int nbNotArcs = getNotNbArcsFrom(i);
			if(nbNotArcs > min) {
				min = nbNotArcs;
				sommet = i;
			}
		}
		return sommet;
	}
	
	/**
	 * Retourne le sommet ayant le plus d'arcs
	 * @return sommet : int
	 */
	public int getWithMostArcs() {
		int sommet = -1;
		int max = 0;
		for(int i=0 ; i<nbSommets ; i++) {
			int nbArcs = getNbArcsFrom(i);
			if(nbArcs > max) {
				max = nbArcs;
				sommet = i;
			}
		}
		return sommet;
	}
	
	/**
	 * Retourne le sommet ayant le plus d'arcs parmi la liste de sommets passée en paramètre
	 * @param sommets : ArrayList<Integer>
	 * @return sommet : int
	 */
	public int getWithMostArcs(ArrayList<Integer> sommets) {
		int sommet = -1;
		int max = 0;
		for(int s : sommets) {
			int nbArcs = getNbArcsFrom(s);
			if(nbArcs > max) {
				max = nbArcs;
				sommet = s;
			}
		}
		return sommet;
	}
	
	/**
	 * Retourne les sommets voisins du sommet passé en paramètre
	 * @param sommet : int
	 * @return ArrayList<Integer>
	 */
	public ArrayList<Integer> getNeightbors(int sommet) {
		ArrayList<Integer> voisins = new ArrayList<>();
		for(int i=0 ; i<nbSommets ; i++) {
			if(arcs[sommet][i] == true) voisins.add(i);
		}
		return voisins;
	}
	
	/**
	 * Retoune un {@link Graphe} etant une clique à partir du {@link Graphe} G
	 * @param G : {@link Graphe}
	 * @return {@link Graphe}
	 */
	public static Graphe getClique(Graphe G) {
		if(G.isClique()) return G;
		else {
			Graphe Gaux = getClique(G.getGrapheWithout(G.getWithLessArcs()));
			return Gaux;
		}
	}
	
	public boolean isClique(ArrayList<Integer> sommets){
		for(Integer s1 : sommets){
			for(Integer s2 : sommets){
				if((s1 != s2 && arcs[s1][s2] == false)) 
					return false;
			}
		}
		return true;
	}
	
	// TODO Le traitement ne se fait que dans un seul sens, traiter les autres ?
	public boolean existingClique(int nbSom){
		System.out.println("Sommet : " + nbSom);
		for(int i = 0 ; i < nbSom ; ++i){ //i est le sommet qu'on ne comptabilise pas pour le moment
			ArrayList<Integer> sommets = new ArrayList<Integer>();
			for(int j = 0; j < nbSom; ++j){ // tous les sommets sauf i
				if(j != i) sommets.add(j);
			}
			if(isClique(sommets)) return true;
		}
		return false;
	}
	
	public int cliqueMax(){
		if(isClique()) return nbSommets; // Pas besoin de tester toute la matrice si le graphe d'origine est une clique
		for(int i = nbSommets ; i > 0 ; --i){	// Le traitement ne s'effectue pas sur tous les sommets ?
			if(existingClique(i)) return i;
			// TODO Attention on renvoie le sommet et non la taille de la Clique Maximale
		}
		return 0;
	}
	
	public static void traitement(Graphe G) {
		// Liste des sommets déjà compris comme partie de la clique
		ArrayList<Integer> compsub = new ArrayList<>(); 
		// Liste des sommets candidats, connectés avec tous les noeuds de compsub
		ArrayList<Integer> candidats = new ArrayList<>();
		// Liste des sommets déjà analysés, menant à une extension valide de compsub et qui ne devraient pas être utilisées
		ArrayList<Integer> not = new ArrayList<>();
		// On prend le premier sommet avec le plus de voisin
		int sommet;
		
		sommet = G.getWithMostArcs();
		System.out.println("Sommet avec le plus de voisins : " + sommet);
		// On l'ajoute à compsub
		compsub.add(sommet);
		
		// Voisins du sommet courant
		ArrayList<Integer> neightbors;
		neightbors = G.getNeightbors(sommet);
		System.out.println("Voisins de " + sommet + " : " + neightbors);
		// Les candidats susceptibles de former une clique sont les voisins du sommet
		candidats = neightbors;
		
		/**
		 * Une clique est trouvée si :
		 * 	il n'y a pas plus de candidats ET
		 * 	il n'y a plus de sommets dans not (sinon ce n'est pas une clique maximale)
		 */
		while(true) {
			sommet = G.getWithMostArcs(candidats);
			compsub.add(sommet);
			
			System.out.println("Sommet avec le plus de voisins de " + candidats + " : " + sommet);
			neightbors = G.getNeightbors(sommet);
			candidats = intersection(candidats, neightbors);
			System.out.println("Voisins de " + sommet + " : " + neightbors);
			System.out.println("Intersection : " + candidats);
			
			if(candidats.isEmpty() && not.isEmpty()) break;
		}
		System.out.println("Clique : " + compsub.size());
		
		
	}
	
	public static void traitement_recursif(Graphe G, ArrayList<Integer> P, ArrayList<Integer> X) {
		// Liste des sommets déjà compris comme partie de la clique
		ArrayList<Integer> compsub = new ArrayList<>(); 
		// Liste des sommets candidats, connectés avec tous les noeuds de compsub
		ArrayList<Integer> candidats = new ArrayList<>();
		// Liste des sommets déjà analysés, menant à une extension valide de compsub et qui ne devraient pas être utilisées
		ArrayList<Integer> not = new ArrayList<>();
		
		int sommet;
		
		if(P == null && X == null) {		// Premier tour de procédure	
			sommet = G.getWithMostArcs(); 	// On prend le sommet avec le plus de voisins
{'fraction_non_alphanumeric': 0.1420389461626575, 'fraction_numerical': 0.005279147367896807, 'mean_word_length': 3.024048096192385, 'pattern_counts': {'":': 0, '<': 95, '<?xml version=': 0, '>': 73, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '634812', 'n_tokens_mistral': 8845, 'n_tokens_neox': 7885, 'n_words': 2016}