module dmain;

import std.stdio;
import std.file;
import std.string;
import std.typecons;

/*
 * This program computes graph coloring and chromatic number,
 * taking adjacency matrix as input
 */

int[][] readAdjacencyMatrix(string text)
{
    int[][] res;
    foreach(line; text.splitLines)
    {
        int[] row;
        foreach(c; line)
        {
            if (c == '1')
                row ~= 1;
            else if (c == '0')
                row ~= 0;
        }
        res ~= row;
    }
    return res;
}

bool isValidAdjacencyMatrix(int[][] matrix)
{
    size_t n = matrix.length;
    foreach(row; matrix)
        if (row.length != n)
            return false;
    return true;
}

void binaryAddRows(int[][] matrix, size_t a, size_t b, size_t dest)
{
    for (size_t i = 0; i < matrix.length; i++)
    {
        matrix[dest][i] = matrix[a][i] || matrix[b][i];
    }
}

Tuple!(int, int[]) coloring(int[][] matrix)
{
    int colors = 0;
    int[] p = new int[matrix.length];

    for (size_t i = 0; i < matrix.length; i++)
    {
        if (p[i] == 0)
        {
            for (size_t j = 0; j < matrix.length; j++)
            {
                if (matrix[i][j] == 0)
                {
                    if (p[j] == 0)
                    {
                        binaryAddRows(matrix, i, j, i);
                        p[j] = colors+1;
                    }
                }
            }

            p[i] = colors+1;
            colors++;
        }
    }

    return tuple(colors, p);
}

void main(string[] args)
{
    assert(args.length > 1, "No input file provided");

    int[][] matrix = readAdjacencyMatrix(readText(args[1]));
    assert(isValidAdjacencyMatrix(matrix), "Invalid input, matrix is not square");

    writeln("Adjacency matrix:");
    foreach(row; matrix)
        writeln(row);
    writeln();

    auto c = coloring(matrix);
    writefln("Chromatic number = %s", c[0]);
    writefln("Colors = %s", c[1]);
}