KFaultVerification

Commentaire :
C'est dans cette classe que reside la partie exponentiel de l'algorithme. Les petits graphs prennent un temps inferieur a une seconde. Mais les graphs plus gros tels la grilleFinale.mgl (grille en 2*3) avec 24 switchs prend 1h30 a faire la verification. Comme optimisation principal, que je n'ai pas eu le temps de faire et qui n'est peut etre pas possible a faire en java :
Ce qui prend beaucoup de temps est la consultation des voisins pour determiner le nombre de sorties voisines d'un sous ensemble. La maniere la plus rapide d'effectuer cela, serait d'enregister pour tous les noeuds tous les voisins sous la forme d'un trableau de bits (0 signifant pas voisin et 1 signifiant voisin) Quand l'on teste les voisins d'un sous ensemble, il suffit d'avoir un seul tableau pour le sous-ensemble et de faire un & bit a bit sur le tableau. Apres, on n'aurait plus qu'a parcourir le graph et a rajouter les entrees des noeuds qui sont marque avec un dans le tableau. Cette optimisation assez complexe permettrait de gagner pas mal de rapidite.
La deuxieme tache de cet algo est d'indiquer les erreurs une fois la verification effectue. Pour cela on met en evidence la coupe du graph en le coloriant.

Principe de l'algo :
Pour faire la verirfication du graph, il faut tester tous les sous-ensembles de l'ensemble des switchs. (c'est pour cela que l'algo est exponentiel) Pour tester tous les sous ensembles a la suite, on considere le sous ensemble comme un tableau de bit. (ici un long, qui contient 64 bit) Si le bit X vaut 0, alors le switch X ne fait pas partie du sous-ensemble. Si le bit Y vaut 1, alors le switch Y fais partie du sous-ensemble. (pour tester le bit X on se sert des decalages en memoire) On augmente le long servant de tableau a chaque passage dans la boucle pour tester le sous-ensemble suivant. Pour un gain de rapidite, on met le sous ensemble dans un tableau de node et non dans un node set. (gain de 16% de rapidite)

Une fois que l'on possed un sous-ensemble, il faut tester le critere de cut crition dessus. Il suffit d'avoir le nombre de switchs du sous-ensemble, (nombre de cases remplis du tableau), le nombre de voisins et le nombre de sorties de ces voisins (avoir les informations sur les voisins est ce qui prend le plus de temps)