using System;
using MPI;


//mpiexec -n 4 ProjectDistributed.exe

class GraphColoringProblem
{
    const int V = 4;

    static bool IsSafe(int v, bool[,] graph, int[] color, int c)
    {
        for (int i = 0; i < V; i++)
        {
            if (graph[v, i] && c == color[i])
                return false;
        }
        return true;
    }

    static bool GraphColoringUtil(bool[,] graph, int m, int[] color, int v)
    {
        if (v == V)
            return true;

        for (int c = 1; c <= m; c++)
        {
            if (IsSafe(v, graph, color, c))
            {
                color[v] = c;

                if (GraphColoringUtil(graph, m, color, v + 1))
                    return true;

                color[v] = 0;
            }
        }
        return false;
    }

    static bool SolveGraphColoring(bool[,] graph, int m, int rank, int size, out int[] colors)
    {
        int[] color = new int[V];
        Array.Fill(color, 0);

        bool foundSolution = false;
        for (int c = rank + 1; c <= m; c += size)
        {
            color[0] = c; // Assign a color to the first vertex based on process rank

            if (GraphColoringUtil(graph, m, color, 1))
            {
                foundSolution = true;
                break;
            }
        }
        colors = color;
        return foundSolution;
    }

    static void PrintSolution(int[] color)
    {
        Console.WriteLine("Solution Exists: Following are the assigned colors");
        for (int i = 0; i < V; i++)
            Console.Write($" {color[i]} ");
        Console.WriteLine();
    }

    static void Main(string[] args)
    {
        using (new MPI.Environment(ref args))
        {
            Intracommunicator comm = Communicator.world;
            int rank = comm.Rank;
            int size = comm.Size;

            bool[,] graph = {
                { false, true, true, true },
                { true, false, true, false },
                { true, true, false, true },
                { true, false, true, false }
            };

            int m = 3; // Number of colors

            

            bool localSolution = SolveGraphColoring(graph, m, rank, size, out int[] colors);
            (bool foundSolution, int[] solution) = comm.Allreduce(
                (localSolution, colors),
                (sol1, sol2) => sol1.Item1 ? sol1 : sol2
            );

            //bool globalSolution = comm.Reduce(localSolution, Operation<bool>.LogicalOr, 0);
            if (rank == 0)
            {
                if (!foundSolution)
                {
                    Console.WriteLine("No solution exists.");
                }
                else
                {
                    Console.WriteLine("A solution has been found by one of the processes.");

                    PrintSolution(solution);
                }
            }
        }
    }
}