// TP 2 : algorithme de Kruskal

clear

function [p,L]=Kruskal(N,arete_A,value_A,opt)

// ENTREE :
//    - N : nombre de sommets du graphe
//    - arete_A : liste des aretes
//    - value_A : liste des valuations des aretes
//    - opt : option (1: poids minimal, 2: poids maximal)
// VARIABLES INTERMEDIAIRES :
//    - nA : nombre d'aretes
//    - id_cc : vecteur de taille N contenant les identifiants de la composante connexe a 
//    laquelle appartient chaque sommet 
//    - rejet : Vecteur de taille nA (1 si arete rejetee, 0 sinon)
// SORTIE :
//    - p : poids de l'arbre couvrant de poids minimal 
//    - L : liste des aretes qui definissent l'arbre couvrant de poids minimal

// PREAMBULE : Rangement des aretes par ordre de poids croissant :
nA=size(value_A,1);

[tmp_value,tmp_order]=gsort(value_A);
if (opt==1) then
    V=tmp_value(nA:-1:1);
    k=tmp_order(nA:-1:1);
elseif(opt==2)
    V=tmp_value;
    k=tmp_order;
end
for i=1:nA
    A(i,1)=arete_A(k(i),1);
    A(i,2)=arete_A(k(i),2);
end
// A et V sont les listes d'aretes et de valuations classees par ordre de poids croissant

// On construit des composantes connexes au fur et a mesure
// QUESTION. En ajoutant une arete, dans quel cas obtient-on un cycle ?
// REPONSE. Un cycle est obtenu si les extremites de l'arete traitee appartiennent deja 
// a une meme composante connexe
// C'est cette remarque que nous allons exploiter pour savoir si l'on peut ajouter ou
// rejeter l'arete consideree

// Dans la suite, on appelle 'identifiant d'un sommet' un 'numero associe a la composante 
// connexe a laquelle appartient l'arete'

// Initialement, le graphe n'a aucune arete : les aretes n'appartiennent a aucune 
// composante connexe et l'identifiant de chaque sommet est assigne a 0 :
for i=1:N
    id_cc(i)=0;
end
// On considere que les deux extremites de l'arete no 1 definissent une composante 
// connexe a laquelle on assigne l'entier 1
id_cc(A(1,1))=1;
id_cc(A(1,2))=1;

// Vecteur qui stocke le rejet des aretes (1 si arete rejetee, 0 sinon)
rejet=zeros(nA,1);

for i=2:nA
    // Pour chaque extremite de l'arete i, determiner l'identifiant de la composante
    // connexe a laquelle elle appartient
    a=id_cc(A(i,1));
    b=id_cc(A(i,2));
    
    // Cas 1 : les deux extremites de l'arete consideree ne sont pas associees a une
    // composante connexe existante.
    // Alors, ces sommets definissent une nouvelle composante connexe dont le numero est 
    // nCC+1, ou nCC est le nombre de composantes connexes actuel.    
    if ((a==0)&(b==0)) then
        id_cc(A(i,1)) = max(id_cc)+1;
        id_cc(A(i,2)) = id_cc(A(i,1));
        p=p+V(i);
        L($+1)=A(i);
        
    end
    
    // Cas 2 : pour l'arete consideree, la premiere extremite est associe a une composante 
    // connexe existante tandis que l'autre extremite ne l'est pas. Alors, on associe le 
    // deuxieme sommet a la composante connexe a laquelle appartient le premier sommet
    if ((a~=0)&(b==0)) then
        id_cc(A(i,1)) = a
        p=p+V(i);
        L($+1)=A(i);
    end
    // Cas symetrique au precedent, en inversant le role des deux extremites.
    if ((a==0)&(b~=0)) then
        (id_cc(A(i,2))) = b
        p=p+V(i);
        L($+1)=A(i);
    end
    
    // Cas 3 : les deux extremites de l'arete appartiennent chacne a une composante 
    // connexe existante (pas necessairement la meme)
    if ((a~=0)&(b~=0)) then
        // Cas 3.1 : soit les deux composantes connexes sont differentes. Alors, il faut 
        // fusionner ces deux composantes en une seule (en ayant ajoute la nouvelle 
        // arete)
        if (a~=b) then
            (for k=1:nA
                id_cc(A(1,k))=min(a,b);
             end
                )
             
            p=p+V(i)];
            L($+1)=A(i);
        else
        // Cas 3.2 : soit les deux composantes connexes sont identiques. Alors, il faut 
        // rejeter l'arete, i.e. ne rien faire. L'information sur le rejet de l'arete
        // est toutefois sauvegardee dans le vecteur 'rejet'
            (rejet[i]=1)
        end
    end
end

// L : liste des aretes retenues dans l'arbre couvrant de poids minimal :
// p : Poids de l'arbre couvrant de poids minimal

()

endfunction

// EXEMPLE DU COURS :

// Definition du graphe oriente :
//     - nombre de sommets
//     - definition des aretes par liste des aretes
//       Convention : l'arete est decrite par ij avec i<j
Ng=5;
arete_Ag=[1,2; 1,3; 1,4; 1,5; 2,3; 2,4; 2,5; 3,5; 4,5];
value_Ag=[  3;   2;   7;   3;   5;   6;   8;   4;   9];
[p,L]=Kruskal(Ng,arete_Ag,value_Ag,1)

// EXEMPLE DU COURS :
// Definition du graphe oriente :
//     - nombre de sommets
//     - definition des aretes par liste des aretes
//       Convention : l'arete est decrite par ij avec i<j

//  1 : Bordeaux (Clermont-Ferrand, Lyon, Nantes, Paris, Pau, Toulouse)
//  2 : Brest (Rennes)
//  3 : Chambery (Lyon)
//  4 : Clermont-Ferrand (Bordeaux(*), Lyon, Paris)
//  5 : Lille (Paris, Rennes, Strasbourg)
//  6 : Lyon (Bordeaux(*), Chambery(*), Clermont-Ferrand(*), Marseille, Montpellier, Nice, 
//            Paris, Strasbourg, Toulouse)
//  7 : Marseille (Lyon(*), Montpellier, Nice)
//  8 : Montpellier (Lyon(*), Marseille(*), Toulouse)
//  9 : Nantes (Bordeaux(*), Paris, Rennes)
// 10 : Nice (Lyon(*), Marseille(*))
// 11 : Paris (Bordeaux(*), Clermont-Ferrand(*), Lille(*), Lyon(*), Nantes(*), Strasbourg)
// 12 : Pau (Bordeaux(*), Toulouse)
// 13 : Rennes (Brest(*), Lille(*), Nantes(*))
// 14 : Strasbourg (Lille(*), Lyon(*), Paris(*))
// 15 : Toulouse (Bordeaux(*), Lyon(*), Montpellier(*), Pau(*))
Ng=15;
arete_Ag=[1,4; 1,6; 1,9; 1,11; 1,12; 1,15; 2,13; 3,6; 4,6; 4,11; 5,11; 5,13; 5,14; 6,7; 6,8; 6,10; 6,11; 6,14; 6,15; 7,8; 7,10; 8,15; 9,11; 9,13; 11,14; 12,15];
value_Ag=[ 35;  35;  21;   40;   14;   15;   12;  15;  13;   30;   15;   40;   30;  20;  20;   35;   30;   30;   35;  12;   15;   17;   25;    6;    35;    12];
[p,L]=Kruskal(Ng,arete_Ag,value_Ag,1);

// EXEMPLE DE L'EXERCICE 2.7 :

Ng=10;
arete_Ag=[1,2; 1,4; 2,3; 2,5; 3,6; 3,9; 4,5; 4,10; 5,7; 5,9; 6,8; 6,10; 7,8; 7,10; 8,9];
value_Ag=[  8;   3;   4;   5;   1;   5;   2;    1;   3;   2;   5;    6;   4;    6;   2];
[p,L]=Kruskal(Ng,arete_Ag,value_Ag,1);

// EXEMPLE de L'EXERCICE 2.10

Ng=6;
arete_Ag=[1,2; 1,3; 1,4; 1,5; 1,6; 2,3; 2,4; 2,5; 2,6; 3,4; 3,5; 3,6; 4,5; 4,6; 5,6];
value_Ag=[ 12;   9;   5;   7;   6;   1;  14;  10;  11;   8;  15;   3;   4;   2;  13];
[p,L]=Kruskal(Ng,arete_Ag,value_Ag,1);


// EXEMPLE de L'EXERCICE 2.9

Ng=10;

arete_Ag=[1,2; 1,3; 1,4; 2,3; 2,5; 2,6; 3,4; 3,5; 3,6; 4,6; 5,6; 5,7; 5,8; 6,7; 6,8; 6,9; 7,8; 7,10; 8,9; 8,10; 9,10];
value_Ag=[  3;   3;   2;   2;  10;   3;   1;   8;   2;   4;   2;   9;   7;   5;   2;   3;   2;    2;   1;    5;    2];
[p,L]=Kruskal(Ng,arete_Ag,value_Ag,1);




