# include <cstdio>
# include <cstdlib>
# include <iostream>
# include <vector>

using namespace std;

struct Arete {
  int depart;
  int arrivee;
  int valeur;
};

unsigned int nombre_sommets, nombre_aretes;
vector<Arete> aretes_retenues, aretes_possibles, aretes;

/*
 * Lit le fichier et remplit les variables globales.
 */
void lire_fichier(const char *nom_fichier) {
  FILE *fichier = fopen(nom_fichier, "r");
  char tampon[101] = "";
  Arete arete;
  unsigned int i;

  fscanf(fichier, "%u\n", &nombre_sommets);
  fscanf(fichier, "%u\n", &nombre_aretes);

  for(i = 0 ; i < nombre_aretes ; i++) {
    fgets(tampon, 100, fichier);

    sscanf(tampon, "%d %d %d\n",
           &(arete.depart), &(arete.arrivee), &(arete.valeur));
    aretes.push_back(arete);
  }
}

bool est_arete_avec_sommet(int sommet, Arete arete) {
  return (arete.depart == sommet || arete.arrivee == sommet) ? true : false;
}

// Nettoie le vecteur contenant les arêtes en enlevant celles qui sont inutiles.
void nettoyer_vecteur(int sommet_actuel,
                      vector<Arete> &vecteur,
                      vector<int> sommets_parcourus) {
  unsigned int i, j;
  bool test;
  vector<Arete> tmp;

  // Pour chaque élément de la pile
  for(i = 0 ; i < vecteur.size() ; i++) {
    test = true;

    // on retire les arêtes contenant des sommets déjà parcourus
    for(j = 0 ; j < sommets_parcourus.size() ; j++) {
      if((sommets_parcourus[j] == vecteur[i].depart
          && sommet_actuel == vecteur[i].arrivee)
      || (sommets_parcourus[j] == vecteur[i].arrivee
          && sommet_actuel == vecteur[i].depart)) {
        test = false;
      }
    }

    // Si l'arête ne contient pas de sommet déjà parcouru
    if(test) {
      tmp.push_back(vecteur[i]); // On l'ajoute au vecteur temporaire.
      cout << "### L'arc (" << vecteur[i].depart << ", ";
      cout << vecteur[i].arrivee << "), de longueur " << vecteur[i].valeur;
      cout << " est present dans le vecteur des aretes possibles." << endl;
    }
  }

  vecteur = tmp;
}

/* Trouve l'arc de poids le plus faible dans un vecteur d'arcs. */
int trouver_minimum(vector<Arete> &vecteur, Arete &minimum) {
  unsigned int i, i_min;
  vector<Arete> tmp;

  if(vecteur.size() == 0) return 1;

  i_min = 0;

  for(i = 1 ; i < vecteur.size() ; i++)
    if(vecteur[i].valeur < vecteur[i_min].valeur)
      i_min = i;

  minimum = vecteur[i_min];

  for(i = 0 ; i < vecteur.size() ; i++)
    if(i != i_min)
      tmp.push_back(vecteur[i]);

  vecteur.clear();
  vecteur = tmp;

  return 0;
}

/* Renvoie vrai si le sommet a déjà été rencontré, faux autrement. */
bool deja_rencontre(int sommet, vector<int> sommets_parcourus) {
  unsigned int i;

  for(i = 0 ; i < sommets_parcourus.size() ; i++)
    if(sommet == sommets_parcourus[i])
      return true;

  return false;
}

int main(void) {
  unsigned int i, poids = 0;
  int sommet_actuel = 0;
  Arete arete_minimale;
  string nom_fichier;

  vector<int> sommets_parcourus;

  cout << "Conversion de graphe en arbre." << endl;
  cout << "Emplacement du graphe : ";
  cin >> nom_fichier;

  lire_fichier(nom_fichier.c_str());

  /*
   * Pour chaque sommet, on ajoute les arêtes au tableau des possibilités,
   * à chaque itération, on ajoute au tableau final les arêtes les plus
   * courtes.
   */

  while(sommets_parcourus.size() < nombre_sommets) {
    sommets_parcourus.push_back(sommet_actuel);
    // On ajoute l'arête aux arêtes possibles.
    for(i = 0 ; i < nombre_aretes ; i++)
      if(aretes[i].depart == sommet_actuel
         || aretes[i].arrivee == sommet_actuel)
        aretes_possibles.push_back(aretes[i]);

    // On retire toutes les arêtes qui ne nous apportent rien.
    nettoyer_vecteur(sommet_actuel, aretes_possibles, sommets_parcourus);

    /*
     * Une fois que le tableau a été trié, il faut choisir le premier chemin
     * le plus court et le supprimer des chemins possibles.
     */
    
    if(trouver_minimum(aretes_possibles, arete_minimale)) break;

    aretes_retenues.push_back(arete_minimale);
    cout << "::: L'arete (" << arete_minimale.depart << ", ";
    cout << arete_minimale.arrivee << ") a ete ajoutee aux aretes retenues.";
    cout << endl;

    poids += arete_minimale.valeur;

    if(deja_rencontre(arete_minimale.depart, sommets_parcourus))
      sommet_actuel = arete_minimale.arrivee;
    if(deja_rencontre(arete_minimale.arrivee, sommets_parcourus))
      sommet_actuel = arete_minimale.depart;
  }

  cout << endl << "Resume :" << endl;
  cout << "Aretes retenues :" << endl;

  for(i = 0 ; i < aretes_retenues.size() ; i++) {
    cout << "--> (" << aretes_retenues[i].depart << ", ";
    cout << aretes_retenues[i].arrivee << "), de longueur ";
    cout << aretes_retenues[i].valeur << "." << endl;
  }

  cout << "--> Le poids final est de " << poids << "." << endl;

  return EXIT_SUCCESS;
}