asymmetrical.c

asymmetrical.c

/*
Algoritmul pentru verificarea grafului asimetric


Conceptul de baza:


Un graf orientat este asimetric daca nu exista perechi simetrice de muchii. Adica, daca
exista o muchie de la nodul A la nodul B , nu trebuie sa existe o muchie de la nodul B la nodul A

Pasii Algoritmului:

1. Validarea initiala.

Se verifica daca matricea de adiacenta este valida (contine doar 0 si 1, nu este null)

2. Parcurgerea sistematica - se parcurg toate perechile de noduri (i,j) din matrice

- daca graph[i][j] = 1 (exista muchie de la i la j)
- si graph[j][i] = 1 (exista muchie de la j la i)

- atunci s-a gasit o pereche simetrica - GRAFUL nu este ASIMETRIC

4. Daca nu s-a gasit nicio pereche simetrica , graful este asimetric

Complexitatea algoritmului O(n^2) unde n este numarul de noduri , deoarece trebuie sa parcurgem toata matricea.

*/

#include <stdio.h>
#include <malloc.h>
#include <stdbool.h>

bool isValidAdjacencyMatrix(int **graph,int n);
 /*
  * Checks if an oriented graph represented as an adjacency matrix, is asymmetrical.
  *
  *
  * @param n - size of the square matrix (number of the vertices)
  * @param graph: 2D array representing the adjacency matrix of the oriented graph
  *          graph[i][j] = 1 means there's an edge from vertex i to vertex j
  *           graph[i][j] = 1 means there's an edge from vertex j to vertex i
  */

bool isAsymmetricalGraph(int **graph, int n){

  if(!isValidAdjacencyMatrix(graph, n)) {
      return false;
  }
  //check for symmetric pairs of edges
  for(int i = 0; i < n; ++i) {
     for(int j = 0; j < n; ++j) {
         if(graph[i][j] == 1 && graph[j][i] == 1) {
           return false; //found a symmetric pairs, not asymmetrical
         }
     }
  }

  return true;

}

/*
 *
 *  Helper function to validate if the input represents a valid adjacency matrix
 *
 *  checks if the matrix contains only 0s and 1s
 *
 *
 *  @param graph
 *  @param n
 *  @return: true if valid adj matrix, false otherwise
 */
bool isValidAdjacencyMatrix(int **graph, int n) {

    if(n <= 0 || graph == NULL) {
      return false;
    }

    for(int i = 0; i < n; ++i) {
        if(graph[i] == NULL) {
          return false;//row is null
        }

        for(int j = 0; j < n; ++j) {
            if(graph[i][j] != 0 && graph[i][j] != 1) return false; //invalud values (not 0 or 1)
        }
    }

    return true;
}

/*
 * Helper function to allocate memory for a 2D matrix
 * @param n: size of the square matrix
 * @return: pointer to allocated 2D array
 */

int**allocateMatrix(int n) {

     int ** matrix = (int**)malloc(n * sizeof(int*));

     if(matrix == NULL) {
        return NULL;
     }

     for(int i = 0; i < n; ++i) {

          matrix[i] = (int*)malloc(n * sizeof(int));

          if(matrix[i] == NULL) {
                   for(int j = 0; j < i; ++j){
                         free(matrix[j]);
                   }

                   free(matrix);
                   return NULL;

          }
     }


     return matrix;
}

/*
 */

void initializeMatrix(int **matrix, int*values, int n) {
  for(int i = 0; i < n; ++i) {
    for(int j = 0; j < n; ++j) {
        matrix[i][j] = values[i * n + j];
    }
  }
}

/*
 */

void printMatrix(int **matrix, int n) {
     for(int i = 0; i < n; ++i) {
       for(int j = 0; j < n; ++j) {
         printf("%d ", matrix[i][j]);
       }
       printf("\n");
     }
}

/*
 */

void freeMatrix(int **matrix, int n) {

    if(matrix != NULL) {
        for(int i = 0; i < n; ++i) {
          if(matrix[i] != NULL) {
            free(matrix[i]);
          }
        }
        free(matrix);
    }
}

int main(int argc, char const *argv[]) {


  //test case 1: asymmetrical graph
  int values1[] = {

       0, 1, 0,
       0, 0, 1,
       1, 0, 0
  };

  //test case 2: non asymmetrical graph
  int values2[] = {

       0, 1, 0,
       1, 0, 1,
       0, 1, 0
  };


  //test case 3: non asymmetrical graph
  int values3[] = {

       1, 1, 0,
       0, 0, 1,
       1, 0, 1
  };

  int n = 3; //size of the matrices

  //alocam memorie pentre matricile test
  int **graph1 = allocateMatrix( n );
  int **graph2 = allocateMatrix( n );
  int **graph3 = allocateMatrix( n );

  if(graph1 == NULL || graph2 == NULL || graph3 == NULL) {
    printf("Memory allocation failed!\n");
    return 1;
  }

  initializeMatrix(graph1, values1, n);
  initializeMatrix(graph2, values2, n);
  initializeMatrix(graph3, values3, n);


  //test functions
  printf("Test Case 1 (Expected: asymmetrical): ");
  printf("%s\n", isAsymmetricalGraph(graph1, n) ? "Asymmetrical" : "Not Asymmetrical");


  printf("Test Case 2 (Expected: asymmetrical): ");
  printf("%s\n", isAsymmetricalGraph(graph2, n) ? "Asymmetrical" : "Not Asymmetrical");


  printf("Test Case 3 (Expected: asymmetrical): ");
  printf("%s\n", isAsymmetricalGraph(graph3, n) ? "Asymmetrical" : "Not Asymmetrical");


  //print matrices for verification

  printf("\nMatrix 1:\n");
  printMatrix(graph1, n);


  printf("\nMatrix 2:\n");
  printMatrix(graph2, n);


  printf("\nMatrix 3:\n");
  printMatrix(graph3, n);

  freeMatrix(graph1, n);
  freeMatrix(graph2, n);
  freeMatrix(graph3, n);

  return 0;
}