Adjacency Matrix

Satu minggu yang lalu...

"Kak, dirimu tau tentang adjacency matrix gak?" Ku kirimkan pesan singkat ke salah satu kawan S2 ku yang kebetulan menempuh S1 pendidikan Matematika.

"gak tau na dek..." balasnya

Pasrah, aku hanya memandangi soal ujian programming yang harus ku kerjakan seminggu itu (yang kebetulan, aku malah harus pergi dinas ke luar kota).

Dan hari ini, adalah waktunya ngebut ngerjain tugas ini dan ku dapatkan juga penjelasan tentang adjacency matrix.

Dalam Matematika dan Computer Science, sebuah adjacency matrix adalah sarana untuk merepresentasikan node-node dari suatu graph yang berdekatan dengan node yang lainnya.

Adjacency matrix adalah matriks yang hanya terdiri dari 1 dan 0. Dimana 1 menandakan jika node i menuju node j memiliki edge, dan 0 jika tidak memiliki edge.

contoh Adjacency matrix beserta graph-nya

So, what did you have to do with that adjacency matrix, Dy?

Guys, aku harus membuat program yang pemrosesannya paralel, untuk mencari himpunan 3 node/vertex yang masing-masing node terhubung dengan 2 node yang lainnya.

Bingung?

Percayalah, aku juga bingung kawans. 

Tapi, setelah bertapa 2 jam, akhirnya selesai juga sintaks programnya dengan menggunakan bahasa C (sangat sederhana, dan belum optimal pengerjaannya, harap maklum ya, hehe), dan program ini belum aku paralel-kan dengan openMP (aku masih perlu bertapa lebih lama lagi untuk itu, hiks).

#include <stdio.h>
#include <stdlib.h>

int main() {
    int numVertex;
    int **adjMatrix;
    int i, j;
    int trip;

    scanf("%d", &numVertex);
    printf("Jumlah vertex adalah %d\n", numVertex);
    adjMatrix = malloc(sizeof (int*) * numVertex);
    for (i = 0; i < numVertex; i++) {
        adjMatrix[i] = malloc(sizeof (int*) * numVertex);
    }

    for (i = 0; i < numVertex; i++) {
        for (j = 0; j < numVertex; j++) {
            printf("edge untuk vertex %d ke vertex %d : ", i, j);
            scanf("%d", &adjMatrix[i][j]);
        }
    }

    printf("Matrix adjacency-nya adalah: \n");
    for (i = 0; i < numVertex; i++) {
        for (j = 0; j < numVertex; j++) {
            printf("%d ", adjMatrix[i][j]);
        }
        printf("\n");
    }

    trip = triples(adjMatrix, numVertex);
    printf("himpunan triple ada: %d\n", trip);
}

int triples(int **adj, int n) {
    int i, j, k;
    int hasil = 0;
    for (i = 0; i < n; i++) {
        for (j = i+1; j < n; j++) {
            if (adj[i][j] == 1) {
                for (k = j+1; k < n; k++) {
                    if (adj[i][k] == 1 && adj[j][k] == 1) {
                        if (adj[i][j] == adj[j][i]
                                && adj[i][k] == adj[k][i]
                                && adj[j][k] == adj[k][j]) {
                            hasil++;
                        }
                    }
                }
            }
        }
    }
    return hasil;
}

Hasilnya akan seperti ini:

http://en.wikipedia.org/wiki/Adjacency_matrix
http://datastructures.itgo.com/graphs/adjmat.htm
http://usmanqayyum.blogspot.com/2012/04/adjacencyincidence-matrix.html
http://stackoverflow.com/questions/8182600/how-to-make-adjacency-matrix-like-this-input
http://stackoverflow.com/questions/6169164/static-allocated-adjacency-matrix-graph-in-c