Новая реализация с поиском всех уникальных циклов

#include <filesystem>
#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <map>
#include <set>


using namespace std;

struct Vertex {
    std::string name;
    std::vector<Vertex*> adjacentVertices;

    Vertex(const std::string& vertexName) : name(vertexName) {}
 };

class InvalidGraphAssignment : public std::exception {
public:
    InvalidGraphAssignment(const std::string& message) : m_message(message) {}

    const char* what() const noexcept override {
        return m_message.c_str();
    }
private:
    std::string m_message;
};

class InvalidInputFile : public std::exception {
public:
    InvalidInputFile(const std::string& message) : m_message(message) {}

    const char* what() const noexcept override {
        return m_message.c_str();
    }
private:
    std::string m_message;
};

/*! Получить правильное имя цикла. Правильное имя состоит из строки, полученной при
    конкатенации имен каждой вершины, и сортировки полученной строки в алфавитном порядке.
* \param[in] cycle - цикл, для которого необходимо получить правильное имя.
* \return правильное имя цикла.
*/
std::string getCorrectCycleName(const std::vector<Vertex*> cycle) {
    // Конкатенируем названия вершин в одну строку
    std::string cycleName = ""; // Определяем строку для создания правильного имени цикла
    // Для каждой вершины цикла
    for (const Vertex* v : cycle) {
        // добавить имя рассматриваемой вершины в строку для создания правильного имени цикла
        cycleName += v->name;
    }
    // Получаем правильное имя цикла, отсортировав строку
    std::sort(cycleName.begin(), cycleName.end());
    // Возвращаем правильное имя цикла
    return cycleName;
}

/*! Определение наличия цикла для указанной вершины, используя алгоритм поиска в глубину.
* \param[in] viewedVertex - рассматриваемая вершина.
* \param[in, out] recStack - массив для промежуточного хранения цикла.
* \param[in, out] visited - массив для хранения просмотренных вершин.
* \param[in] cycles - массив с найденными циклами.
* \return 0 - если цикл не найден. 1 - если цикл найден.
*/
bool dfs(Vertex* viewedVertex, std::vector<Vertex*>& recStack, std::set<Vertex*>& visited, const std::map<std::string, vector<Vertex*>>& cycles) {
    // Добавляем просматриваемую вершину в список посещенных
    visited.insert(viewedVertex);
    // Добавляем текущую вершину в массив с формируемым циклом
    recStack.push_back(viewedVertex);

    // Для каждлой смежной вершины у просматриваемой вершины
    for (Vertex* v : viewedVertex->adjacentVertices) {
        // Если смежную вершину еще не посещали
        if (!visited.contains(v)) {
            // Запускаем алгоритм поиска в глубину для смежной вершины
            if (dfs(v, recStack, visited, cycles)) {
                // Если нашли цикл, то возвращаем истину
                return true;
            }
        }
        // Если смежную вершину уже посещали и  вершина является
        // первой в списке с формируемом циклом, значит, мы нашли цикл
        else if (v == recStack[0]) {
            // Если ранее цикл с таким же правильным именем не находили
            if (!cycles.contains(getCorrectCycleName(recStack)))
                // Считаем, что нашли новый цикл и возвращаем истину
                return true;
        }
    }
    // Если цикла не нашли, то удаляем вершину из массива с формируемым циклом
    recStack.pop_back();
    // Возвращаем ложь, т.к. цикл не нашли
    return false;
}

/*! Поиск любого цикла в графе.
* \param[in] vertexName - название искомой вершины.
* \param[in] graph - массив с вершинами (граф), в котором идет поиск.
* \param[out] cycles - массив с найденными циклами.
* \return 0 - если цикл не найден. 1 - если цикл найден.
*/
bool findCycles(const std::vector<Vertex*>& graph, std::map<std::string, vector<Vertex*>>& cycles) {
    // Определям массив, для хранения возможного цикла и массив посещенных вершин
    std::vector<Vertex*> recStack;
    std::set<Vertex*> visited;

    bool isAnyCycleFound = false;

    // Для каждой вершины графа
    for (Vertex* v : graph) {
        // Если нашли цикл у текущей рассматриваемой вершины
        if (dfs(v, recStack, visited, cycles)) {
            // Добавляем цикл в массив найденных циклов
            std::string cycleName = getCorrectCycleName(recStack);

            recStack.push_back(v);
            cycles[cycleName] = recStack;

            // Помечаем, что был найден цикл
            isAnyCycleFound = true;
            // Очищаем массив для хранения возможного цикла
            recStack.clear();
        }
        // Если цикл не нашли, то очищаем массив песещенных вершин
        visited.clear();
    }
    // Возвращаем результат поиска цикла в графе
    return isAnyCycleFound;
}

/*! Прочитывает входные данные из CSV файла, на их основе
    создает вершины Vertex и сохраняет их в массив graph.
* \param[in] vertexName - название искомой вершины.
* \param[out] graph - массив с вершинами (граф), в котором идет поиск.
*/
Vertex* findVertexInGraph(const std::string vertexName, const vector<Vertex*>& graph) {
    // Для всех вершин графа
    for (Vertex* v : graph) {
        // Если имя вершины равно искомому имени, вернуть эту вершину
        if (v->name == vertexName) return v;
    }
    // Если не нашли вершину с искомым именем, вернуть пустой указатель
    return nullptr;
}

/*! Прочитывает входные данные из CSV файла, на их основе
    создает вершины Vertex и сохраняет их в массив graph.
* \param[in] input_file_path - строка с путем к файлу с входными данными.
* \param[out] graph - массив с вершинами.
* \param[out] delimiter - разделитель элементов в строке, использующийся в CSV файле.
*/
void readCSVFile(const std::string& input_file_path, std::vector<Vertex*>&  graph, const char delimiter=';') {
    // Открываем файл
    std::ifstream input_file(input_file_path); // Закрывать не надо, т.к. после завершения функции закроется автоматом

    // Объявляем перменные для строки файла и строки для считанной клетки
    std::string line, buff;

    // Считываем заголовок таблицы
    std::getline(input_file, line);

    // Открываем поток для строки, чтобы разделить ее по разделителям
    std::stringstream ss(line);

    std::getline(ss, buff, delimiter); // Первую клетку читаем в пустоту

    std::vector<Vertex*> headers_vertexes; // массив для вершин из заголовка

    // Читаем заголовок с названиями вершин
    while (std::getline(ss, buff, delimiter)) {
        // Проверяем на дублирование названий вершин
        if (findVertexInGraph(buff, headers_vertexes) != nullptr)
            throw InvalidGraphAssignment("Неверные входные данные. Повторение вершины " + buff);
        // Добавляем вершину в массив вершин
        headers_vertexes.push_back(new Vertex(buff));
    }
    // Ошибка чтения фала, если граф полностью пустой
    if (headers_vertexes.size() == 0)
        throw InvalidInputFile("Неверные входные данные. Граф не содержит вершин.");

    // Читаем остальной файл
    // Считаем, что количество линий в файле (не считая заголов) - это количество вершин
    int vertexes_count = 0;

    // Определяем массив для хранения вершин, указанных в первом столбце
    std::map<std::string, Vertex*> body_vertexes;

    // Пока не встретили пустую строку
    while (std::getline(input_file, line)) {
        // Инкрементируем счетчик вершин, т.к. считаем, что каждая строка - описание вершин
        vertexes_count++;

        // Если строк больше, чем столбоц в заголовке, то ошибка размерности
        if (vertexes_count > headers_vertexes.size())
            throw InvalidGraphAssignment("Неверные входные данные. Ошибка размерности матрицы");

        // Открываем поток для строки, чтобы разделить ее по разделителям
        std::stringstream ss(line);
        std::getline(ss, buff, delimiter); // Первая клетка содержит название вершины

        // Проверяем, что вершина была указана в множестве вершин из заголовка
        if (findVertexInGraph(buff, headers_vertexes) == nullptr)
            throw InvalidGraphAssignment("Неверные входные данные. Содержится лишняя вершина " + buff);

        // Проверяем, что название вершины не повторяется
        if (body_vertexes.contains(buff))
            throw InvalidGraphAssignment("Неверные входные данные. Повторение вершины " + buff);

        // Получаем объект вершины их массива вершин из заголовка, т.е. уже созаднную
        Vertex* vertex = body_vertexes[buff] = findVertexInGraph(buff, headers_vertexes);

        // Создаем связи для вершины в строке
        int count_cells = 0;
        // Пока имеются клетки в строке матрицы
        while (std::getline(ss, buff, delimiter)) {
            // Переходим к следующему столбцу
            count_cells++;
            if (count_cells > headers_vertexes.size())  // количество клеток больше, чем количество вершин в
                throw InvalidGraphAssignment("Неверные входные данные. Матрица смежностей имеет неправильные размеры.");

            if (buff == "1") // в клетке установлена 1
            {
                // Если новая связть создат петлю, то  выдаем ошибку
                if (vertex->name == headers_vertexes[count_cells - 1]->name)
                    throw InvalidGraphAssignment("Неверные входные данные.В графе содержатся петли.");
                // Создаем связь, добавлением одной вершины в массив связанных у другой
                vertex->adjacentVertices.push_back(headers_vertexes[count_cells - 1]);
            }
            else if (buff != "0") // в клетке установлено значение отличное 0
                throw InvalidGraphAssignment("Неверные входные данные. Неверные параметры обозначения связей");
        }
        if (count_cells != headers_vertexes.size())
            throw InvalidGraphAssignment("Неверные входные данные. "
                "Не указаны ребра, связанные с вершиной " + vertex->name);
    }
    // Копируем вершины в выходной параметр графа.
    for (Vertex* v : headers_vertexes) {
        graph.push_back(v);
    }
}

int main(int argc, char* argv[])
{
    setlocale(LC_ALL, "Russian");
    if (argc != 3)
    {
        std::cerr << "Неправильно указаны параметры запуска. "
            "Убедитесь, что параметры соотвествуют шаблону: \n"
            << argv[0] << " <path/to/input_file.csv> <path/to/save_file.txt>\n";
        return 1;
    }

    std::ifstream input_file(argv[1]);

    if (!input_file.is_open()) {
        std::cerr << "Неверно указан файл с входными данными. Возможно, файл не существует." << argv[1] << '\n';
        return 1;
    }

    filesystem::path output_path = filesystem::path(argv[2]);

    if (!(filesystem::exists(output_path.parent_path()) &&
        filesystem::is_directory(output_path.parent_path()) &&
        output_path.has_filename()))
    {
        std::cerr << "Неверно указан файл для выходных данных. "
            "Возможно указанного расположения не существует или нет прав на запись." << '\n';
        return 1;
    }
    std::ofstream output_file(output_path);

    if (!output_file.is_open()) {
        std::cerr << "Неверно указан файл для выходных данных. "
            "Возможно указанного расположения не существует или нет прав на запись." << '\n';
        return 1;
    }

    std::vector<Vertex*> graph;
    try {
        readCSVFile(argv[1], graph);
    }
    catch (const InvalidGraphAssignment& e) {
        std::cerr << e.what();
        return 1;
    }
    catch (const InvalidInputFile& e) {
        std::cerr << e.what();
        return 1;
    }

    std::map<std::string, vector<Vertex*>> cycles;

    if (findCycles(graph, cycles)) {
        output_file << "True" << '\n';
    }
    else {
        output_file << "False" << '\n';
    }

    for (const auto& [cycleName, cycleVector] : cycles) {
        for (int j = 0; j < cycleVector.size(); j++) {
            output_file << cycleVector[j]->name;
            if (j < cycleVector.size() - 1) output_file << '-';
        }
        output_file << '\n';
    }
    // Закрыть файлы
    input_file.close();
    output_file.close();

    return 0;
}