/*
Le fichier a été renommé de .php à .txt et la balise ouvrante PHP retirée pour que
le serveur web puisse le restituer sans l’exécuter. Le lecteur doit remettre la balise
ouvrante PHP pour pouvoir l’exécuter.
*/
/*
This file is source code accompanying "Diviser n'est pas régner ?"
scientific article.

This source code is free software: you can redistribute it
and/or modify it under the terms of the GNU Lesser General Public
License as published by the Free Software Foundation,
either version 3 of the License,
or (at your option) any later version.

This source code is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU Lesser General Public License for more details.

A copy of the GNU Lesser General Public License is not included.
Please see <http://www.gnu.org/licenses/>.

©Copyright 2022 Laurent Lyaudet
*/



$grapheDeTest = [
  "listeDeSommets" => [
    "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k",
    "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v"
  ],
  "listeDesAretes" => [
    ["a", "b"], ["a", "c"], ["a", "d"],
    ["b", "d"], ["b", "e"],
    ["c", "d"], ["c", "f"],
    ["e", "h"], ["e", "k"],
    ["f", "i"], ["f", "l"],
    ["g", "h"], ["g", "i"], ["g", "j"],
    ["h", "j"],
    ["i", "j"],
    ["k", "l"], ["k", "q"],
    ["l", "r"],
    ["m", "n"], ["m", "o"], ["m", "p"],
    ["n", "p"], ["n", "q"],
    ["o", "p"], ["o", "r"],
    ["q", "t"],
    ["r", "u"],
    ["s", "t"], ["s", "u"], ["s", "v"],
    ["t", "v"],
    ["u", "v"],
  ]
];



function chargerUnGraphe($graphe){
  $graphe["nombreDeSommets"] = count($graphe["listeDeSommets"]);
  $sommetsDedupliques = array_unique($graphe["listeDeSommets"]);
  if($graphe["nombreDeSommets"] != count($sommetsDedupliques)){
    throw Exception(
      "Il y a des sommets dupliqués dans la liste."
    );
  }

  // La liste de sommets correspond aussi avec PHP
  // avec l'application/bijection de l'identifiant
  // interne entier d'un sommet vers son libellé.
  // Pour parser la liste d'arêtes,
  // on veut aussi la bijection réciproque.
  $graphe["etiquetteDeSommetVersIdentifiantInterne"] = array_flip(
    $graphe["listeDeSommets"]
  );
  $etiquetteVersIdentifiantInterne
    = &$graphe["etiquetteDeSommetVersIdentifiantInterne"]
  ;

  // On initialise des listes d'adjacences vides.
  $graphe["listesDadjacences"] = [];
  $listesDadjacences = &$graphe["listesDadjacences"];
  for($i = 0; $i < $graphe["nombreDeSommets"]; ++$i){
    $listesDadjacences[$i] = [];
  }
  // Puis on les remplit.
  foreach($graphe["listeDesAretes"] as $arete){
    if(!isset($etiquetteVersIdentifiantInterne[$arete[0]])){
      throw Exception(
        "Le sommet ".$arete[0]." est référencé dans une arête"
       ." mais n'est pas listé dans les sommets."
      );
    }
    $idDuSommet1 = $etiquetteVersIdentifiantInterne[$arete[0]];
    if(!isset($etiquetteVersIdentifiantInterne[$arete[1]])){
      throw Exception(
        "Le sommet ".$arete[1]." est référencé dans une arête"
       ." mais n'est pas listé dans les sommets."
      );
    }
    $idDuSommet2 = $etiquetteVersIdentifiantInterne[$arete[1]];
    $listesDadjacences[$idDuSommet1] []= $idDuSommet2;
    $listesDadjacences[$idDuSommet2] []= $idDuSommet1;
  }

  // On calcule le degré minimum et le degré maximum du graphe
  $graphe["degreMinimum"] = count($listesDadjacences[0]);
  $graphe["degreMaximum"] = count($listesDadjacences[0]);
  for($i = 1; $i < $graphe["nombreDeSommets"]; ++$i){
    $graphe["degreMinimum"] = min(
      $graphe["degreMinimum"],
      count($listesDadjacences[$i])
    );
    $graphe["degreMaximum"] = max(
      $graphe["degreMaximum"],
      count($listesDadjacences[$i])
    );
  }
  return $graphe;
}



$grapheCharge = chargerUnGraphe($grapheDeTest);
//var_dump($grapheCharge);
echo(
  "Chargement d'un graphe à ".$grapheCharge["nombreDeSommets"]
 ." sommets"
 ." de degré minimum ".$grapheCharge["degreMinimum"]
 ." et de degré maximum ".$grapheCharge["degreMaximum"].".\n"
);



function listeDeSommetsInternePourAffichage($graphe, $liste){
  $identifiantVersEtiquette = $graphe["listeDeSommets"];
  $listeDeSommetsEtiquetes = [];
  foreach($liste as $sommet){
    $listeDeSommetsEtiquetes []=
      $identifiantVersEtiquette[$sommet]
    ;
  }
  return $listeDeSommetsEtiquetes;
}



/**
 * Fonction qui calcule les boules de rayon 2
 * centrées sur tous les sommets d'un graphe.
 * Cette fonction a une complexité en temps et en espace,
 * dans le pire cas :
 * - linéaire sur les graphes de degré borné,
     sur lesquels l'article se focalise,
   - quadratique sur les graphes en général.
 */
function calculerLesBoulesDeRayon2($graphe){
  // Une application qui associe à un sommet
  // la boule de rayon 2 (liste de sommets)
  // centrée sur le sommet.
  $graphe["sommetVersBouleDeRayon2"] = [];

  // Pour chaque sommet (facteur n)
  for($i = 0; $i < $graphe["nombreDeSommets"]; ++$i){
    // On calcule la liste des sommets
    // dans la boule de rayon 2 centrée sur ce sommet
    // (facteur constant si le degré maximum est borné)
    $voisins = $graphe["listesDadjacences"][$i];
    $voisinsDeVoisins = [];
    foreach($voisins as $voisin){
      $voisinsDeVoisins = array_merge(
        $voisinsDeVoisins,
        $graphe["listesDadjacences"][$voisin]
      );
    }
    $boule = array_unique(array_merge($voisins, $voisinsDeVoisins));
    $graphe["sommetVersBouleDeRayon2"][$i] = $boule;
  }
  return $graphe;
}



/**
 * Fonction de décomposition d'un graphe en parties
 * de sommets à distance au moins 3 par un algorithme glouton.
 */
function partitionnerEnPartiesDeSommetsADistanceAuMoins3($graphe){
  if(!isset($graphe["sommetVersBouleDeRayon2"])){
    $graphe = calculerLesBoulesDeRayon2($graphe);
  }

  // ** = puissance donc ici degré max au carré
  $nombrePartiesMax = 1 + $graphe["degreMaximum"]**2;
  // On initialise un tableau donnant la partie
  // associée à chaque sommet
  $graphe["partiesEspaceesDe3"] = [
      "identifiantDeSommetVersPartie" => [],
      "listeDesParties" => [],
  ];
  $sommetVersPartie
    = &$graphe["partiesEspaceesDe3"]["identifiantDeSommetVersPartie"]
  ;
  // -1 correspond à "non affecté"
  for($i = 0; $i < $graphe["nombreDeSommets"]; ++$i){
    $sommetVersPartie[$i] = -1;
  }

  // Pour chaque sommet (facteur n)
  for($i = 0; $i < $graphe["nombreDeSommets"]; ++$i){
    $boule = $graphe["sommetVersBouleDeRayon2"][$i];

    // Pour chaque partie
    // (facteur constant si le degré maximum est borné)
    for($j = 0; $j < $nombrePartiesMax; ++$j){
      // On regarde si un sommet de la boule y est déjà affecté.
      // $partieDejaPrise = false;
      foreach($boule as $sommetDansLaBoule){
        if($sommetVersPartie[$sommetDansLaBoule] === $j){
          // $partieDejaPrise = true;
          continue 2; // On passe directement à la partie suivante
        }
      }
      $sommetVersPartie[$i] = $j;
      break;
    }
  }

  // On regarde de combien de parties on a réellement eu besoin
  $indexMaximumDePartieUtilisee = 0;
  for($i = 0; $i < $graphe["nombreDeSommets"]; ++$i){
    if($sommetVersPartie[$i] < 0){
      // Cela ne devrait pas se produire,
      // sauf si quelqu'un injecte un graphe
      // avec un degré maximum faux.
      throw Exception(
        "Le sommet ".$graphe["listeDeSommets"][$i]
       ." n'a pas de partie."
      );
    }
    $indexMaximumDePartieUtilisee = max(
      $indexMaximumDePartieUtilisee,
      $sommetVersPartie[$i]
    );
  }

  // On remplit les parties
  $listeDesParties
    = &$graphe["partiesEspaceesDe3"]["listeDesParties"]
  ;
  for($i = 0; $i <= $indexMaximumDePartieUtilisee; ++$i){
    $listeDesParties[$i] = [];
  }
  for($i = 0; $i < $graphe["nombreDeSommets"]; ++$i){
    $partie = $sommetVersPartie[$i];
    $listeDesParties[$partie] []= $i;
  }

  return $graphe;
}



$grapheAvecParties = partitionnerEnPartiesDeSommetsADistanceAuMoins3(
  $grapheCharge
);
/*
var_dump(
  $grapheAvecParties["partiesEspaceesDe3"]
  ["identifiantDeSommetVersPartie"]
);
//*/
$partiesEspaceesDe3 = &$grapheAvecParties["partiesEspaceesDe3"];
foreach(
  $grapheAvecParties["sommetVersBouleDeRayon2"]
  as $i => $boule
){
  echo(
    "La boule de rayon 2 centrée sur ".(
      $grapheAvecParties["listeDeSommets"][$i]
    )
   ." contient les sommets suivants : ".join(
      ",",
      listeDeSommetsInternePourAffichage(
        $grapheAvecParties,
        $boule
      )
    ).".\n"
  );
}
$listeDesParties
  = &$partiesEspaceesDe3["listeDesParties"]
;
foreach($listeDesParties as $i => $partie){
  echo(
    "La partie ".($i+1)." contient les ".count($partie)
   ." sommets suivants : ".join(
      ",",
      listeDeSommetsInternePourAffichage(
        $grapheAvecParties,
        $partie
      )
    ).".\n"
  );
}



/**
 * Fonction de vérification qu'un ensemble forme un stable.
 */
function verifierQueDesSommetsFormentUnStable(
  $graphe,
  $listeDeSommetsDuStable
){
  $tableauUnFlagParSommet1 = []; // pour les sommets du stable
  $tableauUnFlagParSommet2 = []; // pour les voisins de ces sommets
  for($i = 0; $i < $graphe["nombreDeSommets"]; ++$i){
    // temps linéaire
    $tableauUnFlagParSommet1[$i] = false;
    $tableauUnFlagParSommet2[$i] = false;
  }
  foreach($listeDeSommetsDuStable as $sommet){
    // temps linéaire
    $tableauUnFlagParSommet1[$sommet] = true;
  }

  foreach($listeDeSommetsDuStable as $sommet){
    // facteur n
    $voisins = $graphe["listesDadjacences"][$sommet];
    foreach($voisins as $voisin){
      // facteur constant si le degré maximum est borné
      $tableauUnFlagParSommet2[$voisin] = true;
    }
  }

  for($i = 0; $i < $graphe["nombreDeSommets"]; ++$i){
    // temps linéaire
    if($tableauUnFlagParSommet1[$i] && $tableauUnFlagParSommet2[$i]){
      return false;
    }
  }
  return true;
}



foreach($listeDesParties as $i => $partie){
  $estStable = verifierQueDesSommetsFormentUnStable(
    $grapheAvecParties,
    $partie
  );
  if(!$estStable){
    throw Exception(
      "La partie ".($i+1)." contenant les sommets suivants : ".join(
        ",",
        listeDeSommetsInternePourAffichage(
          $grapheAvecParties,
          $partie
        )
      )." n'est pas un stable.\n"
    );
  }
}



function creerUnNouveauNoeudDeDecomposition($sommets){
  if(count($sommets) === 1){
    return [
      "typeDeNoeud" => "feuille",
      "sommet" => $sommets[0],
    ];
  }
  return [
    "typeDeNoeud" => "interne",
    "sommets" => $sommets,
    "suiteDApplications" => [],
    "applicationFilsGaucheFilsDroit" => null,
    "filsGauche" => null,
    "filsDroit" => null,
  ];
}



/**
 * Fonction de calcul de la décomposition arborescente
 * questionnable bijective équilibrée d'un stable.
 */
function decomposerUnStableParPremiereDifference(
  $listeDeSommetsDuStable
){

  if(count($listeDeSommetsDuStable) < 1){
    throw Exception("Pas de décomposition de stable vide");
  }
  if(count($listeDeSommetsDuStable) === 1){
    return creerUnNouveauNoeudDeDecomposition(
      $listeDeSommetsDuStable
    );
  }

  $racine = creerUnNouveauNoeudDeDecomposition(
    $listeDeSommetsDuStable
  );
  $chunks = array_chunk(
    $listeDeSommetsDuStable,
    ceil(count($listeDeSommetsDuStable) / 2)
  );
  $listeDeSommetsDuSousStable1 = $chunks[0];
  $listeDeSommetsDuSousStable2 = $chunks[1];
  // logique entre guillemet,
  // voir la définition des profondeurs logique
  // et structurelle de la décomposition
  $applicationLogique = [];
  foreach($listeDeSommetsDuSousStable1 as $sommet){
    $applicationLogique[$sommet] = 'g';
  }
  foreach($listeDeSommetsDuSousStable2 as $sommet){
    $applicationLogique[$sommet] = 'd';
  }
  $applicationStructurelle = [];
  foreach($listeDeSommetsDuSousStable1 as $sommet){
    $applicationStructurelle[$sommet] = 'G';
  }
  foreach($listeDeSommetsDuSousStable2 as $sommet){
    $applicationStructurelle[$sommet] = 'D';
  }

  $racine["suiteDApplications"] []= $applicationLogique;
  $racine["applicationFilsGaucheFilsDroit"] =
    $applicationStructurelle
  ;
  $racine["filsGauche"] = decomposerUnStableParPremiereDifference(
    $listeDeSommetsDuSousStable1
  );
  $racine["filsDroit"] = decomposerUnStableParPremiereDifference(
    $listeDeSommetsDuSousStable2
  );

  return $racine;
}



/**
 * Fonction de calcul de la décomposition arborescente
 * questionnable bijective équilibrée d'un graphe de degré borné.
 * En fait ça marche pour tous les graphes,
 * mais la décomposition n'est pas nécessairement équilibrée
 * si le degré n'est pas borné.
 * Cette fonction et les fonctions qu'elle appelle implémentent
 * un algorithme de complexité quasi-linéaire
 * démontrant le Théorème 3.1.
 */
function decomposerUnGrapheParPremiereDifference(
  $graphe
){
  if(isset($graphe["partiesEspaceesDe3"])){
    $grapheAvecParties = &$graphe;
  }
  else{
    $grapheAvecParties
      = partitionnerEnPartiesDeSommetsADistanceAuMoins3(
        $graphe
    );
  }

  $grapheAvecParties["decompositionParPremiereDifference"] = [
    "decompositionDesParties" => [],
    "decompositionGlobale" => null,
    "sommetVersChaineBinaire" => [],
    "sommetVersChaineQuaternaire" => [],
    // Sénaire : à six chiffres/caractères
    "sommetVersChaineSenaire" => [],
  ];
  foreach(
    $graphe["partiesEspaceesDe3"]["listeDesParties"]
    as $partie
  ){
    $grapheAvecParties["decompositionParPremiereDifference"]
        ["decompositionDesParties"]
      []= decomposerUnStableParPremiereDifference(
        $partie
    );
  }

  $decompositionPartielle
    = $grapheAvecParties["decompositionParPremiereDifference"]
      ["decompositionDesParties"][0]
  ;
  $sommetsGauche =
    $graphe["partiesEspaceesDe3"]["listeDesParties"][0]
  ;
  $tableauUnFlagParSommetAGauche = [];
  $tableauUnFlagParSommetAGaucheRegroupeDansUneEtoile = [];
  for($i = 0; $i < $graphe["nombreDeSommets"]; ++$i){
    // temps linéaire
    $tableauUnFlagParSommetAGauche[$i] = false;
    $tableauUnFlagParSommetAGaucheRegroupeDansUneEtoile[$i] = false;
  }
  foreach($sommetsGauche as $sommet){
    // temps linéaire (sous-ensemble de sommets)
    $tableauUnFlagParSommetAGauche[$sommet] = true;
  }
  for(
    $i = 1,
    $iMax = count(
      $graphe["partiesEspaceesDe3"]["listeDesParties"]
    );
    $i < $iMax;
    ++$i
  ){
    // Dans le cas des graphes de degré borné,
    // cette boucle est exécutée un nombre borné de fois.
    // On joint la décomposition partielle et la partie courante
    $partieCourante
      = $graphe["partiesEspaceesDe3"]["listeDesParties"][$i]
    ;
    $sommetsACetteEtape = array_merge(
      $sommetsGauche,
      $partieCourante
    );
    $racine = creerUnNouveauNoeudDeDecomposition(
      $sommetsACetteEtape
    );
    // La partie structurelle est immédiate et peu intéressante
    $applicationStructurelle = [];
    foreach($sommetsGauche as $sommet){
      // temps linéaire un nombre borné de fois
      // (nombre de parties - 1)
      // dans le cas des graphes de degré borné
      $applicationStructurelle[$sommet] = 'G';
    }
    foreach($partieCourante as $sommet){
      // temps linéaire (sous-ensemble de sommets disjoint)
      $applicationStructurelle[$sommet] = 'D';
    }
    $racine["applicationFilsGaucheFilsDroit"] =
      $applicationStructurelle
    ;
    $racine["filsGauche"] = $decompositionPartielle;
    $racine["filsDroit"]
      = $grapheAvecParties["decompositionParPremiereDifference"]
        ["decompositionDesParties"][$i]
    ;

    // Calcul de la suite d'applications
    // 1) calcul des composantes connexes du graphe biparti
    // On exploite le fait que l'on sait déjà que ce sont des sommets
    // isolés ou des étoiles centrées à droite
    foreach($sommetsGauche as $sommet){
      // temps linéaire un nombre borné de fois si degré borné
      $tableauUnFlagParSommetAGaucheRegroupeDansUneEtoile[$sommet]
        = false
      ;
    }
    $etoilesOuIsole = [];
    foreach($partieCourante as $sommet){
      // temps linéaire (sous-ensemble de sommets disjoint)
      // fois une constante si degré borné
      $composanteConnexe = [$sommet];
      $voisins = $graphe["listesDadjacences"][$sommet];
      foreach($voisins as $voisin){
        if($tableauUnFlagParSommetAGauche[$voisin]){
          $tableauUnFlagParSommetAGaucheRegroupeDansUneEtoile
              [$voisin]
            = true
          ;
          $composanteConnexe []= $voisin;
        }
      }
      $etoilesOuIsole []= $composanteConnexe;
    }
    foreach($sommetsGauche as $sommet){
      // temps linéaire un nombre borné de fois si degré borné
      if(
        !$tableauUnFlagParSommetAGaucheRegroupeDansUneEtoile[$sommet]
      ){
        $etoilesOuIsole []= [$sommet];
      }
    }
    // 2) On exploite les index entiers des composantes connexes
    // pour avoir gratuitement les applications
    $iBitSelectionne = 1;
    $nombreDeComposantes = count($etoilesOuIsole);
    $indexMax = $nombreDeComposantes - 1;
    while($iBitSelectionne <= $indexMax){
      // nombre logarithmique de fois un traitement linéaire
      $applicationLogique = [];

      foreach($etoilesOuIsole as $index => $composante){
        if($index & $iBitSelectionne){
          foreach($composante as $sommet){
            // chaque sommet n'est vu qu'au plus une fois
            // par les 3 boucles foreach pour une exécution
            // de la boucle while
            $applicationLogique[$sommet] = 'd';
          }
        }
        else{
          foreach($composante as $sommet){
            // chaque sommet n'est vu qu'au plus une fois
            // par les 3 boucles foreach pour une exécution
            // de la boucle while
            $applicationLogique[$sommet] = 'g';
          }
        }
      }
      $racine["suiteDApplications"] []= $applicationLogique;

      // On multiplie par 2
      $iBitSelectionne = $iBitSelectionne << 1;
    }

    // Ajout de l'application logique finale
    $applicationLogique = [];
    foreach($sommetsGauche as $sommet){
      // lettre après g plutôt que g' pour rester à taille fixe
      $applicationLogique[$sommet] = 'h';
    }
    foreach($partieCourante as $sommet){
      // lettre après d plutôt que d' pour rester à taille fixe
      $applicationLogique[$sommet] = 'e';
    }
    $racine["suiteDApplications"] []= $applicationLogique;

    // Préparation des données pour l'étape suivante
    $decompositionPartielle = $racine;
    $sommetsGauche = $sommetsACetteEtape;
    foreach($partieCourante as $sommet){
      // temps linéaire (sous-ensemble de sommets disjoint)
      $tableauUnFlagParSommetAGauche[$sommet] = true;
    }
  }
  $grapheAvecParties["decompositionParPremiereDifference"]
    ["decompositionGlobale"] = &$racine;

  for($i = 0; $i < $graphe["nombreDeSommets"]; ++$i){
    // Pour chaque sommet, on concatène les caractères liés.
    // Le temps par sommet est logarithmique,
    // si la profondeur logique de la décomposition
    // est logarithmique, par exemple si le degré est borné.
    $motSenaire = "";
    $noeudDecompositionCourant = $racine;
    while($noeudDecompositionCourant["typeDeNoeud"] !== "feuille"){
      // On parcourt la suite d'applications à l'envers
      // puisque l'on part de la racine.
      for(
        $j = count(
          $noeudDecompositionCourant["suiteDApplications"]
        ) - 1;
        $j >= 0;
        --$j
      ){
        $application
          = $noeudDecompositionCourant["suiteDApplications"][$j]
        ;
        if(!isset($application[$i])){
          var_dump($i, $noeudDecompositionCourant, $application);
          throw Exception("Un sommet isolé a dû se perdre.");
        }
        $motSenaire .= $application[$i];
      }
      $bifurcation
        = $noeudDecompositionCourant
          ["applicationFilsGaucheFilsDroit"][$i]
      ;
      $motSenaire .= $bifurcation;
      if($bifurcation === 'G'){
        $noeudDecompositionCourant
          = $noeudDecompositionCourant["filsGauche"]
        ;
      }
      else{
        $noeudDecompositionCourant
          = $noeudDecompositionCourant["filsDroit"]
        ;
      }
    }

    // On renverse la chaîne (de longueur logarithmique)
    $motSenaire = strrev($motSenaire);
    $motBinaire = strtr($motSenaire, "ghGdeD", "000111");
    $motQuaternaire = strtr($motSenaire, "he", "gd");
    $grapheAvecParties["decompositionParPremiereDifference"]
        ["sommetVersChaineBinaire"][$i]
      = $motBinaire
    ;
    $grapheAvecParties["decompositionParPremiereDifference"]
        ["sommetVersChaineQuaternaire"][$i]
      = $motQuaternaire
    ;
    $grapheAvecParties["decompositionParPremiereDifference"]
        ["sommetVersChaineSenaire"][$i]
      = $motSenaire
    ;
  }
  return $grapheAvecParties;
}



$grapheDecompose = decomposerUnGrapheParPremiereDifference(
  $grapheAvecParties
);
/*
var_dump(
  $grapheDecompose["decompositionParPremiereDifference"]
);
//*/
foreach($grapheDecompose["listeDeSommets"] as $i => $sommet){
  echo(
    "Le sommet $sommet est representé par la chaîne "
    .$grapheDecompose["decompositionParPremiereDifference"]
        ["sommetVersChaineSenaire"][$i]
    .".\n"
  );
}



/**
 * Dédensifier un graphe en remplaçant chaque arête
 * par un chemin de longueur 3.
 * Il suffit de savoir que les tableaux associatifs de PHP
 * sont des tables de hashage et de constater qu'il n'y a pas
 * de boucles imbriquées sur les données pour savoir
 * que cette fonction prouve la complexité linéaire annoncée
 * au Théorème 4.1.
 */
function dedensifierUnGraphe($graphe){
  // On commence par vérifier qu'aucun sommet n'a une étiquette
  // contenant la sous-chaîne "_Vers_",
  // car on va l'utiliser pour l'étiquetage des nouveaux sommets.
  foreach($graphe["listeDeSommets"] as $sommet){
    if(strpos($sommet, "_Vers_") !== false){
      throw Exception(
        "L'étiquette $sommet contient la sous-chaîne _Vers_."
      );
    }
  }

  $graphe["nombreDeSommetsAvantDedensification"]
    = $graphe["nombreDeSommets"]
  ;
  $graphe["nombreDeSommets"]
    = $graphe["nombreDeSommets"]
    + 2 * count($graphe["listeDesAretes"])
  ;
  $graphe["listeDesAretesAvantDedensification"]
    = $graphe["listeDesAretes"]
  ;
  $graphe["listesDadjacencesAvantDedensification"]
    = $graphe["listesDadjacences"]
  ;
  // On calcule le degré minimum et le degré maximum du graphe
  $graphe["degreMinimumAvantDedensification"]
    = $graphe["degreMinimum"]
  ;
  $graphe["degreMaximumAvantDedensification"]
    = $graphe["degreMaximum"]
  ;
  if(count($graphe["listeDesAretesAvantDedensification"]) > 0){
    $graphe["degreMinimum"] = min(2, $graphe["degreMinimum"]);
    $graphe["degreMaximum"] = max(2, $graphe["degreMaximum"]);
  }

  $etiquetteVersIdentifiantInterne
    = &$graphe["etiquetteDeSommetVersIdentifiantInterne"]
  ;

  // On convient que si x-y devient x-x_Vers_y-y_Vers_x-y,
  // alors cette fonction sera appelée la projection
  // d'une arête initiale vers un chemin de longueur 3.
  $graphe["projectionAreteVersChemin"] = [];
  // On inventorie aussi les chemins associés à un sommet
  $graphe["sommetVersChemins"] = [];
  // Ces chemins sont stockés sous la forme d'une liste de 4 sommets,
  // ainsi que des involutions suivantes :
  // visAVis : x est y sont leurs vis-à-vis respectifs,
  // idem pour x_Vers_y et y_Vers_x.
  // proche : x et x_Vers_y sont proches, idem pour y et y_Vers_x.
  // lointain : x et y_Vers_x sont lointains,
  // idem pour y et x_Vers_y.
  $graphe["cheminsDeLongueur3"] = [];


  //Armé de ces notions, on remplit tout.
  $graphe["listeDesAretes"] = [];
  foreach(
    $graphe["listeDesAretesAvantDedensification"] as $i => $arete
  ){
    $x = $arete[0];
    $y = $arete[1];
    // On crée les deux nouveaux sommets et on les enregistre.
    $x_Vers_y__etiquette = $x."_Vers_".$y;
    $y_Vers_x__etiquette = $y."_Vers_".$x;
    $graphe["listeDeSommets"] []= $x_Vers_y__etiquette;
    $etiquetteVersIdentifiantInterne[$x_Vers_y__etiquette]
      = count($graphe["listeDeSommets"]) - 1
    ;
    $graphe["listeDeSommets"] []= $y_Vers_x__etiquette;
    $etiquetteVersIdentifiantInterne[$y_Vers_x__etiquette]
      = count($graphe["listeDeSommets"]) - 1
    ;
    $x__id = $etiquetteVersIdentifiantInterne[$x];
    $y__id = $etiquetteVersIdentifiantInterne[$y];
    $x_Vers_y__id
      = $etiquetteVersIdentifiantInterne[$x_Vers_y__etiquette]
    ;
    $y_Vers_x__id
      = $etiquetteVersIdentifiantInterne[$y_Vers_x__etiquette]
    ;
    $chemin = [
      "areteDeDepart" => $i,
      "sommets" => [
        $x__id,
        $x_Vers_y__id,
        $y_Vers_x__id,
        $y__id,
      ],
      "visAVis" => [
        $x__id => $y__id,
        $y__id => $x__id,
        $x_Vers_y__id => $y_Vers_x__id,
        $y_Vers_x__id => $x_Vers_y__id,
      ],
      "proche" => [
        $x__id => $x_Vers_y__id,
        $x_Vers_y__id => $x__id,
        $y__id => $y_Vers_x__id,
        $y_Vers_x__id => $y__id,
      ],
      "lointain" => [
        $x__id => $y_Vers_x__id,
        $y_Vers_x__id => $x__id,
        $y__id => $x_Vers_y__id,
        $x_Vers_y__id => $y__id,
      ],
    ];
    $graphe["cheminsDeLongueur3"] []= $chemin;
    $graphe["projectionAreteVersChemin"][$i]
      // stocker l'id plutôt que le pointeur ne sert à rien,
      // c'est l'identité
      // = count($graphe["cheminsDeLongueur3"]) - 1
      = $chemin
    ;
    // On ajoute les liens des sommets vers les chemins.
    if(!isset($graphe["sommetVersChemins"][$x__id])){
      $graphe["sommetVersChemins"][$x__id] = [];
    }
    $graphe["sommetVersChemins"][$x__id] []= $chemin;
    if(!isset($graphe["sommetVersChemins"][$y__id])){
      $graphe["sommetVersChemins"][$y__id] = [];
    }
    $graphe["sommetVersChemins"][$y__id] []= $chemin;
    // Les sommets internes ne sont concernés que par un chemin.
    $graphe["sommetVersChemins"][$x_Vers_y__id] = [$chemin];
    $graphe["sommetVersChemins"][$y_Vers_x__id] = [$chemin];

    // On crée les nouvelles arêtes
    $graphe["listeDesAretes"] []= [$x, $x_Vers_y__etiquette];
    $graphe["listeDesAretes"]
      []= [$x_Vers_y__etiquette, $y_Vers_x__etiquette]
    ;
    $graphe["listeDesAretes"] []= [$y_Vers_x__etiquette, $y];
    $indiceMaxArete = count($graphe["listeDesAretes"]) - 1;
    $chemin["aretesDArrivee"] = [
      $indiceMaxArete - 2,
      $indiceMaxArete - 1,
      $indiceMaxArete
    ];
  }


  // On initialise des listes d'adjacences vides.
  $graphe["listesDadjacences"] = [];
  $listesDadjacences = &$graphe["listesDadjacences"];
  for($i = 0; $i < $graphe["nombreDeSommets"]; ++$i){
    $listesDadjacences[$i] = [];
  }
  // Puis on les remplit.
  foreach($graphe["listeDesAretes"] as $arete){
    if(!isset($etiquetteVersIdentifiantInterne[$arete[0]])){
      throw Exception(
        "Le sommet ".$arete[0]." est référencé dans une arête"
       ." mais n'est pas listé dans les sommets."
      );
    }
    $idDuSommet1 = $etiquetteVersIdentifiantInterne[$arete[0]];
    if(!isset($etiquetteVersIdentifiantInterne[$arete[1]])){
      throw Exception(
        "Le sommet ".$arete[1]." est référencé dans une arête"
       ." mais n'est pas listé dans les sommets."
      );
    }
    $idDuSommet2 = $etiquetteVersIdentifiantInterne[$arete[1]];
    $listesDadjacences[$idDuSommet1] []= $idDuSommet2;
    $listesDadjacences[$idDuSommet2] []= $idDuSommet1;
  }

  return $graphe;
}



$grapheDedensifie = dedensifierUnGraphe($grapheCharge);
// var_dump($grapheCharge, $grapheDedensifie);
echo(
  "Dédensification d'un graphe à ".$grapheCharge["nombreDeSommets"]
 ." sommets"
 ." de degré minimum ".$grapheCharge["degreMinimum"]
 ." et de degré maximum ".$grapheCharge["degreMaximum"]
 ." en un graphe à ".$grapheDedensifie["nombreDeSommets"]
 ." sommets"
 ." de degré minimum ".$grapheDedensifie["degreMinimum"]
 ." et de degré maximum ".$grapheDedensifie["degreMaximum"]
 .".\n"
);



/**
 * partitionnerUnGrapheDedensifie()
 * EnPartiesDeSommetsADistanceAuMoins3 nom complet trop long :)
 * Fonction de partitionnement, en k + 1 parties de sommets
 * à distance au moins 3, des sommets d'un graphe
 * obtenu par dédensification d'un graphe de degré maximum k.
 * Cet algorithme s'exécute en temps quadratique
 * en le nombre de sommets dans le pire cas.
 * Je serais vraiment très heureux de le remplacer par un algorithme
 * ayant une complexité en temps quasi-linéaire si quelqu'un
 * en trouve un :)
 * Il permet quand même déjà de démontrer la complexité annoncée
 * au Théorème 4.2, avec l'aide de l'algorithme implémenté
 * dans la fonction decomposerUnGrapheParPremiereDifference().
 */
function partitionnerUnGrapheDedensifie($grapheDedensifie){
  if(
    !isset($grapheDedensifie["nombreDeSommetsAvantDedensification"])
  ){
    throw Exception("Ce n'est pas un graphe dédensifié.");
  }
  $nombrePartiesMax
    = $grapheDedensifie["degreMaximumAvantDedensification"] + 1
  ;
  // On initialise un tableau donnant la partie
  // associée à chaque sommet
  $grapheDedensifie["partiesEspaceesDe3"] = [
      "identifiantDeSommetVersPartie" => [],
      "listeDesParties" => [],
  ];
  $sommetVersPartie
    = &$grapheDedensifie["partiesEspaceesDe3"]
      ["identifiantDeSommetVersPartie"]
  ;
  // -1 correspond à "non affecté".
  for($i = 0; $i < $grapheDedensifie["nombreDeSommets"]; ++$i){
    $sommetVersPartie[$i] = -1;
  }
  $nombreDeSommetsOriginaux
    = $grapheDedensifie["nombreDeSommetsAvantDedensification"]
  ;
  // Les sommets originaux vont dans la première partie.
  for($i = 0; $i < $nombreDeSommetsOriginaux; ++$i){
    $sommetVersPartie[$i] = 0;
  }

  // Les k-1 parties intermédiaires se construisent
  // en prenant un voisin pour chaque sommet original
  // et en renversant un nombre linéaire de choix si nécessaire.
  for($k = 1; $k < $nombrePartiesMax - 1; ++$k){
    for($i = 0; $i < $nombreDeSommetsOriginaux; ++$i){
      // On regarde les au plus k chemins de longueur 3
      // partant du sommet.
      $chemins = $grapheDedensifie["sommetVersChemins"][$i];
      $dernierCheminCandidat = null;
      for($j = 0; $j < count($chemins); ++$j){
        $chemin = $chemins[$j];
        $proche = $chemin["proche"][$i];
        $lointain = $chemin["lointain"][$i];
        // $lointain est aussi le vis-à-vis de $proche.
        if($sommetVersPartie[$proche] !== -1){
          // On ne prend pas un sommet déjà pris
          // à une étape précédente.
          continue;
        }
        $dernierCheminCandidat = $chemin;
        if($sommetVersPartie[$lointain] === $k){
          // On ne prend pas en première intention
          // un sommet dont le voisin est dans la partie courante.
          continue;
        }
        $sommetVersPartie[$proche] = $k;
        // Si on a trouvé, on passe à l'itération suivante
        // de la boucle sur les sommets.
        continue 2;
      }
      if($dernierCheminCandidat === null){
        // S'il n'y a plus de chemin candidat,
        // c'est que le sommet avait un degré inférieur à k
        // et qu'il est déjà traité complètement.
        continue;
      }

      // Si on arrive là, c'est qu'il faut renverser un chemin.
      $proche = $dernierCheminCandidat["proche"][$i];
      $lointain = $dernierCheminCandidat["lointain"][$i];
      $sommetVersPartie[$proche] = $k;
      $sommetVersPartie[$lointain] = -1;
      $sommetPrecedent = $i;
      $sommetCourant = $dernierCheminCandidat["visAVis"][$i];
      while(true){
        // On regarde les k chemins de longueur 3 partant du sommet.
        $chemins
          = $grapheDedensifie["sommetVersChemins"][$sommetCourant]
        ;
        $dernierCheminCandidat = null;
        for($j = 0; $j < count($chemins); ++$j){
          $chemin = $chemins[$j];
          $sommetSuivant = $chemin["visAVis"][$sommetCourant];
          if($sommetSuivant === $sommetPrecedent){
            // Pas le droit de retoucher son père.
            continue;
          }
          $proche = $chemin["proche"][$i];
          $lointain = $chemin["lointain"][$i];
          if($sommetVersPartie[$proche] !== -1){
            // On ne prend pas un sommet déjà pris
            // à une étape précédente.
            continue;
          }
          $dernierCheminCandidat = $chemin;
          if($sommetVersPartie[$lointain] === $k){
            // On ne prend pas en première intention
            // un sommet dont le voisin est dans la partie courante.
            continue;
          }
          $sommetVersPartie[$proche] = $k;
          // Si on a trouvé, on passe à l'itération suivante
          // de la boucle for sur les sommets.
          continue 3;
        }

        if($dernierCheminCandidat === null){
          // S'il n'y a plus de chemin candidat,
          // c'est que le sommet avait un degré inférieur à k
          // et qu'il est déjà traité complètement,
          // sauf pour le fait de "retoucher son père"
          // qu'il pourra faire lors de la prochaine partie.
          continue;
        }

        // Sinon on continue à renverser le chemin.
        $proche = $dernierCheminCandidat["proche"][$sommetCourant];
        $lointain
          = $dernierCheminCandidat["lointain"][$sommetCourant]
        ;
        $sommetVersPartie[$proche] = $k;
        $sommetVersPartie[$lointain] = -1;
        $sommetPrecedent = $sommetCourant;
        $sommetCourant
          = $dernierCheminCandidat["visAVis"][$sommetCourant]
        ;
      }
    }
  }
  // Très important : un sommet de degré strictement inférieur à k
  // ne peut pas accumuler plus d'une partie de retard.
  // Car il n'accumule ce retard que si son "père" dans un
  // retournement de chemin était l'unique choix restant
  // pour ce sommet.
  // Et nécessairement, il résorbe ce retard à l'étape d'après.
  // En conséquence, à l'issue du calcul des k premières parties,
  // tous les sommets de degré strictement inférieur à k ont été
  // traités
  // ou bien ils ont été bloqués par leur "père" à l'étape k.

  // La (k + 1)-ème partie se construit
  // en prenant un voisin pour chaque sommet original
  // et en échangeant un nombre linéaire de choix si nécessaire
  // entre la k-ème et la (k + 1)-ème partie.
  $k = $nombrePartiesMax - 2; // La première partie correspond à 0
  for($i = 0; $i < $nombreDeSommetsOriginaux; ++$i){
    // On regarde les k chemins de longueur 3 partant du sommet.
    $chemins = $grapheDedensifie["sommetVersChemins"][$i];
    $dernierCheminCandidat = null;
    for($j = 0; $j < count($chemins); ++$j){
      $chemin = $chemins[$j];
      $proche = $chemin["proche"][$i];
      $lointain = $chemin["lointain"][$i];
      // $lointain est aussi le vis-à-vis de $proche.
      if($sommetVersPartie[$proche] !== -1){
        // On ne prend pas un sommet déjà pris
        // à une étape précédente.
        continue;
      }
      $dernierCheminCandidat = $chemin;
      if($sommetVersPartie[$lointain] === $k + 1){
        // On ne prend pas en première intention
        // un sommet dont le voisin est dans la partie courante.
        continue;
      }
      $sommetVersPartie[$proche] = $k + 1;
      // Si on a trouvé, on passe à l'itération suivante
      // de la boucle sur les sommets.
      continue 2;
    }

    if($dernierCheminCandidat === null){
      // S'il n'y a plus de chemin candidat,
      // c'est que le sommet avait un degré inférieur à k
      // et qu'il est déjà traité complètement.
      continue;
    }

    // Si on arrive là, c'est qu'il faut renverser un chemin.
    // On trouve le chemin sortant de $i à l'étape k
    $cheminSuivant = null;
    for($j = 0; $j < count($chemins); ++$j){
      $chemin = $chemins[$j];
      $proche = $chemin["proche"][$i];
      if($sommetVersPartie[$proche] === $k){
        $cheminSuivant = $chemin;
        break;
      }
    }
    $proche = $dernierCheminCandidat["proche"][$i];
    // Avant de poser un autre choix pour l'étape k
    $sommetVersPartie[$proche] = $k;
    if($cheminSuivant === null){
      // Pas de chemin suivant, on a réussi à compléter en k étapes
      // un sommet de degré inférieur à k qui n'était complété
      // qu'en k+1 étapes :)
      break;
    }
    $sommetCourant = $i;

    while(true){
      $sommetPrecedent = $sommetCourant;
      $cheminCourant = $cheminSuivant;
      $sommetCourant = $cheminCourant["visAVis"][$sommetPrecedent];

      // On trouve le chemin sortant de $sommetCourant à l'étape k
      $chemins
        = $grapheDedensifie["sommetVersChemins"][$sommetCourant]
      ;
      $cheminSuivant = null;
      for($j = 0; $j < count($chemins); ++$j){
        $chemin = $chemins[$j];
        $proche = $chemin["proche"][$sommetCourant];
        if($sommetVersPartie[$proche] === $k){
          $cheminSuivant = $chemin;
          break;
        }
      }
      // On inverse entre sommet précédent et sommet courant.
      $proche = $cheminCourant["proche"][$sommetPrecedent];
      $sommetVersPartie[$proche] = $k + 1;
      $lointain = $cheminCourant["lointain"][$sommetPrecedent];
      if($sommetVersPartie[$lointain] !== $k + 1){
        // Pas de conflit, on peut sortir de la boucle while.
        break;
      }
      // Sinon, comme on sait déjà où se poursuit le chemin
      // de l'étape k, on peut corriger le sommet du chemin courant.
      $sommetVersPartie[$lointain] = $k;
      if($cheminSuivant === null){
        // Pas de chemin suivant, on a réussi à compléter en k étapes
        // un sommet de degré inférieur à k qui n'était complété
        // qu'en k+1 étapes :)
        break;
      }

      // Et on boucle
    }
  }

  // On remplit les parties
  $listeDesParties
    = &$grapheDedensifie["partiesEspaceesDe3"]["listeDesParties"]
  ;
  for($i = 0; $i < $nombrePartiesMax; ++$i){
    $listeDesParties[$i] = [];
  }
  for($i = 0; $i < $grapheDedensifie["nombreDeSommets"]; ++$i){
    $partie = $sommetVersPartie[$i];
    $listeDesParties[$partie] []= $i;
  }

  return $grapheDedensifie;
}



$grapheDedensifieAvecParties = partitionnerUnGrapheDedensifie(
  $grapheDedensifie
);
/*
var_dump(
  $grapheDedensifieAvecParties["partiesEspaceesDe3"]
  ["identifiantDeSommetVersPartie"]
);
//*/
$partiesEspaceesDe3
  = &$grapheDedensifieAvecParties["partiesEspaceesDe3"]
;
$listeDesParties
  = &$partiesEspaceesDe3["listeDesParties"]
;
foreach($listeDesParties as $i => $partie){
  echo(
    "La partie ".($i+1)." contient les ".count($partie)
   ." sommets suivants : ".join(
      ",",
      listeDeSommetsInternePourAffichage(
        $grapheDedensifieAvecParties,
        $partie
      )
    ).".\n"
  );
}



/**
 * partitionnerUnGrapheDedensifieParAlgoGlouton()
 * Fonction de partitionnement, en k + 2 parties de sommets
 * à distance au moins 3, des sommets d'un graphe
 * obtenu par dédensification d'un graphe de degré maximum k.
 * Cet algorithme s'exécute sur les graphes de degré borné
 * en temps linéaire en le nombre de sommets dans le pire cas.
 * Il est donc plus rapide que la fonction précédente,
 * mais malheureusement il utilise une partie de plus.
 */
function partitionnerUnGrapheDedensifieParAlgoGlouton($graphe){
  if(!isset($graphe["sommetVersBouleDeRayon2"])){
    $graphe = calculerLesBoulesDeRayon2($graphe);
  }

  $nombrePartiesMax = 2 + $graphe["degreMaximum"];
  // On initialise un tableau donnant la partie
  // associée à chaque sommet
  $graphe["partiesEspaceesDe3"] = [
      "identifiantDeSommetVersPartie" => [],
      "listeDesParties" => [],
  ];
  $sommetVersPartie
    = &$graphe["partiesEspaceesDe3"]["identifiantDeSommetVersPartie"]
  ;
  // -1 correspond à "non affecté"
  for($i = 0; $i < $graphe["nombreDeSommets"]; ++$i){
    $sommetVersPartie[$i] = -1;
  }
  $nombreDeSommetsOriginaux
    = $grapheDedensifie["nombreDeSommetsAvantDedensification"]
  ;
  // Les sommets originaux vont dans la première partie.
  for($i = 0; $i < $nombreDeSommetsOriginaux; ++$i){
    $sommetVersPartie[$i] = 0;
  }

  // Pour chaque sommet (facteur n)
  for(
    $i = $nombreDeSommetsOriginaux;
    $i < $graphe["nombreDeSommets"];
    ++$i
  ){
    $boule = $graphe["sommetVersBouleDeRayon2"][$i];

    // Pour chaque partie
    // (facteur constant si le degré maximum est borné)
    for($j = 1; $j < $nombrePartiesMax; ++$j){
      // On regarde si un sommet de la boule y est déjà affecté.
      // $partieDejaPrise = false;
      foreach($boule as $sommetDansLaBoule){
        if($sommetVersPartie[$sommetDansLaBoule] === $j){
          // $partieDejaPrise = true;
          continue 2; // On passe directement à la partie suivante
        }
      }
      $sommetVersPartie[$i] = $j;
      break;
    }
  }

  // On regarde de combien de parties on a réellement eu besoin
  $indexMaximumDePartieUtilisee = 0;
  for($i = 0; $i < $graphe["nombreDeSommets"]; ++$i){
    if($sommetVersPartie[$i] < 0){
      // Cela ne devrait pas se produire,
      // sauf si quelqu'un injecte un graphe
      // avec un degré maximum faux.
      throw Exception(
        "Le sommet ".$graphe["listeDeSommets"][$i]
       ." n'a pas de partie."
      );
    }
    $indexMaximumDePartieUtilisee = max(
      $indexMaximumDePartieUtilisee,
      $sommetVersPartie[$i]
    );
  }

  // On remplit les parties
  $listeDesParties
    = &$graphe["partiesEspaceesDe3"]["listeDesParties"]
  ;
  for($i = 0; $i <= $indexMaximumDePartieUtilisee; ++$i){
    $listeDesParties[$i] = [];
  }
  for($i = 0; $i < $graphe["nombreDeSommets"]; ++$i){
    $partie = $sommetVersPartie[$i];
    $listeDesParties[$partie] []= $i;
  }

  return $graphe;
}



$grapheDedensifieDecompose = decomposerUnGrapheParPremiereDifference(
  $grapheDedensifieAvecParties
);
/*
var_dump(
  $grapheDedensifieDecompose["decompositionParPremiereDifference"]
);
//*/
foreach(
  $grapheDedensifieDecompose["listeDeSommets"] as $i => $sommet
){
  echo(
    "Le sommet $sommet est representé par la chaîne "
    .$grapheDedensifieDecompose["decompositionParPremiereDifference"]
        ["sommetVersChaineSenaire"][$i]
    .".\n"
  );
}



/**
 * Calcul en temps linéaire (n+m) des composantes connexes
 * d'un sous-graphe induit.
 * Cette fonction renvoie un tableau associant chaque sommet
 * à son numéro de composante connexe.
 */
function calculerLesComposantesDunSousGrapheInduit(
  $graphe,
  $listeDeSommets
){
  $sommetVersComposante = [];
  // L'absence du tableau associatif (table de hashage)
  // nous permet de tester la (non-)appartenance aux sommets du
  // sous-graphe induit en temps constant.
  // Donc on utilise la valeur -1 pour avoir l'appartenance
  // d'un sommet qui n'a pas encore reçu sa composante.
  foreach($listeDeSommets as $i){
    $sommetVersComposante[$i] = -1;
  }
  $numeroComposanteCourante = 0;
  foreach($listeDeSommets as $i){
    if($sommetVersComposante[$i] !== -1){
      continue;
    }

    $sommetsADepiler = [$i];
    // Parcours en profondeur classique
    while(!empty($sommetsADepiler)){
      $sommetCourant = array_pop($sommetsADepiler);
      $sommetVersComposante[$sommetCourant]
        = $numeroComposanteCourante
      ;
      foreach(
        $graphe["listesDadjacences"][$sommetCourant] as $voisin
      ){
        if(
          // Si le voisin n'est pas dans le sous-graphe induit,
          !isset($sommetVersComposante[$voisin])
          // ou s'il a déjà une composante
          || $sommetVersComposante[$voisin] !== -1
        ){
          // on l'ignore.
          continue;
        }
        // Sinon, on l'ajoute.
        $sommetVersComposante[$voisin] = $numeroComposanteCourante;
        $sommetsADepiler []= $voisin;
      }
    }
    ++$numeroComposanteCourante;
  }
  return $sommetVersComposante;
}



/*
$sommetVersComposante = calculerLesComposantesDunSousGrapheInduit(
  $grapheCharge,
  [0, 1, 2, 3, 6, 10, 11, 17] // a,b,c,d,g,k,l,r
);
var_dump($sommetVersComposante);
//*/



/**
 * Étant donné un graphe connexe $graphe,
 * et un sous-graphe induit $listeDeSommets
 * dont les c composantes connexes sont à distance
 * exactement 2 dans $graphe,
 * calcul en temps quadratique (complexité non optimisée)
 * d'un sous-graphe induit connexe
 * $listeDeSommetsEtendue qui contient $listeDeSommets.
 * Dans le cas qui nous intéresse où les sommets restants
 * sont de degré 2, on ajoute exactement c-1 sommets de plus.
 */
function calculerUneExtensionConnexeDunSousGrapheInduit(
  $graphe,
  $listeDeSommets
){
  $sommetVersComposante = calculerLesComposantesDunSousGrapheInduit(
    $graphe,
    $listeDeSommets
  );
  $listeDeSommetsEtendue = $listeDeSommets;
  for($i = 0; $i < $graphe["nombreDeSommets"]; ++$i){
    if(isset($sommetVersComposante[$i])){
      // On cherche les sommets à ajouter, pas ceux qu'on a déjà.
      continue;
    }
    $composantesDesVoisins = [];
    foreach(
      $graphe["listesDadjacences"][$i] as $voisin
    ){
      // Temps linéaire n+m
      if(
        // Si le voisin n'est pas dans le sous-graphe induit,
        !isset($sommetVersComposante[$voisin])
      ){
        // on l'ignore.
        continue;
      }
      // Sinon, on ajoute sa composante.
      $composantesDesVoisins []= $sommetVersComposante[$voisin];
    }
    $composantesDesVoisins = array_unique($composantesDesVoisins);
    if(count($composantesDesVoisins) > 1){
      $listeDeSommetsEtendue []= $i;
      $composanteMin = min($composantesDesVoisins);
      $sommetVersComposante[$i] = $composanteMin;
      foreach($composantesDesVoisins as $composante){
        // Bien que l'on soit dans une boucle imbriquée,
        // pour l'ensemble des sommets de la première boucle for,
        // on ne peut rentrer dans cette boucle qu'au plus n fois
        if($composante === $composanteMin){
          continue;
        }
        foreach($sommetVersComposante as $sommet => $saComposante){
          // Chaque sommet est parcouru,
          // d'où la complexité quadratique.
          if($saComposante === $composante){
            // On réunit tout
            $sommetVersComposante[$sommet] = $composanteMin;
          }
        }
      }
    }
  }
  return $listeDeSommetsEtendue;
}



$partiesEspaceesDe3
  = &$grapheDedensifieDecompose["partiesEspaceesDe3"]
;
$listeDesParties
  = &$partiesEspaceesDe3["listeDesParties"]
;
$sommetsPeuConnectes
  = calculerUneExtensionConnexeDunSousGrapheInduit(
      $grapheDedensifieDecompose,
      array_merge(
        $listeDesParties[0],
        $listeDesParties[1],
        $listeDesParties[2]
      )
);
echo(
  "Les ".count($sommetsPeuConnectes)
 ." sommets suivants sont connectés mais peu : ".join(
    ",",
    listeDeSommetsInternePourAffichage(
      $grapheDedensifieDecompose,
      $sommetsPeuConnectes
    )
  ).".\n"
);
echo(
  "L'important pour la complexité modérément exponentielle"
 ." c'est que le nombre de sommets soit au moins égal à"
 ." 3 * 22 + ((22 / 2) - 1) = 76.\n"
 ." Ce qui implique qu'il reste au plus 12 =  22/2 + 1 sommets,"
 ." pour l'énumération exhaustive.\n"
);



/**
 * Temps constant si le degré est borné.
 */
function calculerLeDegreDansUnSousGrapheInduit(
  &$graphe,
  &$sommet,
  // Sous forme id => true plutôt que liste
  &$sommetsCandidats
){
  $degre = 0;
  foreach(
    $graphe["listesDadjacences"][$sommet] as $voisin
  ){
    if(isset($sommetsCandidats[$voisin])){
      ++$degre;
    }
  }
  return $degre;
}



/**
 * Cette fonction implémente l'algorithme glouton
 * qui détecte une feuille
 * pour étendre un stable en un stable maximum
 * de la sous-forêt considérée.
 * Elle fonctionne en temps linéaire n+m,
 * où n est le nombre de sommets du sous-graphe,
 * et m est la somme des degrés de ces sommets,
 * mais dans le graphe de départ et non le sous-graphe.
 * Comme je considère des graphes de degré borné,
 * cela n'importe que peu.
 * Son fonctionnement est légèrement étendu pour accepter
 * un sous-graphe induit quelconque,
 * donc elle va "grignoter" les feuilles jusqu'à obtenir
 * un graphe sans feuille.
 * Et elle admet comme optimisation une pile avec test d'appartenance
 * en temps constant (je fais ça avec deux tableaux associatifs PHP),
 * qui permet de restreindre l'ensemble de sommets initiaux
 * à considérer pour trouver une feuille.
 */
function trouverUnStableMaximumDUneSousForetInduite(
  $graphe,
  // passages de tableaux par référence
  &$listeDeSommetsDuSousGraphe, // une liste
  &$sommetsCandidats = null, // idSommet => true
  &$sommetsADepilerPourTrouverUneFeuille = null, // Une pile
  &$sommetsAEvaluerPourTrouverUneFeuille = null // idSommet => true
){
  $listeDeSommetsDuStable = [];
  // Sous forme id => true dans la table de hashage.
  // Cela permet d'ajouter ou d'enlever un sommet,
  // de les compter, ou de tester l'appartenance en temps constant.
  if($sommetsCandidats === null){
    $sommetsCandidats = [];
    foreach($listeDeSommetsDuSousGraphe as $sommet){
      $sommetsCandidats[$sommet] = true;
    }
  }
  if($sommetsADepilerPourTrouverUneFeuille === null){
    // On va utiliser ce tableau comme une pile.
    // Quand le degré est borné, chaque sommet est ajouté
    // à cette pile au plus un nombre constant de fois.
    $sommetsADepilerPourTrouverUneFeuille
      = $listeDeSommetsDuSousGraphe
    ;
    // Et on utilise cette copie pour évaluer
    $sommetsAEvaluerPourTrouverUneFeuille = $sommetsCandidats;
    // Donc dans le cas qui nous intéresse la recherche de feuilles
    // se fait en temps linéaire sur tout l'algorithme.
  }

  while(count($sommetsADepilerPourTrouverUneFeuille) > 0){
    $sommet = array_pop($sommetsADepilerPourTrouverUneFeuille);
    unset($sommetsAEvaluerPourTrouverUneFeuille[$sommet]);
    // Si entre temps, le sommet n'est plus candidat,
    // à cause d'un ajout de feuille au stable,
    // on passe ce sommet.
    if(!isset($sommetsCandidats[$sommet])){
      continue;
    }
    $degre = calculerLeDegreDansUnSousGrapheInduit(
      $graphe,
      $sommet,
      $sommetsCandidats
    );
    if($degre > 1){
      continue;
    }
    // On a trouvé une feuille ou un sommet isolé ;
    // on la prend.
    $listeDeSommetsDuStable []= $sommet;
    unset($sommetsCandidats[$sommet]);
    if($degre === 1){
      foreach(
        $graphe["listesDadjacences"][$sommet] as $voisin
      ){
        if(isset($sommetsCandidats[$voisin])){
          // On a trouvé le voisin.
          break;
        }
      }
      // Le voisin n'est plus candidat.
      unset($sommetsCandidats[$voisin]);
      // On regarde s'il a lui même des voisins candidats
      // qui pourraient être des feuilles.
      foreach(
        $graphe["listesDadjacences"][$voisin] as $voisinDeVoisin
      ){
        if(
          // Si le voisin de voisin n'est pas candidat,
          !isset($sommetsCandidats[$voisinDeVoisin])
          // ou qu'il est déjà dans la pile
          || isset(
            $sommetsAEvaluerPourTrouverUneFeuille[$voisinDeVoisin]
          )
        ){
          // alors il ne nous intéresse pas
          continue;
        }
        // Sinon, on l'ajoute à la pile
        $sommetsADepilerPourTrouverUneFeuille []= $voisinDeVoisin;
        $sommetsAEvaluerPourTrouverUneFeuille[$voisinDeVoisin]
          = true
        ;
        // Si après ça, vous n'êtes pas convaincu que les tableaux
        // associatifs de PHP sont de vrais couteaux suisses,
        // je ne sais pas ce qu'il vous faut :)
      }
    }
  }
  return $listeDeSommetsDuStable;
}



$sousForet = [0,1,2,4,7,10];
$stableMaximumDUneSousForet
  = trouverUnStableMaximumDUneSousForetInduite(
      $grapheCharge,
      $sousForet
);
echo(
  "Les ".count($stableMaximumDUneSousForet)
 ." sommets suivants : ".join(
    ",",
    listeDeSommetsInternePourAffichage(
      $grapheCharge,
      $stableMaximumDUneSousForet
    )
  )
  ." forment un stable maximum de la sous-forêt : ".join(
    ",",
    listeDeSommetsInternePourAffichage(
      $grapheCharge,
      $sousForet
    )
  )
  .".\n"
);



/**
 * Cette fonction renvoie en temps linéaire
 * (cf. fonction précédente) un stable maximum d'un cycle induit.
 */
function trouverUnStableMaximumDUnCycleInduit(
  $graphe,
  $listeDeSommetsDuCycle,
  $sommetANePasPrendre = null
){
  if($sommetANePasPrendre === null){
    // On peut casser le cycle de manière arbitraire
    // avec un sommet que l'on ne prend pas.
    $sommetANePasPrendre = $listeDeSommetsDuCycle[0];
  }
  $sommetsCandidats = [];
  foreach($listeDeSommetsDuCycle as $sommet){
    $sommetsCandidats[$sommet] = true;
  }
  unset($sommetsCandidats[$sommetANePasPrendre]);
  $listeDeSommets = array_keys($sommetsCandidats);
  // On ne part qu'avec un seul sommet à dépiler :
  // l'un des deux voisins du sommet à ne pas prendre.
  // De cette manière la pile n'aura jamais plus d'un élément.
  $sommetsADepilerPourTrouverUneFeuille = [];
  $sommetsAEvaluerPourTrouverUneFeuille = [];
  foreach(
    $graphe["listesDadjacences"][$sommetANePasPrendre] as $voisin
  ){
    if(isset($sommetsCandidats[$voisin])){
      break;
    }
  }
  $sommetsADepilerPourTrouverUneFeuille []= $voisin;
  $sommetsAEvaluerPourTrouverUneFeuille[$voisin] = true;

  return trouverUnStableMaximumDUneSousForetInduite(
    $graphe,
    $listeDeSommets,
    $sommetsCandidats,
    $sommetsADepilerPourTrouverUneFeuille,
    $sommetsAEvaluerPourTrouverUneFeuille
  );
}



$cycleInduit = [0,1,2,4,5,6,7,8];
$stableMaximumDUnCycleInduit
  = trouverUnStableMaximumDUnCycleInduit(
      $grapheCharge,
      $cycleInduit
);
echo(
  "Les ".count($stableMaximumDUneSousForet)
 ." sommets suivants : ".join(
    ",",
    listeDeSommetsInternePourAffichage(
      $grapheCharge,
      $stableMaximumDUnCycleInduit
    )
  )
  ." forment un stable maximum du cycle induit : ".join(
    ",",
    listeDeSommetsInternePourAffichage(
      $grapheCharge,
      $cycleInduit
    )
  )
  .".\n"
);



/**
 * Cette fonction implémente l'algorithme glouton
 * qui détecte une feuille ou un cycle-feuille
 * pour étendre un stable en un stable maximum
 * du sous-graphe peu dense considéré.
 * Peu d'effort d'optimisation a été fait.
 * Elle a une complexité quadratique en temps.
 */
function trouverUnStableMaximumDUnSousGrapheInduitPeuDense(
  $graphe,
  $listeDeSommets
){
  $listeDeSommetsDuStable = [];
  $sommetsCandidats = [];
  foreach($listeDeSommets as $sommet){
    $sommetsCandidats[$sommet] = true;
  }
  $sommetsADepilerPourTrouverUneFeuille = $listeDeSommets;
  $sommetsAEvaluerPourTrouverUneFeuille = $sommetsCandidats;

  while(count($sommetsCandidats) > 0){
    $listeDeSommetsDuStable = array_merge(
      $listeDeSommetsDuStable,
      // Rappel : cette fonction accepte aussi un sous-graphe induit
      // qui n'est pas une sous-forêt, auquel cas elle se contente
      // de "grignoter" les feuilles éventuelles.
      trouverUnStableMaximumDUneSousForetInduite(
        $graphe,
        $listeDeSommets,
        $sommetsCandidats,
        $sommetsADepilerPourTrouverUneFeuille,
        $sommetsAEvaluerPourTrouverUneFeuille
      )
    );
    // Si on arrive là, on regarde s'il reste des candidats
    if(count($sommetsCandidats) <= 0){
      break;
    }
    // On cherche un cycle-feuille.
    // Le moyen le plus simple en temps linéaire,
    // c'est de faire un parcours en profondeur.
    // En effet, tout cycle boucle nécessairement sur un ancêtre
    // du sommet courant dans l'arbre de parcours.
    // Il suffit alors de vérifier qu'au plus un sommet a un degré
    // supérieur à deux.
    reset($sommetsCandidats);
    // reset() ne vide pas le tableau.
    // Cela rembobine juste l'itérateur intégré.
    // On part du premier candidat
    $premierCandidat = key($sommetsCandidats);
    $sommetsADepiler = [$premierCandidat];
    $predecesseurs = [];
    $predecesseurs[$premierCandidat] = false;
    // Parcours en profondeur classique
    while(!empty($sommetsADepiler)){
      $sommetCourant = array_pop($sommetsADepiler);
      foreach(
        $graphe["listesDadjacences"][$sommetCourant] as $voisin
      ){
        if(
          // Si le voisin n'est pas dans le sous-graphe induit,
          !isset($sommetsCandidats[$voisin])
        ){
          // on l'ignore.
          continue;
        }
        if(isset($predecesseurs[$voisin])){
          // Si on a détecté un cycle,
          // on regarde si c'est un cycle-feuille.
          $sommetDeDegreSuperieurA2 = null;
          $sommetDuCycle = $sommetCourant;
          $listeDeSommetsDuCycle = [$voisin];
          while($sommetDuCycle !== $voisin){
            $listeDeSommetsDuCycle []= $sommetDuCycle;
            $degre = calculerLeDegreDansUnSousGrapheInduit(
              $graphe,
              $sommetDuCycle,
              $sommetsCandidats
            );
            if($degre > 2){
              if($sommetDeDegreSuperieurA2 === null){
                $sommetDeDegreSuperieurA2 = $sommetDuCycle;
              }
              else{
                $sommetDeDegreSuperieurA2 = "PlusDun";
                break;
              }
            }
            $sommetDuCycle = $predecesseurs[$sommetDuCycle];
          }
          if($sommetDeDegreSuperieurA2 !== "PlusDun"){
            // On a bien trouvé un cycle feuille.
            $listeDeSommetsDuStable = array_merge(
              $listeDeSommetsDuStable,
              trouverUnStableMaximumDUnCycleInduit(
                $graphe,
                $listeDeSommetsDuCycle,
                // Le sommet à ne pas prendre
                $sommetDeDegreSuperieurA2
              )
            );
            foreach($listeDeSommetsDuCycle as $sommetDuCycle){
              unset($sommetsCandidats[$sommetDuCycle]);
            }
            if($sommetDeDegreSuperieurA2 !== null){
              // Si on avait un sommet de degré supérieur à 2
              // dans le cycle, son éventuel voisin est peut être
              // devenu une feuille.
              foreach(
                $graphe["listesDadjacences"]
                  [$sommetDeDegreSuperieurA2]
                as $voisin
              ){
                if(
                  isset($sommetsCandidats[$voisin])
                  && !isset(
                    $sommetsAEvaluerPourTrouverUneFeuille[$voisin]
                  )
                ){
                  $sommetsADepilerPourTrouverUneFeuille []= $voisin;
                  $sommetsAEvaluerPourTrouverUneFeuille[$voisin]
                    = true
                  ;
                }
              }
            }
            // Il faut 3 niveaux pour repartir
            // dans la boucle while principale
            // while(count($sommetsCandidats) > 0)
            continue 3;
          }
        }
        $sommetsADepiler []= $voisin;
      }
    }
  }
  return $listeDeSommetsDuStable;
}



/**
 * Maintenant que le lecteur est familiarisé
 * avec les tableaux associatifs de PHP,
 * on peut factoriser un peu :)
 */
function listeVersTableauIdToBool(&$liste){
  $idToBool = [];
  foreach($liste as $element){
    $idToBool[$element] = true;
  }
  return $idToBool;
}



/**
 * C'est ici que se passe l'énumération exhaustive,
 * plus une partie de l'assemblage des morceaux.
 */
function trouverUnStableMaximumDUnGrapheDedensifie(
  $grapheDedensifie
){
  $grapheDedensifieAvecParties = partitionnerUnGrapheDedensifie(
    $grapheDedensifie
  );
  $partiesEspaceesDe3
    = &$grapheDedensifieAvecParties["partiesEspaceesDe3"]
  ;
  $listeDesParties
    = &$partiesEspaceesDe3["listeDesParties"]
  ;
  $sommetsPeuConnectes
    = calculerUneExtensionConnexeDunSousGrapheInduit(
        $grapheDedensifieAvecParties,
        array_merge(
          $listeDesParties[0],
          $listeDesParties[1],
          $listeDesParties[2]
        )
  );
  $sommetsPeuConnectesIdToBool = listeVersTableauIdToBool(
    $sommetsPeuConnectes
  );
  $sommetsRestants = [];
  $sommetsRestantsIdToBool = [];
  foreach(
    $grapheDedensifie["etiquetteDeSommetVersIdentifiantInterne"]
    as $sommet
  ){
    if(!isset($sommetsPeuConnectesIdToBool[$sommet])){
      $sommetsRestants []= $sommet;
      $sommetsRestantsIdToBool[$sommet] = true;
    }
  }
  $stableMaximum = [];
  // énumération exhaustive sur les sommets restants
  // chaque bit correspond au choix d'un sommet.
  // ATTENTION : je ne gère pas plus de 63 sommets restants
  // avec cette énumération exhaustive à la "va comme je te pousse".
  // Le lecteur qui a lu jusqu'ici et aura compris,
  // ne devrait pas avoir de mal à utiliser php-gmp
  // pour palier à cette limitation.
  for($i = 0; $i < 2**count($sommetsRestants); ++$i){
    $sousStable = [];
    foreach($sommetsRestants as $j => $sommet){
      if(($i & (1 << $j)) > 0){
        $sousStable []= $sommet;
      }
    }
    $estStable = verifierQueDesSommetsFormentUnStable(
      $grapheDedensifie,
      $sousStable
    );
    if(!$estStable){
      continue;
    }
    $sousStableIdToBool = listeVersTableauIdToBool(
      $sousStable
    );
    // On ampute les sommets peu connectés
    // des voisins des sommets du sous-stable.
    $listeDeSommets = [];
    foreach($sommetsPeuConnectes as $sommet){
      foreach(
        $grapheDedensifie["listesDadjacences"][$sommet] as $voisin
      ){
        if(isset($sousStableIdToBool[$voisin])){
          continue 2;
        }
      }
      $listeDeSommets []= $sommet;
    }
    $stableCandidat = array_merge(
      $sousStable,
      trouverUnStableMaximumDUnSousGrapheInduitPeuDense(
        $grapheDedensifie,
        $listeDeSommets
      )
    );
    if(count($stableCandidat) > count($stableMaximum)){
      $stableMaximum = $stableCandidat;
    }
  }

  return $stableMaximum;
}



/**
 * Voilà la fonction de calcul d'un stable maximum
 * d'un graphe 3-régulier où on finit l'assemblage
 * des morceaux.
 */
function trouverUnStableMaximumDUnGraphe3Regulier($graphe){
  $grapheDedensifie = dedensifierUnGraphe($graphe);
  $stableMaximumDedensifie
    = trouverUnStableMaximumDUnGrapheDedensifie(
      $grapheDedensifie
  );
  $stableMaximumDedensifieIdToBool = listeVersTableauIdToBool(
    $stableMaximumDedensifie
  );
  $etiquetteVersIdentifiantInterne
    = &$graphe["etiquetteDeSommetVersIdentifiantInterne"]
  ;
  // On "redensifie" le stable
  foreach($graphe["listeDesAretes"] as $arete){
    $sommet1 = $etiquetteVersIdentifiantInterne[$arete[0]];
    $sommet2 = $etiquetteVersIdentifiantInterne[$arete[1]];
    if(
      // Si deux sommets adjacents sont dans le stable
      isset($stableMaximumDedensifieIdToBool[$sommet1])
      && isset($stableMaximumDedensifieIdToBool[$sommet2])
    ){
      // On en enlève un de manière arbitraire.
      unset($stableMaximumDedensifieIdToBool[$sommet2]);
    }
  }
  $stableMaximum = [];
  foreach(
    $graphe["etiquetteDeSommetVersIdentifiantInterne"]
    as $sommet
  ){
    if(isset($stableMaximumDedensifieIdToBool[$sommet])){
      $stableMaximum []= $sommet;
    }
  }
  return $stableMaximum;
}



$stableMaximum = trouverUnStableMaximumDUnGraphe3Regulier(
  $grapheCharge
);
echo(
  "Les ".count($stableMaximum)
 ." sommets suivants : ".join(
    ",",
    listeDeSommetsInternePourAffichage(
      $grapheCharge,
      $stableMaximum
    )
  )
  ." forment un stable maximum du graphe en exemple.\n"
);
$estStable = verifierQueDesSommetsFormentUnStable(
  $grapheCharge,
  $stableMaximum
);
if(!$estStable){
  throw Exception(
    "Le résultat de la fonction"
   ." trouverUnStableMaximumDUnGraphe3Regulier()"
   ." n'est pas un stable.\n"
  );
}