#include <iostream> #include<vector> #include<set> #include<unordered_map> using namespace std; class Edge { public: int v1; int v2; int weight; Edge(int v1, int v2, int w) { this->v1 = v1; this->v2 = v2; this->weight = w; } }; class DJPathInfo // 存放已知最短路 { public: vector<vector<int>> shortest_path; vector<int> shortest_path_len; DJPathInfo(int n) { vector<int> empty; this->shortest_path=vector<vector<int>>(n, empty); this->shortest_path_len= vector<int>(n, 0); } }; class Node { public: std::vector<Edge> edges; int id; Node(int i) { this->id = i; } int degree() { return this->edges.size(); } vector<int> neighbors() { vector<int> res; if (this->edges.size() > 0) { for (auto edge : this->edges) { if (edge.v1 == this->id) res.push_back(edge.v2); else res.push_back(edge.v1); } return res; } else return res; } float cluster_coeff(vector<vector<bool>> adj_mat) { int num_neighbor = this->edges.size() - 1; if (num_neighbor < 2) return 0; vector<int> neighbors = this->neighbors(); float E = 0; //邻居之间的边数 for (auto i : neighbors) { for (auto j : neighbors) { if (i >= j) continue; if (adj_mat[i][j] == true) E++; } } cout << 2 * E / (neighbors.size() * (neighbors.size() - 1)) << endl; return 2 * E / (neighbors.size() * (neighbors.size() - 1)); } }; class Graph { public: vector<vector<bool>> adj_mat; vector<vector<float>> w_mat; int node_num; vector<Edge> edges; vector<Node> nodes; Graph(vector<vector<bool>> A, vector<vector<float>> W) { this->adj_mat = A; this->w_mat = W; this->node_num = A.size(); for (int i = 0; i < node_num; i++) this->nodes.push_back(Node(i)); for (int i = 0; i < node_num; i++) for (int j = 0; j < i; j++) { if (A[i][j] == true) this->add_edge(i, j, W[i][j]); } } Graph(int n) { vector<float> zero(n, 0); vector<bool> all_false(n, false); vector<vector<bool>> A(n, all_false); vector<vector<float>> W(n, zero); this->adj_mat = A; this->w_mat = W; this->node_num = A.size(); for (int i = 0; i < node_num; i++) this->nodes.push_back(Node(i)); for (int i = 0; i < node_num; i++) for (int j = 0; j < i; j++) { if (A[i][j] == true) this->add_edge(i, j, W[i][j]); } } void add_edge(int id1, int id2, int weight) { Edge e = Edge(id1, id2, weight); this->adj_mat[id1][id2] = true; this->adj_mat[id2][id1] = true; this->w_mat[id1][id2] = weight; this->w_mat[id2][id1] = weight; this->edges.push_back(e); this->nodes[id1].edges.push_back(e); this->nodes[id2].edges.push_back(e); } void tell_info() { for (auto v : this->nodes) { std::cout << "Node ID:" << v.id << std::endl; std::cout << "Neighbor/Weight:"; for (auto i : v.neighbors()) cout <<'(' << i<<','<< this->w_mat[v.id][i] << ')' << ','; std::cout<<std::endl; } } vector<int> DJ(int s, int dest) // Dijkstra算法 { DJPathInfo info(this->nodes.size()); vector<int> res = {s}; set<int> S; S.insert(s); set<int> U; for (auto v : this->nodes[s].neighbors()) U.insert(v); if (U.size() == 0) return res; for (auto v : U) { info.shortest_path[v].push_back(v); info.shortest_path_len[v] = this->w_mat[s][v]; } info.shortest_path_len[s] = 0; while (U.size() != 0) { int n = *U.begin(); int n_len = info.shortest_path_len[n]; for (auto it = U.begin(); it != U.end(); it++) { if (info.shortest_path_len[n] > info.shortest_path_len[*it]) { n = *it; n_len = info.shortest_path_len[*it]; } } S.insert(n); U.erase(n); for (auto v : this->nodes[n].neighbors()) { if (S.find(v) != S.end()) continue; U.insert(v); if (info.shortest_path[v].size() == 0) { info.shortest_path[v] = info.shortest_path[n]; info.shortest_path[v].push_back(v); info.shortest_path_len[v] = info.shortest_path_len[n] + this->w_mat[n][v]; continue; } if (info.shortest_path_len[n] + this->w_mat[n][v] < info.shortest_path_len[v]) { info.shortest_path[v] = info.shortest_path[n]; info.shortest_path[v].push_back(v); info.shortest_path_len[v] = info.shortest_path_len[n] + this->w_mat[n][v]; } } } if (S.find(dest) != S.end()) { for (auto v : info.shortest_path[dest]) res.push_back(v); info.shortest_path_len[dest]; } return res; } float cluster_coeff() { float res=0; for (auto node : this->nodes) res += node.cluster_coeff(this->adj_mat); return res / float(this->nodes.size()); } void degree_distribution() // 度分布 { vector<float> res; unordered_map<int, int> degree_count; for (auto v : this->nodes) { degree_count.emplace(v.degree(), 0); } for (auto v : this->nodes) { degree_count[v.degree()]++; } for (auto it : degree_count) { std::cout << "degree =" << it.first << ', '<<" prob=" << float(it.second) / this->nodes.size() << endl; } } }; int main() { Graph G = Graph(11); G.add_edge(0, 1, 2); G.add_edge(0, 2, 9); G.add_edge(0, 3, 1); G.add_edge(1, 4, 1); G.add_edge(1, 2, 6); G.add_edge(2, 4, 5); G.add_edge(2, 5, 1); G.add_edge(2, 6, 2); G.add_edge(2, 3, 7); G.add_edge(3, 6, 9); G.add_edge(4, 7, 2); G.add_edge(4, 8, 9); G.add_edge(4, 5, 3); G.add_edge(5, 8, 6); G.add_edge(5, 6, 4); G.add_edge(6, 8, 3); G.add_edge(6, 9, 1); G.add_edge(7, 8, 7); G.add_edge(7, 10, 9); G.add_edge(8, 10, 2); G.add_edge(8, 9, 1); G.add_edge(9, 10, 4); G.tell_info(); cout << "Djkstra Test: shortest 0 -> 10: "; for (const auto& p : G.DJ(0, 10)) cout << p << ','; cout<<endl; cout << "clustring coefficient=" << G.cluster_coeff() << endl; cout << "degree distribution:" << endl; G.degree_distribution(); return 0; }