/*  Ant-based Clustering    Copyright (C) 2004 Julia Handl    Email: Julia.Handl@gmx.de    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*//***************************************************date: 7.4.2003author: Julia Handl (julia.handl@gmx.de)description:implementation of ant-based clusteringRun Algorithm as follows:- Construct accl object (constructor requires a pointer  to a configuration object, to a data collection,  and an evaluation object)- Call initialisation routine init()- Call main routine run()- Possibly convert spatial distribution to explicit  partitioning using constructclustering()- Solution can be visualised by calling routine  visualize() from parent class clalg  - Evaluation object must be initialised by the  spatial distribution or the explicit partitioning  or an array of the grid-positions of all data  elements; subsequently evaluation functions  can be called***************************************************/#ifndef ACCL_JH_2003#define ACCL_JH_2003#include "clalg.h"/* class accl*/class accl:public clalg {    class ant;    class antcolony; private:    antcolony * colony;    int generation_ctr;    /* Class Antcolony */    class antcolony {    private:    	/* Array of ants that make up the colony */	ant * ants;	/* Toroidal grid, the ants "live" on */	grid * env;	/* Pointer to the configuration object encapsulating all parameter settings */	conf * par;	    public:    	/* Constructor: requires a pointer to the current configuration object	and a pointer to a grid object */	antcolony(conf * c, grid * e);	/* Destructor */	~antcolony();	/* Read/Write access to individual members / ants of the colony */	ant &operator[](int i);	/* Starting phase: all ants are randomly placed on the grid	and pick up a data elements */	void init();	/* Main phase: members of the colony are subsequently	activated and transport data elements */	void cometolive();	/* Ending phase: all ants drop their data items at the	position where they picked them up */	void finish();    };    class ant {        	/* Short term memory of an ant */	class memory {	    friend class ant;	public:	    /* Array of the last transported data items */	    int * index;	    /* Array of corresponding dropping positions */	    position<int>* pos;	    /* Flag to indicate whether the memory is full.	       Only then it will be used */	    int initialized;	    /* Flag for the intermediate deactivation of the memory	       until next picking operation */	    int braindead;	    	    /* Pointer to the next writing position in the memory */	    int ptr;	    	    /* Size of the memory */	    int size;	    /* Each ant needs a pointer to the environment:	       this environment provides access to local neighbourhood and	       permits the comparison of data items	    */	    grid * env;	    /* Constructor:	       requires a pointer to the environment and the desired size	       if the memory 	    */	    memory(grid * e, int s);	    /* Desctructor:	       deletion of the allocated memory	    */	    ~memory();	    /* store a new data item <data> and its corresponding dropping position <p> in the memory */	    void remember(int data, position<int>& p, double alpha);	    /* find the best matching data item (for <data>) in the memory and	       set <p> to the corresponding dropping position */	    double bestmatch(int data, position<int>&p, ant & a, int clusterphase, int lookahead);	};	friend class antcolony;	friend class memory;    public:	/* parameters that can be set individually for each ant */	double kd;	double kp;	double alpha;	double scalefactor;	int radius;	double nsize;	int size;	int memsize;	int speed;	int failure_ctr;	int activation_ctr;	int adapt;	/* each ant has a memory, a pointer to the grid and a pointer to	   the current configuration object */	memory * mem;	grid * env;	conf * par;	/* current ant position on the grid */	position<int>pos;	/* grid position where currently carried data item was picked up */	position<int> lastpos;	/* currently carried data item */	int dat;    public:        	/* Constructor:	   requires a pointer to the current configuratio object	   and to the environment 	*/	ant(conf * , grid * ec);	/* Destructor:	*/	~ant();	/* randomly pick up a first data item */	void init();	/* drop down the carried data item at the position	   where it was picked up 	*/	void finish();	/* do one random (possibly biased) move on the grid	*/	void move();	/* try to drop data item; if successful pick up a new one */	void dropandpick();	/* threshold function for pickup operation */	double th_pick(double f);	/* theshold function for dropping operation */	double th_drop(double f);	double square(double x);	/* memory access for data index and the corresponding position (x and y coordinate respectively) */	int ithmemory(int i);	int ithmemoryx(int i);	int ithmemoryy(int i);    }; public:    /* Construcor:       requires pointer to the current configuration object,       the current data collection <bin> and an evaluation       object */    accl(conf * par, databin<USED_DATA_TYPE> * bin, evaluation * e);        /* Destructor:       free all resources       */    ~accl();        /* Initialisation:       construct grid and ant colony    */    void init();        /* Run ant algrithm; must be preceeded by initialisation */    void run();        /* Transform ant solution to explicit clustering using agglomerative clustering */    void constructclustering();    /* Single link linkage criterion for agglomerative clustering algorithm */    double minlink(int * cluster1, int * cluster2, position<double> ** docindex);};#endif