#include "Laplacian.h"void Lapland (int* fa, int nf, int nv, sparse_matrix_arr *m){}void Laplacian (int* faces_array, int number_of_faces, int number_of_vertices, sparse_matrix_arr * matrix) { int i, x1, x2, x3; int** temp_single_faces_array = (int**) calloc(number_of_vertices, sizeof(int*)); for (i = 0; i < number_of_vertices; i++) temp_single_faces_array[i] = (int*) calloc(MAX_NUMBER_OF_FACES_FOR_VERTICE, sizeof(int) ); for (i=0; i < (number_of_faces*3); i = i+3) { x1 = faces_array[i]; x2 = faces_array[i+1]; x3 = faces_array[i+2]; Insert_to_temp_array(x1,x2,temp_single_faces_array); Insert_to_temp_array(x2,x1,temp_single_faces_array); Insert_to_temp_array(x2,x3,temp_single_faces_array); Insert_to_temp_array(x3,x2,temp_single_faces_array); Insert_to_temp_array(x3,x1,temp_single_faces_array); Insert_to_temp_array(x1,x3,temp_single_faces_array); } //After this loop, the temp_single_faces_array should contain for each vertice all neighbouring vertices in ascending order /*for (x1 = 0; x1 < number_of_vertices; x1++) { for (x2 = 0; x2 < MAX_NUMBER_OF_FACES_FOR_VERTICE; x2++) printf("%d,",temp_single_faces_array[x1][x2]); printf("\n"); }*/ Create_Sparse_Laplacian_Matrix(number_of_faces, number_of_vertices, temp_single_faces_array,matrix); for (i = 0; i< number_of_vertices; i++) free(temp_single_faces_array[i]); free(temp_single_faces_array); //freeing allocated memory} void Insert_to_temp_array (int x, int y, int** base_array) { int tmp, tmp2; int i = 0; int cnt = 1; //when cnt == 0, then the loop needs to end regardless of i while (i < MAX_NUMBER_OF_FACES_FOR_VERTICE && cnt) { if (base_array[x][i] == 0) { //if x has no already known neighbours. if (y == 0) //in case y is the zero placed vertice, we'll place a -1 in the array base_array[x][i] = -1; else base_array[x][i] = y; cnt = 0; } else if (base_array[x][i] == y) //in case y and x are already neighbours cnt = 0; else if (base_array[x][i] == -1 && y == 0) cnt = 0; else if (base_array[x][i] > y) { //if y should be inserted before already existing neighbouring vertices of x (his index is smaller) cnt = 0; tmp = base_array[x][i]; if (y == 0) //in case y is the zero placed vertice, we'll place a -1 in the array base_array[x][i] = -1; else base_array[x][i] = y; while (i < (MAX_NUMBER_OF_FACES_FOR_VERTICE-1) && tmp != 0) { //we need to push all higher indexes further on the array i++; tmp2 = base_array[x][i]; base_array[x][i] = tmp; tmp = tmp2; } } else i++; }}void Create_Sparse_Laplacian_Matrix(int number_of_faces,int number_of_vertices, int** temp_single_faces_array, sparse_matrix_arr * matrix) { int neighbour_quantity, i, j, k, diff, pos; int* temp_laplacian_values; int* temp_laplacian_rows; int* temp_laplacian_cols; neighbour_quantity = counting_matrix(number_of_faces, temp_single_faces_array); temp_laplacian_values = (int*) calloc(neighbour_quantity+number_of_vertices, sizeof(int)); temp_laplacian_rows = (int*) calloc(neighbour_quantity+number_of_vertices, sizeof(int)); temp_laplacian_cols = (int*) calloc(number_of_faces+1, sizeof(int)); //free(*laplacian_values); //making sure we get rid of previous made laplacian matrix, if such exists //free(*laplacian_rows); //??? - is this needed - do we create this more than once? can we free a memory we haven't allocated or will it fail? //free(*laplacian_cols); for (j = 0; j < number_of_vertices; j++) { k = counting_row_in_matrix(j, temp_single_faces_array) + 1; //additional 1 for the trivial neighbouring of a vertice and itself if (j == 0) { //setting the collumns array right temp_laplacian_cols[0] = 0; temp_laplacian_cols[1] = k; } else temp_laplacian_cols[j+1] = temp_laplacian_cols[j] + k; diff=0; // if we reached Aii in the matrix, there will be a 1 position difference between where to look in the temp_array, and where to place in the values & rows array pos = temp_laplacian_cols[j]; for (i=0; i < k; i++) { //setting the values and rows straight if ((diff == 0 && j < temp_single_faces_array[j][i]) || temp_single_faces_array[j][i-diff] == 0) { temp_laplacian_values[pos+i] = k-1; temp_laplacian_rows[pos+i] = j; diff = 1; } else { temp_laplacian_values[pos+i] = -1; if (temp_single_faces_array[j][i - diff] == -1) //for fixing the 0 / -1 problem from the creation of the temp_array temp_laplacian_rows[pos+i] = 0; else temp_laplacian_rows[pos+i] = temp_single_faces_array[j][i-diff]; } } } /* for (i = 0; i < neighbour_quantity+ number_of_vertices; i++) printf("%d %d \n",temp_laplacian_values[i], temp_laplacian_rows[i]); for (i = 0; i < number_of_faces + 1; i++) printf("%d \n", temp_laplacian_cols[i]);*/ (*matrix).values = temp_laplacian_values; (*matrix).rowind = temp_laplacian_rows; (*matrix).colptr = temp_laplacian_cols; (*matrix).n = number_of_faces;}int counting_matrix(int number_of_faces, int** temp_single_faces_array) { //Counts how many neighbours there are in the matrix int i, j, count; count = 0; for (i=0; i < number_of_faces; i++) { j = 0; while (j < MAX_NUMBER_OF_FACES_FOR_VERTICE && temp_single_faces_array[i][j] != 0) { j++; count++; } } return (count);} int counting_row_in_matrix(int row, int** temp_single_faces_array) { int i = 0; int count = 0; while (i < MAX_NUMBER_OF_FACES_FOR_VERTICE && temp_single_faces_array[row][i] != 0) { i++; count++; } return (count);}