Changes between Version 6 and Version 7 of CaoCourseTme8
- Timestamp:
- Apr 4, 2007, 7:54:06 PM (18 years ago)
Legend:
- Unmodified
- Added
- Removed
- Modified
-
CaoCourseTme8
v6 v7 134 134 comprise entre GMAX et GMAX. Chaque case correspond à une valeur de gain, et 135 135 contient un pointeur sur une des listes doublement chaînées définies ci-dessus. 136 * Le gain des cellules rattachées à la case d'index 0 est égal à GMAX 137 * Le gain des cellules rattachées à la case d'index i est égal à GMAX - i 138 * Le gain des cellules rattachées à la case d'index 2*GMAX est égal à - GMAX 136 139 137 140 On fait la même chose pour représenter la liste GAIN_R. … … 140 143 chaînée qui correspond à sa valeur de gain. Au fur et à mesure que les noeuds 141 144 sont transférés, les listes se vident, car un noeud qui a subi un mouvement 142 n'est plus autorisé à bouger. Puisque le gain des noeuds change ntau cours145 n'est plus autorisé à bouger. Puisque le gain des noeuds change au cours 143 146 de l'algorithme, un même noeud peut être retiré d'une liste et inséré dans 144 147 une autre, ce qui justifie l'utilisation de listes doublement chaînées. … … 158 161 bichain_t *PREV; // pointeur sur le noeud précédent de même gain 159 162 unsigned INODE; // index du noeud 160 int IGAIN; // index dans le tableau des gains : Gain = GMAX - INODE161 unsigned PART; // numero de la partie 0 pour R, 1 pour L163 int IGAIN; // index dans le tableau des gains 164 unsigned PART; // numero de la partie 0 pour R, 1 pour L 162 165 } bichain_t 163 166 }}} … … 167 170 bichain_t **GAIN_L; // pointeur sur le tableau de pointeurs pour la partie gauche 168 171 bichain_t **GAIN_R; // pointeur sur le tableau de pointeurs pour la partie droite 169 int LX; 170 int RX; 172 int LX; // index de la première case non vide de GAIN_L (init à -1) 173 int RX; // index de la première case non vide de GAIN_R (init à -1) 171 174 bichain_t **NODES; // pointeur sur le tableau de pointeurs sur les noeuds 172 175 } move_manager_t … … 178 181 179 182 '''graph_t * parse_graph(char *filename)''':: 180 Cette fonction prend pour argument un nom de fichier au format .dot181 représentant le graphe à partitionner, etconstruit en mémoire la structure183 Cette fonction prend pour argument un nom de fichier au format .dot 184 représentant le graphe à partitionner, construit en mémoire la structure 182 185 graph_t correspondante, et renvoie un pointeur sur cette structure. Si aucune 183 186 partition initiale n'est définie dans le fichier .dot, les noeuds d'index … … 192 195 graph 193 196 { 194 // l es clusters sont optionnels197 // la définition des clusters est optionnelle 195 198 subgraph cluster0 {0 1 2 3} 196 199 subgraph cluster1 {4 5 6 7} … … 206 209 207 210 '''void drive_graph(graph_t *p, char *filename)''':: 208 Cette fonction prend en paramètreun pointeur p sur une structure graph_t,211 Cette fonction prend pour argument un pointeur p sur une structure graph_t, 209 212 ainsi que le nom du fichier de sortie, et écrit sur disque un fichier au 210 213 format .dot, en conservant dans le fichier les informations de partition … … 213 216 214 217 '''bichain_t * cons_bichain (bichain_t *prev, bichain_t *next, unsigned inode, int igain, unsigned part)''':: 215 Cette fonction alloue la mémoire nécessaire pour créer un élément d'une liste218 Cette fonction alloue la mémoire nécessaire pour créer un objet de type bichain_t appartenant à une liste 216 219 doublement chaînée, elle initialise les différents champs de cette structure, 217 220 et renvoie un pointeur sur cette structure. … … 228 231 '''void add_node (move_manager_t *mm, bichain_t *node)''':: 229 232 Cette fonction prend pour arguments un pointeur sur la structure représentant 230 les gestionnaire de mouvements, un pointeur sur un élément de liste doublement 231 chaînée (représentant un noeud), contenant l'index du nSud dans le graphe, 232 un entier représentant l'index dans le tableau GAIN_R ou GAIN_L, et un entier 233 définissant le sous-ensemble d'appartenance (0 pour R, 1 pour L). Elle range 233 le gestionnaire de mouvements et un pointeur sur un élément de type bichain_t 234 représentant un noeud) dont les champs INODE, IGAIN et PART sont définis. Elle range 234 235 ce noeud dans la liste doublement chaînée correspondante, elle met à jour 235 le tableau NODES et les index LX ou LR. Les champs NEXT et PREV du nSud ne 236 sont pas utilisés, ils sont initialisés par la fonction add_node elle-même. 236 le tableau NODES et les index LX ou LR. Les champs NEXT et PREV sont initialisés par la fonction add_node(). 237 237 238 238 '''bichain_t * del_node(move_manager_t *mm, bichain_t *node)''':: 239 239 cette fonction prend pour arguments un pointeur sur la structure représentant 240 le sgestionnaire de mouvements, et un pointeur sur un élément de liste240 le gestionnaire de mouvements, et un pointeur sur un élément de liste 241 241 doublement chaînée (représentant un noeud). Elle retire cet élément de la 242 liste doublement chaînée, et renvoie un pointeur sur la structure bichain_t242 liste doublement chaînée, met à jour le chaînage, et renvoie un pointeur sur la structure bichain_t 243 243 pour une éventuelle libération de la mémoire. 244 244
