import java.util.Vector;
import java.lang.Integer;
import java.lang.Double;

public class Graphe{

    int NS; //nombre de sommets 
    int[][] dico; //dico qui contient les successeurs
    int NA; // nombre d'arcs
    int[] orig; //tableau pour les origines des arcs
    int[] extr; //tableau pour les extrémités des arcs

    boolean[] marque; //tableau pour marquer les sommets explorés
    double[] distance; //tableau des distances au sommet source du parcours
    int[] peres; //tableau stockant la suite des peres pour les chemins les plus courts en partant du sommet source

    //constructeur à partir du dictionnaire
    Graphe(int dico[][]){
	this.dico = dico;
	this.NS = dico.length;
	initialiseNA();
	initialiseArcs();
    }

    //constructeur à partir des arcs
    Graphe(int NS, int[] orig, int[] extr){
	this.NS = NS;
	this.orig = orig;
	this.extr=extr;
	this.NA = orig.length;
	initialiseDico();
    }

    //affiche les successeurs du sommet s
    void afficheSuccesseurs(int s){
	System.out.print(s+" : ");
	for (int i =0; i<dico[s-1].length;i++){
	    System.out.print(dico[s-1][i]+" ");
	}
	System.out.println();
    }

    //affiche le graphe
    void affiche(){
	//affiche le dico
	System.out.println("Dictionnaire du graphe :");
	for (int i =0; i<NS; i++){
	    afficheSuccesseurs(i+1);
	}
	//affiche les tableaux représentants les arcs
	System.out.println();
	System.out.println("Arcs :");
	System.out.print("orig | ");
	for (int i=0; i<NA;i++){
	    System.out.print(orig[i]+" | ");
	}
	System.out.println();
	System.out.print("extr | ");
	for (int i=0; i<NA;i++){
	    System.out.print(extr[i]+" | ");
	}
	System.out.println();
    }

    //affiche les prédécesseurs du sommet s
    void affichePredecesseurs(int s){
	System.out.print("Prédécesseurs de "+s+ " : ");
	for (int i = 0; i< NS; i++){
	    for (int j =0; j< dico[i].length;j++){
		if (dico[i][j]==s){
		    System.out.print((i+1)+" ");
		    break;
		}
	    }
	}
	System.out.println();
    }

    //initialise NA à partir de t
    void initialiseNA(){
	NA = 0;
	for(int i = 0; i< NS; i++){
	    NA = NA+  dico[i].length;
	}
    }

    //initialise les tableaux orig et extr à partir de t
    void initialiseArcs(){
	orig = new int[NA];
	extr = new int[NA];
	int k =0; //indice de l'arc
	for (int i = 0; i< NS; i++){
	    for (int j =0; j< dico[i].length;j++){
		orig[k] = i+1;
		extr[k]=dico[i][j];
		k++;
	    }
	}
    }

    //calcul Matrice incidence à partir des arcs
    int[][] matriceIncidence(){
	int[][] m = new int[NS][NS];
	for (int k =0; k<NA;k++){
	    m[orig[k]-1][extr[k]-1] =1;
	}
	return(m);
    }

    //intialise Dico à partir des arcs via la matrice d'incidence
    void initialiseDico(){
	dico = new int[NS][];
	int[][] m = matriceIncidence();
	int nb;
	int k;
	for(int i =0; i<NS;i++){
	    //calcul le nombre de successeurs du sommet i+1
	    nb =0;
	    for(int j = 0; j<NS;j++){
		nb = nb+m[i][j];
	    }
	    //creer la liste des successeurs du sommet i+1
	    dico[i] = new int[nb];
	    k=0;
	    for(int j = 0; j<NS;j++){
		if (m[i][j]==1){
		    dico[i][k] = j+1;
		    k++;
		}
	    }
	}
    }

    void initMarques(){
	marque = new boolean[NS];
	for(int i =0; i<NS;i++) marque[i] =false;
    }

    void marquer(int s){
	marque[s-1] = true;
    }

    //parcours en largeur le graphe à partir du sommet deb
    void parcours (int deb){
	initMarques();
	initDistance(deb);
	initPeres();
	Vector<Integer> file = new Vector<Integer>();
	file.add(deb);
	marquer(deb);
	System.out.println("Parcours à partir du sommet "+deb);
	while(!file.isEmpty()){
	    int s = file.firstElement();
	    file.remove(0);
	    for(int  j=0; j<dico[s-1].length; j++){
		int t = dico[s-1][j]; //un des successeurs de s
		if(!marque[t-1]) {
		    file.add(t);
		    marquer(t);
		    distance[t-1]=distance[s-1]+1;
		    peres[t-1]= s;
		    System.out.print("Sommet "+t+" exploré.");
		    System.out.println(" Ce sommet est à distance "+ distance[t-1]+ " de "+deb);
		    afficheChemin(t);
		}
	    } 
	}
    }

    void initDistance(int deb){
	distance = new double[NS];
	for (int i =0;i<NS;i++){
	    distance[i] = Double.POSITIVE_INFINITY;
	}
	distance[deb-1]=0;
    }

    void initPeres(){
	peres = new int[NS];
    }

    //méthode utilisée dans parcours pour afficher un chemin minimal du sommet de départ vers t
    void afficheChemin(int t){
	if (distance[t-1]== Double.POSITIVE_INFINITY){
	    System.out.println("Le sommet "+t+" n'est pas accessible à partir du sommet de départ");
	    return;
	}
	String result = t+".";
	while (!(distance[t-1]==0)){
	    t = peres[t-1];
	    result = t+ " -> " +result;
	}
	System.out.println("Un chemin de longueur minimal : "+result);
    }

    public static void main(String[] arg){
	System.out.println("Graphe du TD");
	int [][] dico={{2,4,5}, {4,6}, {5,6},{2}, {3,4,6}, {4}};
	Graphe g = new Graphe(dico);
	g.affiche();
	System.out.println();
	g.parcours(1);
	System.out.println();
	g.parcours(5);
    }
}