Matrices, domaines

A propos des matrices

Il est parfois utile que les ressources d'un certain type soient représentées par un tableau à 2 dimensions. L'exemple le plus fréquent est lorsque vous avez un nombre fixé de créneaux horaires par jour et un nombre de jours fixés par semaine.
De tels types de ressources sont appelés types de ressources matricielles ou matrices.

Toutes les ressources dans une matrice ont toujours des noms spéciaux, formés de deux entiers séparés par un espace simple.Le premier entier représente l'index de la colonne (abscisse) et le second l'index de la ligne (ordonnée). Les ressources dans une matrice sont toujours ordonnées en premier par lignes, ensuite par colonnes (voir la documentation de la fonction res_new_matrix() ).

Module modifié

Disons que nous voulons modifier l'exemple précédent de sorte à ce que nous ayons seulement la ligne d'une ressource qu'un évènement devra utiliser, et non la ressource exacte. Nous modifierons également le module pour qu'il utilise les domaines de ressources, une nouveauté des noyaux 0.2.x .

#include <stdio.h>
#include <stdlib.h>
#include "module.h"

#define        RESTYPE                "dummy-type"

static resourcetype *dummy;
static int width, height;

int handler(char *restriction, char *content, tupleinfo *tuple)
{
        int row;
        int result;
        int typeid;

        int *resid_list;
        int resid_num;

        int n;

        domain *dom;

        result=sscanf(content, "%d", &row);
        if(result!=1) {
                error(_("L'index de ligne doit être un entier"));
                return -1;
        }

        if(row<0||row>height-1) {
                error(_("L'index de ligne doit être entre 0 et %d"), height-1);
                return -1;
        }

        typeid=dummy->typeid;

        resid_list=malloc(sizeof(*resid_list)*width);
        if(resid_list==NULL) {
                error(_("Ne pas allouer de mémoire"));
                return -1;
        }

        for(n=0;n<width;n++) resid_list[n]=row+n*height;
        resid_num=width;

        dom=tuple->dom[typeid];

        domain_and(dom, resid_list, resid_num);

        free(resid_list);

        return 0;
}

int module_init(moduleoption *opt)
{
        int result;

        dummy=restype_find(RESTYPE);
        if(dummy==NULL) {
                error(_("Pas trouvé le type de ressource '%s'"), RESTYPE);
                return -1;
        }

        result=res_get_matrix(dummy, &width, &height);
        if(result) {
                error(_("Le type de ressource " RESTYPE " n'est pas une matrice"));
                return -1;
        }

        if(handler_tup_new("row-" RESTYPE, handler)==NULL) return -1;

        return(0);
}

Initialisation du module

La première chose que vous aurez remarqué est que ce module ne définit pas de fonction d'ajustage. Pour cette raison, la fonction d'initialisation est succinte. Tout d'abord, nous essayons de trouver notre type de ressource. Nous utilisons ensuite la fonction res_get_matrix() pour obtenir les dimensions de la matrice ( width (largeur) et height (hauteur) ). C'est important de vérifier que le type de ressource est bien une matrice : la fonction res_get_matrix() retournera -1 si elle ne peut pas déterminer les dimensions, et 0 en cas de succès.
La dernière opération dans l'initialisation est l'appel maintenant familier de la fonction handler_tup_new() pour définir un nouveau gestionnaire de restriction de tuple.

Gestionnaire de restriction

Comme vous pouvez le voir, la partie importante du code est cette fois dans le gestionnaire de restriction. Au lieu d'utiliser une fonction d'ajustage pour dire à l'algorithme génétique quels emplois du temps sont les meilleurs, nous allons simplement réduire l'espace de recherche de l'algorithme. Cela signifie évidemment qu'il est impossible de faire un module non-obligatoire avec cette approche. Pour ce qui concerne l'algorithme génétique, les emplois du temps qui se satisfont pas notre restriction ne sont même pas considérés pour la recherche de solution.

Si vous regardez le code du gestionnaire de restriction, vous remarquerez que nous lisons en premier le numéro de ligne fourni par l'utilisateur et vérifions s'il est dans la plage des index autorisés. Nous faisons ensuite une liste de tous les identifiants de ressources que l'évènement peut utiliser. Puisque nous savons dans quelle ligne les ressources autorisées doivent être, et que nous savons comment sont ordonnées les ressources dans la matrice, cela est simple à faire.

Le tableau resid_list contient les identifiants de ressources et la variable (de type entier) resid_num contient la taille du tableau. Il y a exactement width ressources par ligne, si bien que nous pouvons définir la taille immédiatement. Les ressources sont ordonnées d'abord par numéros de ligne, ensuite par numéros de colonnes. Ainsi, la première ressource de la ligne row a l'identifiant de ressource égal à row. La distance avec la seconde ressource est exactement de height ressources.

Ensuite, nous passons la liste des ressources autorisées à la fonction domain_and() . Cette fonction prend un domaine de ressources et une liste de ressources en arguments. Elle enlève toutes les ressources du domaine qui ne sont pas dans la liste. Remarquez que cela réduit effectivement l'espace de recherche au plus petit dénominateur commum de toutes les restrictions de ce type, même celles définies par d'autres modules qui utilisent la fonction domain_and() .

Les pointeurs vers les structures des domaines pour le tuple pour lequel le gestionnaire de restriction a été invoqué peuvent être trouvés dans la structure tupleinfo . Le champ dom contient un tableau de pointeurs vers les structures de domaine, ordonnés par identifiant de ressource. Pour cette raison, nous devons en premier obtenir l'identifiant de notre type de ressources "dummy-type". Puisque nous avons déjà un pointeur vers ce type, nous avons simplement à lire l'identifiant depuis le champ type .

Tester le module

Nous pouvons construire un test simple pour vérifier que le module fonctionne correctement :

<?xml version="1.0" encoding="iso-8859-1"?>
<ttm version="0.2.0">
        <modules>
                <module name="row.so" weight="10" mandatory="yes"/>
        </modules>

        <resources>
                <variable>
                        <resourcetype type="dummy-type">
                                <matrix width="10" height="10"/>
                        </resourcetype>
                </variable>
        </resources>

        <events>
                <event name="dummy-event" repeats="1">
                        <restriction type="row-dummy-type">3</restriction>
                </event>
        </events>
</ttm>

Si vous lancez Tablix en utilisant ce fichier de test, et vérifier un des fichiers résultat, vous lirez quelque chose comme :

<event name="dummy-event" repeats="1" tupleid="0">
        <restriction type="row-dummy-type">3</restriction>
        <resource type="dummy-type" name="4 3"/>
</event>

Vous pouvez constater que le numéro de la ligne de la ressource choisie (second entier du nom de la ressource) est égal au numéro de ligne demandé. Si vous lancez plusieurs fois Tablix avec ce fichier de test et comparez les résultats, vous verrez que le numéro de la colonne de la ressource est choisie au hasard alors le numéro de ligne sera toujours le même.

Discussion

Vous devriez toujours utiliser les domaines de ressources dans vos modules, et utiliser des modules qui sont basés sur cette restriction, quand c'est possible. Parce que cela réduit l'espace de recherche dans lequel Tablix trouvera la solution, cela augmente la vitesse à laquelle le problème est résolu. En revanche, si il y a beaucoup de restrictions qui utilisent les fonctions d'ajustage, Tablix prendra plus de temps pour trouver la solution.

Tablix détectera si un domaine ne contient aucune ressource. Cela signifie que l'utilisateur a appliqué une combinaison impossible de restriction à un évènement, et qu'aucune solution ne pourra être trouvée. C'est l'un des rares cas où Tablix peut prédire qu'il n'existe pas de solution au problème décrit dans le fichier de configuration. Une combinaison impossible de restrictions basées sur des fonctions d'ajustage ne sera, dans la plupart des cas, pas automatiquement détectée .