UndirectedWeightedGraph

UndirectedWeightedGraph

//
// Created by mfzhu on 2017/4/19.
//

#ifndef ALGORITHM_DIJKSTRA_H
#define ALGORITHM_DIJKSTRA_H

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <set>

using namespace std;
class Edge;
struct CmpByValue{
  bool operator()(const pair<pair<int, int>, int>& lhs, const pair<pair<int,int>, int>& rhs) {
    return lhs.second < rhs.second;
  }
};
class undirectedGraphNode{
public:
    int label;
    vector<Edge*> neighbors;
    undirectedGraphNode(int l): label(l) {};
};
class Edge{
public:
    int weight;
    undirectedGraphNode* start;
    undirectedGraphNode* end;
    Edge(undirectedGraphNode* s, undirectedGraphNode* e, int w): weight(w), start(s), end(e){};
};

class undirectedWeightedGraph{
public:
    undirectedWeightedGraph();
    ~undirectedWeightedGraph(){};

    void prime();
    void kruskal();

    void insertEdge(int start, int end, int weight);
    void insertNode(int val);
    void print();

private:
    int nNode;
    int nEdge;
    map<int, undirectedGraphNode*> nodeTable;
    void insertNode(map<int, undirectedGraphNode*> &nodeTable, int val);
    void insertEdge(map<int, undirectedGraphNode*> &nodeTable, int start, int end, int val);
    void kruskal(map<int, undirectedGraphNode*> nodeTable);
    void prime(map<int, undirectedGraphNode*> nodeTable);

};
undirectedWeightedGraph::undirectedWeightedGraph() {
    cout << "please input the number of vertex:" << endl;
    cin >> nNode;
    cout << "please input the number of edge:" << endl;
    cin >> nEdge;
    for (int i = 0; i < nNode; i++){
        cout << "please input the label of vertex:" << endl;
        int label;
        cin >> label;
        undirectedGraphNode* node = new undirectedGraphNode(label);
        nodeTable.insert({label, node});
    }

    for (int i = 0; i < nEdge; i++){
        cout << "please input the info of Edge:" << endl;
        int start;
        int end;
        int weight;
        cin >> start >> end >> weight;
        Edge* edge1 = new Edge(nodeTable[start], nodeTable[end], weight);
        nodeTable[start]->neighbors.push_back(edge1);
        Edge* edge2 = new Edge(nodeTable[end], nodeTable[start], weight);
        nodeTable[end]->neighbors.push_back(edge2);
    }
}
void undirectedWeightedGraph::print() {
    auto it = nodeTable.begin();
    while(it != nodeTable.end()){
        cout << "the node label is :" << it->first << endl;
        cout << "the node info is:" << endl;
        for (auto i : it->second->neighbors){
            cout << i->start->label << "->" << i->end->label << "  weight:" << i->weight << endl;
        }
        it++;
    }
}
void undirectedWeightedGraph::insertNode(map<int, undirectedGraphNode *> &nodeTable, int val) {
    if (nodeTable.find(val) == nodeTable.end()){
        undirectedGraphNode* node = new undirectedGraphNode(val);
        nodeTable.insert({val, node});
    }else{
        cout << "the node is existed" << endl;
    }
}
void undirectedWeightedGraph::insertNode(int node) {
    insertNode(nodeTable, node);
}
void undirectedWeightedGraph::insertEdge(map<int, undirectedGraphNode *> &nodeTable, int start, int end, int w) {
    Edge* e = new Edge(nodeTable[start], nodeTable[end], w);
    nodeTable[start]->neighbors.push_back(e);
}
void undirectedWeightedGraph::insertEdge(int start, int end, int weight) {
    insertEdge(nodeTable, start, end, weight);
}

void undirectedWeightedGraph::kruskal(map<int, undirectedGraphNode*> nodeTable) {
    int union_array[nNode + 1];
    for (int i = 1; i < nNode + 1; i++){
        union_array[i] = i;
    }
    map<pair<int, int>, int> result;
    map<pair<int, int>, int> Edge_map;

    for(auto it = nodeTable.begin(); it != nodeTable.end(); it++){
        for (auto edge: it->second->neighbors){
            pair<int, int> forward{edge->start->label, edge->end->label};
            pair<int, int> backward{edge->end->label, edge->start->label};
            if (Edge_map.find(forward) == Edge_map.end() && Edge_map.find(backward) == Edge_map.end()){
                Edge_map.insert({forward, edge->weight});
            }
        }
    }
    vector<pair<pair<int, int>, int>> Edge_vec(Edge_map.begin(), Edge_map.end());
    sort(Edge_vec.begin(), Edge_vec.end(), CmpByValue());


    for (auto it = Edge_vec.begin(); result.size() != nNode - 1; it++){
        int start = it->first.first;
        int end = it->first.second;
        int weight = it->second;

        if (union_array[start] == union_array[end]){
            continue;
        }else{
            result.insert({{start, end}, weight});
            int head = union_array[start];
            int tail = union_array[end];
            for (int i = 1; i < nNode + 1; i++){
                if (union_array[i] == head || union_array[i] == tail){
                    union_array[i] = head;
                }
            }
        }
    }
    for (auto it = result.begin(); it != result.end(); it++){
        cout << it->first.first << "->" << it->first.second << ": " << it->second << endl;
    }
}
void undirectedWeightedGraph::kruskal() {
    kruskal(nodeTable);
}
void undirectedWeightedGraph::prime(map<int, undirectedGraphNode *> nodeTable) {
    map<pair<int, int>, int> result;
    map<pair<int, int>, int> Edge_set;
    for (auto it = nodeTable.begin(); it != nodeTable.end(); it++){
        for (auto edge : it->second->neighbors){
            Edge_set.insert({{edge->start->label, edge->end->label}, edge->weight});
        }
    }
    auto index = nodeTable.begin();
    set<int> visited{index->first};
    set<int> unvisited;
    while(++index != nodeTable.end()){
        unvisited.insert(index->first);
    }

    int cur_min_distance = INT8_MAX;
    int v_node = 0;
    int u_node = 0;
    while(!unvisited.empty()){
        for (auto i = visited.begin(); i != visited.end(); i++){
            for (auto j = unvisited.begin(); j != unvisited.end(); j++){
                pair<int, int> tmp{*i,*j};
                if (Edge_set.find(tmp) != Edge_set.end() && Edge_set[tmp] < cur_min_distance){
                    cur_min_distance = Edge_set[tmp];
                    v_node = *i;
                    u_node = *j;
                }
            }
        }
        result.insert({{v_node, u_node}, cur_min_distance});
        cur_min_distance = INT8_MAX;
        visited.insert(u_node);
        unvisited.erase(u_node);
    }
    for (auto iter = result.begin(); iter != result.end(); iter++){
        cout << iter->first.first << "->" << iter->first.second << ": " << iter->second << endl;
    }
}
void undirectedWeightedGraph::prime() {
    prime(nodeTable);
}
#endif //ALGORITHM_DIJKSTRA_H