mca

// M-Coloring Problem using OpenMP
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <omp.h>

#define V N

// Function to check if the current color assignment is safe
bool is_safe(int v, int graph[V][V], int color[], int c) {
    for (int i = 0; i < V; i++) {
        if (graph[v][i] && color[i] == c) {
            return false;
        }
    }
    return true;
}

// Recursive utility function for m-coloring problem (sequential)
bool graph_coloring_util(int graph[V][V], int m, int color[], int v) {
    if (v == V) {
        return true;
    }

    for (int c = 1; c <= m; c++) {
        if (is_safe(v, graph, color, c)) {
            color[v] = c;
            if (graph_coloring_util(graph, m, color, v + 1)) {
                return true;
            }
            color[v] = 0;  // Backtrack
        }
    }
    return false;
}

// Parallel version using OpenMP
bool graph_coloring_parallel(int graph[V][V], int m, int color[]) {
    bool found_solution = false;

    #pragma omp parallel for shared(found_solution)
    for (int c = 1; c <= m; c++) {
        if (found_solution) continue;  // Early termination if solution is found

        int temp_color[V] = {0};
        temp_color[0] = c;

        if (is_safe(0, graph, temp_color, c)) {
            if (graph_coloring_util(graph, m, temp_color, 1)) {
                #pragma omp critical
                {
                    if (!found_solution) {
                        for (int i = 0; i < V; i++) {
                            color[i] = temp_color[i];
                        }
                        found_solution = true;
                    }
                }
            }
        }
    }

    return found_solution;
}

// Function to print the solution
void print_solution(int color[]) {
    printf("Solution Exists: Following are the assigned colors:\n");
    for (int i = 0; i < V; i++) {
        printf("Vertex %d -> Color %d\n", i, color[i]);
    }
}
int main() {
    int graph[V][V] = {
        {0, 1, 1, 1},
        {1, 0, 1, 0},
        {1, 1, 0, 1},
        {1, 0, 1, 0}
    };
    int m = 3;  // Number of colors
    int color[V] = {0};

    double start = omp_get_wtime();
    bool result = graph_coloring_parallel(graph, m, color);
    double end = omp_get_wtime();
    if (result) {
        print_solution(color);
    } else {
        printf("No solution exists.\n");
    }
    printf("Execution Time: %f seconds\n", end - start);
    return 0;
}