/*!
 * @file graph_algorithm.h
 * @author CyberDash计算机考研, cyberdash@163.com(抖音id:cyberdash_yuan)
 * @brief 图算法h文件
 * @version 0.2.1
 * @date 2021-02-04
 */

#ifndef CYBER_DASH_GRAPH_ALGORITHM_H
#define CYBER_DASH_GRAPH_ALGORITHM_H


#include <iostream>
#include <set>
#include <queue>
#include <vector>
#include "graph.h"


using namespace std;


/*!
 * @brief **最小生成树模板类**
 * @tparam TVertex 结点类型模板参数
 * @tparam TWeight 边权值类型模板参数
 */
template<typename TVertex, typename TWeight>
class MinimumSpanTree {
public:

    /*!
     * @brief **构造函数(边数上限)**
     * @param max_size 边数上限
     * @note
     * 构造函数
     * -------
     * -------
     *
     * -------
     * mst_edges_分配内存\n
     * **if** 内存分配失败 :\n
     * &emsp; 抛出bad_alloc()\n
     *
     *
     * -------
     */
    explicit MinimumSpanTree(int max_size): max_size_(max_size), size_(0) {
        this->mst_edges_ = new Edge<TVertex, TWeight>[max_size];                            // mst_edges_分配内存
        if (!this->mst_edges_) {                                                            // if 内存分配失败
            throw bad_alloc();                                                              // 抛出bad_alloc()
        }
    }

    /*!
     * @brief **插入边**
     * @param edge 边
     * @return 当前最小生成树边的数量
     * @note
     * 插入边
     * -----
     * -----
     *
     * -----
     * + **1 合法性判断**\n
     * **if** 当前边数量 >= 最大边数量 :\n
     * &emsp; 返回-1\n
     * + **2 执行插入**\n
     * &emsp; 插入到最后一项\n
     * &emsp; size_加1\n
     *
     *
     * -----
     */
    int Insert(Edge<TVertex, TWeight>& edge) {
        // ---------- 1 合法性判断 ----------

        if (size_ >= max_size_) {                                                           // if 当前边数量 >= 最大边数量 :
            return -1;                                                                      // 返回-1
        }

        // ---------- 2 执行插入 ----------

        mst_edges_[size_] = edge;                                                           // 插入到最后一项
        size_++;                                                                            // size_加1

        return size_ - 1;
    }

    /*!@brief 显示最小生成树
     * @note
     * 显示最小生成树
     * -------------
     * -------------
     *
     * -------------
     * 初始化total_weight(总权值)
     * **for loop** 遍历最小生成树 :\n
     * &emsp; 获取当前边权值\n
     * &emsp; 打印当前边信息\n
     * 打一段文本\n
     *
     *
     * -------------
     * */
    void Print() {
        TWeight total_weight = 0;                                                           // 初始化total_weight(总权值)
        for (int i = 0; i < this->size_; i++) {                                             // for loop 遍历最小生成树
            total_weight += this->mst_edges_[i].weight;
            cout << "starting_vertex: " << this->mst_edges_[i].starting_vertex              // 获取当前边权值\n
                 << ", ending_vertex: " << mst_edges_[i].ending_vertex                      // 打印当前边信息\n
                 << ", weight: " << mst_edges_[i].weight << endl;
        }

        cout << "最小生成树边, 总权值: " << total_weight << endl;                              // 打一段文本\n
    }

protected:
    Edge<TVertex, TWeight>* mst_edges_; //!< **最小生成树边数组**
    int max_size_;                      //!< **边数上限**
    int size_;                          //!< **当前边数量**
};


// 深度优先遍历
template<typename TVertex, typename TWeight>
void Dfs(const Graph<TVertex, TWeight>& graph, const TVertex& vertex);


// 深度优先遍历(递归)
template<typename TVertex, typename TWeight>
void DfsOnVertexRecursive(const Graph<TVertex, TWeight>& graph, const TVertex& vertex, set<TVertex>& visited_vertex_set);


// 图广度优先遍历
template<typename TVertex, typename TWeight>
void Bfs(const Graph<TVertex, TWeight>& graph, const TVertex& vertex);


// 拓扑排序
template<typename TVertex, typename TWeight>
bool TopologicalSort(const Graph<TVertex, TWeight>& graph,
                     const TVertex& starting_vertex,
                     vector<TVertex>& topology_sorted_list);


// 求图的连通分量
template<typename TVertex, typename TWeight>
int Components(const Graph<TVertex, TWeight>& graph);


// 最小生成树Prim
template<typename TVertex, typename TWeight>
bool Prim(const Graph<TVertex, TWeight>& graph, MinimumSpanTree<TVertex, TWeight>& min_span_tree);


// 最小生成树Kruskal
template<typename TVertex, typename TWeight>
void Kruskal(const Graph<TVertex, TWeight>& graph, MinimumSpanTree<TVertex, TWeight>& min_span_tree);


// 迪杰斯特拉(Dijkstra)最短路径(优先队列)
template<class Vertex, class Weight>
void Dijkstra(const Graph<Vertex, Weight>& graph,
              const Vertex& starting_vertex,
              Weight distance[],
              int predecessor[]);


// 贝尔曼福特(Bellman-Ford)最短路径
template<typename Vertex, typename Weight>
bool BellmanFord(const Graph<Vertex, Weight>& graph,
                 const Vertex& starting_vertex,
                 Weight distance[],
                 int predecessor[]);


// 弗洛伊德(Floyd-Warshall)最短路径
template<class Vertex, class Weight>
void Floyd(const Graph<Vertex, Weight>& graph, vector<vector<Weight> >& distance, vector<vector<int> >& predecessor);


// 打印单源最短路径(迪杰斯特拉Dijkstra, 贝尔曼福特BellmanFord等)
template<typename TVertex, typename TWeight>
void PrintSingleSourceShortestPath(const Graph<TVertex, TWeight>& graph,
                                   const TVertex& starting_vertex,
                                   TWeight distance[],
                                   const int predecessor[]);


// 打印多源最短路径(弗洛伊德Floyd等)
template<typename TVertex, typename TWeight>
void PrintMultipleSourceShortestPath(const Graph<TVertex, TWeight>& graph,
                                     const vector<vector<TWeight> >& distance,
                                     const vector<vector<int> >& predecessor);


// 求起点到各结点的关键路径
template<typename TVertex, typename TWeight>
vector<TWeight> GetCriticalPath(const Graph<TVertex, TWeight>& graph, const TVertex& starting_vertex);


#endif // CYBER_DASH_GRAPH_ALGORITHM_H