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

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

Make names of fields in SimilMeasureGreedy? unique because object fields from many objects are merged into one list and they would clash with names of fields from SimilMeasureHungarian?

File size: 46.9 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                { "Creature: Similarity: Graph greedy", 1, 7, "SimilMeasureGreedy", "Evaluates morphological dissimilarity using greedy measure. More information:\nhttp://www.framsticks.com/bib/Komosinski-et-al-2001\nhttp://www.framsticks.com/bib/Komosinski-and-Kubiak-2011\nhttp://www.framsticks.com/bib/Komosinski-2016\nhttps://doi.org/10.1007/978-3-030-16692-2_8", },
17                { "simil_greedy_parts", 0, 0, "Weight of parts count", "f 0 100 0", FIELD(m_adFactors[0]), "Differing number of parts is also handled by the 'part degree' similarity component.", },
18                { "simil_greedy_partdeg", 0, 0, "Weight of parts' degree", "f 0 100 1", FIELD(m_adFactors[1]), "", },
19                { "simil_greedy_neuro", 0, 0, "Weight of neurons count", "f 0 100 0.1", FIELD(m_adFactors[2]), "", },
20                { "simil_greedy_partgeom", 0, 0, "Weight of parts' geometric distances", "f 0 100 0", FIELD(m_adFactors[3]), "", },
21                { "simil_greedy_fixedZaxis", 0, 0, "Fix 'z' (vertical) axis?", "d 0 1 0", FIELD(fixedZaxis), "", },
22                { "simil_greedy_weightedMDS", 0, 0, "Should weighted MDS be used?", "d 0 1 0", FIELD(wMDS), "If activated, weighted MDS with vertex (i.e., Part) degrees as weights is used for 3D alignment of body structure.", },
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.