Графы веса (new)

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

const double INF = 1e9 + 7;

/// <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>
/// <typeparam name="Edge"> тип ребер графа </typeparam>
template <class Vertice, class Edge>
struct triple
{
    Edge dist; map<Vertice, int> order; Vertice last;

    triple() {}
    triple(Edge d, map<Vertice, int> o, Vertice l) : dist(d), order(o), last(l) {}

    bool operator < (const triple& t) const { return dist < t.dist; }
    bool operator > (const triple& t) const { return dist > t.dist; }
};

/// <summary>
/// Алгоритм Дейкстры поиска кратчайшего пути
/// от одной вершины до всех других вершин
/// </summary>
/// <typeparam name="Vertice"> тип вершин графа </typeparam>
/// <typeparam name="Edge"> тип ребер графа </typeparam>
/// <param name="edges"> список смежности графа </param>
/// <param name="s"> стартовая вершина </param>
/// <param name="t"> конечная вершина </param>
/// <param name="k"> количество путей </param>
/// <param name="ways"> восстановление путей </param>
template <class Vertice, class Edge>
void Dijkstra(map<Vertice, map<Vertice, Edge>> &edges, Vertice s, Vertice t, int k, map<Vertice, priority_queue<triple<Vertice, Edge>>> &ways)
{
    for (auto p : edges)
    {
        Vertice u = p.first;
        ways[u] = priority_queue<triple<Vertice, Edge>>();
    }

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

    map <Vertice, int> ord; ord[s] = 0;
    pq.push(triple<Vertice, Edge>(0, ord, s));

    while (!pq.empty())
    {
        Edge d = pq.top().dist; map<Vertice, int> cur_ord = pq.top().order;
        Vertice u = pq.top().last; pq.pop();

        if (ways[u].size() >= k && d > ways[u].top().dist) continue;

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

            if (cur_ord.count(v)) continue;

            if (ways[v].size() < k)
            {
                auto new_ord = cur_ord;
                new_ord[v] = new_ord.size();
                triple<Vertice, Edge> to = triple<Vertice, Edge>(d + w, new_ord, v);
                ways[v].push(to);
                pq.push(to);
            }
            else if (d + w < ways[v].top().dist)
            {
                ways[v].pop();
                auto new_ord = cur_ord;
                new_ord[v] = new_ord.size();
                triple<Vertice, Edge> to = triple<Vertice, Edge>(d + w, new_ord, v);
                ways[v].push(to);
                pq.push(to);
            }
        }
    }
}

/// <summary>
/// Восстановление путей по предкам
/// </summary>
/// <typeparam name="Vertice"> тип вершин графа </typeparam>
/// <typeparam name="Edge"> тип ребер графа </typeparam>
/// <param name="edges"> список смежности графа </param>
/// <param name="parents"> список предков вершин графа </param>
/// <param name="s"> начало пути </param>
/// <param name="cur"> текущая вершина пути </param>
/// <param name="cnt"> порядковый номер пути </param>
/// <param name="path"> история пути </param>
template <class Vertice, class Edge>
void FindPaths(map<Vertice, map<Vertice, Edge>> &edges, map<Vertice, set<Vertice>>& parents, Vertice s, Vertice cur, int& cnt, int k, vector<Vertice> &path)
{
    if (cnt == k) return;

    path.push_back(cur);

    if (cur == s)
    {
        cout << ++cnt << ": ";

        for (int i = path.size() - 1; i > 0; --i)
        {
            Vertice u = path[i], v = path[i - 1]; Edge w = edges[u][v];

            cout << u << " --(" << w << ")--> ";
        }

        cout << path[0] << "\n";
    }
    else
    {
        for (auto p : parents[cur])
            FindPaths<Vertice, Edge>(edges, parents, s, p, cnt, k, path);
    }

    path.pop_back();
}

/// <summary>
/// Алгоритм Беллмана-Форда поиска кратчайшего пути
/// между двумя заданными вершинами
/// </summary>
/// <typeparam name="Vertice"> тип вершин графа </typeparam>
/// <typeparam name="Edge"> тип ребер графа </typeparam>
/// <param name="edges"> список смежности графа </param>
/// <param name="s"> начальная вершина </param>
/// <param name="t"> конечная вершина </param>
/// <param name="parents"> список предков вершин графа </param>
/// <returns> расстояние между вершинами s и t </returns>
template <class Vertice, class Edge>
Edge Bellman(map<Vertice, map<Vertice, Edge>>& edges, Vertice s, Vertice t, map<Vertice, set<Vertice>> &parents)
{
    map<Vertice, Edge> dist;

    for (auto p : edges)
    {
        Vertice u = p.first;
        dist[u] = INF;
    }

    dist[s] = 0;

    for (int i = 0; i < edges.size() - 1; ++i)
    {
        bool flag = false;

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

            if (dist[u] == INF) continue;

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

                if (dist[v] >= dist[u] + w)
                {
                    if (dist[v] > dist[u] + w)
                    {
                        parents[v].clear();
                        dist[v] = dist[u] + w;
                        flag = true;
                    }

                    parents[v].insert(u);
                }
            }
        }

        if (!flag) break;
    }

    return dist[t];
}

/// <summary>
/// Задание IV a: поиск всех кратчайших путей
/// между заданными вершинами s и t
/// </summary>
/// <typeparam name="Vertice"> тип вершин графа </typeparam>
/// <typeparam name="Edge"> тип ребер графа </typeparam>
/// <param name="g"> граф </param>
/// <param name="s"> начальная вершина </param>
/// <param name="t"> конечная вершина </param>
template <class Vertice, class Edge>
void AllShortestPaths(Graph<Vertice, Edge>& g, Vertice s, Vertice t)
{
    map<Vertice, map<Vertice, Edge>> edges = g.edges();
    map<Vertice, set<Vertice>> parents;

    try
    {
        if (edges.find(s) == edges.end()) throw "Задание IV a: вершины s нет в графе";
        else if (edges.find(t) == edges.end()) throw "Задание IV a: вершины t нет в графе";
        else
        {
            Edge length = Bellman(edges, s, t, parents);

            if (parents[t].size() == 0) cout << "Вершины s = " << s << " и t = " << t << " находятся в разных компонентах связности\n";
            else
            {
                cout << "Всевозможные пути (длины " << length << ")\n";

                int cnt = 0;
                vector<Vertice> path;
                FindPaths<Vertice, Edge>(edges, parents, s, t, cnt, INF, path);

                cout << "Итого: " << cnt << " различных кратчайших путей\n";
            }
        }
    }
    catch (const char* msg)
    {
        cout << msg << "\n";
    }
}

/// <summary>
/// Задание IV b: поиск k кратчайших путей
/// между заданными вершинами s и t
/// </summary>
/// <typeparam name="Vertice"> тип вершин графа </typeparam>
/// <typeparam name="Edge"> тип ребер графа </typeparam>
/// <param name="g"> граф </param>
/// <param name="s"> начальная вершина </param>
/// <param name="t"> конечная вершина </param>
/// <param name="k"> количество кратчайших путей </param>
template <class Vertice, class Edge>
void KShortestPaths(Graph<Vertice, Edge>& g, Vertice s, Vertice t, int k)
{
    map<Vertice, priority_queue<triple<Vertice, Edge>>> ways;
    map <Vertice, map<Vertice, Edge>> edges = g.edges();

    try
    {
        if (edges.find(s) == edges.end()) throw "Задание IV b: вершины s нет в графе";
        else if (edges.find(t) == edges.end()) throw "Задание IV b: вершины t нет в графе";
        else if (k <= 0) throw "Задание IV b: Значение k должно быть положительным";
        else
        {
            Dijkstra(edges, s, t, k, ways);

            if (ways[t].size() == 0) cout << "Вершины s = " << s << " и t = " << t << " находятся в разных компонентах связности\n";
            else
            {
                vector<triple<Vertice, Edge>> ans;

                while (!ways[t].empty())
                {
                    ans.push_back(ways[t].top());
                    ways[t].pop();
                }

                int cnt = 1;

                for (int i = ans.size() - 1; i >= 0 && cnt <= k; --i, ++cnt)
                {
                    cout << "Путь №" << cnt << ": длина = " << ans[i].dist << "\n";

                    vector <Vertice> way(ans[i].order.size());

                    for (auto p : ans[i].order)
                        way[p.second] = p.first;

                    for (int i = 0; i < way.size() - 1; ++i)
                        cout << way[i] << " ---(" << edges[way[i]][way[i + 1]] << ")--> ";

                    cout << way.back() << "\n\n";
                }

                if (cnt < k) cout << "В графе не нашлось k = " << k << " путей между вершинами s и t\n";
            }
        }
    }
    catch (const char* msg)
    {
        cout << msg << "\n";
    }
}

/// <summary>
/// Алгоритм Флойда поиска кратчайших путей
/// между всеми парами вершин
/// </summary>
/// <typeparam name="Vertice"> тип вершин графа </typeparam>
/// <typeparam name="Edge"> тип ребер графа </typeparam>
/// <param name="mat"> матрица кратчайших расстояний </param>
/// <param name="vertices"> вершины графа </param>
template <class Vertice, class Edge>
void Floyd(map<Vertice, map<Vertice, Edge>>& mat, vector<Vertice>& vertices)
{
    for (auto k : vertices)
    {
        map<Vertice, map<Vertice, Edge>> res = mat;

        for (auto u : vertices)
            for (auto v : vertices)
                if (mat[u][k] != INF && mat[k][v] != INF)
                    res[u][v] = min(mat[u][v], mat[u][k] + mat[k][v]);

        mat = res;
    }
}

/// <summary>
/// Задание IV c: поиск всех пар вершин, длина
/// пути между которыми может быть сколь угодно малой
/// </summary>
/// <typeparam name="Vertice"> тип вершин графа </typeparam>
/// <typeparam name="Edge"> тип ребер графа </typeparam>
/// <param name="g"> граф </param>
template <class Vertice, class Edge>
void AllPairs(Graph<Vertice, Edge>& g)
{
    vector<Vertice> vertices;
    map <Vertice, map<Vertice, Vertice>> ans;
    map <Vertice, map<Vertice, Edge>> edges = g.edges();

    for (auto p : edges)
    {
        Vertice v = p.first;
        vertices.push_back(v);
        ans[v] = map<Vertice, Vertice>();
    }

    for (auto s : vertices)
    {
        vector <Vertice> from_vertices;
        vector <Vertice> to_vertices;

        for (auto p : edges[s])
            from_vertices.push_back(p.first);

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

            for (auto p2 : edges[u])
            {
                if (p2.first == s) to_vertices.push_back(u);
            }
        }

        Graph<Vertice, Edge> gs = g; gs.removeVertice(s);

        map<Vertice, map<Vertice, Edge>> mat;
        map <Vertice, map<Vertice, Edge>> edges = gs.edges();

        for (auto u : vertices)
            if (u != s)
                for (auto v : vertices)
                    if (v != s) mat[u][v] = (u == v || edges[u].count(v) == 0) ? INF : edges[u][v];

        vector <Vertice> new_vertices;

        for (auto v : vertices)
            if (v != s) new_vertices.push_back(v);

        Floyd(mat, new_vertices);

        set <Vertice> in_cycle;

        for (auto v : new_vertices)
            if (mat[v][v] < 0) in_cycle.insert(v);

        for (auto u : from_vertices)
            for (auto v : to_vertices)
                for (auto k : in_cycle)
                    if (mat[u][k] != INF && mat[k][v] != INF) ans[s][s] = k;

        for (auto t : vertices)
            if (t != s)
            {
                map<Vertice, map<Vertice, Edge>> mat;
                map <Vertice, map<Vertice, Edge>> edges = gs.edges();
                vector <Vertice> to_vertices;

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

                    for (auto p2 : edges[u])
                    {
                        if (p2.first == t) to_vertices.push_back(u);
                    }
                }

                Graph<Vertice, Edge> gst = gs; gst.removeVertice(t);

                edges = gst.edges();

                for (auto u : vertices)
                    if (u != s && u != t)
                        for (auto v : vertices)
                            if (v != s && v != t)
                                mat[u][v] = (u == v || edges[u].count(v) == 0) ? INF : edges[u][v];

                vector <Vertice> new_vertices;

                for (auto v : vertices)
                    if (v != s && v != t) new_vertices.push_back(v);

                Floyd(mat, new_vertices);

                set <Vertice> in_cycle;

                for (auto v : new_vertices)
                    if (mat[v][v] < 0) in_cycle.insert(v);

                for (auto u : from_vertices)
                    if (u != t)
                        for (auto v : to_vertices)
                            if (v != s)
                                for (auto k : in_cycle)
                                    if (mat[u][k] != INF && mat[k][v] != INF) ans[s][t] = k;
            }
    }

    cout << "    | ";

    for (auto v : vertices)
        cout << left << setw(2) << v << " ";

    cout << "\n----+-";

    for (int i = 0; i < vertices.size(); ++i)
        cout << "---";

    cout << "\n";

    for (auto u : vertices)
    {
        cout << " " << left << setw(2) << u << " | ";

        for (auto v : vertices)
        {
            if (ans[u].count(v) == 0) cout << "--" << " ";
            else cout << left << setw(2) << ans[u][v] << " ";
        }

        cout << "\n";
    }
}