Triple Matrix Adjacency

Tugas Take Home Kuliah Komputasi Parallel yang dikasi pak Reza bener-bener bikin mumet..
Cari pake browsing google dengan 1001 trik tetap tidak ketemu. Akhirnya berkat kerja bareng temen-temen tugas take home itu terseslesaikan juga..
Tugasnya adalah mencari triple matriks adjacency.

Triple matriks adalah suatu local graf dalam suatu graf atau anak matematika sering nyebutnya subgraf :D. Dimana subgraf ini mengandung tiga buah verteks yang saling berhubungan (dihubungkan oleh suatu edge) sehingga membentuk suatu lintasan tertutup.

/** AdjacencyMatrixTriple.c
  * Adalah program untuk mencari triple Matrix
  * Program ini belum menerapkan konsep paralelisme
  * hanya digunakan sebagai pembanding untuk mengecek kebenaran program 
  * dan running program
  *
  * usage: ./AdjacencyMatrixTriple [Jumlah Verteks]
  * */

#include <stdio.h>
#include <math.h>
#include <time.h>

int triples(int **adjm, int n);
int main(int argc,char **argv)
{
    srand(time(NULL));
    int i,j, k;
    int n = atoi(argv [1]); // Argumen n sebagai jumlah verteks
    int **adjm;
    adjm = malloc (n*sizeof(int*));
    for(k=0; k < n; k++)
    {
		adjm[k]=malloc(n*sizeof(int));
    }

    //Membuat Matrik Adjacency Matrik
    for(i=0; i<n; i++)
    {
		for(j=0; j<n; j++)
		{
			if(i==j)
			{
                adjm[i][j]=0;
			}
			else
			{
				adjm[i][j]=rand()%2; //Membangun Adjacency Matriks dengan 0 atau 1 secara acak
				//adjm[i][j]=1;
			}
			adjm[j][i]=adjm[i][j];
        }
    }

    //Mencetak Adjacency Matriks
    /**
    for(i=0; i<n; i++)
    {
        for(j=0; j<n; j++)
        {
           printf("%d \t", adjm[i][j]);
        }
        printf("\n");
    }
    * */
    	

    int triple = 0;

	double start_time = clock();
    for(i=0;i<n-1;i++)
    {
      for(j=i+1;j<n;j++)
      {
        if(adjm[i][j]==1)
        {
          for(k=j+1;k<n;k++)
          {
			  if(adjm[i][k]==1 && adjm[j][k]==1)
              {
				  triple++;
			  }
          }
        }
      }
    }
    double end_time = clock();
	double result_time = (end_time - start_time) / CLOCKS_PER_SEC;

    printf("\nJumlah Tripel : %d \n", triple);
    printf("Time: %f\n", result_time);
    printf ("\n\n");
}

Advertisement