Algorithme de GraphToBiparti.java :

Commentaires :

Il n'y a pas de probleme de rapidite. (il prends moins d'un seconde pour des graphes qui demanderont plusieurs heures ou plusieurs jours pour la verification)

Principe de l'algo :

L'algorithme de transformation est recursif. Le principe de l'algorithme est qu'avant de traiter le noeud courant, il traite tous les noeuds voisins.

Si le noeud est un switch, il suffit de rajouter des noeuds speciaux si le switch a des sorties et de rajouter des noeuds speciaux entre lui et les switchs voisins.

Si le noeud fait partie d'un block (le noeud a une entree), il faut former un block avec tous les noeuds-blocks voisins. Plus simplement, il ne doit rester qu'un noeud ayant la somme des entrees, sortie et tous les liens des noeuds-blocks voisins. On fait cela en "aglomerant" tous les noeuds-blocks voisins au noued courant si leur traitement est fini.