Context Navigation

measure-greedy.cpp @ 1326

Last change on this file since 1326 was 1174, checked in by Maciej Komosinski, 3 years ago
Cosmetic
File size: 47.7 KB

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

Note: See TracBrowser for help on using the repository browser.

Context Navigation

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

Download in other formats: