#include <object.h> #include "digraph.h" //! Tämän algoritmin sisäistä toimintaa ei kannata miettiä tahi //! ymmärtää. Se on pimeä ja mystinen. void Digraph::traverse (NodeList& avoin, NodeList& suljettu, NodeList& lyhin, int& min, int depth) const { int cnt, len = 0; // Mikäli avoin ei ole tyhjä, kutsutaan generaattoria edelleen // rekursiivisesti muutellen solmujen järjestystä sopivalla // tavalla. //! Tuo tapa on melko monimutkainen; avointen jokun //! solmujen järjestys vaihtelee melko omituisella tavalla, mutta //! se toimii. if (avoin.size) // Iteroidaan läpi avoimien solmujen ja käydään ne rekursiivisesti läpi // Huom! Avointen solmujen lukumäärä voi muuttua iteraatioiden aikana... for (cnt=0; cnt<avoin.size; cnt++) { // Muutetaan järjestystä ja kutsutaan itseämme rekursiivisesti // Siirretään yksi alkio avointen joukosta suljettuihin. suljettu[suljettu.size++] = avoin [cnt]; // Ja poistetaan se avointen joukosta. avoin[cnt] = avoin [--avoin.size]; // Kutsutaan generaattoria uudelleen rekursiivisesti. traverse (avoin, suljettu, lyhin, min, depth-1); // Palautetaan alkio takaisin avointen joukkoon. avoin[avoin.size++] = avoin [cnt]; avoin[cnt] = suljettu [--suljettu.size]; // Ja tehdään siis tämä kaikille avointen joukon alkioille } else { // Jos avoimessa joukossa ei ollutkaan enää yhtään alkioita, // suoritetaan vertailu, josko tämä polku olisi lyhyin // Lasketaan suljetun joukon pituus. len = length (suljettu); if (len < min && len>=0) { // Pituus on aikaisempaa minimiä lyhyempi niin asetetaan // uusi minimi, min = len; // Kopioidaan suljettu reitti lyhimpään, lyhin = suljettu; // Kytketään graafi tuon reitin mukaisesti tulostusta varten const_cast<Digraph*>(this)->connarr (lyhin); //! Tulostetaan nyt tämä versio. //! Tämän nyt oikeastaan pitäisi olla lipun takana mutta äh. //! printf ("%s\n", (CONSTR) toString ()); //! for (int i=0; i<lyhin.size; i++) { //! if (i) //! printf ("-"); //! printf ("%d", lyhin[i]); //!} //!printf ("\n"); //!*///! Tulostetaan vielä jotain paskaa jotta päästään http:n //! puskuroinnin läpi. VOI VITTUJEN VITTU. //! for (int i=0; i<200; i++) //! printf ("xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx\n"); } } } NodeList* Digraph::travel () const { // Maksimissaan 8 solmua, paitsi jos erityisesti pyydetty 9 tai 10 int tspsize = nodes.size>10? 8 : nodes.size; // Solmut jotka eivät vielä ole kytkettynä mihinkään. Kun kaikki graafin // solmut ovat kytkettynä renkaaseen, ei avoimessa ole enää solmuja ja // pituusvertailu voidaan suorittaa.<P> NodeList avoin (tspsize); // Kullakin hetkellä toisiinsa renkaana kytkettyinä olevat // solmut. Viimeinen solmu on kytkettynä ensimmäiseen. NodeList suljettu (tspsize); // Osoitin lyhyimpään löydettyyn ratkaisuun ja sen pituus. Kun // suljettu on täynnä niin sen pituutta vertaillaan tähän // pituuteen. Jos pituus on lyhyempi kuin vanha minimi, kopioidaan // suljettujen solmujen vektori lyhimpään. NodeList* lyhin = new NodeList (tspsize); int min = INFINITEINT; // Laitetaan kaikki solmut avointen solmujen listaan. for (int i=0; i<tspsize; i++) avoin[i] = i; avoin.size = tspsize; // Ja sitten matkustellaan traverse (avoin, suljettu, *lyhin, min, tspsize); return lyhin; }
Generated with (Python version) of tab4.cgi by Marko Grönroos (magi@iki.fi), 1999