Графы каркас

////////////////////////////////////////////////////////////////////////////////////////////////////////
// GOOGLE DRIVE: https://drive.google.com/drive/folders/1eNXlQ50LanvYKPj_qr-Qr2qJmPa2o_Ze?usp=sharing //
////////////////////////////////////////////////////////////////////////////////////////////////////////

///////////////////////////////////
//            Graph.h            //
///////////////////////////////////

#pragma once
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <fstream>
#include <utility>
#include <vector>
#include <queue>
#include <map>
using namespace std;

/// <summary>
/// Граф
/// </summary>
/// <typeparam name="Vertice"> тип вершин графа </typeparam>
/// <typeparam name="Edge"> тип ребер графа (int по умолчанию) </typeparam>
template <class Vertice, class Edge = int>
class Graph
{
    /// <summary>
    /// Количество вершин и ребер в графе
    /// </summary>
    int _N = 0, _M = 0;

    /// <summary>
    /// Критерий ориентированности и взвешенности графа
    /// </summary>
    bool IsDirected = false, IsWeighted = false;

    /// <summary>
    /// Список смежности графа
    /// </summary>
    map <Vertice, map<Vertice, Edge>> graph;

public:

    /// <summary>
    /// Конструктор по умолчанию
    /// </summary>
    Graph() {};

    /// <summary>
    /// Конструктор, создающий пустой граф, определяющий
    /// ориентированность и взвешенность графа
    /// </summary>
    /// <param name="direction"> критерий ориентированности </param>
    /// <param name="weighting"> критерий взвешенности </param>
    Graph(string direction, string weighting)
    {
        if (direction == "directed") IsDirected = true;
        if (weighting == "weighted") IsWeighted = true;
    }

    /// <summary>
    /// Конструктор, считывающий информацию из файла
    /// или из консоли (stdin)
    /// </summary>
    /// <param name="filePath"> путь к файлу или ключевое слово stdin </param>
    Graph(string filePath)
    {
        ifstream fin;

        if (filePath == "stdin") fin = ifstream(stdin);
        else fin = ifstream(filePath);

        string cmd, direction, weighting;
        fin >> cmd >> direction >> weighting;

        *this = Graph(direction, weighting);

        fin >> cmd >> _N;

        for (int i = 0; i < _N; ++i)
        {
            Vertice v; fin >> v;
            graph.insert(pair<Vertice, map<Vertice, Edge>>(v, map<Vertice, Edge>()));
        }

        fin >> cmd >> _M;

        for (int i = 0; i < _M; ++i)
        {
            Vertice u, v; Edge w; fin >> u >> v;

            if (!IsWeighted) w = 1;
            else fin >> w;

            graph[u].insert(pair<Vertice, Edge>(v, w));
            if (!IsDirected) graph[v].insert(pair<Vertice, Edge>(u, w));
        }

        if (filePath != "stdin") fin.close();
    }

    /// <summary>
    /// Количество вершин графа
    /// </summary>
    /// <returns> количество вершин графа </returns>
    int n() { return _N; }

    /// <summary>
    /// Количество ребер графа
    /// </summary>
    /// <returns> количество ребер графа </returns>
    int m() { return _M; }

    /// <summary>
    /// Метод, выдающий информацию об
    /// ориентированности графа
    /// </summary>
    /// <returns> true, если граф ориентированный, иначе - false </returns>
    bool isDirected() { return IsDirected; }

    /// <summary>
    /// Метод, выдающий информацию о
    /// взвешенности графа
    /// </summary>
    /// <returns> true, если граф взвешенный, иначе - false </returns>
    bool isWeighted() { return IsWeighted; }

    /// <summary>
    /// Метод, возращающий список смежности графа
    /// </summary>
    /// <returns> список смежности графа </returns>
    map<Vertice, map<Vertice, Edge>> edges() { return graph; }

    /// <summary>
    /// Добавление вершины в граф
    /// </summary>
    /// <param name="v"> добавляемая в граф вершина </param>
    void addVertice(Vertice v)
    {
        try
        {
            if (graph.find(v) != graph.end()) throw "Добавление вершины: заданная вершина уже есть в графе";
            else
            {
                ++_N;
                graph.insert(pair<Vertice, map<Vertice, Edge>>(v, map<Vertice, Edge>()));
            }
        }
        catch (const char* msg)
        {
            cout << msg << "\n";
        }
    }

    /// <summary>
    /// Удаление вершины из графа
    /// </summary>
    /// <param name="v"> удаляемая из графа вершина </param>
    void removeVertice(Vertice v)
    {
        try
        {
            if (graph.find(v) == graph.end()) throw "Удаление вершины: в графе отсутствует заданная вершина";
            else
            {
                --_N; _M -= graph[v].size();

                graph.erase(v);

                for (auto p : graph)
                    if (graph[p.first].find(v) != graph[p.first].end())
                    {
                        if (IsDirected) --_M;
                        graph[p.first].erase(v);
                    }
            }
        }
        catch (const char* msg)
        {
            cout << msg << "\n";
        }
    }

    /// <summary>
    /// Добавление ребра в граф
    /// </summary>
    /// <param name="u"> первая вершина ребра </param>
    /// <param name="v"> вторая вершина ребра </param>
    /// <param name="w"> вес ребра (для невзвешенных графов w = 1) </param>
    void addEdge(Vertice u, Vertice v, Edge w)
    {
        try
        {
            if (graph.find(u) == graph.end() || graph.find(v) == graph.end()) throw "Добавление ребра: в графе отсутствует(ют) заданная(ые) вершина(ы)";
            else if (!IsDirected && u == v) throw "Добавление ребра: невозможно добавить петлю в неориентированный граф";
            else if (graph[u].find(v) != graph[u].end()) throw "Добавление ребра: заданное ребро уже есть в графе";
            else
            {
                ++_M;
                graph[u][v] = w;
                if (!IsDirected) graph[v][u] = w;
            }
        }
        catch (const char* msg)
        {
            cout << msg << "\n";
        }
    }

    /// <summary>
    /// Удаление ребра из графа
    /// </summary>
    /// <param name="u"> первая вершина ребра </param>
    /// <param name="v"> вторая вершина ребра </param>
    void removeEdge(Vertice u, Vertice v)
    {
        try
        {
            if (graph.find(u) == graph.end() || graph.find(v) == graph.end()) throw "Удаление ребра: в графе отсутствует(ют) заданная(ые) вершина(ы)";
            else
            {
                if (graph[u].find(v) == graph[u].end()) throw "Удаление ребра: в графе отсутствует заданное ребро";
                else
                {
                    --_M;
                    graph[u].erase(v);
                    if (!IsDirected) graph[v].erase(u);
                }
            }
        }
        catch (const char* msg)
        {
            cout << msg << "\n";
        }
    }

    /// <summary>
    /// Очищение графа (ориентированность
    /// и взвешенность остаются прежними)
    /// </summary>
    void clear()
    {
        _N = 0; _M = 0;
        graph.clear();
    }

    /// <summary>
    /// Вывод информации о графе в файл или
    /// на консоль (stdout)
    /// </summary>
    /// <param name="filePath"> путь к файлу или ключевое слово stdout </param>
    void print(string filePath)
    {
        ofstream fout;

        if (filePath == "stdout") fout = ofstream(stdout);
        else fout = ofstream(filePath);

        if (filePath != "stdout")
        {
            fout << "GRAPH ";

            if (IsDirected) fout << "directed ";
            else fout << "undirected ";

            if (IsWeighted) fout << "weighted\n";
            else fout << "unweighted\n";

            fout << "VERTICES: " << _N << "\n";

            for (auto p : graph)
                fout << p.first << "\n";

            fout << "EDGES: " << _M << "\n";

            for (auto p1 : graph)
            {
                Vertice u = p1.first;

                for (auto p2 : p1.second)
                {
                    Vertice v = p2.first; Edge w = p2.second;

                    if (IsDirected || u < v)
                    {
                        fout << u << " " << v << " ";
                        if (IsWeighted) fout << w;
                        fout << "\n";
                    }
                }
            }

            fout.close();
        }
        else
        {
            fout << "GRAPH ";

            if (IsDirected) fout << "directed ";
            else fout << "undirected ";

            if (IsWeighted) fout << "weighted\n";
            else fout << "unweighted\n";

            fout << "VERTICES: " << _N << "\n";

            for (auto p : graph)
                fout << p.first << "\n";

            fout << "EDGES: " << _M << "\n";

            for (auto p1 : graph)
            {
                Vertice u = p1.first;

                fout << u << ": ";

                for (auto p2 : p1.second)
                {
                    Vertice v = p2.first; Edge w = p2.second;

                    if (!IsWeighted) fout << v << " ";
                    else fout << "(" << v << ", " << w << ") ";
                }

                fout << "\n";
            }
        }
    }
};

/// <summary>
/// Система непересекающихся множеств
/// </summary>
/// <typeparam name="Vertice"> тип вершин графа </typeparam>
template <class Vertice>
class DSU
{
    /// <summary>
    /// Словари: вершина - вершина-родитель и
    /// вершина - высота соответствующего дерева
    /// </summary>
    map <Vertice, Vertice> parent;
    map <Vertice, int> r;

public:

    /// <summary>
    /// Конструктор
    /// </summary>
    /// <param name="vertices"> вершины исходного графа </param>
    DSU(vector <Vertice> vertices)
    {
        for (auto v : vertices)
            parent[v] = v;
    }

    /// <summary>
    /// Получение вершины-представителя множества
    /// </summary>
    /// <param name="v"> вершина </param>
    /// <returns> вершина-представитель </returns>
    Vertice get(Vertice v)
    {
        return (v == parent[v]) ? v : parent[v] = get(parent[v]);
    }

    /// <summary>
    /// Объединение множеств DSU
    /// </summary>
    /// <param name="u"> 1-ая вершина </param>
    /// <param name="v"> 2-ая вершина </param>
    /// <returns> степень успеха операции </returns>
    bool merge(Vertice u, Vertice v)
    {
        // нам нужны вершины-представители
        u = get(u); v = get(v);

        // одна компонента связности => ничего связывать не нужно
        if (u == v) return false;

        // должно быть r[u] <= r[v]
        if (r[u] > r[v]) swap(u, v);

        // подцепляем множество u (с меньшей высотой)
        // к множеству v (с большей высотой)
        parent[u] = v;
        r[v] += r[u];

        // операция выполнилась успешно
        return true;
    }
};

/// <summary>
/// Алгоритм Краскала построения
/// минимального остовного дерева
/// </summary>
/// <typeparam name="Vertice"> тип вершин графа </typeparam>
/// <typeparam name="Edge"> тип ребер графа </typeparam>
/// <param name="g"> граф </param>
template <class Vertice, class Edge>
void MST_Kruskal(Graph<Vertice, Edge>& g)
{
    try
    {
        if (g.isDirected()) throw "Задание III (Каркас) : граф должен быть неориентированным";
        else if (!g.isWeighted()) throw "Задание III (Каркас) : граф должен быть взвешенным";
        else
        {
            vector <Vertice> vertices;
            map <Vertice, map<Vertice, Edge>> edges = g.edges();
            vector <pair <Edge, pair <Vertice, Vertice>>> edgeList;

            map <Vertice, map <Vertice, Edge>> MST;

            for (auto p1 : edges)
            {
                Vertice u = p1.first;
                vertices.push_back(u);

                MST[u] = map<Vertice, Edge>();

                for (auto p2 : edges[u])
                {
                    Vertice v = p2.first; Edge w = p2.second;

                    if (u < v) edgeList.push_back({ w, { u, v } });
                }
            }

            sort(edgeList.begin(), edgeList.end());

            Edge MST_cost = 0;

            int cnt = 0;

            DSU<Vertice> dsu(vertices);

            for (int i = 0; i < g.m(); ++i)
            {
                Edge w = edgeList[i].first;
                Vertice u = edgeList[i].second.first, v = edgeList[i].second.second;

                if (dsu.merge(u, v))
                {
                    MST_cost += w; ++cnt;
                    MST[u][v] = w; MST[v][u] = w;
                }
            }

            if (cnt != g.n() - 1) cout << "Задание III (Каркас): граф не связен (построить минимальное остовное дерево не удалось). Зато получился лес: \n";
            else
            {
                cout << "Вес минимального остовного дерева: " << MST_cost << "\n";

                cout << "Само минимальное остовное дерево имеет вид:\n";
            }

            cout << "VERTICES: " << g.n() << "\n";

            for (auto p : MST)
                cout << p.first << "\n";

            cout << "EDGES: " << cnt << "\n";

            for (auto p1 : MST)
            {
                Vertice u = p1.first;

                cout << u << ": ";

                for (auto p2 : p1.second)
                {
                    Vertice v = p2.first; Edge w = p2.second;

                    cout << "(" << v << ", " << w << ") ";
                }

                cout << "\n";
            }
        }
    }
    catch (const char* msg)
    {
        cout << msg << "\n";
    }
}

/// <summary>
/// Алгоритм Прима построения
/// минимального остовного дерева
/// </summary>
/// <typeparam name="Vertice"> тип вершин графа </typeparam>
/// <typeparam name="Edge"> тип ребер графа </typeparam>
/// <param name="g"> граф </param>
template <class Vertice, class Edge>
void MST_Prim(Graph<Vertice, Edge>& g)
{
    try
    {
        if (g.isDirected()) throw "Задание III (Каркас) : граф должен быть неориентированным";
        else if (!g.isWeighted()) throw "Задание III (Каркас) : граф должен быть взвешенным";
        else
        {
            map <Vertice, bool> used;
            map <Vertice, map<Vertice, Edge>> MST;
            map <Vertice, map<Vertice, Edge>> edges = g.edges();

            Vertice start;

            for (auto p1 : edges)
            {
                Vertice u = p1.first;

                if (used.size() == 0) start = u;
                used[u] = false;

                MST[u] = map<Vertice, Edge>();
            }

            Edge MST_cost = 0;

            priority_queue < pair<pair<Edge, Vertice>, Vertice>,
                vector <pair<pair<Edge, Vertice>, Vertice>>,
                greater < pair<pair<Edge, Vertice>, Vertice>> > pq;

            pq.push({ { 0, start }, start });

            int cnt = 0;

            while (!pq.empty())
            {
                Vertice u = pq.top().second;
                Vertice v = pq.top().first.second; Edge w = pq.top().first.first; pq.pop();

                if (!used[v])
                {
                    MST_cost += w;

                    used[v] = true;

                    if (u != v)
                    {
                        ++cnt;

                        MST[u][v] = w;
                        MST[v][u] = w;
                    }

                    for (auto p : edges[v])
                    {
                        Vertice u = p.first; Edge w = p.second;

                        if (!used[u])
                            pq.push({ { w, u }, v });
                    }
                }
            }

            try
            {
                if (cnt != g.n() - 1) throw "Задание III (Каркас): граф несвязный :(";
                else
                {
                    cout << "Вес минимального остовного дерева: " << MST_cost << "\n";

                    cout << "Само минимальное остовное дерево имеет вид:\n";

                    cout << "VERTICES: " << g.n() << "\n";

                    for (auto p : MST)
                        cout << p.first << "\n";

                    cout << "EDGES: " << g.n() - 1 << "\n";

                    for (auto p1 : MST)
                    {
                        Vertice u = p1.first;

                        cout << u << ": ";

                        for (auto p2 : p1.second)
                        {
                            Vertice v = p2.first; Edge w = p2.second;

                            cout << "(" << v << ", " << w << ") ";
                        }

                        cout << "\n";
                    }
                }
            }
            catch (const char* msg)
            {
                cout << msg << "\n";
            }
        }
    }
    catch (const char* msg)
    {
        cout << msg << "\n";
    }
}

//////////////////////////////////////////////
//            ConsoleInterface.h            //
//////////////////////////////////////////////

#pragma once
#include "Graph.h"
#include <vector>
#include <string>

/// <summary>
/// Консольный интерфейс, работающий с одним графом
/// </summary>
/// <typeparam name="Vertice"> тип вершин графа </typeparam>
/// <typeparam name="Edge"> тип ребер графа </typeparam>
template <class Vertice, class Edge = int>
class ConsoleInterface
{
    /// <summary>
    /// Граф
    /// </summary>
    Graph<Vertice, Edge> g;

    /// <summary>
    /// Вывод на консоль списка доступных команд
    /// </summary>
    void Hint()
    {
        cout << "+---------------------------------------+\n";
        cout << "|             СПИСОК КОМАНД             |\n";
        cout << "+---------------------------------------+\n";
        cout << "|  1. CREATE GRAPH direction weighting  |\n";
        cout << "|  2. CREATE GRAPH filePath             |\n";
        cout << "|  3. ADD VERTICE v                     |\n";
        cout << "|  4. REMOVE VERTICE v                  |\n";
        cout << "|  5. ADD EDGE u v [w]                  |\n";
        cout << "|  6. REMOVE EDGE u w                   |\n";
        cout << "|  7. CLEAR GRAPH                       |\n";
        cout << "|  8. PRINT GRAPH filePath              |\n";
        cout << "|  9. TASK Kruskal                      |\n";
        cout << "|  10. TASK Prim                        |\n";
        cout << "|  11. GET HINT                         |\n";
        cout << "|  12. EXIT                             |\n";
        cout << "+---------------------------------------+\n";
    }

public:

    /// <summary>
    /// Конструктор по умолчанию
    /// </summary>
    ConsoleInterface() {};

    /// <summary>
    /// Запуск интерфейса
    /// </summary>
    void Start()
    {
        Hint();

        while (true)
        {
            cout << ">> ";

            string w1; cin >> w1;

            if (w1 == "CREATE")
            {
                string w2, w3; cin >> w2 >> w3;

                if (w3 == "directed" || w3 == "undirected")
                {
                    string w4; cin >> w4;
                    g = Graph<Vertice, Edge>(w3, w4);
                }
                else g = Graph<Vertice, Edge>(w3);
            }
            else if (w1 == "ADD")
            {
                string w2; cin >> w2;

                if (w2 == "VERTICE")
                {
                    Vertice w3; cin >> w3;
                    g.addVertice(w3);
                }
                else
                {
                    Vertice w3, w4; Edge w5; cin >> w3 >> w4;

                    if (!g.isWeighted()) w5 = 1;
                    else cin >> w5;

                    g.addEdge(w3, w4, w5);
                }
            }
            else if (w1 == "REMOVE")
            {
                string w2; cin >> w2;

                if (w2 == "VERTICE")
                {
                    Vertice w3; cin >> w3;
                    g.removeVertice(w3);
                }
                else
                {
                    Vertice w3, w4; cin >> w3 >> w4;
                    g.removeEdge(w3, w4);
                }
            }
            else if (w1 == "CLEAR")
            {
                string w2; cin >> w2;
                g.clear();
            }
            else if (w1 == "PRINT")
            {
                string w2, w3; cin >> w2 >> w3;
                g.print(w3);
            }
            else if (w1 == "TASK")
            {
                string w2; cin >> w2;

                if (w2 == "Kruskal") MST_Kruskal(g);
                else if (w2 == "Prim") MST_Prim(g);
            }
            else if (w1 == "GET")
            {
                string w2; cin >> w2;
                Hint();
            }
            else if (w1 == "EXIT")
            {
                break;
            }
        }
    }
};

/////////////////////////////////////
//            Graph.cpp            //
/////////////////////////////////////

#include "ConsoleInterface.h"
#include <Windows.h>

int main()
{
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);

    ConsoleInterface<string, int> consoleInterface;
    consoleInterface.Start();

    return 0;
}