Skip to content
Snippets Groups Projects
MST_OpenMPI.c 8.98 KiB
// IF3230 - Sistem Paralel dan Terdistribusi
// Michael Hans / 13518056
// Kevin Austin Stefano / 13518104

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <mpi.h>
#include <stddef.h>

// Edge structure
typedef struct
{
    int src;
    int dest;
    int weight;
} Edge;

// Graph structure
typedef struct 
{
    int V; // number of vertices
    int E; // number of edges
    Edge *edge;
} Graph;


//Struct for OpenMPI
void makeStruct(MPI_Datatype *mpi_edge_type) 
{

    //Inisialisasi
    MPI_Datatype types[3] = {MPI_INT, MPI_INT, MPI_INT};
    MPI_Aint offset[3];
    int block[3] = {1,1,1};

    //Fill with our datatype
    offset[0] =  offsetof(Edge, src);
    offset[1] =  offsetof(Edge, dest);
    offset[2] =  offsetof(Edge, weight);

    //Connect
    MPI_Type_create_struct(3, block, offset, types, &(*mpi_edge_type));
    MPI_Type_commit(&(*mpi_edge_type));
}

// Create new Graph based on V vertices and E edges
Graph *CreateGraph(int V, int E)
{
    Graph *graph = (Graph *)(malloc(sizeof(Graph)));
    graph->V = V;
    graph->E = E;
    graph->edge = (Edge *)(malloc(E * sizeof(Edge)));
    return graph;
}

// Print all graph component to the CLI
void PrintGraph(Graph *graph)
{
    printf("Vertices : %d\n", graph->V);
    printf("Edges : %d\n", graph->E);
    for (int i = 0; i < graph->E; i++)
    {
        printf("%d -- %d = %d\n", graph->edge[i].src, graph->edge[i].dest, graph->edge[i].weight);
    }
}

// Implement the value of 2^x
int pow2(int x){
    return 1 << x; 
}

// Menuliskan array ke layar
void PrintArray(Edge arr[], int a, int b)
{
    for (int i = a; i <= b; i++)
    {
        printf("%d ", arr[i-1].weight);
    }
    printf("%d\n", arr[b-1].weight);
}

// Melakukan partisi sembari menukar value dengan pivot ke-i
void Partisi(Edge T[], int i, int j, int *k)
{
    Edge pivot = T[i - 1];
    int p = i;
    int q = j;
    while (p <= q)
    {
        while (T[p - 1].weight < pivot.weight)
        {
            p++;
        }
        while (T[q - 1].weight > pivot.weight)
        {
            q--;
        }
        if (p < q)
        {
            Edge temp = T[p - 1];
            T[p - 1] = T[q - 1];
            T[q - 1] = temp;
            p++;
            q--;
        }
        else if (p == q)
        {
            p++;
        }
    }
    *k = q;
}

// Mengurutkan array dengan menggunakan Quick Sort versi Sequential
void SequentialQuickSort(Edge T[], int i, int j)
{
    int k;
    if (i < j)
    {
        Partisi(T, i, j, &k);
        SequentialQuickSort(T, i, k);
        SequentialQuickSort(T, k + 1, j);
    }
}

// Mengurutkan array dengan metode Quick Sort Parallel
void QuickSort(Edge T[], int i, int j, int rank, int max_rank, int rank_index){
    MPI_Datatype mpi_edge_type;
    makeStruct(&mpi_edge_type);
        
    int distributed_process = rank + pow2(rank_index);
    rank_index++;

    // If the rank of distributed process is higher than max rank
    if (distributed_process >= max_rank) {
        SequentialQuickSort(T, i, j);
    }
    else {
        int pivot;
        Partisi(T, i, j, &pivot);

        // Upper half of array is larger than lower half of array
        if (pivot-i+1 > j-pivot){
            MPI_Send(&T[pivot], j - pivot, mpi_edge_type, distributed_process, 1, MPI_COMM_WORLD);
			QuickSort(T, i, pivot, rank, max_rank, rank_index + 1);
			MPI_Recv(&T[pivot], j - pivot, mpi_edge_type, distributed_process, 1, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
		} else {
			MPI_Send(&T[i-1], pivot - i + 1, mpi_edge_type, distributed_process, 1, MPI_COMM_WORLD);
			QuickSort(T, pivot + 1, j, rank, max_rank, rank_index + 1);
			MPI_Recv(&T[i-1], pivot - i + 1, mpi_edge_type, distributed_process, 1, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
        }
    }
}

/// Create graph based from the adjacency matrix in file
Graph *ReadArguments()
{
    Graph *graph = (Graph *)(malloc(sizeof(Graph)));

    int V, weight;
    scanf("%d", &V);
    graph->V = V;
    graph->edge = (Edge *)(malloc(((V * V - V) / 2) * sizeof(Edge)));

    // Read the adjacency matrix
    int E = 0;
    for (int i = 0; i < V; i++)
    {
        for (int j = 0; j < V; j++)
        {
            scanf("%d", &weight);
            // int r = (rand() % (2 * V)) + 1;
            // int weight = (r < 0.3 * V) ? -1: r;
            if ((weight != -1) && (i <= j))
            {
                graph->edge[E].src = i;
                graph->edge[E].dest = j;
                graph->edge[E].weight = weight;
                E += 1;
            }
        }
    }
    graph->E = E;
    return graph;
}

// Structure to represent a subset for union-find
typedef struct
{
    int parent;
    int rank;
} Subset;

// Create new subset
Subset *CreateSubset(int V)
{
    Subset *subsets = (Subset *)(malloc(V * sizeof(Subset)));

// Create V subsets with single elements
    for (int i = 0; i < V; i++)
    {
        subsets[i].parent = i;
        subsets[i].rank = 0;
    }
    return subsets;
}

int find(Subset subsets[], int i)
{
    // find root and make root as parent of i
    // (path compression)
    if (subsets[i].parent != i)
        subsets[i].parent = find(subsets, subsets[i].parent);
    return subsets[i].parent;
}

void Union(Subset subsets[], int x, int y)
{
    int xroot = find(subsets, x);
    int yroot = find(subsets, y);

    // Attach smaller rank tree under root of high
    // rank tree (Union by Rank)
    if (subsets[xroot].rank < subsets[yroot].rank)
        subsets[xroot].parent = yroot;
    else if (subsets[xroot].rank > subsets[yroot].rank)
        subsets[yroot].parent = xroot;

    // If ranks are same, then make one as root and
    // increment its rank by one
    else
    {
        subsets[yroot].parent = xroot;
        subsets[xroot].rank++;
    }
}

// Compare two edges according to their weights.
int compare(const void *a, const void *b)
{
    Edge *a1 = (Edge *)a;
    Edge *b1 = (Edge *)b;
    return a1->weight > b1->weight;
}

// Compare two sources according to their number
int compare_src(const void *a, const void *b)
{
    Edge *a1 = (Edge *)a;
    Edge *b1 = (Edge *)b;
    return a1->src > b1->src;
}


// Minimum Spanning Tree using Kruskal's Algorithm
void KruskalMST(Graph *graph, Edge result[], int *e, int size, int rank)
{
    int V = graph->V;
    int i = 0;

    // Step 1: Sort all the edges into correspendent sorted edges
    QuickSort(graph->edge, 0, graph->E, rank, size, 0);
    // PrintArray(graph->edge, 1, graph->E);

    // Step 2: Allocate memory for creating V subsets
    Subset *subsets = CreateSubset(V);

    while (((*e) < V - 1) && (i < graph->E))
    {
        // Pick the smallest edge of the graph
        Edge next_edge = graph->edge[i++];
        int x = find(subsets, next_edge.src);
        int y = find(subsets, next_edge.dest);
        if (x != y)
        {
            result[(*e)++] = next_edge;
            Union(subsets, x, y);
        }
    }

    // QuickSortSrc(graph->edge, 0, graph->E, size, rank);
    // QuickSortSrc(result, 1, (*e));
    qsort(result, *e, sizeof(result[0]), compare_src);
    return;
}

void printResult(Edge *result, int e)
{ 
    // Get the number of processes
    int minimumCost = 0;
    for (int i = 0; i < e; i++)
    {
        minimumCost += result[i].weight;
    }
    printf("%d\n", minimumCost);

    for (int i = 0; i < e; i++)
    {
        printf("%d-%d\n", result[i].src, result[i].dest);
    }
}

// Driver program to test above functions
int main()
{

    MPI_Init(NULL, NULL);
    // Get the number of processes
    int size;
    MPI_Comm_size(MPI_COMM_WORLD, &size);

    // Get the rank of the process
    int rank;
    MPI_Comm_rank(MPI_COMM_WORLD, &rank);

    // For the process with rank 0
    if (rank == 0){
        Graph *graph= ReadArguments();
        Edge result[graph->E];
        int e = 0;
        double t = MPI_Wtime();
        KruskalMST(graph, result, &e, size, rank);
        t = MPI_Wtime() - t;
        printResult(result, e);
        // printf("Waktu Eksekusi: %f ms \n", (t * 1000));
        // MPI_Abort(MPI_COMM_WORLD, EXIT_FAILURE);
 
    } else {
        MPI_Datatype mpi_edge_type;
        makeStruct(&mpi_edge_type);
        
        int idxcnt = 0;
        int arrLength;
        MPI_Status status;

        // Calculate rank
        while (rank >= pow2(idxcnt)) {
            idxcnt = idxcnt+1;
        }

        // Get source of the sender
        int source = MPI_Probe(MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &status);
        source = MPI_Get_count(&status, mpi_edge_type, &arrLength);
        int src = status.MPI_SOURCE;

        // Declare the array buffer to receive data from the source process
        Edge* temp = (Edge *) malloc (sizeof(Edge) *arrLength);
        source = MPI_Recv(temp, arrLength, mpi_edge_type, src, 1, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
        
        // Sort the received buffer with QuickSort
        QuickSort(temp, 1, arrLength, rank, size, idxcnt);

        // Send the sorted array back to the source process
        source = MPI_Send(temp, arrLength, mpi_edge_type, src, 1, MPI_COMM_WORLD);
        // printf("Process %d\n", rank);
        free(temp);
    }
    MPI_Finalize();
    
    return 0;
}