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

Last change on this file since 1045 was 1044, checked in by oriona, 3 years ago

Similarity measures code refactored. Distribution-based similarity measure added.

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