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

Last change on this file since 1048 was 1048, checked in by Maciej Komosinski, 3 years ago

SimilMeasure? -> SimilMeasureBase?; introduced a new class (SimilMeasure?) that allows scripts to access all similarity measures; a number of minor fixes and improvements

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