Logo Search packages:      
Sourcecode: tablix2 version File versions  Download package

chromo.h

Go to the documentation of this file.
/* TABLIX, PGA general timetable solver                              */
/* Copyright (C) 2002-2004 Tomaz Solc                                      */

/* This program is free software; you can redistribute it and/or modify    */
/* it under the terms of the GNU General Public License as published by    */
/* the Free Software Foundation; either version 2 of the License, or       */
/* (at your option) any later version.                                     */

/* This program is distributed in the hope that it will be useful,         */
/* but WITHOUT ANY WARRANTY; without even the implied warranty of          */
/* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the           */
/* GNU General Public License for more details.                            */

/* You should have received a copy of the GNU General Public License       */
/* along with this program; if not, write to the Free Software             */
/* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */

/* $Id: chromo.h,v 1.1.2.26 2005/10/07 12:19:11 avian Exp $ */

#include "config.h"

#ifndef _CHROMO_H
#define _CHROMO_H

/** @file */

/*
 * This is the API reference for the development branch (BRANCH_0_2_0 in the 
 * CVS repository) of the Tablix kernel. Please note that interface may still 
 * change between different development versions. 
 */

/** @mainpage
 *
 * <center>
 * <a href="http://www.tablix.org">Tablix home page</a>
 *
 * <a href="http://www.tablix.org/wiki/wiki.pl">Tablix wiki</a>
 * </center>
 *
 * */

/** @brief Number of resource structs to allocate at once. */
00044 #define RES_ALLOC_CHUNK 10

/** @brief Number of tuples to allocate at once. */
00047 #define TUPLE_ALLOC_CHUNK 10

typedef struct resource_t resource;
typedef struct resourcetype_t resourcetype;
typedef struct domain_t domain;
typedef struct chromo_t chromo;
typedef struct table_t table;
typedef struct population_t population;
typedef struct tupleinfo_t tupleinfo;

/** @brief Resource structure.
 *
 * This structure describes a resource (for example: a teacher, a group of 
 * students, a classroom, a timeslot, etc.) */
00061 struct resource_t {
      /** @brief Name of this resource */
00063       char *name;

      /** @brief Resource ID */
00066       int resid;

      /** @brief Type of this restriction */
00069       resourcetype *restype;
};

/** @brief Resource type structure.
 *
 * This structure describes a type of resources (for example: teachers, groups
 * of students, classrooms, timeslots, etc.) */
00076 struct resourcetype_t {
      /** @brief Name of this resource type */
00078       char *type;
      
      /** @brief Set to 1 if this is a variable resource and set to 0 if
       * this is a constant resource. */
00082       int var;

      /** @brief Resource type ID */
00085       int typeid;
      
      /** @brief This is a two-dimensional array describing conflicts 
       * between resources of this type. 
       *
       * If \code conflists[n][m]==1 \endcode then the resources with 
       * resource IDs \a n and \a m conflict. This means that the variable
       * resources used with events with resource \a n will show on the 
       * extensions for resource \a m and vice versa. */
00094       int **conflicts;

      /** @brief Lookup table for conflicts.
       *
       * \code c_loopup[n] \endcode is an array of resources that conflict
       * with resource \a n. Length of array is \code c_num[n] \endcode. */
00100       int **c_lookup;

      /** @brief Lengths of lookup arrays. */ 
00103       int *c_num;

      /** @brief Set to 1 if there are non-trivial conflicts defined. */
00106       int c_inuse;

      /** @brief Number of resources of this type */
00109       int resnum;

      /** @brief Array of \a resnum resources */
00112       resource *res;
};

/** @brief Domain structure.
 *
 * This structure describes which resources of a certain variable resource
 * type can be assigned to tuples (events) in this domain. */
00119 struct domain_t {
      /** @brief Number of resources in the array. */
00121       int valnum;

      /** @brief Array of possible resource IDs for this variable. */
00124       int *val;

      /** @brief Pointer to the resource type this domain belongs to. */
00127       resourcetype *restype;

      /** @brief Number of tuples in the array. */
00130       int tuplenum;

      /** @brief Array of tuple IDs that are in this domain. */
00133       int *tuples;

      /** @brief Pointer to the next struct in the linked list. */
00136       domain *next;

      /** @brief Pointer to the previous struct in the linked list. */
00139       domain *prev;
};

/** @brief Chromosome structure.
 *
 * This structure holds an array of resources of one resource type that were
 * assigned (either automatically by the genetic algorithm in the case of
 * variable resource or by hand in the config file in the case of constant
 * resources) to all events (tuples) in the timetable */
00148 struct chromo_t {
      /** @brief Number of tuples (length of the array). */
00150       int gennum;

      /** @brief Array of \a gennum resource IDs. (telling which 
       * resource has been assigned to which tuple) */
00154       int *gen;

      /** @brief Pointer to the resource type struct this chromosome belongs
       * to. */
00158       resourcetype *restype;

      /** @brief Pointer to the table this chromosome belongs to. */
00161       table *tab;
};

/** @brief Timetable structure.
 *
 * This structure describes an individual (a candidate solution to the 
 * timetabling problem) in the population of the genetic algorithm. 
 *
 * Each individual has n chromosomes, where n>0. These chromosomes are split
 * between two groups: constant and variable. Constant chromosomes are not 
 * touched by the genetic algorithm (their contents are defined in the config 
 * file). */
00173 struct table_t {
      /** @brief Number of chromosomes (equal to the number of defined
       * resource types). */
00176       int typenum;

      /** @brief Pointer to an array of \a typenum chromosomes. */
00179       chromo *chr;

      /** @brief Fitness of this individual. If less than
       * 0 then this individual needs to be evaluated. */
00183         int fitness;

      /** @brief Array of n integers, where n is the number of fitness 
       * functions used, containing individial error counts of each part 
       * of the fitness function */
00188         int *subtotals; 

        /** @brief Set to 1 if this structures describes an acceptable 
       * solution to the timetabling problem. Set to 0 if not. */
00192       int possible;
};

/** @brief Population structure.
 *
 * Main data structure on which the genetic algorithm operates. */
00198 struct population_t {
      /** @brief Population size (number of individuals) */ 
00200       int size;

      /** @brief Generation counter */ 
00203       int gencnt;

      /** @brief Array of pointers to \a size individuals 
       * (candidate solutions to the timetabling problem) */
00207       table **tables;
};

/** @brief This structure holds information about defined tuples (events). */
00211 struct tupleinfo_t {
      /** @brief Name of the event. */
00213       char *name;

      /** @brief Tuple ID of this tuple. */
00216       int tupleid;

      /** @brief Array of resource IDs that are used by this event. 
       *
       * This array hold the static information that was loaded from the XML 
       * configuration file.
       *
       * Length of array is equal to the number of resource types defined
       * \a dat_typenum. The first element in the array defines the resource 
       * with resource type ID 0 and so on. 
       *
       * If an element of this array is equal to INT_MIN then the information
       * about this resource type was not included in the XML file. This
       * value is always different from INT_MIN for constant resource types */
00230       int *resid;

      /** @brief Array of pointers to domains for this event. 
       *
       * Length of array is equal to the number of resource types defined
       * \a dat_typenum. The first element in the array defines the domain
       * for the resource type ID 0 and so on. */
00237       domain **dom;
};

population *population_new(int size, int typenum, int tuplenum);
void population_free(population *pop);
population *population_load(char *filename);
int population_save(char *filename, population *pop);
#endif

Generated by  Doxygen 1.6.0   Back to index