import java.util.ArrayList;
import java.util.Set;
import java.util.HashSet;
import java.util.Map;
import java.util.HashMap;
// Classe principale
public class Graphes {
public static void main(String[] args) {
// Insérer des exemples ici : construire un graphe, lui ajouter
// des sommets et des arêtes, et contrôler les couleurs, les
// composantes connexes, les accessibilités...
}
}
// Un graphe est constitué de sommets et d'arêtes.
// On veut notamment :
// - Créer un graphe vide
// - Ajouter des sommets
// - Ajouter des arêtes
// - Effectuer un coloriage
class Graphe {
// Ensembles de sommets et d'arêtes, directement représentés comme tels.
private Set<Sommet> sommets;
private Set<Arete> aretes;
// Une composante connexe est représentée par un sommet principal
// Idée : utiliser l'algorithme Union-Find de Tarjan (dans ce corrigé,
// il y a au passage les optimisations "union par rangs" et "compression
// de chemins".
private Set<Sommet> composantes;
// Le nombre de composantes pourrait être recalculé à la demande plutôt
// qu'enregistré, mais ça ne coûte pas cher.
private int nbComposantes;
// Graphe vide : pas de sommets, pas d'arêtes, pas de composantes.
public Graphe() {
sommets = new HashSet<Sommet>();
aretes = new HashSet<Arete>();
composantes = new HashSet<Sommet>();
nbComposantes = 0;
}
// Ajout d'un sommet de nom [n]
public void ajouteSommet(String n) {
Sommet s = new Sommet(this, n);
sommets.add(s);
// Un nouveau sommet crée une nouvelle composante
composantes.add(s);
nbComposantes++;
}
// Ajout d'une arête entre deux sommets [s1] et [s2]
public void ajouteArete(Sommet s1, Sommet s2) {
Arete a = new Arete(s1, s2);
aretes.add(a);
// On récupère les composantes des deux sommets reliés...
Sommet sc1 = s1.composante();
Sommet sc2 = s2.composante();
// ... si elles étaient différentes, alors on les unit.
if (sc1 != sc2) {
nbComposantes--;
composantes.remove(sc1);
composantes.remove(sc2);
composantes.add(sc1.union(sc2));
}
}
// Vérifie que tous deux sommets adjacents ont des couleurs différentes
public boolean bienColore() {
for(Sommet s : sommets) {
if (!s.bienColore()) return false;
}
return true;
}
// Prend les sommets dans l'ordre, affecte à chacun la plus petite couleur
// disponible, et renvoie la couleur maximale utilisée.
public int colorie() {
int couleurMax = 0;
for(Sommet s : sommets) {
couleurMax = Math.max(couleurMax, s.colorie());
}
return couleurMax;
}
}
// Un sommet possède un nom et une couleur.
// On peut :
// - Créer un sommet
// - Lui ajouter des arêtes incidentes
// - Obtenir sa composante connexe
// - Lui donner une couleur
// Ici, les sommets représentent aussi des composantes connexes, on
// peut donc encore :
// - Unir la composante d'un sommet avec celle d'un autre sommet
class Sommet {
private String nom;
private int couleur;
// Je croyais que j'avais besoin de cet attribut mais à l'heure
// actuelle il n'est pas utilisé...
private Graphe graphe;
// Le dominant est le père du sommet considéré dans la structure Union-Find
private Sommet dominant;
// Le rang est une borne sur la hauteur de la structure Union-Find
private int rang=0;
// Ensemble des arêtes incidentes
private Set<Arete> incidences;
// Les sommets accessibles sont représentés par une table associant
// chaque sommet accessible à un chemin.
// On veut que le chemin mémorisé soit le plus court.
// On pourrait obtenir une représentation plus compacte en mémorisant
// moins d'information : pour les besoins des méthodes du TP il suffirait
// d'avoir la longueur du chemin et sa première arête.
private Map<Sommet, Chemin> accessibles;
public Sommet(Graphe g, String n) {
graphe = g;
nom = n;
dominant = this;
// Un sommet est créé sans arêtes incidentes.
// Le seul sommet accessible est lui-même, via le chemin vide.
incidences = new HashSet<Arete>();
accessibles = new HashMap<Sommet, Chemin>();
accessibles.put(this, new Chemin(this));
}
// Ajout d'une arête incidente.
// Pour mettre à jour l'ensemble des sommets accessible dans le graphe,
// il faut prendre tous les sommets accessibles depuis le sommet actuel,
// tous les sommets accessibles depuis le sommet cible, et comparer le
// nouveau chemin créé avec le meilleur chemin qui existait déjà.
public void ajouteArete(Arete a) {
incidences.add(a);
for(Map.Entry<Sommet, Chemin> accS1 : this.accessibles.entrySet()) {
for(Map.Entry<Sommet, Chemin> accS2 :
a.autreExtremite(this).accessibles.entrySet()) {
// À compléter...
// On construit le nouveau chemin entre deux extrémités,
// on le compare à l'éventuel chemin déjà existant, et on
// garde le plus court.
}
}
}
// Un sommet est bien coloré s'il n'a pas la même couleur que ses voisins.
public boolean bienColore() {
for (Arete a : incidences) {
if (a.autreExtremite(this).couleur == this.couleur) return false;
}
return true;
}
// Affecte à un sommet la plus petite couleur pas déjà prise par ses
// voisins.
public int colorie() {
this.couleur = 0;
while (!this.bienColore()) this.couleur++;
return this.couleur;
}
// Donne le sommet représentant la composante connexe à laquelle
// appartient [this].
public Sommet composante() {
if (dominant != this) {
// Cette mise à jour correspond à l'optimisation
// "compression de chemins".
dominant = dominant.composante();
}
return dominant;
}
// Fait l'union de deux composantes connexes.
// Pré-condition : [this] et [s] doivent être chacun le représentant
// de sa composante connexe (c'est-à-dire la racine de l'arbre
// correspondant dans la structure Union-Find), sans quoi la structure
// de données serait corrompue.
// Remarque : pas forcément malin de donner une pré-condition si critique
// à une méthode qui n'est pas privée. Il serait plus raisonnable de
// d'abord appliquer la méthode [composante()].
protected Sommet union(Sommet s) {
if (this.rang > s.rang) {
s.dominant = this; return this;
} else {
this.dominant = s;
if (this.rang == s.rang) s.rang++;
return s;
}
}
}
// Une arête a deux extrémités (ordre arbitraire, on regarde des graphes
// non orientés).
// On peut :
// - Savoir si un sommet est une extrémité
// - Obtenir l'autre extrémité si on en a déjà une
// - Obtenir le poids de l'arête (par défaut, 1)
class Arete {
// On représente les extrémités par un tableau à deux cases
// Comme souvent ici : c'est une possibilité parmi d'autres
private Sommet[] extremites;
public Arete(Sommet s1, Sommet s2) {
// On range les extrémité dans l'ordre donné par les paramètres
// Variante : on les classe en fonction d'un ordre (pas utile ici)
extremites = new Sommet[2];
extremites[0] = s1;
extremites[1] = s2;
// On inscrit l'arête dans les listes d'incidence de ses extrémités
s1.ajouteArete(this);
s2.ajouteArete(this);
}
// Donne l'autre extrémité
// Pré-condition : [s] est l'une des extrémités
public Sommet autreExtremite(Sommet s) {
if (s == extremites[0]) return extremites[1];
else return extremites[0];
}
// Vérifie qu'un sommet est une extrémité
public boolean admetExtremite(Sommet s) {
return (s == extremites[0] || s == extremites[1]);
}
// Pour une arête non pondérée, le poids est 1
public int getPoids() { return 1; }
}
// Une arête pondérée est une arête avec en plus un poids.
class AretePonderee extends Arete {
private int poids;
public AretePonderee(Sommet s1, Sommet s2, int p) {
super(s1, s2);
poids = p;
}
public int getPoids() { return poids; }
}
// Un chemin est un ensemble d'arêtes entre une source et une destination
// On peut :
// - Créer un chemin vide
// - Obtenir la longueur du chemin
// - Ajouter une arête compatible à la fin du chemin
// - Concaténer un chemin à la fin du chemin
// - Obtenir le chemin inverse
class Chemin {
protected ArrayList<Arete> aretes;
private Sommet source;
private Sommet destination;
// Le chemin vide est quand même défini au niveau d'un sommet
public Chemin(Sommet s) {
aretes = new ArrayList<Arete>();
source = s;
destination = s;
}
// La longueur est la somme des poids des chemins
public int longueur() {
int l = 0;
for(Arete a : aretes) {
l += a.getPoids();
}
return l;
}
// Ajout d'une arête à la fin du chemin
// - renvoie vraie si l'arête est compatible
// - renvoie faux (et ne fait rien) sinon
public boolean ajouteArete(Arete a) {
if (a.admetExtremite(destination)) {
aretes.add(a);
destination = a.autreExtremite(destination);
return true;
}
return false;
}
// Concaténation d'un chemin à la fin du chemin, renvoie un booléen
// comme l'ajout d'arête
public boolean concatene(Chemin c) {
if (c.source != this.destination) return false;
for (Arete a : aretes) {
this.ajouteArete(a);
}
return true;
}
// Construit un (nouveau) chemin renversé
public Chemin rev() {
Chemin c = new Chemin(destination);
for (int i=aretes.size()-1; i>=0; i--) {
c.ajouteArete(aretes.get(i));
}
return c;
}
}