Changes between Version 5 and Version 6 of CaoCourseTme8
- Timestamp:
- Apr 4, 2007, 7:24:57 PM (18 years ago)
Legend:
- Unmodified
- Added
- Removed
- Modified
-
CaoCourseTme8
v5 v6 1 1 {{{ 2 2 #!html 3 <h1>TME 8 : Méthode de partitionnement de graphe Min-Cut</h1>3 <h1>TME 8 : Méthode de partitionnement de graphe Min-Cut</h1> 4 4 }}} 5 5 [[PageOutline]] … … 32 32 33 33 Attention: avec cette définition, à un seul signal de la net-list peuvent 34 correspondre plusieurs arêtes dans le graphe: si l e signal desortie d'une35 porte logique Cx attaque n portes C1 à Cn, on a n arêtes dans le graphe.34 correspondre plusieurs arêtes dans le graphe: si la sortie d'une 35 porte logique attaque n autres portes, on a n arêtes dans le graphe. 36 36 37 37 On appelle «matrice d'adjacence» {Aij} la matrice carrée N * N qui représente … … 53 53 54 54 On part d'une bi-partition équilibrée initiale arbitraire en deux ensembles 55 L et R, et on cherche à optimiser la fonction de coût FC, sans forcément56 rechercherle minimum absolu, mais avec un temps de calcul très court.55 L et R, et on cherche à optimiser la fonction de coût FC, sans garantie d'atteindre 56 le minimum absolu, mais avec un temps de calcul très court. 57 57 58 58 L'idée de base de l'algorithme est de pré-calculer, pour chaque cellule Ci … … 147 147 du graphe sont identifiés par leur index. On a donc besoin d'introduire dans 148 148 la structure «move_manager_t» représentant le gestionnaire de mouvements, 149 un tableau de pointeurs NODES [ ], indexé par le numéro du noeud, et contenant150 un pointeur sur la structure bichain_t représentant un les noeuds du graphe151 dans les listes doublement chaînées GAIN_L et GAIN_R.149 un moyen d'obtenir le pointeur sur la structure bichain_t représentant 150 un noeud du graphe lorsqu'on connait son index. On construit donc un 151 tableau de pointeurs NODES [ ], indexé par le numéro du noeud. 152 152 153 153 On utilise donc les structures suivantes: … … 157 157 bichain_t *NEXT; // pointeur sur le noeud suivant de même gain 158 158 bichain_t *PREV; // pointeur sur le noeud précédent de même gain 159 unsigned INODE; // index du n Sud160 int IGAIN; // index dans le tableau des gains 159 unsigned INODE; // index du noeud 160 int IGAIN; // index dans le tableau des gains : Gain = GMAX - INODE 161 161 unsigned PART; // numero de la partie 0 pour R, 1 pour L 162 162 } bichain_t
