Changes between Version 2 and Version 3 of CaoCourseTme8

Timestamp:

Apr 4, 2007, 6:03:09 PM (18 years ago)

Author:

franck

Comment:

--

CaoCourseTme8

@@ -9 +9 @@
 On souhaite implanter en langage C un algorithme de partitionnement de graphe utilisant
 la méthode Min-Cut, dont le principe a été présenté en cours.
-
-{{{
-#!html
-<h1>TME 8 : Partitionnement de Graphe/MinCut</h1>
-}}}
 
 = A. Introduction = 
@@ -182 +177 @@
 On dispose d'un ensemble de fonctions permettant de construire et de manipuler les deux structures de données graph_t et move_manager_t. 
 
-== D.1. graph_t * parse_graph(char *filename) ==
-
-Cette fonction prend pour argument un nom de fichier au format.dot
-représentant le graphe à partitionner, et construit en mémoire la structure
-graph_t correspondante, et renvoie un pointeur sur cette structure. Si aucune
-partition initiale n'est définie dans le fichier .dot, les noeuds d'index
-inférieur à NBNODE/2 sont arbitrairement rangés dans le sous-ensemble L,
-et les noeuds d'index supérieur à NBNODE/2 sont rangés dans le sous-ensemble R.
-
-Un exemple de fichier au format .dot est donné ci-dessous. Les noeuds du graphe
-sont identifiés par un index, il y a une ligne par arête, les deux sous-graphes
-cluster0 et cluster1 définissent la partition initiale et sont optionnels.
+ '''graph_t * parse_graph(char *filename)'''::
+        Cette fonction prend pour argument un nom de fichier au format.dot
+        représentant le graphe à partitionner, et construit en mémoire la structure
+        graph_t correspondante, et renvoie un pointeur sur cette structure. Si aucune
+        partition initiale n'est définie dans le fichier .dot, les noeuds d'index
+        inférieur à NBNODE/2 sont arbitrairement rangés dans le sous-ensemble L,
+        et les noeuds d'index supérieur à NBNODE/2 sont rangés dans le sous-ensemble R.
+
+        Un exemple de fichier au format .dot est donné ci-dessous. Les noeuds du graphe
+        sont identifiés par un index, il y a une ligne par arête, les deux sous-graphes
+        cluster0 et cluster1 définissent la partition initiale et sont optionnels.
 
 {{{
@@ -211 +205 @@
 }}}
 
-== D.2. void drive_graph(graph_t *p, char *filename) ==
-
-Cette fonction prend en paramètre un pointeur p sur une structure graph_t,
-ainsi que le nom du fichier de sortie, et écrit sur disque un fichier au
-format .dot, en conservant dans le fichier les informations de partition
-(sous-ensemble L et R). Ce format est affichable sous forme graphique et
-permet de visualiser la partition.
-
-== D.3. bichain_t * cons_bichain (bichain_t *prev, bichain_t *next, unsigned inode, int igain, unsigned part) ==
-
-Cette fonction alloue la mémoire nécessaire pour créer un élément d'une liste
-doublement chaînée, elle initialise les différents champs de cette structure,
-et renvoie un pointeur sur cette structure.
-
-== D.4. void free_bichain (bichain_t *p) ==
-
-Cette fonction libère la mémoire allouée lors de la construction de l'objet
-bichain_t par la donction cons_bichain().
-
-== D.5. move_manager_t * cons_move_manager(graph_t *p) ==
-
-Cette fonction pend pour argument un pointeur sur la structure représentant
-le graphe partitionné, et construit en mémoire la structure move_manager_t
-correspondant à cette partition.
-
-== D.6. void add_node (move_manager_t *mm, bichain_t *node) ==
-
-Cette fonction prend pour arguments un pointeur sur la structure représentant
-les gestionnaire de mouvements, un pointeur sur un élément de liste doublement
-chaînée (représentant un noeud), contenant l'index du nSud dans le graphe,
-un entier représentant l'index dans le tableau GAIN_R ou GAIN_L, et un entier
-définissant le sous-ensemble d'appartenance (0 pour R, 1 pour L). Elle range
-ce noeud dans la liste doublement chaînée correspondante, elle met à jour
-le tableau NODES et les index LX ou LR. Les champs NEXT et PREV du nSud ne
-sont pas utilisés, ils sont initialisés par la fonction add_node elle-même.
-
-== D.7. bichain_t * del_node(move_manager_t *mm, bichain_t *node) ==
-
-cette fonction prend pour arguments un pointeur sur la structure représentant
-les gestionnaire de mouvements, et un pointeur sur un élément de liste
-doublement chaînée (représentant un noeud). Elle retire cet élément de la
-liste doublement chaînée, et renvoie un pointeur sur la structure bichain_t
-pour une éventuelle libération de la mémoire.
-
-== D.8. int compute_gain (graph_t *g, unsigned index) ==
-
-Cette fonction prend pour argument un pointeur sur la structure représentant le
-graphe, un index désignant un noeud particulier, et calcule le gain associé
-à ce noeud, pour la partition courante.
-
-== D.9. int global_cost (graph_t *g) ==
-
-Cette fonction prend pour argument un pointeur sur la structure représentant
-le graphe, calcule la fonction de coût globale pour la partition courante,
-et renvoie la valeur calculée.
+ '''void drive_graph(graph_t *p, char *filename)'''::
+        Cette fonction prend en paramètre un pointeur p sur une structure graph_t,
+        ainsi que le nom du fichier de sortie, et écrit sur disque un fichier au
+        format .dot, en conservant dans le fichier les informations de partition
+        (sous-ensemble L et R). Ce format est affichable sous forme graphique et
+        permet de visualiser la partition.
+
+ '''bichain_t * cons_bichain (bichain_t *prev, bichain_t *next, unsigned inode, int igain, unsigned part)'''::
+        Cette fonction alloue la mémoire nécessaire pour créer un élément d'une liste
+        doublement chaînée, elle initialise les différents champs de cette structure,
+        et renvoie un pointeur sur cette structure.
+
+ '''void free_bichain (bichain_t *p)'''::
+        Cette fonction libère la mémoire allouée lors de la construction de l'objet
+        bichain_t par la donction cons_bichain().
+
+ '''move_manager_t * cons_move_manager(graph_t *p)'''::
+        Cette fonction pend pour argument un pointeur sur la structure représentant
+        le graphe partitionné, et construit en mémoire la structure move_manager_t
+        correspondant à cette partition.
+
+ '''void add_node (move_manager_t *mm, bichain_t *node)'''::
+        Cette fonction prend pour arguments un pointeur sur la structure représentant
+        les gestionnaire de mouvements, un pointeur sur un élément de liste doublement
+        chaînée (représentant un noeud), contenant l'index du nSud dans le graphe,
+        un entier représentant l'index dans le tableau GAIN_R ou GAIN_L, et un entier
+        définissant le sous-ensemble d'appartenance (0 pour R, 1 pour L). Elle range
+        ce noeud dans la liste doublement chaînée correspondante, elle met à jour
+        le tableau NODES et les index LX ou LR. Les champs NEXT et PREV du nSud ne
+        sont pas utilisés, ils sont initialisés par la fonction add_node elle-même.
+
+ '''bichain_t * del_node(move_manager_t *mm, bichain_t *node)'''::
+        cette fonction prend pour arguments un pointeur sur la structure représentant
+        les gestionnaire de mouvements, et un pointeur sur un élément de liste
+        doublement chaînée (représentant un noeud). Elle retire cet élément de la
+        liste doublement chaînée, et renvoie un pointeur sur la structure bichain_t
+        pour une éventuelle libération de la mémoire.
+
+ '''int compute_gain (graph_t *g, unsigned index)'''::
+        Cette fonction prend pour argument un pointeur sur la structure représentant le
+        graphe, un index désignant un noeud particulier, et calcule le gain associé
+        à ce noeud, pour la partition courante.
+
+ '''int global_cost (graph_t *g)'''::
+        Cette fonction prend pour argument un pointeur sur la structure représentant
+        le graphe, calcule la fonction de coût globale pour la partition courante,
+        et renvoie la valeur calculée.
 
 = E. Travail à réaliser =
@@ -272 +258 @@
 progressivement les fichiers objets fournis par vos propres fichiers objet.
 
-== E.1. Construction et initialisation du gestionnaire de mouvements ==
-
-C'est un point important puisque que c'est la structure de base de
-l'algorithme. Vous disposez pour vous aidez d'une fonction dump_move_manager()
-qui affiche le contenu de la structure.
-
-== E.2. Ecriture de l'algorithme MinCut glouton ==
-
-Ecrivez la boucle réalisant les transferts de cellules tant que le transfert
-d'une paire de cellules améliore la fonction de coût FC.
-
-== E.3. Exécution et évaluation ==
-
-Exécutez cet algorithme sur différents graphes que vous définirez
-vous-mêmes. La partition résultante est-elle toujours la partition
-optimale? Pourquoi? Donnez un contre-exemple.
-
-== E.4. Ecriture des fonctions ==
-
-Ecrire les différentes fonctions d'accès aux structures de données définies
-dans la partie D, et validez ces fonctions en les intégrant peu à peu dans
-votre programme.
-
-== E.5. construction du graphe en mémoire ==
-
-L'objectif est ici d'écrire la fonction parse_graph(), en utilisant lex et
-yacc. Nous vous suggérons de supposer qu'il n'y a pas de clusters dans le
-fichier, puis de les introduire. Si vous n'avez pas le temps de construire
-le graphe, étudiez au moins la grammaire de ce petit langage.
+ '''1. Construction et initialisation du gestionnaire de mouvements'''::
+       C'est un point important puisque que c'est la structure de base de
+       l'algorithme. Vous disposez pour vous aidez d'une fonction dump_move_manager()
+       qui affiche le contenu de la structure.
+
+ '''2. Ecriture de l'algorithme !MinCut glouton'''::
+       Ecrivez la boucle réalisant les transferts de cellules tant que le transfert 
+       d'une paire de cellules améliore la fonction de coût FC.
+
+ '''3. Exécution et évaluation'''::
+       Exécutez cet algorithme sur différents graphes que vous définirez
+       vous-mêmes. La partition résultante est-elle toujours la partition
+       optimale? Pourquoi? Donnez un contre-exemple.
+
+ '''4. Ecriture des fonctions''':: 
+       Ecrire les différentes fonctions d'accès aux structures de données définies
+       dans la partie D, et validez ces fonctions en les intégrant peu à peu dans
+       votre programme.
+
+ '''5. construction du graphe en mémoire'''::
+       L'objectif est ici d'écrire la fonction parse_graph(), en utilisant lex et
+       yacc. Nous vous suggérons de supposer qu'il n'y a pas de clusters dans le
+       fichier, puis de les introduire. Si vous n'avez pas le temps de construire
+       le graphe, étudiez au moins la grammaire de ce petit langage.