La classe FordFulkerson

Tout l’algorithme est « encapsulé » dans une classe template. Cette classe prend en paramètres deux map qui représentent les deux listes d’employés et de postes (avec comme clé un indice dans la liste), une liste des affectations et un coefficient maximum pour le flux.

	   typedef std::map<int,T1> MapT1;
           typedef std::map<int,T2> MapT2;
           typedef Affectation<int> AffectationFF;
           typedef std::list<AffectationFF> ListAffectation;
           __fastcall FordFulkerson(const MapT1&mapT1,const MapT2&mapT2,const ListAffectation&ListeAffectations,int CoeffMax);
	  

Pour limiter la place mémoire et pour accélérer les traitements, tout ce qui est interne à la classe FordFulkerson travaille sur les indices (int) des données dans les listes plutôt que sur les objets comme les employés ou les postes par exemple. Tout l’algorithme est dans le constructeur de la classe FordFulkerson. A la sortie du constructeur, la classe connaît la solution optimale et on peut utiliser la classe pour connaître la solution avec les méthodes suivantes :

           const T2 * __fastcall T1EstAffecteAT2(const T1 &t);
           const T1 * __fastcall T2EstAffecteAT1(const T2 &t);
	  

La première méthode prend un employé et donne le poste affecté et la seconde prend un poste et donne l’employé correspondant.

La matrice

Une matrice est un tableau de valeur à deux dimensions. Pour chaque couple t1 - t2 est associée une et une seule valeur. Le map a donc été utilisé pour représenter la matrice. La clé étant une paire de type int et int (pair <int,int>) et la donnée étant un entier (int) pour le coefficient.

Le graphe

Les sommets du graphe sont de type hétérogène ; nous avons des employés (ou T1), des postes (ou T2), une entrée et une sortie qui ne sont ni des postes, ni des employés. Pour résoudre ce problème, nous avons créé un nouveau type pour identifier les sommets du graphe. Il s’agit d’une paire avec comme première partie le type de sommet (entrée et sortie, employé ou poste) et un identifiant (pour différencier l’entrée de la sortie, ou l’indice de l’employé ou du poste).

           enum TypeSommet { ets_EntreeSortie = 0, ets_Indice1, ets_Indice2, };
           #define INDICE_ENTREE 1
           #define INDICE_SORTIE 2
           typedef pair<enum TypeSommet,int> IDSommet;
	  

Dans le graphe nous trouvons aussi des arcs. Un arc va d’un sommet à un autre avec un flux courant et un flux maximum.

           class Chemin
           {
           public: int FluxMax;
           int FluxCourant;
           IDSommet DuPoint,AuPoint;
           }
           typedef std::list<Chemin> ListChemin;
           typedef std::list<Chemin *> ListpChemin;
	  

Il faut ensuite relier les sommets aux arcs. Pour cela, un sommet doit avoir une liste d'arcs suivants pour avancer et une liste d’arcs précédents pour reculer.

           class Sommet
           {
           public: IDSommet ID;
           ListChemin SommetsSuivants;
           ListpChemin SommetsPrecedents;
           }
	  

Tous ces sommets sont ensuite mis dans une liste et pour que ce soit plus rapide quand on recherche un sommet particulier, on a utilisé un map avec comme clé l’identifiant du sommet et comme valeur ses caractéristiques (listes des arcs suivants et précédents) :

           typedef std::map<IDSommet,Sommet> MapSommet;
	  

La file des sommets marqués

Nous avons choisi de prendre une liste avec pour élément une classe dans laquelle nous trouvons un sommet d’arrivée, un sommet de départ, un booléen représentant le sens (true = + = on augmente le flux) et un coefficient représentant le flux.

	   template <class T> class FileChemin
           {
           public: T PointArrivee,PointDepart;
           bool Avance; //true si on avance vers la sortie et false sinon
           int Coeff;
           };
           typedef list<FileChemin<IDSommet> > ListeChemins;
	  

Optimisations

Comme nous l’avons vu précédemment, la classe FordFulkerson ne dépend pas des types de données sur lequel va s’appliquer l’algorithme. La taille mémoire prise par l’algorithme ne sera donc dépendante que du nombre d’employés (et du nombre de postes qui est identique). Pour éviter de perdre de la mémoire, nous travaillons toujours sur la même matrice, même en cas de situation de blocage où l’on « décale les zéros ». Pour optimiser encore un peu, en cas de blocage le graphe est conservé pour y rajouter les nouveaux arcs et supprimer ceux qui ont disparu après le « décalage des zéros ». Ceci implique des vérifications et des retraitements quand on supprime un arc dont le flux n’est pas nul, mais évite de recréer un graphe presque identique et de perdre les chemins déjà trouvés entre l’entrée et la sortie.