source: cpp/frams/model/similarity/measure-greedy.cpp @ 1158

Last change on this file since 1158 was 1158, checked in by Maciej Komosinski, 4 weeks ago

Cosmetic/minor improvements

File size: 47.7 KB
Line 
1// This file is a part of Framsticks SDK.  http://www.framsticks.com/
2// Copyright (C) 1999-2021  Maciej Komosinski and Szymon Ulatowski.
3// See LICENSE.txt for details.
4
5#include "measure-greedy.h"
6#include <cstdlib> //std::qsort()
7#include <assert.h>
8
9#define DB(x)  //define as x if you want to print debug information
10
11const int SimilMeasureGreedy::iNOFactors = 4;
12int fuzzDepth = 0; //TODO make local, but not crucial because currently "fuzzy vertex degree" is not activated by default
13
14#define FIELDSTRUCT SimilMeasureGreedy
15
16static ParamEntry simil_greedy_paramtab[] = {
17                { "Creature: Similarity: Graph greedy", 1, 7, "SimilMeasureGreedy", "Evaluates morphological dissimilarity using greedy measure. More information:\nhttp://www.framsticks.com/bib/Komosinski-et-al-2001\nhttp://www.framsticks.com/bib/Komosinski-and-Kubiak-2011\nhttp://www.framsticks.com/bib/Komosinski-2016\nhttps://doi.org/10.1007/978-3-030-16692-2_8", },
18                { "simil_greedy_parts", 0, 0, "Weight of parts count", "f 0 100 0", FIELD(m_adFactors[0]), "Differing number of parts is also handled by the 'part degree' similarity component.", },
19                { "simil_greedy_partdeg", 0, 0, "Weight of parts' degree", "f 0 100 1", FIELD(m_adFactors[1]), "", },
20                { "simil_greedy_neuro", 0, 0, "Weight of neurons count", "f 0 100 0.1", FIELD(m_adFactors[2]), "", },
21                { "simil_greedy_partgeom", 0, 0, "Weight of parts' geometric distances", "f 0 100 0", FIELD(m_adFactors[3]), "", },
22                { "simil_greedy_fixedZaxis", 0, 0, "Fix 'z' (vertical) axis?", "d 0 1 0", FIELD(fixedZaxis), "", },
23                { "simil_greedy_weightedMDS", 0, 0, "Should weighted MDS be used?", "d 0 1 0", FIELD(wMDS), "If activated, weighted MDS with vertex (i.e., Part) degrees as weights is used for 3D alignment of body structure.", },
24                { "evaluateDistance", 0, PARAM_DONTSAVE | PARAM_USERHIDDEN, "Evaluate model dissimilarity", "p f(oGeno,oGeno)", PROCEDURE(p_evaldistance), "Calculates dissimilarity between two models created from Geno objects.", },
25                { 0, },
26};
27
28#undef FIELDSTRUCT
29
30SimilMeasureGreedy::SimilMeasureGreedy(): localpar(simil_greedy_paramtab, this), m_iDV(0), m_iDD(0), m_iDN(0), m_dDG(0.0)
31{       
32        localpar.setDefault();
33       
34        for (int i = 0; i < 2; i++)
35        {
36                m_aDegrees[0] = nullptr;
37                m_fuzzyNeighb[0] = nullptr;
38                m_Neighbours[0] = nullptr;
39        }
40       
41        m_pMatching = nullptr;
42        tempMatching = nullptr;
43       
44        //Determines whether "fuzzy vertex degree" should be used.
45        //In preliminary experiments in 2017, "fuzzy vertex degree" turned out to be not beneficial.
46        isFuzzy = false;
47        fuzzyDepth = 10;
48        save_matching = false;
49}
50
51double SimilMeasureGreedy::distanceForTransformation()
52{
53        // now the positions are recomputed
54        computeMatching();
55
56        // teraz m_pMatching istnieje i jest pełne
57        assert(m_pMatching != NULL);
58        assert(m_pMatching->isFull() == true);
59        // wykorzystaj to dopasowanie i geometrię do obliczenia tymczasowej wartości miary
60       
61        int iTempRes = countPartsDistance();
62        // załóż sukces
63        assert(iTempRes == 1);
64        double dCurrentSim = m_adFactors[0] * double(m_iDV) +
65                m_adFactors[1] * double(m_iDD) +
66                m_adFactors[2] * double(m_iDN) +
67                m_adFactors[3] * double(m_dDG);
68        // załóż poprawną wartość podobieństwa
69        assert(dCurrentSim >= 0.0);
70        SAFEDELETE(tempMatching);
71        return dCurrentSim;
72}
73
74
75double SimilMeasureGreedy::distanceWithoutAlignment()
76{
77        return distanceForTransformation();
78}
79
80void SimilMeasureGreedy::beforeTransformation()
81{
82        if (m_pMatching != NULL)
83                if (!m_pMatching->isEmpty())
84                        m_pMatching->empty();
85}
86
87/** Computes elements of similarity (m_iDD, m_iDN, m_dDG) based on underlying matching.
88        Assumptions:
89        - Matching (m_pMatching) exists and is full.
90        - Internal arrays m_aDegrees and coordinates exist and are properly filled in
91        Exit conditions:
92        - Elements of similarity are computed (m)iDD, m_iDN, m_dDG).
93        @return 1 if success, otherwise 0.
94        */
95int SimilMeasureGreedy::countPartsDistance()
96{
97        int i, temp;
98
99        // assume existence of m_pMatching
100        assert(m_pMatching != NULL);
101        // musi byc pelne!
102        assert(m_pMatching->isFull() == true);
103
104        // roznica w stopniach
105        m_iDD = 0;
106        // roznica w liczbie neuronów
107        m_iDN = 0;
108        // roznica w odleglosci dopasowanych Parts
109        m_dDG = 0.0;
110
111        int iOrgPart, iOrgMatchedPart; // orginalny indeks Part i jego dopasowanego Part
112        int iMatchedPart; // indeks (wg sortowania) dopasowanego Part
113
114        // wykorzystanie dopasowania do zliczenia m_iDD - roznicy w stopniach
115        // i m_iDN - roznicy w liczbie neuronow
116        // petla w wiekszej tablicy
117        for (i = 0; i < m_aiPartCount[1 - m_iSmaller]; i++)
118        {
119                // dla kazdego elementu [i] z wiekszego organizmu
120                // pobierz jego orginalny indeks w organizmie z tablicy TDN
121                iOrgPart = m_aDegrees[1 - m_iSmaller][i][0];
122                if (!(m_pMatching->isMatched(1 - m_iSmaller, i)))
123                {
124                        // gdy nie zostal dopasowany
125                        // dodaj jego stopien do DD
126                        m_iDD += m_aDegrees[1 - m_iSmaller][i][1];
127                        // dodaj liczbe neuronow do DN
128                        m_iDN += m_aDegrees[1 - m_iSmaller][i][3];
129                        // i oblicz odleglosc tego Part od srodka organizmu (0,0,0)
130                        // (uzyj orginalnego indeksu)
131                        //no need to compute distane when m_dDG weight is 0
132                        m_dDG += m_adFactors[3] == 0 ? 0 : coordinates[1 - m_iSmaller][iOrgPart].length();
133                }
134                else
135                {
136                        // gdy byl dopasowany
137                        // pobierz indeks (po sortowaniu) tego dopasowanego Part
138                        iMatchedPart = m_pMatching->getMatchedIndex(1 - m_iSmaller, i);
139                        // pobierz indeks orginalny tego dopasowanego Part
140                        iOrgMatchedPart = m_aDegrees[m_iSmaller][iMatchedPart][0];
141                        // dodaj ABS roznicy stopni do DD
142                        temp = m_aDegrees[1 - m_iSmaller][i][1] -
143                                m_aDegrees[m_iSmaller][iMatchedPart][1];
144                        m_iDD += abs(temp);
145                        // dodaj ABS roznicy neuronow do DN
146                        temp = m_aDegrees[1 - m_iSmaller][i][3] -
147                                m_aDegrees[m_iSmaller][iMatchedPart][3];
148                        m_iDN += abs(temp);
149                        // pobierz polozenie dopasowanego Part
150                        if (m_adFactors[3] > 0) //no need to compute distance when m_dDG weight is 0
151                        {
152                            Pt3D MatchedPartPos(coordinates[m_iSmaller][iOrgMatchedPart]);
153                            // dodaj euklidesowa odleglosc Parts do sumy odleglosci
154                            m_dDG += coordinates[1 - m_iSmaller][iOrgPart].distanceTo(MatchedPartPos);
155                        }
156                }
157        }
158
159        // obliczenie i dodanie różnicy w liczbie neuronów OnJoint...
160        temp = m_aOnJoint[0][3] - m_aOnJoint[1][3];
161        m_iDN += abs(temp);
162        DB(printf("OnJoint DN: %i\n", abs(temp));)
163                // ... i Anywhere
164                temp = m_aAnywhere[0][3] - m_aAnywhere[1][3];
165        m_iDN += abs(temp);
166        DB(printf("Anywhere DN: %i\n", abs(temp));)
167
168                return 1;
169}
170
171void SimilMeasureGreedy::computeMatching()
172{
173        // uniwersalne liczniki
174        int i, j;
175
176        assert(m_pMatching != NULL);
177        assert(m_pMatching->isEmpty() == true);
178
179        // rozpoczynamy etap dopasowywania Parts w organizmach
180        // czy dopasowano już wszystkie Parts?
181        int iCzyDopasowane = 0;
182        // koniec grupy aktualnie dopasowywanej w każdym organizmie
183        int aiKoniecGrupyDopasowania[2] = { 0, 0 };
184        // koniec grupy już w całości dopasowanej
185        // (Pomiedzy tymi dwoma indeksami znajduja sie Parts w tablicy
186        // m_aDegrees, ktore moga byc dopasowywane (tam nadal moga
187        // byc tez dopasowane - ale nie musi to byc w sposob
188        // ciagly)
189        int aiKoniecPierwszejGrupy[2] = { 0, 0 };
190        // Tablica przechowująca odległości poszczególnych Parts z aktualnych
191        // grup dopasowania. Rozmiar - prostokąt o bokach równych liczbie elementów w
192        // dopasowywanych aktualnie grupach. Pierwszy wymiar - pierwszy organizm.
193        // Drugi wymiar - drugi organizm (nie zależy to od tego, który jest mniejszy).
194        // Wliczane w rozmiar tablicy są nawet już dopasowane elementy - tablice
195        // paiCzyDopasowany pamiętają stan dopasowania tych elementów.
196        typedef double *TPDouble;
197        double **aadOdleglosciParts;
198        // dwie tablice okreslajace Parts, ktore moga byc do siebie dopasowywane
199        // rozmiary: [0] - aiRozmiarCalychGrup[1]
200        //                       [1] - aiRozmiarCalychGrup[0]
201        std::vector<bool> *apvbCzyMinimalnaOdleglosc[2];
202        // rozmiar aktualnie dopasowywanej grupy w odpowiednim organizmie (tylko elementy
203        // jeszcze niedopasowane).
204        int aiRozmiarGrupy[2];
205        // rozmiar aktualnie dopasowywanych grup w odpowiednim organizmie (włączone są
206        // w to również elementy już dopasowane).
207        int aiRozmiarCalychGrup[2] = { 0, 0 };
208
209        // DOPASOWYWANIE PARTS
210        while (!iCzyDopasowane)
211        {
212                // znajdz konce obu grup aktualnie dopasowywanych w obu organizmach
213                for (i = 0; i < 2; i++)
214                {
215                        // czyli poszukaj miejsca zmiany stopnia lub konca tablicy
216                        for (j = aiKoniecPierwszejGrupy[i] + 1; j < m_aiPartCount[i]; j++)
217                        {
218                                if (m_aDegrees[i][j][DEG] < m_aDegrees[i][j - 1][DEG])
219                                {
220                                        break;
221                                }
222                        }
223                        aiKoniecGrupyDopasowania[i] = j;
224
225                        // sprawdz poprawnosc tego indeksu
226                        assert((aiKoniecGrupyDopasowania[i] > 0) &&
227                                (aiKoniecGrupyDopasowania[i] <= m_aiPartCount[i]));
228
229                        // oblicz rozmiary całych grup - łącznie z dopasowanymi już elementami
230                        aiRozmiarCalychGrup[i] = aiKoniecGrupyDopasowania[i] -
231                                aiKoniecPierwszejGrupy[i];
232
233                        // sprawdz teraz rozmiar tej grupy w sensie liczby niedopasowanzch
234                        // nie moze to byc puste!
235                        aiRozmiarGrupy[i] = 0;
236                        for (j = aiKoniecPierwszejGrupy[i]; j < aiKoniecGrupyDopasowania[i]; j++)
237                        {
238                                // od poczatku do konca grupy
239                                if (!m_pMatching->isMatched(i, j))
240                                {
241                                        // jesli niedopasowany, to zwieksz licznik
242                                        aiRozmiarGrupy[i]++;
243                                }
244                        }
245                        // grupa nie moze byc pusta!
246                        assert(aiRozmiarGrupy[i] > 0);
247                }
248
249                // DOPASOWYWANIE PARTS Z GRUP
250
251                // stworzenie tablicy odległości lokalnych
252                // stwórz pierwszy wymiar - wg rozmiaru zerowego organizmu
253                aadOdleglosciParts = new TPDouble[aiRozmiarCalychGrup[0]];
254                assert(aadOdleglosciParts != NULL);
255                // stwórz drugi wymiar - wg rozmiaru drugiego organizmu
256                for (i = 0; i < aiRozmiarCalychGrup[0]; i++)
257                {
258                        aadOdleglosciParts[i] = new double[aiRozmiarCalychGrup[1]];
259                        assert(aadOdleglosciParts[i] != NULL);
260                }
261
262                // stworzenie tablic mozliwosci dopasowania (indykatorow minimalnej odleglosci)
263                apvbCzyMinimalnaOdleglosc[0] = new std::vector<bool>(aiRozmiarCalychGrup[1], false);
264                apvbCzyMinimalnaOdleglosc[1] = new std::vector<bool>(aiRozmiarCalychGrup[0], false);
265                // sprawdz stworzenie tablic
266                assert(apvbCzyMinimalnaOdleglosc[0] != NULL);
267                assert(apvbCzyMinimalnaOdleglosc[1] != NULL);
268
269                // wypełnienie elementów macierzy (i,j) odległościami pomiędzy
270                // odpowiednimi Parts: (i) w organizmie 0 i (j) w organizmie 1.
271                // UWAGA! Uwzględniamy tylko te Parts, które nie są jeszcze dopasowane
272                // (reszta to byłaby po prostu strata czasu).
273                int iDeg, iNeu; // ilościowe określenie różnic stopnia, liczby neuronów i połączeń Parts
274                //int iNIt;
275                double dGeo; // ilościowe określenie różnic geometrycznych pomiędzy Parts
276                // indeksy konkretnych Parts - indeksy sa ZERO-BASED, choć właściwy dostep
277                // do informacji o Part wymaga dodania aiKoniecPierwszejGrupy[]
278                // tylko aadOdleglosciParts[][] indeksuje sie bezposrednio zawartoscia iIndex[]
279                int iIndex[2];
280                int iPartIndex[2] = { -1, -1 }; // at [iModel]: original index of a Part for the specified model (iModel)
281
282                // debug - wypisz zakres dopasowywanych indeksow
283                DB(printf("Organizm 0: grupa: (%2i, %2i)\n", aiKoniecPierwszejGrupy[0],
284                        aiKoniecGrupyDopasowania[0]);)
285                        DB(printf("Organizm 1: grupa: (%2i, %2i)\n", aiKoniecPierwszejGrupy[1],
286                                aiKoniecGrupyDopasowania[1]);)
287
288                        for (i = 0; i < aiRozmiarCalychGrup[0]; i++)
289                        {
290
291                                // iterujemy i - Parts organizmu 0
292                                // (indeks podstawowy - aiKoniecPierwszejGrupy[0])
293
294                                if (!(m_pMatching->isMatched(0, aiKoniecPierwszejGrupy[0] + i)))
295                                {
296                                        // interesuja nas tylko te niedopasowane jeszcze (i)
297                                        for (j = 0; j < aiRozmiarCalychGrup[1]; j++)
298                                        {
299
300                                                // iterujemy j - Parts organizmu 1
301                                                // (indeks podstawowy - aiKoniecPierwszejGrupy[1])
302
303                                                if (!(m_pMatching->isMatched(1, aiKoniecPierwszejGrupy[1] + j)))
304                                                {
305                                                        // interesuja nas tylko te niedopasowane jeszcze (j)
306                                                        // teraz obliczymy lokalne różnice pomiędzy Parts
307                                                        iDeg = abs(m_aDegrees[0][aiKoniecPierwszejGrupy[0] + i][1]
308                                                                - m_aDegrees[1][aiKoniecPierwszejGrupy[1] + j][1]);
309
310                                                        //iNit currently is not a component of distance measure
311                                                        //iNIt = abs(m_aDegrees[0][ aiKoniecPierwszejGrupy[0] + i ][2]
312                                                        //- m_aDegrees[1][ aiKoniecPierwszejGrupy[1] + j ][2]);
313
314                                                        iNeu = abs(m_aDegrees[0][aiKoniecPierwszejGrupy[0] + i][3]
315                                                                - m_aDegrees[1][aiKoniecPierwszejGrupy[1] + j][3]);
316
317                                                        // obliczenie także lokalnych różnic geometrycznych pomiędzy Parts
318                                                        // find original indices of Parts for both of the models
319                                                        iPartIndex[0] = m_aDegrees[0][aiKoniecPierwszejGrupy[0] + i][0];
320                                                        iPartIndex[1] = m_aDegrees[1][aiKoniecPierwszejGrupy[1] + j][0];
321                                                        // now compute the geometrical distance of these Parts (use coordinates
322                                                        // which should be computed by SVD)
323                                                       
324                                                        if (m_adFactors[3] > 0)
325                                                        {
326                                                                Pt3D Part0Pos(coordinates[0][iPartIndex[0]]);
327                                                                Pt3D Part1Pos(coordinates[1][iPartIndex[1]]);
328                                                                dGeo = Part0Pos.distanceTo(Part1Pos);
329                                                        }
330                                                        else
331                                                            dGeo = 0; //no need to compute distance when m_dDG weight is 0
332
333                                                        // tutaj prawdopodobnie należy jeszcze dodać sprawdzanie
334                                                        // identyczności pozostałych własności (oprócz geometrii)
335                                                        // - żeby móc stwierdzić w ogóle identyczność Parts
336
337                                                        // i ostateczna odleglosc indukowana przez te roznice
338                                                        // (tutaj nie ma różnicy w liczbie wszystkich wierzchołków)
339                                                        aadOdleglosciParts[i][j] = m_adFactors[1] * double(iDeg) +
340                                                                m_adFactors[2] * double(iNeu) +
341                                                                m_adFactors[3] * dGeo;
342                                                        DB(printf("Parts Distance (%2i,%2i) = %.3lf\n", aiKoniecPierwszejGrupy[0] + i,
343                                                                aiKoniecPierwszejGrupy[1] + j, aadOdleglosciParts[i][j]);)
344                                                                DB(printf("Parts geometrical distance = %.20lf\n", dGeo);)
345                                                                DB(printf("Pos0: (%.3lf %.3lf %.3lf)\n", Part0Pos.x, Part0Pos.y, Part0Pos.z);)
346                                                                DB(printf("Pos1: (%.3lf %.3lf %.3lf)\n", Part1Pos.x, Part1Pos.y, Part1Pos.z);)
347                                                }
348                                        }
349                                }
350                        }
351
352                // tutaj - sprawdzic tylko, czy tablica odleglosci lokalnych jest poprawnie obliczona
353
354                // WYKORZYSTANIE TABLICY ODLEGLOSCI DO BUDOWY DOPASOWANIA
355
356                // trzeba raczej iterować aż do zebrania wszystkich możliwych dopasowań w grupie
357                // dlatego wprowadzamy dodatkowa zmienna - czy skonczyla sie juz grupa
358                bool bCzyKoniecGrupy = false;
359                while (!bCzyKoniecGrupy)
360                {
361                        for (i = 0; i < 2; i++)
362                        {
363                                // iterujemy (i) po organizmach
364                                // szukamy najpierw jakiegoś niedopasowanego jeszcze Part w organizmach
365
366                                // zakładamy, że nie ma takiego Part
367                                iIndex[i] = -1;
368
369                                for (j = 0; j < aiRozmiarCalychGrup[i]; j++)
370                                {
371                                        // iterujemy (j) - Parts organizmu (i)
372                                        // (indeks podstawowy - aiKoniecPierwszejGrupy[0])
373                                        if (!(m_pMatching->isMatched(i, aiKoniecPierwszejGrupy[i] + j)))
374                                        {
375                                                // gdy mamy w tej grupie jakis niedopasowany element, to ustawiamy
376                                                // iIndex[i] (chcemy w zasadzie pierwszy taki)
377                                                iIndex[i] = j;
378                                                break;
379                                        }
380                                }
381
382                                // sprawdzamy, czy w ogole znaleziono taki Part
383                                if (iIndex[i] < 0)
384                                {
385                                        // gdy nie znaleziono takiego Part - mamy koniec dopasowywania w
386                                        // tych grupach
387                                        bCzyKoniecGrupy = true;
388                                }
389                                // sprawdz poprawnosc indeksu niedopasowanego Part - musi byc w aktualnej grupie
390                                assert((iIndex[i] >= -1) && (iIndex[i] < aiRozmiarCalychGrup[i]));
391                        }
392
393
394                        // teraz mamy sytuacje:
395                        // - mamy w iIndex[0] i iIndex[1] indeksy pierwszych niedopasowanych Part
396                        //              w organizmach, albo
397                        // - nie ma w ogóle już czego dopasowywać (należy przejść do innej grupy)
398                        if (!bCzyKoniecGrupy)
399                        {
400                                // gdy nie ma jeszcze końca żadnej z grup - możemy dopasowywać
401                                // najpierw wyszukujemy w tablicy minimum odległości od tych
402                                // wyznaczonych Parts
403
404                                // najpierw wyczyscimy wektory potencjalnych dopasowan
405                                // dla organizmu 1 (o rozmiarze grupy z 0)
406                                for (i = 0; i < aiRozmiarCalychGrup[0]; i++)
407                                {
408                                        apvbCzyMinimalnaOdleglosc[1]->operator[](i) = false;
409                                }
410                                // dla organizmu 0 (o rozmiarze grup z 1)
411                                for (i = 0; i < aiRozmiarCalychGrup[1]; i++)
412                                {
413                                        apvbCzyMinimalnaOdleglosc[0]->operator[](i) = false;
414                                }
415
416                                // szukanie minimum dla Part o indeksie iIndex[0] w organizmie 0
417                                // wsrod niedopasowanych Parts z organizmu 1
418                                // zakładamy, że nie znaleŸliśmy jeszcze minimum
419                                double dMinimum = HUGE_VAL;
420                                for (i = 0; i < aiRozmiarCalychGrup[1]; i++)
421                                {
422                                        if (!(m_pMatching->isMatched(1, aiKoniecPierwszejGrupy[1] + i)))
423                                        {
424
425                                                // szukamy minimum obliczonej lokalnej odleglosci tylko wsrod
426                                                // niedopasowanych jeszcze Parts
427                                                if (aadOdleglosciParts[iIndex[0]][i] < dMinimum)
428                                                {
429                                                        dMinimum = aadOdleglosciParts[iIndex[0]][i];
430                                                }
431                                                // przy okazji - sprawdz, czy HUGE_VAL jest rzeczywiscie max dla double
432                                                assert(aadOdleglosciParts[iIndex[0]][i] < HUGE_VAL);
433                                        }
434                                }
435                                // sprawdz, czy minimum znaleziono - musi takie byc, bo jest cos niedopasowanego
436                                assert((dMinimum >= 0.0) && (dMinimum < HUGE_VAL));
437
438                                // teraz zaznaczamy w tablicy te wszystkie Parts, ktore maja
439                                // rzeczywiscie te minimalna odleglosc do Part iIndex[0] w organizmie 0
440                                for (i = 0; i < aiRozmiarCalychGrup[1]; i++)
441                                {
442                                        if (!(m_pMatching->isMatched(1, aiKoniecPierwszejGrupy[1] + i)))
443                                        {
444                                                if (aadOdleglosciParts[iIndex[0]][i] == dMinimum)
445                                                {
446                                                        // jesli w danym miejscu tablicy odleglosci jest faktyczne
447                                                        // minimum odleglosci, to mamy potencjalna pare dla iIndex[0]
448                                                        apvbCzyMinimalnaOdleglosc[0]->operator[](i) = true;
449                                                }
450
451                                                // sprawdz poprawnosc znalezionego wczesniej minimum
452                                                assert(aadOdleglosciParts[iIndex[0]][i] >= dMinimum);
453                                        }
454                                }
455
456                                // podobnie szukamy minimum dla Part o indeksie iIndex[1] w organizmie 1
457                                // wsrod niedopasowanych Parts z organizmu 0
458                                dMinimum = HUGE_VAL;
459                                for (i = 0; i < aiRozmiarCalychGrup[0]; i++)
460                                {
461                                        if (!(m_pMatching->isMatched(0, aiKoniecPierwszejGrupy[0] + i)))
462                                        {
463                                                // szukamy minimum obliczonej lokalnej odleglosci tylko wsrod
464                                                // niedopasowanych jeszcze Parts
465                                                if (aadOdleglosciParts[i][iIndex[1]] < dMinimum)
466                                                {
467                                                        dMinimum = aadOdleglosciParts[i][iIndex[1]];
468                                                }
469                                                // przy okazji - sprawdz, czy HUGE_VAL jest rzeczywiscie max dla double
470                                                assert(aadOdleglosciParts[i][iIndex[1]] < HUGE_VAL);
471                                        }
472                                }
473                                // sprawdz, czy minimum znaleziono - musi takie byc, bo jest cos niedopasowanego
474                                assert((dMinimum >= 0.0) && (dMinimum < HUGE_VAL));
475
476                                // teraz zaznaczamy w tablicy te wszystkie Parts, ktore maja
477                                // rzeczywiscie te minimalne odleglosci do Part iIndex[1] w organizmie 1
478                                for (i = 0; i < aiRozmiarCalychGrup[0]; i++)
479                                {
480                                        if (!(m_pMatching->isMatched(0, aiKoniecPierwszejGrupy[0] + i)))
481                                        {
482                                                if (aadOdleglosciParts[i][iIndex[1]] == dMinimum)
483                                                {
484                                                        // jesli w danym miejscu tablicy odleglosci jest faktyczne
485                                                        // minimum odleglosci, to mamy potencjalna pare dla iIndex[1]
486                                                        apvbCzyMinimalnaOdleglosc[1]->operator[](i) = true;
487                                                }
488
489                                                // sprawdz poprawnosc znalezionego wczesniej minimum
490                                                assert(aadOdleglosciParts[i][iIndex[1]] >= dMinimum);
491                                        }
492                                }
493
494                                // teraz mamy juz poszukane potencjalne grupy dopasowania - musimy
495                                // zdecydowac, co do czego dopasujemy!
496                                // szukamy Part iIndex[0] posrod mozliwych do dopasowania dla Part iIndex[1]
497                                // szukamy takze Part iIndex[1] posrod mozliwych do dopasowania dla Part iIndex[0]
498                                bool PartZ1NaLiscie0 = apvbCzyMinimalnaOdleglosc[0]->operator[](iIndex[1]);
499                                bool PartZ0NaLiscie1 = apvbCzyMinimalnaOdleglosc[1]->operator[](iIndex[0]);
500
501                                if (PartZ1NaLiscie0 && PartZ0NaLiscie1)
502                                {
503                                        // PRZYPADEK 1. Oba Parts maja sie wzajemnie na listach mozliwych
504                                        // dopasowan.
505                                        // AKCJA. Dopasowanie wzajemne do siebie.
506
507                                        m_pMatching->match(0, aiKoniecPierwszejGrupy[0] + iIndex[0],
508                                                1, aiKoniecPierwszejGrupy[1] + iIndex[1]);
509
510                                        // zmniejsz liczby niedopasowanych elementow w grupach
511                                        aiRozmiarGrupy[0]--;
512                                        aiRozmiarGrupy[1]--;
513                                        // debug - co zostalo dopasowane
514                                        DB(printf("Przypadek 1.: dopasowane Parts: (%2i, %2i)\n", aiKoniecPierwszejGrupy[0]
515                                                + iIndex[0], aiKoniecPierwszejGrupy[1] + iIndex[1]);)
516
517                                }// PRZYPADEK 1.
518                                else
519                                        if (PartZ1NaLiscie0 || PartZ0NaLiscie1)
520                                        {
521                                                // PRZYPADEK 2. Tylko jeden z Parts ma drugiego na swojej liscie
522                                                // mozliwych dopasowan
523                                                // AKCJA. Dopasowanie jednego jest proste (tego, ktory nie ma
524                                                // na swojej liscie drugiego). Dla tego drugiego nalezy powtorzyc
525                                                // duza czesc obliczen (znalezc mu nowa mozliwa pare)
526
527                                                // indeks organizmu, ktorego Part nie ma dopasowywanego Part
528                                                // z drugiego organizmu na swojej liscie
529                                                int iBezDrugiego;
530
531                                                // okreslenie indeksu organizmu z dopasowywanym Part
532                                                if (!PartZ1NaLiscie0)
533                                                {
534                                                        iBezDrugiego = 0;
535                                                }
536                                                else
537                                                {
538                                                        iBezDrugiego = 1;
539                                                }
540                                                // sprawdz indeks organizmu
541                                                assert((iBezDrugiego == 0) || (iBezDrugiego == 1));
542
543                                                int iDopasowywany = -1;
544                                                // poszukujemy pierwszego z listy dopasowania
545                                                for (i = 0; i < aiRozmiarCalychGrup[1 - iBezDrugiego]; i++)
546                                                {
547                                                        if (apvbCzyMinimalnaOdleglosc[iBezDrugiego]->operator[](i))
548                                                        {
549                                                                iDopasowywany = i;
550                                                                break;
551                                                        }
552                                                }
553                                                // sprawdz poprawnosc indeksu dopasowywanego (musimy cos znalezc!)
554                                                // nieujemny i w odpowiedniej grupie!
555                                                assert((iDopasowywany >= 0) &&
556                                                        (iDopasowywany < aiRozmiarCalychGrup[1 - iBezDrugiego]));
557
558                                                // znalezlismy 1. Part z listy dopasowania - dopasowujemy!
559                                                m_pMatching->match(
560                                                        iBezDrugiego,
561                                                        aiKoniecPierwszejGrupy[iBezDrugiego] + iIndex[iBezDrugiego],
562                                                        1 - iBezDrugiego,
563                                                        aiKoniecPierwszejGrupy[1 - iBezDrugiego] + iDopasowywany);
564                                                DB(printf("Przypadek 2.1.: dopasowane Parts dopasowanie bez drugiego: (%2i, %2i)\n", aiKoniecPierwszejGrupy[iBezDrugiego] + iIndex[iBezDrugiego],
565                                                        aiKoniecPierwszejGrupy[1 - iBezDrugiego] + iDopasowywany);)
566
567                                                        // zmniejsz liczby niedopasowanych elementow w grupach
568                                                        aiRozmiarGrupy[0]--;
569                                                aiRozmiarGrupy[1]--;
570
571                                                // sprawdz, czy jest szansa dopasowania tego Part z drugiej strony
572                                                // (ktora miala mozliwosc dopasowania tego Part z poprzedniego organizmu)
573                                                if ((aiRozmiarGrupy[0] > 0) && (aiRozmiarGrupy[1] > 0))
574                                                {
575                                                        // jesli grupy sie jeszcze nie wyczrpaly
576                                                        // to jest mozliwosc dopasowania w organizmie
577
578                                                        int iZDrugim = 1 - iBezDrugiego;
579                                                        // sprawdz indeks organizmu
580                                                        assert((iZDrugim == 0) || (iZDrugim == 1));
581
582                                                        // bedziemy szukac minimum wsrod niedopasowanych - musimy wykasowac
583                                                        // poprzednie obliczenia minimum
584                                                        // dla organizmu 1 (o rozmiarze grupy z 0)
585                                                        for (i = 0; i < aiRozmiarCalychGrup[0]; i++)
586                                                        {
587                                                                apvbCzyMinimalnaOdleglosc[1]->operator[](i) = false;
588                                                        }
589                                                        // dla organizmu 0 (o rozmiarze grup z 1)
590                                                        for (i = 0; i < aiRozmiarCalychGrup[1]; i++)
591                                                        {
592                                                                apvbCzyMinimalnaOdleglosc[0]->operator[](i) = false;
593                                                        }
594
595                                                        // szukamy na nowo minimum dla Part o indeksie iIndex[ iZDrugim ] w organizmie iZDrugim
596                                                        // wsrod niedopasowanych Parts z organizmu 1 - iZDrugim
597                                                        dMinimum = HUGE_VAL;
598                                                        for (i = 0; i < aiRozmiarCalychGrup[1 - iZDrugim]; i++)
599                                                        {
600                                                                if (!(m_pMatching->isMatched(
601                                                                        1 - iZDrugim,
602                                                                        aiKoniecPierwszejGrupy[1 - iZDrugim] + i)))
603                                                                {
604                                                                        // szukamy minimum obliczonej lokalnej odleglosci tylko wsrod
605                                                                        // niedopasowanych jeszcze Parts
606                                                                        if (iZDrugim == 0)
607                                                                        {
608                                                                                // teraz niestety musimy rozpoznac odpowiedni organizm
609                                                                                // zeby moc indeksowac niesymetryczna tablice
610                                                                                if (aadOdleglosciParts[iIndex[0]][i] < dMinimum)
611                                                                                {
612                                                                                        dMinimum = aadOdleglosciParts[iIndex[0]][i];
613                                                                                }
614                                                                                // przy okazji - sprawdz, czy HUGE_VAL jest rzeczywiscie max dla double
615                                                                                assert(aadOdleglosciParts[iIndex[0]][i] < HUGE_VAL);
616
617                                                                        }
618                                                                        else
619                                                                        {
620                                                                                if (aadOdleglosciParts[i][iIndex[1]] < dMinimum)
621                                                                                {
622                                                                                        dMinimum = aadOdleglosciParts[i][iIndex[1]];
623                                                                                }
624                                                                                // przy okazji - sprawdz, czy HUGE_VAL jest rzeczywiscie max dla double
625                                                                                assert(aadOdleglosciParts[i][iIndex[1]] < HUGE_VAL);
626                                                                        }
627                                                                }
628                                                        }
629                                                        // sprawdz, czy minimum znaleziono - musi takie byc, bo jest cos niedopasowanego
630                                                        assert((dMinimum >= 0.0) && (dMinimum < HUGE_VAL));
631
632                                                        // teraz zaznaczamy w tablicy te wszystkie Parts, ktore maja
633                                                        // rzeczywiscie te minimalne odleglosci do Part w organizmie iZDrugim
634                                                        for (i = 0; i < aiRozmiarCalychGrup[1 - iZDrugim]; i++)
635                                                        {
636                                                                if (!(m_pMatching->isMatched(
637                                                                        1 - iZDrugim,
638                                                                        aiKoniecPierwszejGrupy[1 - iZDrugim] + i)))
639                                                                {
640                                                                        if (iZDrugim == 0)
641                                                                        {
642                                                                                // teraz niestety musimy rozpoznac odpowiedni organizm
643                                                                                // zeby moc indeksowac niesymetryczna tablice
644                                                                                if (aadOdleglosciParts[iIndex[0]][i] == dMinimum)
645                                                                                {
646                                                                                        // jesli w danym miejscu tablicy odleglosci jest faktyczne
647                                                                                        // minimum odleglosci, to mamy potencjalna pare dla iIndex[1]
648                                                                                        apvbCzyMinimalnaOdleglosc[0]->operator[](i) = true;
649                                                                                }
650                                                                        }
651                                                                        else
652                                                                        {
653                                                                                if (aadOdleglosciParts[i][iIndex[1]] == dMinimum)
654                                                                                {
655                                                                                        apvbCzyMinimalnaOdleglosc[1]->operator[](i) = true;
656                                                                                }
657                                                                        }
658                                                                }
659                                                        }
660
661                                                        // a teraz - po znalezieniu potencjalnych elementow do dopasowania
662                                                        // dopasowujemy pierwszy z potencjalnych
663                                                        iDopasowywany = -1;
664                                                        for (i = 0; i < aiRozmiarCalychGrup[1 - iZDrugim]; i++)
665                                                        {
666                                                                if (apvbCzyMinimalnaOdleglosc[iZDrugim]->operator[](i))
667                                                                {
668                                                                        iDopasowywany = i;
669                                                                        break;
670                                                                }
671                                                        }
672                                                        // musielismy znalezc jakiegos dopasowywanego
673                                                        assert((iDopasowywany >= 0) &&
674                                                                (iDopasowywany < aiRozmiarCalychGrup[1 - iZDrugim]));
675
676                                                        // no to juz mozemy dopasowac
677                                                        m_pMatching->match(
678                                                                iZDrugim,
679                                                                aiKoniecPierwszejGrupy[iZDrugim] + iIndex[iZDrugim],
680                                                                1 - iZDrugim,
681                                                                aiKoniecPierwszejGrupy[1 - iZDrugim] + iDopasowywany);
682                                                        DB(printf("Przypadek 2.1.: dopasowane Parts dopasowaniebz drugim: (%2i, %2i)\n", aiKoniecPierwszejGrupy[iZDrugim] + iIndex[iZDrugim], aiKoniecPierwszejGrupy[1 - iZDrugim] + iDopasowywany);)
683
684                                                                //aiKoniecPierwszejGrupy[ 1-iBezDrugiego ] + iDopasowywany ;)
685                                                                //aiKoniecPierwszejGrupy[ 1-iBezDrugiego ] + iDopasowywany ;)
686                                                                // zmniejsz liczby niedopasowanych elementow w grupach
687                                                                aiRozmiarGrupy[0]--;
688                                                        aiRozmiarGrupy[1]--;
689
690                                                }
691                                                else
692                                                {
693                                                        // jedna z grup sie juz wyczerpala
694                                                        // wiec nie ma mozliwosci dopasowania tego drugiego Partu
695                                                        /// i trzeba poczekac na zmiane grupy
696                                                }
697
698                                                DB(printf("Przypadek 2.\n");)
699
700                                        }// PRZYPADEK 2.
701                                        else
702                                        {
703                                                // PRZYPADEK 3. Zaden z Parts nie ma na liscie drugiego
704                                                // AKCJA. Niezalezne dopasowanie obu Parts do pierwszych ze swojej listy
705
706                                                // najpierw dopasujemy do iIndex[0] w organizmie 0
707                                                int iDopasowywany = -1;
708                                                // poszukujemy pierwszego z listy dopasowania - w organizmie 1
709                                                for (i = 0; i < aiRozmiarCalychGrup[1]; i++)
710                                                {
711                                                        if (apvbCzyMinimalnaOdleglosc[0]->operator[](i))
712                                                        {
713                                                                iDopasowywany = i;
714                                                                break;
715                                                        }
716                                                }
717                                                // musielismy znalezc jakiegos dopasowywanego
718                                                assert((iDopasowywany >= 0) &&
719                                                        (iDopasowywany < aiRozmiarCalychGrup[1]));
720
721                                                // teraz wlasnie dopasowujemy
722                                                m_pMatching->match(
723                                                        0,
724                                                        aiKoniecPierwszejGrupy[0] + iIndex[0],
725                                                        1,
726                                                        aiKoniecPierwszejGrupy[1] + iDopasowywany);
727
728                                                // zmniejszamy liczbe niedopasowanych Parts
729                                                aiRozmiarGrupy[0]--;
730                                                aiRozmiarGrupy[1]--;
731
732                                                // debug - dopasowanie
733                                                DB(printf("Przypadek 3.: dopasowane Parts: (%2i, %2i)\n", aiKoniecPierwszejGrupy[0]
734                                                        + iIndex[0], aiKoniecPierwszejGrupy[1] + iDopasowywany);)
735
736                                                        // teraz dopasowujemy do iIndex[1] w organizmie 1
737                                                        iDopasowywany = -1;
738                                                // poszukujemy pierwszego z listy dopasowania - w organizmie 0
739                                                for (i = 0; i < aiRozmiarCalychGrup[0]; i++)
740                                                {
741                                                        if (apvbCzyMinimalnaOdleglosc[1]->operator[](i))
742                                                        {
743                                                                iDopasowywany = i;
744                                                                break;
745                                                        }
746                                                }
747                                                // musielismy znalezc jakiegos dopasowywanego
748                                                assert((iDopasowywany >= 0) &&
749                                                        (iDopasowywany < aiRozmiarCalychGrup[0]));
750
751                                                // no i teraz realizujemy dopasowanie
752                                                m_pMatching->match(
753                                                        0,
754                                                        aiKoniecPierwszejGrupy[0] + iDopasowywany,
755                                                        1,
756                                                        aiKoniecPierwszejGrupy[1] + iIndex[1]);
757
758                                                // zmniejszamy liczbe niedopasowanych Parts
759                                                aiRozmiarGrupy[0]--;
760                                                aiRozmiarGrupy[1]--;
761
762                                                // debug - dopasowanie
763                                                DB(printf("Przypadek 3.: dopasowane Parts: (%2i, %2i)\n", aiKoniecPierwszejGrupy[0]
764                                                        + iDopasowywany, aiKoniecPierwszejGrupy[1] + iIndex[1]);)
765
766
767                                        } // PRZYPADEK 3.
768
769                        }// if (! bCzyKoniecGrupy)
770                        else
771                        {
772                                // gdy mamy juz koniec grup - musimy zlikwidowac tablice aadOdleglosciParts
773                                // bo za chwilke skonczy sie nam petla
774                                for (i = 0; i < aiRozmiarCalychGrup[0]; i++)
775                                {
776                                        SAFEDELETEARRAY(aadOdleglosciParts[i]);
777                                }
778                                SAFEDELETEARRAY(aadOdleglosciParts);
779
780                                // musimy tez usunac tablice (wektory) mozliwosci dopasowania
781                                SAFEDELETE(apvbCzyMinimalnaOdleglosc[0]);
782                                SAFEDELETE(apvbCzyMinimalnaOdleglosc[1]);
783                        }
784                } // while (! bCzyKoniecGrupy)
785
786                // PO DOPASOWANIU WSZYSTKIEGO Z GRUP (CO NAJMNIEJ JEDNEJ GRUPY W CALOSCI)
787
788                // gdy rozmiar ktorejkolwiek z grup dopasowania spadl do zera
789                // to musimy przesunac KoniecPierwszejGrupy (wszystkie dopasowane)
790                for (i = 0; i < 2; i++)
791                {
792                        // grupy nie moga miec mniejszego niz 0 rozmiaru
793                        assert(aiRozmiarGrupy[i] >= 0);
794                        if (aiRozmiarGrupy[i] == 0)
795                                aiKoniecPierwszejGrupy[i] = aiKoniecGrupyDopasowania[i];
796                }
797
798                // sprawdzenie warunku konca dopasowywania - gdy nie
799                // ma juz w jakims organizmie co dopasowywac
800                if (aiKoniecPierwszejGrupy[0] >= m_aiPartCount[0] ||
801                        aiKoniecPierwszejGrupy[1] >= m_aiPartCount[1])
802                {
803                        iCzyDopasowane = 1;
804                }
805        } // koniec WHILE - petli dopasowania
806}
807
808void SimilMeasureGreedy::copyMatching()
809{
810        SAFEDELETE(tempMatching);
811        tempMatching = new SimilMatching(*m_pMatching);
812}
813
814void SimilMeasureGreedy::prepareData()
815{       
816        // create Parts matching object
817        m_pMatching = new SimilMatching(models[0]->getPartCount(), models[1]->getPartCount());
818
819        // utworzenie tablicy rozmiarow
820        for (int i = 0; i < 2; i++)
821        {
822                m_aiPartCount[i] = models[i]->getPartCount();
823        }
824       
825        // difference in the number of vertices (Parts) - positive
826        // find object that has less parts (m_iSmaller)
827        m_iDV = (models[0]->getPartCount() - models[1]->getPartCount());
828        if (m_iDV < 0)
829                m_iDV = -m_iDV;
830
831        // check if index of the smaller organism is a valid index
832        assert((m_iSmaller == 0) || (m_iSmaller == 1));
833        // validate difference in the parts number
834        assert(m_iDV >= 0);
835       
836        if (!createPartInfoTables())
837                logPrintf("GreedyMeasure", "PrepareData", LOG_ERROR, "Unable to create part info tables.");
838        if (!countPartDegrees())
839                logPrintf("GreedyMeasure", "PrepareData", LOG_ERROR, "Unable to count part degrees.");
840        if (!countPartNeurons())
841                logPrintf("GreedyMeasure", "PrepareData", LOG_ERROR, "Unable to count part neurons.");
842
843        DB(printf("Przed sortowaniem:\n");)
844        DB(_PrintDegrees(0);)
845        DB(_PrintDegrees(1);)
846
847        if (!sortPartInfoTables())
848                logPrintf("GreedyMeasure", "PrepareData", LOG_ERROR, "Unable to sort part info tables.");
849
850        DB(printf("Po sortowaniu:\n");)
851        DB(_PrintDegrees(0);)
852        DB(_PrintDegrees(1);)
853
854        if (m_adFactors[3] == 0)
855            with_alignment = false;
856}
857
858void SimilMeasureGreedy::cleanData()
859{
860        // delete degree arrays created in CreatePartInfoTables
861        SAFEDELETEARRAY(m_aDegrees[0]);
862        SAFEDELETEARRAY(m_aDegrees[1]);
863       
864        // in fuzzy mode delete arrays of neighbourhood and fuzzy neighbourhood
865        if (isFuzzy)
866        {
867                for (int i = 0; i != 2; ++i)
868                {
869                        for (int j = 0; j != models[i]->getPartCount(); ++j)
870                        {
871                                delete[] m_Neighbours[i][j];
872                                delete[] m_fuzzyNeighb[i][j];
873                        }
874                        delete[] m_Neighbours[i];
875                        delete[] m_fuzzyNeighb[i];
876                }
877
878        }
879       
880        // delete created matching
881        SAFEDELETE(m_pMatching);
882       
883        with_alignment = true; //restore default value
884}
885
886/** Creates arrays holding information about organisms' Parts (m_aDegrees) andm_Neigh
887        fills them with initial data (original indices and zeros).
888        Assumptions:
889        - Models (models) are created and available.
890        */
891int SimilMeasureGreedy::createPartInfoTables()
892{
893        int i, j, partCount;
894        // utwórz tablice na informacje o stopniach wierzchołków i liczbie neuroitems
895        for (i = 0; i < 2; i++)
896        {
897                partCount = models[i]->getPartCount();
898                // utworz i wypelnij tablice dla Parts wartosciami poczatkowymi
899                m_aDegrees[i] = new TDN[partCount];
900
901                if (isFuzzy)
902                {
903                        m_Neighbours[i] = new int*[partCount];
904                        m_fuzzyNeighb[i] = new float*[partCount];
905                }
906
907                if (m_aDegrees[i] != NULL && ((!isFuzzy) || (m_Neighbours[i] != NULL && m_fuzzyNeighb[i] != NULL)))
908                {
909                        // wypelnij tablice zgodnie z sensem TDN[0] - orginalny index
910                        // TDN[1], TDN[2], TDN[3] - zerami
911                        DB(printf("m_aDegrees[%i]: %p\n", i, m_aDegrees[i]);)
912                                for (j = 0; j < partCount; j++)
913                                {
914                                        m_aDegrees[i][j][0] = j;
915                                        m_aDegrees[i][j][1] = 0;
916                                        m_aDegrees[i][j][2] = 0;
917                                        m_aDegrees[i][j][3] = 0;
918                                        m_aDegrees[i][j][4] = 0;
919
920                                        // sprawdz, czy nie piszemy po jakims szalonym miejscu pamieci
921                                        assert(m_aDegrees[i][j] != NULL);
922
923                                        if (isFuzzy)
924                                        {
925                                                m_Neighbours[i][j] = new int[partCount];
926                                                for (int k = 0; k < partCount; k++)
927                                                {
928                                                        m_Neighbours[i][j][k] = 0;
929                                                }
930
931                                                m_fuzzyNeighb[i][j] = new float[fuzzyDepth];
932                                                for (int k = 0; k < fuzzyDepth; k++)
933                                                {
934                                                        m_fuzzyNeighb[i][j][k] = 0;
935                                                }
936
937                                                assert(m_Neighbours[i][j] != NULL);
938                                                assert(m_fuzzyNeighb[i][j] != NULL);
939                                        }
940
941                                }
942                }
943                else
944                {
945                        logPrintf("ModelSimil", "CreatePartInfoTables", LOG_ERROR, "Not enough memory?");
946                        return 0;
947                }
948                // wypelnij tablice OnJoints i Anywhere wartościami początkowymi
949                // OnJoint
950                m_aOnJoint[i][0] = 0;
951                m_aOnJoint[i][1] = 0;
952                m_aOnJoint[i][2] = 0;
953                m_aOnJoint[i][3] = 0;
954                // Anywhere
955                m_aAnywhere[i][0] = 0;
956                m_aAnywhere[i][1] = 0;
957                m_aAnywhere[i][2] = 0;
958                m_aAnywhere[i][3] = 0;
959        }
960        return 1;
961}
962
963/** Computes degrees of Parts of both organisms. Fills in the m_aDegrees arrays
964        with proper information about degrees.
965        Assumptions:
966        - Models (models) are created and available.
967        - Arrays m_aDegrees are created.
968        */
969int SimilMeasureGreedy::countPartDegrees()
970{
971        Part *P1, *P2;
972        int i, j, i1, i2;
973
974        // dla obu stworzen oblicz stopnie wierzcholkow
975        for (i = 0; i < 2; i++)
976        {
977                // dla wszystkich jointow
978                for (j = 0; j < models[i]->getJointCount(); j++)
979                {
980                        // pobierz kolejny Joint
981                        Joint *J = models[i]->getJoint(j);
982                        // wez jego konce
983                        P1 = J->part1;
984                        P2 = J->part2;
985                        // znajdz ich indeksy w Modelu (indeksy orginalne)
986                        i1 = models[i]->findPart(P1);
987                        i2 = models[i]->findPart(P2);
988                        // zwieksz stopien odpowiednich Parts
989                        m_aDegrees[i][i1][DEG]++;
990                        m_aDegrees[i][i2][DEG]++;
991                        m_aDegrees[i][i1][FUZ_DEG]++;
992                        m_aDegrees[i][i2][FUZ_DEG]++;
993                        if (isFuzzy)
994                        {
995                                m_Neighbours[i][i1][i2] = 1;
996                                m_Neighbours[i][i2][i1] = 1;
997                        }
998                }
999                // dla elementow nie osadzonych na Parts (OnJoint, Anywhere) -
1000                // stopnie wierzchołka są już ustalone na zero
1001        }
1002
1003        if (isFuzzy)
1004        {
1005                countFuzzyNeighb();
1006        }
1007
1008        return 1;
1009}
1010
1011void SimilMeasureGreedy::getNeighbIndexes(int mod, int partInd, std::vector<int> &indexes)
1012{
1013        indexes.clear();
1014        int i, size = models[mod]->getPartCount();
1015
1016        for (i = 0; i < size; i++)
1017        {
1018                if (m_Neighbours[mod][partInd][i] > 0)
1019                {
1020                        indexes.push_back(i);
1021                }
1022        }
1023}
1024
1025int compareFuzzyRows(const void *pa, const void *pb)
1026{
1027        float **a = (float**)pa;
1028        float **b = (float**)pb;
1029
1030        for (int i = 1; i < fuzzDepth; i++)
1031        {
1032                if (a[0][i] > b[0][i])
1033                {
1034                        return -1;
1035                }
1036                if (a[0][i] < b[0][i])
1037                {
1038                        return 1;
1039                }
1040        }
1041
1042        return 0;
1043}
1044
1045void SimilMeasureGreedy::fuzzyOrder()
1046{
1047        int i, depth, partInd, prevPartInd, partCount;
1048        for (int mod = 0; mod < 2; mod++)
1049        {
1050                partCount = models[mod]->getPartCount();
1051                partInd = m_fuzzyNeighb[mod][partCount - 1][0];
1052                m_aDegrees[mod][partInd][FUZ_DEG] = 0;
1053
1054                for (i = (partCount - 2); i >= 0; i--)
1055                {
1056                        prevPartInd = partInd;
1057                        partInd = m_fuzzyNeighb[mod][i][0];
1058                        m_aDegrees[mod][partInd][FUZ_DEG] = m_aDegrees[mod][prevPartInd][FUZ_DEG];
1059                        for (depth = 1; depth < fuzzyDepth; depth++)
1060                        {
1061                                if (m_fuzzyNeighb[mod][i][depth] != m_fuzzyNeighb[mod][i + 1][depth])
1062                                {
1063                                        m_aDegrees[mod][partInd][FUZ_DEG]++;
1064                                        break;
1065                                }
1066                        }
1067                }
1068        }
1069}
1070
1071//sort according to fuzzy degree
1072void SimilMeasureGreedy::sortFuzzyNeighb()
1073{
1074        fuzzDepth = fuzzyDepth;
1075        for (int mod = 0; mod < 2; mod++)
1076        {
1077                std::qsort(m_fuzzyNeighb[mod], (size_t)models[mod]->getPartCount(), sizeof(m_fuzzyNeighb[mod][0]), compareFuzzyRows);
1078        }
1079}
1080
1081//computes fuzzy vertex degree
1082void SimilMeasureGreedy::countFuzzyNeighb()
1083{
1084        std::vector<int> nIndexes;
1085        float newDeg = 0;
1086
1087        for (int mod = 0; mod < 2; mod++)
1088        {
1089                int partCount = models[mod]->getPartCount();
1090
1091                for (int depth = 0; depth < fuzzyDepth; depth++)
1092                {
1093                        //use first column for storing indices
1094                        for (int partInd = 0; partInd < partCount; partInd++)
1095                        {
1096                                if (depth == 0)
1097                                {
1098                                        m_fuzzyNeighb[mod][partInd][depth] = partInd;
1099                                }
1100                                else if (depth == 1)
1101                                {
1102                                        m_fuzzyNeighb[mod][partInd][depth] = m_aDegrees[mod][partInd][DEG];
1103                                }
1104                                else
1105                                {
1106                                        getNeighbIndexes(mod, partInd, nIndexes);
1107                                        for (unsigned int k = 0; k < nIndexes.size(); k++)
1108                                        {
1109                                                newDeg += m_fuzzyNeighb[mod][nIndexes.at(k)][depth - 1];
1110                                        }
1111                                        newDeg /= nIndexes.size();
1112                                        m_fuzzyNeighb[mod][partInd][depth] = newDeg;
1113                                        for (int mod = 0; mod < 2; mod++)
1114                                        {
1115                                                int partCount = models[mod]->getPartCount();
1116                                                for (int i = partCount - 1; i >= 0; i--)
1117                                                {
1118
1119                                                }
1120                                        }
1121                                        newDeg = 0;
1122                                }
1123                        }
1124                }
1125        }
1126
1127        sortFuzzyNeighb();
1128        fuzzyOrder();
1129}
1130
1131/** Computes numbers of neurons and neurons' inputs for each Part of each
1132        organisms and fills in the m_aDegrees array.
1133        Assumptions:
1134        - Models (models) are created and available.
1135        - Arrays m_aDegrees are created.
1136        */
1137int SimilMeasureGreedy::countPartNeurons()
1138{
1139        // sprawdz zalozenie - o modelach
1140        assert((models[0] != NULL) && (models[1] != NULL));
1141        assert(models[0]->isValid() && models[1]->isValid());
1142
1143        // sprawdz zalozenie - o tablicach
1144        assert(m_aDegrees[0] != NULL);
1145        assert(m_aDegrees[1] != NULL);
1146       
1147        Part *P1;
1148        Joint *J1;
1149        int i, j, i2, neuro_connections;
1150
1151        // dla obu stworzen oblicz liczbe Neurons + connections dla Parts
1152        // a takze dla OnJoints i Anywhere
1153        for (i = 0; i < 2; i++)
1154        {
1155                for (j = 0; j < models[i]->getNeuroCount(); j++)
1156                {
1157                        // pobierz kolejny Neuron
1158                        Neuro *N = models[i]->getNeuro(j);
1159                        // policz liczbe jego wejść i jego samego tez
1160                        // czy warto w ogole liczyc polaczenia...? co to da/spowoduje?
1161                        neuro_connections = N->getInputCount() + 1;
1162                        // wez Part, na ktorym jest Neuron
1163                        P1 = N->getPart();
1164                        if (P1)
1165                        {
1166                                // dla neuronow osadzonych na Partach
1167                                i2 = models[i]->findPart(P1); // znajdz indeks Part w Modelu
1168                                m_aDegrees[i][i2][2] += neuro_connections; // zwieksz liczbe Connections+Neurons dla tego Part (TDN[2])
1169                                m_aDegrees[i][i2][3]++; // zwieksz liczbe Neurons dla tego Part (TDN[3])
1170                        }
1171                        else
1172                        {
1173                                // dla neuronow nie osadzonych na partach
1174                                J1 = N->getJoint();
1175                                if (J1)
1176                                {
1177                                        // dla tych na Jointach
1178                                        m_aOnJoint[i][2] += neuro_connections; // zwieksz liczbe Connections+Neurons
1179                                        m_aOnJoint[i][3]++; // zwieksz liczbe Neurons
1180                                }
1181                                else
1182                                {
1183                                        // dla tych "gdziekolwiek"
1184                                        m_aAnywhere[i][2] += neuro_connections; // zwieksz liczbe Connections+Neurons
1185                                        m_aAnywhere[i][3]++; // zwieksz liczbe Neurons
1186                                }
1187                        }
1188                }
1189        }
1190        return 1;
1191}
1192
1193/** Sorts arrays m_aDegrees (for each organism) by Part's degree, and then by
1194        number of neural connections and neurons in groups of Parts with the same
1195        degree.
1196        Assumptions:
1197        - Models (models) are created and available.
1198        - Arrays m_aDegrees are created.
1199        @saeDegrees, CompareItemNo
1200        */
1201int SimilMeasureGreedy::sortPartInfoTables()
1202{
1203        int i;
1204        int(*pfDegreeFunction) (const void*, const void*) = NULL;
1205        pfDegreeFunction = isFuzzy ? &compareFuzzyDegrees : &compareDegrees;
1206        // sortowanie obu tablic wg stopni punktów - TDN[1]
1207        for (i = 0; i < 2; i++)
1208        {
1209                DB(_PrintDegrees(i));
1210                std::qsort(m_aDegrees[i], (size_t)(models[i]->getPartCount()),
1211                        sizeof(TDN), pfDegreeFunction);
1212                DB(_PrintDegrees(i));
1213        }
1214
1215        // sprawdzenie wartosci parametru
1216        DB(i = sizeof(TDN);)
1217                int degreeType = isFuzzy ? FUZ_DEG : DEG;
1218
1219        // sortowanie obu tablic m_aDegrees wedlug liczby neuronów i
1220        // czesci neuronu - ale w obrebie grup o tym samym stopniu
1221        for (i = 0; i < 2; i++)
1222        {
1223                int iPocz = 0;
1224                int iDeg, iNewDeg, iPartCount, j;
1225                // stopien pierwszego punktu w tablicy Degrees  odniesienie
1226                iDeg = m_aDegrees[i][0][degreeType];
1227                iPartCount = models[i]->getPartCount();
1228                // po kolei dla kazdego punktu w organizmie
1229                for (j = 0; j <= iPartCount; j++)
1230                {
1231                        // sprawdz stopien punktu (lub nadaj 0 - gdy juz koniec tablicy)
1232                        //                      iNewDeg = (j != iPartCount) ? m_aDegrees[i][j][1] : 0;
1233                        // usunieto stara wersje porownania!!! wprowadzono znak porownania <
1234
1235                        iNewDeg = (j < iPartCount) ? m_aDegrees[i][j][degreeType] : 0;
1236                        // skoro tablice sa posortowane wg stopni, to mamy na pewno taka kolejnosc
1237                        assert(iNewDeg <= iDeg);
1238                        if (iNewDeg != iDeg)
1239                        {
1240                                // gdy znaleziono koniec grupy o tym samym stopniu
1241                                // sortuj po liczbie neuronow w obrebie grupy
1242                                DB(_PrintDegrees(i));
1243                                DB(printf("qsort( poczatek=%i, rozmiar=%i, sizeof(TDN)=%i)\n", iPocz, (j - iPocz), sizeof(TDN));)
1244                                        // wyswietlamy z jedna komorka po zakonczeniu tablicy
1245                                        DB(_PrintArray(m_aDegrees[i][iPocz], 0, (j - iPocz) * 4);)
1246
1247                                        std::qsort(m_aDegrees[i][iPocz], (size_t)(j - iPocz),
1248                                                sizeof(TDN), SimilMeasureGreedy::compareConnsNo);
1249                                DB(_PrintDegrees(i));
1250                                // wyswietlamy z jedna komorka po zakonczeniu tablicy
1251                                DB(_PrintArray(m_aDegrees[i][iPocz], 0, (j - iPocz) * 4);)
1252                                        // rozpocznij nowa grupe
1253                                        iPocz = j;
1254                                iDeg = iNewDeg;
1255                        }
1256                }
1257        }
1258        return 1;
1259}
1260
1261
1262/** Prints the state of the matching object. Debug method.
1263 */
1264void SimilMeasureGreedy::_PrintPartsMatching()
1265{
1266        // assure that matching exists
1267        assert(m_pMatching != NULL);
1268
1269        printf("Parts matching:\n");
1270        m_pMatching->printMatching();
1271}
1272
1273/** Comparison function required for qsort() call. Used while sorting groups of
1274        Parts with respect to degree. Compares two TDN structures
1275        with respect to their [1] field (degree). Highest degree goes first.
1276        @param pElem1 Pointer to the TDN structure of some Part.
1277        @param pElem2 Pointer to the TDN structure of some Part.
1278        @return (-1) - pElem1 should go first, 0 - equal, (1) - pElem2 should go first.
1279        */
1280int SimilMeasureGreedy::compareDegrees(const void *pElem1, const void *pElem2)
1281{
1282        int *tdn1 = (int *)pElem1;
1283        int *tdn2 = (int *)pElem2;
1284
1285        if (tdn1[1] > tdn2[1])
1286        {
1287                // when degree - tdn1[1] - is BIGGER
1288                return -1;
1289        }
1290        else
1291                if (tdn1[1] < tdn2[1])
1292                {
1293                        // when degree - tdn2[1] - is BIGGER
1294                        return 1;
1295                }
1296                else
1297                {
1298                        return 0;
1299                }
1300}
1301
1302/** Comparison function required for qsort() call. Used while sorting groups of
1303        Parts with respect to fuzzy vertex degree. Compares two TDN structures
1304        with respect to their [4] field ( fuzzy vertex degree). Highest degree goes first.
1305        @param pElem1 Pointer to the TDN structure of some Part.
1306        @param pElem2 Pointer to the TDN structure of some Part.
1307        @return (-1) - pElem1 should go first, 0 - equal, (1) - pElem2 should go first.
1308        */
1309int SimilMeasureGreedy::compareFuzzyDegrees(const void *pElem1, const void *pElem2)
1310{
1311        int *tdn1 = (int *)pElem1;
1312        int *tdn2 = (int *)pElem2;
1313
1314        if (tdn1[4] > tdn2[4])
1315        {
1316                // when degree - tdn1[4] - is BIGGER
1317                return -1;
1318        }
1319        else
1320                if (tdn1[4] < tdn2[4])
1321                {
1322                        // when degree - tdn2[4] - is BIGGER
1323                        return 1;
1324                }
1325                else
1326                {
1327                        return 0;
1328                }
1329}
1330
1331/** Comparison function required for qsort() call. Used while sorting groups of Parts with
1332                the same degree. Firstly, compare NIt. Secondly, compare Neu. If both are equal -
1333                compare Parts' original index (they are never equal). So this sorting assures
1334                that the order obtained is deterministic.
1335                @param pElem1 Pointer to the TDN structure of some Part.
1336                @param pElem2 Pointer to the TDN structure of some Part.
1337                @return (-1) - pElem1 should go first, 0 - equal, (1) - pElem2 should go first.
1338                */
1339int SimilMeasureGreedy::compareConnsNo(const void *pElem1, const void *pElem2)
1340{
1341        // pointers to TDN arrays
1342        int *tdn1, *tdn2;
1343        // definitions of elements being compared
1344        tdn1 = (int *)pElem1;
1345        tdn2 = (int *)pElem2;
1346
1347        // comparison according to Neural Connections (to jest TDN[2])
1348        if (tdn1[NEUR_CONNS] > tdn2[NEUR_CONNS])
1349        {
1350                // when number of NConn Elem1 is BIGGER
1351                return -1;
1352        }
1353        else
1354                if (tdn1[NEUR_CONNS] < tdn2[NEUR_CONNS])
1355                {
1356                        // when number of NConn Elem1 is SMALLER
1357                        return 1;
1358                }
1359                else
1360                {
1361                        // when numbers of NConn are EQUAL
1362                        // compare Neu numbers (TDN[3])
1363                        if (tdn1[NEUROS] > tdn2[NEUROS])
1364                        {
1365                                // when number of Neu is BIGGER for Elem1
1366                                return -1;
1367                        }
1368                        else
1369                                if (tdn1[NEUROS] < tdn2[NEUROS])
1370                                {
1371                                        // when number of Neu is SMALLER for Elem1
1372                                        return 1;
1373                                }
1374                                else
1375                                {
1376                                        // when numbers of Nconn and Neu are equal we check original indices
1377                                        // of Parts being compared
1378
1379                                        // comparison according to OrgIndex
1380                                        if (tdn1[ORG_IND] > tdn2[ORG_IND])
1381                                        {
1382                                                // when the number of NIt Deg1 id BIGGER
1383                                                return -1;
1384                                        }
1385                                        else
1386                                                if (tdn1[ORG_IND] < tdn2[ORG_IND])
1387                                                {
1388                                                        // when the number of NIt Deg1 id SMALLER
1389                                                        return 1;
1390                                                }
1391                                                else
1392                                                {
1393                                                        // impossible, indices are alway different
1394                                                        return 0;
1395                                                }
1396                                }
1397                }
1398}
1399
1400/** Returns number of factors involved in final distance computation.
1401                These factors include differences in numbers of parts, degrees,
1402                number of neurons.
1403                */
1404int SimilMeasureGreedy::getNOFactors()
1405{
1406        return SimilMeasureGreedy::iNOFactors;
1407}
1408
1409/** Prints the array of degrees for the given organism. Debug method.
1410 */
1411void SimilMeasureGreedy::_PrintDegrees(int i)
1412{
1413        int j;
1414        printf("Organizm %i :", i);
1415        printf("\n      ");
1416        for (j = 0; j < models[i]->getPartCount(); j++)
1417                printf("%3i ", j);
1418        printf("\nInd:  ");
1419        for (j = 0; j < models[i]->getPartCount(); j++)
1420                printf("%3i ", (int)m_aDegrees[i][j][0]);
1421        printf("\nDeg:  ");
1422        for (j = 0; j < models[i]->getPartCount(); j++)
1423                printf("%3i ", (int)m_aDegrees[i][j][1]);
1424        printf("\nNIt:  ");
1425        for (j = 0; j < models[i]->getPartCount(); j++)
1426                printf("%3i ", (int)m_aDegrees[i][j][2]);
1427        printf("\nNeu:  ");
1428        for (j = 0; j < models[i]->getPartCount(); j++)
1429                printf("%3i ", (int)m_aDegrees[i][j][3]);
1430        printf("\n");
1431}
1432
1433/** Prints one array of ints. Debug method.
1434        @param array Base pointer of the array.
1435        @param base First index of the array's element.
1436        @param size Number of elements to print.
1437        */
1438void SimilMeasureGreedy::_PrintArray(int *array, int base, int size)
1439{
1440        int i;
1441        for (i = base; i < base + size; i++)
1442        {
1443                printf("%i ", array[i]);
1444        }
1445        printf("\n");
1446}
1447
1448void SimilMeasureGreedy::_PrintArrayDouble(double *array, int base, int size)
1449{
1450        int i;
1451        for (i = base; i < base + size; i++)
1452        {
1453                printf("%f ", array[i]);
1454        }
1455        printf("\n");
1456}
1457
1458/** Prints one array of parts neighbourhood.
1459        @param index of organism
1460        */
1461void SimilMeasureGreedy::_PrintNeighbourhood(int o)
1462{
1463        assert(m_Neighbours[o] != 0);
1464        printf("Neighbourhhod of organism %i\n", o);
1465        int size = models[o]->getPartCount();
1466        for (int i = 0; i < size; i++)
1467        {
1468                for (int j = 0; j < size; j++)
1469                {
1470                        printf("%i ", m_Neighbours[o][i][j]);
1471                }
1472                printf("\n");
1473        }
1474}
1475
1476/** Prints one array of parts fuzzy neighbourhood.
1477        @param index of organism
1478        */
1479void SimilMeasureGreedy::_PrintFuzzyNeighbourhood(int o)
1480{
1481        assert(m_fuzzyNeighb[o] != NULL);
1482        printf("Fuzzy neighbourhhod of organism %i\n", o);
1483        int size = models[o]->getPartCount();
1484        for (int i = 0; i < size; i++)
1485        {
1486                for (int j = 0; j < fuzzyDepth; j++)
1487                {
1488                        printf("%f ", m_fuzzyNeighb[o][i][j]);
1489                }
1490                printf("\n");
1491        }
1492}
1493
1494int SimilMeasureGreedy::setParams(std::vector<double> params)
1495{
1496        int i = 0;
1497        for (i = 0; i < SimilMeasureGreedy::iNOFactors; i++)
1498                m_adFactors[i] = params.at(i);
1499        fixedZaxis = params.at(i);
1500        return 0;
1501}
Note: See TracBrowser for help on using the repository browser.