using System;
using System.Collections.Generic;
using System.IO;

namespace Cliques
{
    internal class Program
    {
        private static void Main(string[] args)
        {
            using (StreamReader infile = File.OpenText(args[0]))
            using (StreamWriter outfile = File.CreateText(args[1]))
            {
                //Read Graph (note we work with the complement of the input graph) 
                Console.WriteLine("Clique Algorithm.");
                int n, i, j, k, K, p, q, r, s, min, edge, counter = 0;
                n = infile.ReadInt();
                var graph = new List<List<int>>();
                for (i = 0; i < n; i++)
                {
                    var row = new List<int>();
                    for (j = 0; j < n; j++)
                    {
                        edge = infile.ReadInt();
                        if (edge == 0) row.Add(1);
                        else row.Add(0);
                    }
                    graph.Add(row);
                }
                //Find Neighbors 
                var neighbors = new List<List<int>>();
                for (i = 0; i < graph.Count; i++)
                {
                    var neighbor = new List<int>();
                    for (j = 0; j < graph.Count; j++)
                        if (graph[j] == 1) neighbor.Add(j);
                    neighbors.Add(neighbor);
                }
                Console.WriteLine("Graph has n = {0} vertices.", n);
                //Read maximum size of Clique wanted 
                Console.Write("Find a Clique of size at least k = ");
                K = Console.In.ReadInt();
                k = n - K;
                //Find Cliques 
                bool found = false;
                Console.WriteLine("Finding Cliques...");
                min = n + 1;
                var covers = new List<List<int>>();
                var allcover = new List<int>();
                for (i = 0; i < graph.Count; i++)
                    allcover.Add(1);
                for (i = 0; i < allcover.Count; i++)
                {
                    if (found) break;
                    counter++;
                    Console.Write("{0} . ", counter);
                    outfile.Write("{0}. ", counter);
                    List<int> cover = allcover;
                    cover = 0;
                    cover = procedure_1(neighbors, cover);
                    s = cover_size(cover);
                    if (s < min) min = s;
                    if (s <= k)
                    {
                        WriteClique(outfile,cover, n, s);
                        covers.Add(cover);
                        found = true;
                        break;
                    }
                    for (j = 0; j < n - k; j++)
                        cover = procedure_2(neighbors, cover, j);
                    s = cover_size(cover);
                    if (s < min) min = s;
                    WriteClique(outfile,cover, n, s);
                    covers.Add(cover);
                    if (s <= k)
                    {
                        found = true;
                        break;
                    }
                }
                //Pairwise Intersections 
                for (p = 0; p < covers.Count; p++)
                {
                    if (found) break;
                    for (q = p + 1; q < covers.Count; q++)
                    {
                        if (found) break;
                        counter++;
                        Console.Write("{0} . ", counter);
                        outfile.Write("{0}. ", counter);
                        List<int> cover = allcover;
                        for (r = 0; r < cover.Count; r++)
                            if (covers[p][r] == 0 && covers[q][r] == 0) cover[r] = 0;
                        cover = procedure_1(neighbors, cover);
                        s = cover_size(cover);
                        if (s < min) min = s;
                        if (s <= k)
                        {
                            WriteClique(outfile,cover, n, s);
                            found = true;
                            break;
                        }
                        for (j = 0; j < k; j++)
                            cover = procedure_2(neighbors, cover, j);
                        s = cover_size(cover);
                        if (s < min) min = s;
                        WriteClique(outfile,cover, n, s);
                        if (s <= k)
                        {
                            found = true;
                            break;
                        }
                    }
                }
                infile.Close();
                outfile.Close();
                if (found) Console.WriteLine("Found Clique of size at least {0}.", K);
                else
                    Console.Write("Could not find Clique of size at least {0}. Maximum Clique size found is {1}.", K,
                                  n - min);
            }
            Console.WriteLine("See cliques.txt for results.");
            Console.ReadKey();
        }

        private static bool removable(List<int> neighbor, List<int> cover)
        {
            bool check = true;
            for (int i = 0; i < neighbor.Count; i++)
                if (cover[neighbor] == 0)
                {
                    check = false;
                    break;
                }
            return check;
        }

        private static int max_removable(List<List<int>> neighbors, List<int> cover)
        {
            int r = -1, max = -1;
            for (int i = 0; i < cover.Count; i++)
            {
                if (cover == 1 && removable(neighbors, cover))
                {
                    List<int> temp_cover = cover;
                    temp_cover = 0;
                    int sum = 0;
                    for (int j = 0; j < temp_cover.Count; j++)
                        if (temp_cover[j] == 1 && removable(neighbors[j], temp_cover))
                            sum++;
                    if (sum > max)
                    {
                        max = sum;
                        r = i;
                    }
                }
            }
            return r;
        }

        private static List<int> procedure_1(List<List<int>> neighbors, List<int> cover)
        {
            List<int> temp_cover = cover;
            int r = 0;
            while (r != -1)
            {
                r = max_removable(neighbors, temp_cover);
                if (r != -1) temp_cover[r] = 0;
            }
            return temp_cover;
        }

        private static List<int> procedure_2(List<List<int>> neighbors, List<int> cover, int k)
        {
            int count = 0;
            List<int> temp_cover = cover;
            //int i = 0;
            for (int i = 0; i < temp_cover.Count; i++)
            {
                if (temp_cover == 1)
                {
                    int sum = 0, index = 0;
                    for (int j = 0; j < neighbors.Count; j++)
                        if (temp_cover[neighbors[j]] == 0)
                        {
                            index = j;
                            sum++;
                        }
                    if (sum == 1 && cover[neighbors[index]] == 0)
                    {
                        temp_cover[neighbors[index]] = 1;
                        temp_cover = 0;
                        temp_cover = procedure_1(neighbors, temp_cover);
                        count++;
                    }
                    if (count > k) break;
                }
            }
            return temp_cover;
        }

        private static int cover_size(List<int> cover)
        {
            int count = 0;
            for (int i = 0; i < cover.Count; i++)
                if (cover == 1) count++;
            return count;
        }

        private static void WriteClique(StreamWriter outfile,List<int> cover,int n, int s)
        {
            outfile.Write("Clique ({0}): ", n - s);
            for (int j = 0; j < cover.Count; j++) if (cover[j] == 0) 
                outfile.Write("{0} ", j + 1);
            outfile.WriteLine();
            Console.WriteLine("Clique Size: {0}", n - s);
        }
    }

    public static class Extensions
    {
        public static int ReadInt(this TextReader reader)
        {
            var c = (char) reader.Read();
            while (Char.IsWhiteSpace(c))
                c = (char) reader.Read();
            return c - 48;
        }
    }
}