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

Last change on this file since 1073 was 1073, checked in by oriona, 8 months ago

Comments added.

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