Поиск клик графа по алгоритму Брона-Кербоша на C#

Новая программа с исходниками на языке C#. В этой программе реализуется алгоритм Брона-Кербоша (поиск всех клик неориентированного графа) с возможностью ввода начальных данных из текстового файла.

Текстовый файл вот такого формата:

Первая строка размерность матрицы, остальные - единицы и нули. В готовом проекте идет несколько файлов с примерами

В общем случае Брон-Кербош работает, рассматривая всех соседей произвольного элемента. Для каждого соседа алгоритм рассматривает клику. Если в какой-либо точке нет вершин, которые остаются как возможность, и также нет вершин, исключенных, алгоритм сообщает о максимальной клике.

По сути здесь всего два основных части: метод FindAllCliques() для поиска клик и вложенный класс VertexMatrix. В FindAllCliques() мы создаем несколько списков List: для вершин, образующих клику, для вершин графа, для «отработанных вершин» и список несмежных с вершиной вершин.

Также используются три подметода.

SubtractSet(List<int> set, int vert) - вычитает вершину из множества.
SubtractSet(List<int> set1, List<int> set2) - вычитает второе множество из первого
List<int> G(int vert) – возвращает список вершин, не смежных с vert

Класс VertexMatrix кроме геттеров и сеттеров имеет два поля: размерность матрицы и непосредственно саму матрицу (двумерный массив). А также метод заполнения второго поля чтением из файла:

public int[,] ReadGraphFromFile(string filename)
        {
            List<string> input = File.ReadAllText(filename).Replace("\r\n", "\n").Replace(" \n", "\n").Split('\n').ToList();
            int size = Convert.ToInt32(input[0]);
            input.RemoveAt(0);
            int i = 0, j = 0;

            int[,] result = new int[size, size];
            foreach (var row in input)
            {
                j = 0;
                foreach (var col in row.Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries))
                {
                    result[i, j] = int.Parse(col.Trim());
                    j++;
                }
                i++;
            }
            return (int[,])result.Clone();
        }

После выбора файла и нажатия «Go» в каждой строке текстбокса будет клика

В тексте программы имеются комментарии. Полный код с исходниками вы можете заказать у меня. Цена на данный момент - 500 рублей.

Автор этого материала - я - Пахолков Юрий. Я оказываю услуги по написанию программ на языках Java, C++, C# (а также консультирую по ним) и созданию сайтов. Работаю с сайтами на CMS OpenCart, WordPress, ModX и самописными. Кроме этого, работаю напрямую с JavaScript, PHP, CSS, HTML - то есть могу доработать ваш сайт или помочь с веб-программированием. Пишите сюда.