Available nodes

 Coursidor

Le jeu de Quoridor est un jeu de société créé par Mirko Marchesi en 1997. Il se joue sur un plateau de jeu carré, avec deux joueurs possédant un pion initialement placé dans leur zone de départ. L'objectif de chaque joueur est d'atteindre une zone d'arrivée située usuellement du côté opposé du plateau. A chaque tour de jeu, un joueur peut choisir entre soit déplacer son pion d'une case, soit placer un mur limitant les mouvements possibles sur le plateau (dans le meilleur des cas, les mouvements de l'adversaire) sans jamais les bloquer complètement.
(image tirée du site jeuxdenim.be)

Le jeu a été longuement étudié, et a fait en particulier l'objet d'un mémoire de master par L. Glendenning en 2005, qui s'est intéressée à différents algorithmes de jeu, ainsi qu'à un autre document (résultat aussi probablement d'un master) de P.M.C. Mertens en 2006. Le site QuoridorStrats propose aussi des tutoriels et des exemples de stratégies. De manière assez intéressante et non triviale, le jeu de Quoridor ne termine pas forcément pour des joueurs optimaux, et peut conduire à des situations de match nul, comme discuté dans ce forum.
Ce projet propose d'implémenter une variante de Quoridor nommée Coursidor, dans laquelle on remplace l'objectif de traverser le plateau par la règle suivante : les deux joueurs ont pour objectif de parcourir le plateau pour passer sur un certain nombre de bases appelées objectifs, dans un ordre quelconque, à la manière du jeu de baseball. Le plus rapide à passer par l'ensemble des bases, puis à revenir à sa zone de départ, est déclaré vainqueur. Comme dans le jeu de Quoridor, les joueurs peuvent décider de placer des murs pour ralentir leur adversaire, tout en essayant de ne pas se ralentir trop eux-mêmes.

La variante canadienne suppose que chaque joueur ne voie pas les murs posés par son adversaire. La seule façon pour un joueur de détecter un mur consiste à chercher à se déplacer dedans1. Il s'agit d'une variante tout à fait sérieuse d'algorithmes de graphes existants, comme par exemple le problème du voyageur canadien.

 Graphes de jeu

Le plateau de jeu de Coursidor est représenté par un graphe, ayant la propriété d'être sous-graphe du pavage triangulaire. Ces graphes sont représentés en mémoire par leur matrice d'ajacence, qui est implémentée comme une matrice creuse définie dans la GNU Scientific Library (cf. la section dédiée pour plus de détails). Le graphe contient un nombre de sommets num_vertices (ou n pour simplifier) et un nombre d'arêtes num_edges. La matrice d'adjacence du graphe, nommée t, est une matrice de taille n*n représentant les arêtes du graphe. Les ids des sommets sont des entiers compris entre 0 et num_vertices-1 au sens large. Le graphe est supposé plongé dans le plan, de manière à ce que les arêtes ne puissent prendre que 7 directions possibles, à savoir NO_EDGE=0, NW=1, NE=2, E=3, SE=4, SW=5, et W=6. Une direction spéciale, WALL_DIR, indique la présence d'un mur. Plus précisément:
  • t[i][j] vaut NO_EDGE s'il n'y a pas d'arête entre les deux sommets i et j,
  • il vaut WALL_DIR si l'arête entre le sommet j et le sommet i est bloquée par un mur,
  • il vaut NW si le sommet j se situe au nord-ouest de i,
  • il vaut SW si le sommet j se situe au sud-ouest de i,
  • il vaut W si le sommet j se situe à l'ouest de i,
  • … et symétriquement pour les directions restantes.
Exemple de graphe :
(pas d'arête entre 1 et 2)
num_vertices = 4
t = [[ 0 3 4 0 ]
     [ 6 0 0 4 ]
     [ 1 0 0 3 ]
     [ 0 1 6 0 ]]
Le graphe sur lequel la partie est joué est non-dirigé. Ainsi, les directions des arêtes se correspondent deux à deux, de manière symétrique. Les directions des arêtes sont utilisées principalement pour aider au placement des murs sur le plateau de jeu.
Le sujet propose de travailler sur plusieurs plateaux de jeu de formes différentes, de taille variable spécifiée par un entier m. Le nombre m peut être fourni sur la ligne de commande et permet généralement de spécifier la largeur du graphe. Les plateaux de jeu disponibles pour les parties contiennent au moins les deux plateaux suivants2 :
Graphe parallèlogramme (type P), avec m impair ≥ 2 Graphe triangulaire (type T), avec m ≥ 2

Dans le jeu, il est possible de placer des murs pour empêcher les joueurs d'utiliser certaines arêtes. Chaque joueur dispose au début de la partie d'un certain nombre de murs. Le nombre de murs donnés à chaque joueur est le nombre d'arêtes du graphe divisé par 16, dont on prend la partie supérieure. Le jeu standard se joue sur un graphe triangulaire de largeur 5 avec 156 arêtes, ce qui donne 10 murs par joueur. Les murs ne peuvent pas être placés de n'importe quelle manière sur le graphe. Un mur doit être placé sur deux arêtes consécutives d'un sommet du graphe, comme dans les exemples suivants:

Le placement d'un mur sur deux arêtes du graphe est équivalent au fait de retirer les deux arêtes du graphe.
Les graphes doivent être implémentés en utilisant les matrices définies dans la GSL. Comme la GSL n'implémente pas directement de structure de données de graphes, un des objectifs du projet est de définir une abstraction sous la forme d'une interface permettant de manipuler ces matrices comme des graphes (créer un graphe, ajouter une arête, …).

 Règles du jeu

Les règles du jeu de Quoridor sont décrites de manière très imagée dans ce lien. Les règles de Coursidor reprennent les mêmes principes de base.
  • Initialement, le plateau de jeu est choisi parmi les plateaux décrits dans la section précédente. Chaque joueur dispose d'un pion ainsi que d'un ensemble de murs. Les positions de départ du pion de chaque joueur sont fixées sur le plateau de jeu, et différentes. Le plateau de jeu définit aussi un ensemble de positions objectifs. Les positions des joueurs et des objectifs est assurée d'être symétrique. Il doit forcément exister au moins un objectif sur le plateau de jeu. Les objectifs ne peuvent pas être les positions de départ des joueurs.
  • Les deux joueurs sont représentés par les entiers 0 (BLACK) et 1 (WHITE). Le joueur 0 commence la partie.
  • L'objectif de chaque joueur est de déplacer son pion sur l'ensemble des sommets objectifs, puis de revenir à sa case de départ.
  • A chaque tour de jeu, le joueur produit un coup sous la forme d'une valeur de type struct move_t (les types sont décrits dans la partie suivante).
    enum player_color_t { BLACK=0, WHITE=1, NO_COLOR=2 };   // The colors of the players
    
    enum move_type_t { NO_TYPE = 0, WALL = 1, MOVE = 2, JUMP = 3, WATERLOO = 4 }; // The possible types of moves
    
    typedef size_t vertex_t;                                // The ids of the vertices
    
    struct edge_t { vertex_t fr, to; };                     // An edge of the graph
    
    struct move_t {                                         // A move in the game, given by :
      enum move_type_t t;                                   // - its type
      enum player_color_t c;                                // - the color of the player issueing the move
      vertex_t m;                                           // - the id of a vertex in case of MOVE or JUMP or WATERLOO
      struct edge_t e[2];                                   // - the two edges for the wall in case of WALL or WATERLOO
    };
    Le coup possède un champ de type enum move_type_t, qui spécifie le type du coup. Ce champ peut prendre les valeurs MOVE (pour un déplacement), JUMP (pour un saut), WALL (pour le placement d'un mur), WATERLOO (pour un coup spécial), ou encore NO_TYPE pour décrire un coup invalide. Les coups valides sont les suivants:
    • Déplacement du pion (de type MOVE):
      Le pion se déplace en ligne droite de sa position à une position d'arrivée. Il est caractérisé par la donnée de l'identifiant du sommet sur lequel le pion se déplace, placée dans le champ m. La distance à laquelle les pions peuvent se déplacer dépend de leur dernier mouvement précédent et de la direction qu'ils veulent prendre :
      • si le déplacement se fait dans la même direction que le dernier mouvement, le pion peut se déplacer jusqu'à une distance 3 dans la même direction;
      • si le déplacement se fait dans une direction à 60° du dernier mouvement, le pion peut se déplacer jusqu'à une distance 2 dans la même direction;
      • sinon le déplacement se fait sur n'importe lequel des sommets voisins.

      Un déplacement se fait forcément sur une case différente de la case de départ. Pour effectuer un déplacement, il faut que toutes les cases (arrivée, et cases intermédiaires en cas de déplacement d'une longueur > 1) soient valides (i.e correspondent à une arête du graphe) et libres (i.e pas d'adversaire dessus). Tout objectif traversé par un déplacement (même long) est considéré comme validé. Un déplacement qui cherche à traverser un mur (connu ou inconnu) est en fait de type WATERLOO. Tant que le joueur ne s'est pas déplacé, il n'est possible de faire des déplacements qu'à distance 1. Le fait de poser un mur n'a pas d'incidence sur le dernier mouvement. Le champ e est non utilisé.
    • Saut par dessus l'adversaire (de type JUMP):
      Ce coup ne peut être réalisé que dans le cas où le pion de l'adversaire est adjacent au pion du joueur. Dans ce cas, celui-ci peut choisir de déplacer son pion en sautant par dessus l'adversaire. La position d'arrivée doit dans ce cas être une case adjacente à la position de l'adversaire, sans être la position de départ. Le dernier déplacement unitaire correspond à l'arête entre la position de l'adversaire et la position d'arrivée du saut. Tout objectif traversé par le saut (même la position de l'adversaire) est considéré comme validé. Un déplacement qui cherche à traverser un mur (connu ou inconnu) est en fait de type WATERLOO. Le champ e est non utilisé.
    • Placement d'un mur (de type WALL):
      Ce coup est caractérisé par la donnée des deux arêtes du plateau recouvertes par le mur, placées dans le champ e, à l'aide d'une structure struct edge_t[2]. Il ne peut être réalisé que si le joueur possède encore des murs à placer. Le placement d'un mur ne peut se faire s'il empêche l'un des joueurs de rejoindre sa case d'arrivée ou n'importe lequel des objectifs par un chemin sur le graphe de jeu. Chaque joueur doit pouvoir continuer à jouer la partie, même après la pose d'un mur.

      Le champ m est non utilisé. On impose que le champ fr soit le même pour les deux arêtes, et que les deux arêtes correspondent à deux directions consécutives sur le graphe à partir de fr (dans n'importe quel sens, par exemple NE et E, ou E et NE). Lorsque le joueur place un mur, le serveur ne transmet que l'information du mur, et pas les arêtes du mur (typiquement { .t = WALL, .e = { INVALID_EDGE, INVALID_EDGE } }).

      Il n'est possible de placer un mur que sur des arêtes existantes. Dans le cas contraire, le coup est invalide. Si le fait de poser un mur empêche l'un des joueurs de rejoindre sa case d'arrivée ou n'importe lequel de ces objectifs, c'est aussi un WATERLOO.

    Pour tous les coups joués, les champs t et c doivent être positionnés correctement.
  • Frappe de Waterloo : un coup de déplacement ou la pose d'un mur, même valide, peut être invalidé par le serveur de jeu. En pratique, cela se produit lorsqu'un joueur propose de se déplacer sur le graphe ou de poser un mur, sans connaître l'existence d'un autre mur qui le bloque. Dans ce cas, le mouvement ou le placement du mur qu'il propose lui est refusé, et les règles sont les suivantes :
    • Si il s'agissait d'un déplacement de type MOVE, le joueur se déplaçait en ligne droite, et il est arrêté par le premier mur qu'il rencontre. Cela signifie en particulier qu'il peut quand même avancer jusqu'au mur en question. En ce cas, le coup retourné est de type WATERLOO, le champ m contient la position du joueur juste avant le mur et le champ e contient l'arête ayant bloqué le déplacement (l'autre arête étant positionnée à INVALID_EDGE)

      Ex. : { .t = MOVE, .m = 7 } est transformé en { .t = WATERLOO, .m = 6, .e = {{6, 7},INVALID_EDGE} }

    • Si il s'agissait d'un déplacement de type JUMP, le joueur reste sur place. En ce cas, le coup retourné est de type WATERLOO, le champ m contient la position inchangée du joueur et le champ e contient les arêtes ayant bloqué le déplacement. Dans l'exemple suivant, le joueur est en position 6 et saute par dessus l'adversaire en position 7 pour arriver en position 8. Il reste sur place à cause d'un mur entre 6 et 7 :

      Ex. : { .t = JUMP, .m = 8 } est transformé en { .t = WATERLOO, .m = 6, .e = {{6, 7},INVALID_EDGE} }

      Remarque : le joueur resterait aussi sur place s'il n'y avait qu'un mur entre 7 et 8, et ce serait ce mur qui lui serait renvoyé.

    • Dans les deux cas précédents (JUMP et MOVE), le dernier déplacement unitaire n'est modifié que dans le cas où le joueur s'est effectivement déplacé (et donc, dans le cas d'un JUMP, il n'est pas modifié, même si le joueur avait le droit de sauter sur son adversaire).
    • Si il s'agissait d'un placement de mur WALL placé sur un mur déjà existant, le nouveau mur n'est pas placé. En ce cas, le coup retourné est de type WATERLOO, le champ m est placé à INVALID_VERTEX et le champ e contient les arêtes ayant bloqué le placement.

      Ex. : { .t = WALL, .e = {{20, 21}, {20, 22}} } est transformé en { .t = WATERLOO, .e = {{21, 20},INVALID_EDGE} } (le mur ayant bloqué le déplacement partage une arête avec le mur demandé)

    • Si il s'agissait d'un placement de mur WALL qui empêcherait le joueur de rejoindre ses objectifs, alors le nouveau mur n'est pas posé. En ce cas, le coup retourné est de type WATERLOO, le champ m est placé à INVALID_VERTEX et le champ e contient deux arêtes invalides.

      Ex. : { .t = WALL, .e = {{20, 21}, {20, 22}} } est transformé en { .t = WATERLOO, .m = INVALID_VERTEX, .e = {INVALID_EDGE, INVALID_EDGE} }

  • Les pions des deux joueurs ne peuvent jamais occuper la même position. Deux murs ne peuvent jamais se chevaucher.
  • Le gagnant de la partie est le premier joueur à rejoindre sa case de départ après avoir parcouru tous les objectifs, c'est-à-dire avoir déplacé son pion sur toutes les cases d'objectifs au moins une fois.
  • Toute forme de coup invalide fait immédiatement perdre le joueur qui l'a joué.
MOVE JUMP WALL
Type du coup (.t) invalide ILLEGAL ILLEGAL ILLEGAL
Couleur du joueur incorrecte ILLEGAL ILLEGAL ILLEGAL
Déplacement hors des positions valides ILLEGAL ILLEGAL N/A
Déplacement à travers arête inexistante ILLEGAL ILLEGAL N/A
Saut sans passer sur l'adversaire N/A ILLEGAL N/A
Saut sur place N/A ILLEGAL N/A
Déplacement à travers l'adversaire ILLEGAL N/A N/A
Déplacement à travers un mur WATERLOO WATERLOO N/A
Placement de mur sur des arêtes invalides N/A N/A ILLEGAL
Placement de mur au delà du nombre autorisé N/A N/A ILLEGAL
Placement de mur sur un mur déjà existant N/A N/A WATERLOO
Placement de mur bloquant l'adversaire N/A N/A WATERLOO

 Murs et masques

Cette partie contient une précision sur la façon de gérer les murs dans le graphe de jeu. Elle n'est pas obligatoire pour le fonctionnement du projet, dans la mesure où chaque client et serveur peut encoder les murs dans sa matrice de la façon dont il le désire.

On propose de gérer les arêtes murées en utilisant un bitmask Dans le projet, les directions sont des enum dir_t stockés à travers des entiers non signés. Pour simplifier, , je considère les entiers comme codés sur 8 bits. Dans ce cas, les directions prennent la forme suivante :

NO_EDGE = 0 = 00000000
NW = 1 = 00000001
NE = 2 = 00000010
E = 3 = 00000011
SE = 4 = 00000100
SW = 5 = 00000101
W = 6 = 00000110
Pour représenter des arêtes murées, on ajoute à cela la constante WALL_MASK qui vaut :
WALL_MASK = 10000000
L'idée est de coder dans le bit de poids fort (le plus à gauche ici) le fait d'être un mur ou pas. Ainsi, une direction vers le NE qui a été murée correspond à :
WALL_NE = 10000010
Noter le bit à 1 au début du mot (le mur), et les bits 010 à la fin du mot (la direction NE).

Pour calculer avec les bitmasks, il suffit d'utiliser les opérations binaires en C. Par exemple :

WALL_NE == (NE | WALL_MASK)
Avec ces opérations, il est même possible d'enlever un mur à une direction (ce qui ne sert pas a priori dans le jeu qui nous concerne) :
NE == (WALL_NE & ~WALL_MASK)
Et enfin, il est très facile de tester si une direction est murée :
enum dir_t i_am_dir; (i_am_dir & WALL_MASK) != 0 ssi i_am_dir est murée
Pour plus d'informations au sujet des bitmasks, la page Wikipedia fournit des exemples de cas d'utilisation des bitmasks en programmation.

 Serveur et client

L'objectif du projet consiste à implémenter un ensemble de fonctions permettant de faire jouer deux joueurs à une partie de Coursidor. Le code sera décomposé en deux parties distinctes :
  • Un ensemble de clients implémentant tous une interface commune, gérant leur propre plateau de jeu et jouant chacun selon leur objectif propre. Ces clients sont censés être automatiques : ils doivent décider d'un coup à jouer à l'aide d'un algorithme, sans intervention extérieure.
  • Un serveur de jeu organisant une partie, faisant jouer chaque client à son tour en lui envoyant les coups joués par son adversaire, enregistrant le coup du client à son tour et notifiant les clients de la fin de la partie.
Un certain nombre d'interfaces sont fournies pour le projet. Ces interfaces sont non modifiables:
  • Le fichier move.h décrit le format des coups joués dans la partie (discutés dans la section Règles du jeu).
  • Le fichier graph.h décrit le format des graphes utilisés comme graphes de jeu (discutés dans la section Graphes de jeu).
  • Le fichier player.h décrit la liste de fonctions à implémenter pour un client désirant jouer à la partie.
Le serveur joue le rôle d'entremetteur entre les joueurs. Il commence par décider qui est le premier joueur, nommé BLACK ou 0. Il construit le plateau de jeu sur lequel la partie va se dérouler, et initialise les positions des joueurs et des objectifs. Le serveur transmet ensuite ces informations à chaque joueur en utilisant leur fonction initialize.

Après cela, il fait alterner les coups des deux joueurs en appelant leur fonction play. Cette fonction retourne un struct move_t indiquant le coup du joueur courant. Un joueur ne peut pas jouer de coup de type WATERLOO. Le serveur vérifie le coup du joueu selon les règles du jeu. En particulier, il détermine si le coup est un WATERLOO ou pas, et si c'est le cas, il calcule le coup réel joué dans la partie. Au tour suivant, il transmet les deux derniers coups réels des deux joueurs à chaque joueur, tout en masquant les positions des murs.

Lorsque la partie se termine, le serveur appelle les fonctions finalize des deux joueurs.

Au final, l'ensemble de ces interactions correspond au pseudo-algorithme suivant :
first_player = random_or_config()
graph = make_graph()
previous_moves = { { .t = NO_TYPE }, { .t = NO_TYPE } }
for each player p
    player_col = (p == first_player) ? BLACK : WHITE
    p->initialize(player_col, graph)
while true
   p = compute_next_player()
   reduced_moves = hide_wall_data(previous_moves)
   player_move = p->play(reduced_moves)
   if is_invalid(player_move) or is_game_over()
      break
   if is_waterloo(player_move)
     player_move = waterloo_move(player_move)
   previous_moves[p] = player_move

for each player p
   p->finalize()
Exemple de début de partie du point de vue du serveur :
sophy->initialize(B, graph)
david->initialize(W, graph)

sophy->play({{.t=NO_TYPE,.c=NO_COLOR}, {.t=NO_TYPE,.c=NO_COLOR}})
//                -> returns a move : {.t=MOVE,.c=B,.m=6}

david->play({{.t=MOVE,.c=B,.m=6}, {.t=NO_TYPE,.c=NO_COLOR}})
//                -> returns a move : {.t=MOVE,.c=W,.m=4}

sophy->play({{.t=MOVE,.c=B,.m=6}, {.t=MOVE,.c=W,.m=4}})
//                -> returns a wall : {.t=WALL,.c=B,.e={{.fr=0,.to=1},{.fr=0,.to=3}}}
//                -> server hides wall data for next player

david->play({{.t=WALL,.c=B,.e={INVALID_EDGE,INVALID_EDGE}}, {.t=MOVE,.c=W,.m=4}})

 Détails techniques

Pour les besoins du projet, les fichiers devront être organisés de la manière suivante dans le dépôt :
    /               -- Base directory
     Makefile       -- Global Makefile
    /src            -- Source files
    /test           -- Source files for the tests
    /install        -- Install directory (should be empty in the repository but for an empty .gitkeep file)
Le serveur de jeu se présentera sous la forme d'un exécutable server installé dans le répertoire install. Il devra, par l'intermédiaire d'options passées sur la ligne de commande permettre de configurer la partie, et en particulier sélectionner la forme du plateau (avec des graphes de tailles et de formes différentes).
./install/server [-m M] [-t T] [-M NB] ./install/player1.so ./install/player2.so

Les tests seront réalisés sous la forme d'exécutables test* qui doivent eux aussi être installés dans le répertoire install. Ils doivent être compilés avec -lgcov et permettre d'exécuter l'ensemble des tests présents dans le code. En particulier, ils serviront d'outil de mesure de la couverture des tests avec gcov.

Tout exécutable ou autre fichier non indispensable au projet (fichiers temporaires, fichiers objets, fichiers de logs …) stocké à l'intérieur du dépôt verra la personne ayant initié le premier commit se voir infliger un blâme. De la même manière, après avoir exécuté la règle make install, le répertoire install doit contenir exactement trois types d'exécutables : server pour le serveur principal, test* pour le(s) exécutable(s) de test, et *.so pour les clients sous la forme de bibliothèques partagées.

 Makefile

Le fichier Makefile  devra fournir :
  • une règle build qui compilera l'ensemble du code sans les tests,
  • une règle build_tests qui compilera les tests,
  • une règle test qui exécutera les tests
  • une règle install qui copiera les exécutables (un exécutable nommé server, et un nombre non spécifié de fichiers .so et test_*) à l'intérieur du répertoire désigné, et
  • une règle clean qui supprimera les fichiers compilés et installés.
Le Makefile doit pouvoir prendre une variable GSL_PATH qui indique le répertoire où est installée la bibliothèque libgsl.so. Par exemple :
GSL_PATH=/net/ens/renault/save/gsl-2.6/install make
Cette variable pourra prendre des valeurs différentes selon les machines sur lesquelles le code sera compilé (en particulier la forge).

Pour permettre à l'exécutable de trouver de lui-même les bibliothèques nécessaires, il est demandé d'utiliser l'option --rpath du linker. La documentation donne quelques explications, la plupart du temps, il s'agira de passer les bonnes options au compilateur lors de l'édition de liens (avec une syntaxe d'une évidence trouble) :

LDFLAGS += -Wl,--rpath=${GSL_PATH}/lib

 dlopen

L'un des aspects de ce projet est de rendre les clients interopérables entre équipes de projets. A cet effet, il est demandé que chaque client soit compilé sous la forme d'une bibliothèque partagée et chargeable de manière dynamique par le serveur.
  • Les différents clients doivent être compilés avec l'option -shared de gcc;
  • Le serveur doit pouvoir charger les clients de manière dynamique, en utilisant les fonctions de la famille dlopen, définies dans dlfcn.h. Il est possible de s'inspirer des instructions données dans la page suivante, qui contiennent, entre autres, un exemple complet d'utilisation.
Il est demandé d'implémenter au moins deux clients différents, i.e ayant des stratégies différentes. Il est aussi demandé de faire attention à éviter la duplication du code (en particulier pour les données du plateau de jeu). Remarquer que l'interface ne permet pas de communication dudit plateau entre client et serveur pendant la partie.

 GSL

La GNU Scientific Library est une bibliothèque C et C++ permettant de faire des calculs numériques. Dans le cadre de ce sujet, elle fournit des implémentations de matrices denses et creuses, ainsi que des algorithmes de résolution de systèmes linéaires. Malheureusement, elle ne fournit pas d'algorithmes de graphes, ce qui laisse toute latitude pour les implémenter.
La version 2.6 est la version miminale pour compiler et exécuter le projet. Une version de cette bibliothèque est installée sur les machines de l'école dans le répertoire /net/ens/renault/save/gsl-2.6/install.
Pour créer une matrice creuse avec la GSL, il suffit de faire:
gsl_spmatrix_uint *mat = gsl_spmatrix_uint_alloc(n, n);
for (each edge from i to j)                               // The edges depends on the graph
    gsl_spmatrix_uint_set(mat, i, j, 1);
Ceci crée une matrice creuse d'entiers au format COO (Coordinate Storage). Comme les graphes considérés ont des degrés faibles, cette façon de faire permet de stocker efficacement leurs matrices d'ajacence. Mais, si on désire itérer sur les arêtes des graphes, il est nécessaire de faire:
// Loop over all pairs of vertices (n*n iterations)
for (unsigned int i = 0; i < mat->size1; i++) {
    for (unsigned int j = 0; j < mat->size2; j++) {
        if (gsl_spmatrix_uint_get(mat, i, j) == 1) {      // Select only the edges in the matrix
                                                          // Do something for the edge from i to j
        }
    }
}
Il n'est pas difficile de se rendre compte que cette manière de faire est algorithmiquement inefficace : pour trouver les voisins d'un sommet i du graphe, il faut parcourir toute la ligne i de la matrice d'adjacence. Heureusement, la bibliothèque GSL permet de convertir la matrice précédente dans un format plus efficace :
gsl_spmatrix_uint* csr = gsl_spmatrix_uint_compress(mat, GSL_SPMATRIX_CSR);
Ceci crée une matrice creuse d'entiers au format CSR (Compressed Row Format) dans laquelle les indices des valeurs non nulles de la matrice sont stockés consécutivement dans un tableau.
for (unsigned int i = 0; i < csr->size1; i++) {           // Loop over all edges (nnz iterations, ie the non-zero values of csr)
    for (unsigned int k = csr->p[i]; k < csr->p[i+1]; k++) {
         unsigned int j = csr->i[k];                      // `j` is the index of the other extremity of the edge
                                                          // Do something for the edge from i to j
    }
  }
Pour le sujet, il est demandé à ce que les matrices utilisées soient toutes au format CSR. Si les matrices sont dans des formats différents, cela rendra les clients et les serveurs non interopérables. Pour vérifier le format de la matrice mat, il suffit d'appeler la fonction gsl_spmatrix_uint_type(mat) (qui renvoie une chaîne de caractères "COO" ou "CSR").

 Graphviz et Dot

Le sujet peut être facilité si l'on dispose d'outils efficaces pour représenter les graphes. Pour aider en cela, la bibliothèque Graphviz fournit des outils efficaces. Cette section donne quelques pistes pour leur utilisation, mais elle n'est pas indispensable au projet.
  • La page Wikipedia exposant le format du langage DOT de manière simplifiée;
  • La documentation de Graphviz, en particulier toutes les couleurs utilisables;
Deux commandes à retenir pour utiliser Graphviz (les rendus diffèrent selon la commande utilisée) : L'exemple de graphe à 4 sommets de la section Graphes de jeu au format .dot (mais avec un peu de couleur) :
dot -Tpdf graph.dot -o graph.pdf

neato -Tpdf graph.dot -o graph.pdf
graph G {
  graph [bgcolor=gray];
  node[style=filled];
  0 [fontcolor=white,fillcolor=green,shape=circle,fixedsize=true,width=0.5];
  1 [fontcolor=white,fillcolor=red,shape=circle,fixedsize=true,width=0.5];
  2;
  3;
  0 -- 1;
  0 -- 2;
  1 -- 3;
  2 -- 3;
}

 Contact

Pour toute information complémentaire, contacter : David RENAULT.

1.L'expression consacrée est évidemment "frapper son Waterloo".
2.D'autres plateaux de jeu pourront être ajoutés au fur et à mesure des projets.