组网算法单机原型（C++实现）
郝伟 2020/09/15
本文通过C++代码，介绍了组网算法的核心思想，并提供了单机版C++实现代码，用于演示了组网算法的主要逻辑。由于需求或需求理解可能有变化，所以以下代码根据实际情况会有一定调整。
#include <iostream> #include <vector> #include <tuple> #include <random> #include <list> #include <string> #include <regex> #include <map> #include<stack> // 预定义的内容 #define CountryCount 8 using uint = unsigned int; using namespace std; // Note: string variables in args should be in c_str() fromat. template<typename ... Args> string format(const std::string &format, Args ... args) { size_t size = snprintf(nullptr, 0, format.c_str(), args ...) + 1; // Extra space for '\0' unique_ptr<char[]> buf(new char[size]); snprintf(buf.get(), size, format.c_str(), args ...); return string(buf.get(), buf.get() + size - 1); // remove '\0' } // 拆分字符串 vector<string> split(const string &in, const string &delimit) { regex re{delimit}; return vector<string>{sregex_token_iterator(in.begin(), in.end(), re, -1), sregex_token_iterator()}; } // 产生一个 [0, count) 间的随机整数 uint nextInt(int count) { static std::default_random_engine e(0); return count > 0 ? e() % count : 0; } // 节点类型 enum NodeType { Undefined = 0, // 未定义 GateWay = 1, // 网关节点 ManagerNode = 2, // 注册节点 RouterNode = 3, // 路由节点 ExecutionNode = 4, // 远控节点 }; enum LinkType { HighSpeed = 1, HighSecurity = 2, }; // 国家编号 enum Countries { CHN = 1, // 中国 RUS = 2, // 俄罗斯 ITA = 3, // 意大利 JPN = 4, // 日本 KOR = 5, // 韩国 USA = 6, // 美国 GBR = 7, // 英国 ESP = 8 // 西班牙 }; string NodeTypeNames[5]{"Undefined", "GateWay", "ManagerNode", "RouterNode", "ExecutionNode"}; string CountryNames[9]{"Undefined", "China", "Russa", "Italy", "Japan", "Korea", "Amarica", "Britain", "Spain"}; // 用于表示筛选条件 class Condition { public: uint pre_area = 0; // 在链路上的目标国家的前一国家，为0时表示不指定。 uint tar_area = 0; // 目标节点IP uint to_jumps = 0; // 去的跳数，不包括pre_area和tar_area uint back_jumps = 0; // 返回跳数 uint linkType = HighSecurity; // 链路类型 Condition() {} Condition(uint tar, uint jumps) { tar_area = tar; back_jumps = jumps / 2; to_jumps = jumps - back_jumps - 1; } Condition(uint tar, uint _to_jumps, uint _from_jumps) { tar_area = tar; to_jumps = _to_jumps; back_jumps = _from_jumps; } Condition(uint pre, uint tar, uint _to_jumps, uint _from_jumps) { pre_area = pre; tar_area = tar; to_jumps = _to_jumps; back_jumps = _from_jumps; } Condition(uint pre, uint tar, uint _to_jumps, uint _from_jumps, uint linktype) { pre_area = pre; tar_area = tar; to_jumps = _to_jumps; back_jumps = _from_jumps; linkType = linktype; } // 返回总路国家，包括去的路由节点，pre, tar 和 回来国家 uint size() { uint count = to_jumps + back_jumps + 1; if (pre_area > 0) count++; return count; } }; // 用于表示网络中的节点，包括四类节点，通过节点类型区分 class Node { public: uint ip = 0; // IP地址 double lat = 0; // 纬度 double lon = 0; // 经度 uint country = 0; // 国家 uint nodeType = 0; // 节点类型 bool online = true; // 是否在线 uint bandwidth = 1024; // 带宽 uint latecy = 100; // 延时 int politics = 0; // 政域值，取值范围为 [-9, 9] vector<Node *> mnodes; // 注册节点列表 vector<Node *> rnodes; // 路由节点列表 Node() {} Node(int ip) { this->ip = ip; } static double getDistance(double lat1, double long1, double lat2, double long2) { return 6371 * acos(sin(lat1 * 0.01745329) * sin(lat2 * 0.01745329) + cos(lat1 * 0.01745329) * cos(lat2 * 0.01745329) * cos((long1 - long2) * 0.01745329)); } double getDistance(Node *n) { return getDistance(lat, lon, n->lat, n->lon); } // ip, country, nodetype, politics, latitude, longtitude string toString() { return format("ip=%2d: %s(politics=%2d), # of rnodes=%d", ip, CountryNames[country].c_str(), politics, rnodes.size()); } // ip,country,nodetype,politics,online,bandwidth,latecy,latitude,longtitude string toString1() { return format("%2d,%d,%d,%2d,%d,%4d,%3d,%6.2f,%6.2f", ip, country, nodeType, politics, online, bandwidth, latecy, lat, lon); } void fromString1(string s) { auto ss = split(s, ","); ip = atoi(ss.at(0).c_str()); country = atoi(ss.at(1).c_str()); nodeType = atoi(ss.at(2).c_str()); politics = atoi(ss.at(3).c_str()); online = atoi(ss.at(4).c_str()); bandwidth = atoi(ss.at(5).c_str()); latecy = atoi(ss.at(6).c_str()); lat = atof(ss.at(7).c_str()); lon = atof(ss.at(8).c_str()); } void print() { cout << "------- " << toString() << " -------" << endl; for (auto n : rnodes) cout << "\t" << n->toString1() << endl; cout << endl; } // copy properties except ip void copy(Node *n) { this->country = n->country; this->politics = n->politics; this->bandwidth = n->bandwidth; this->latecy = n->latecy; this->lat = n->lat; this->lon = n->lon; this->online = n->online; this->nodeType = n->nodeType; } // 根据带宽，延时，是否在线等选择路由节点。 Node *selectRnode() { int ip = 0; return rnodes.size() > 0 ? rnodes.at(nextInt(rnodes.size())) : nullptr; } // 本函数用于测试，用于产生连续IP的Node static Node *newInstance() { static int ip = 0; auto n = new Node(); n->ip = ++ip; return n; } }; class algo { public: // 初始化整个网络，这个网络分布在8个国家，每个国家有3-10个路由节点 // 通过添加注册和路由节点，组成一个树型结构 static Node *generate_network() { tuple<uint, double, double, int> countryInfo[8] { make_tuple(CHN, 116.40, 39.87, 9), make_tuple(JPN, 139.41, 36.43, -3), make_tuple(KOR, 127.45, 36.17, -2), make_tuple(USA, -76.53, 38.86, -9), make_tuple(RUS, -296.30, 58.88, 5), make_tuple(GBR, -361.34, 53.20, -7), make_tuple(ITA, 15.34, 41.03, -5), make_tuple(ESP, -3.34, 39.38, -5) }; auto gw = new Node(); for (int i = 0; i < CountryCount; i++) { // 在本层循环中，首先生成一个注册节点，然后再为注册节点生成多个路由节点 // 生成一个注册节点 auto manager_node = Node::newInstance(); manager_node->nodeType = NodeType::ManagerNode; manager_node->country = get<0>(countryInfo[i]); manager_node->lat = get<1>(countryInfo[i]); manager_node->lon = get<2>(countryInfo[i]); manager_node->politics = get<3>(countryInfo[i]); gw->mnodes.push_back(manager_node); // 生成3-10个路由节点，并添加至注册节点下(rnodes) for (int j = 0, count = nextInt(8) + 3; j < count; j++) { auto router_node = Node::newInstance(); router_node->copy(manager_node); router_node->nodeType = NodeType::RouterNode; router_node->lat = manager_node->lat + 0.01 * nextInt(100); router_node->lon = manager_node->lon + 0.01 * nextInt(100); router_node->bandwidth = 100 + nextInt(2000); router_node->latecy = 10 + nextInt(190); router_node->online = nextInt(100) > 14; // 85% 的在线率 manager_node->rnodes.push_back(router_node); } } // 因为任意注册节点都需要知道其他注册节点，所以本操作为广播操作通知所有其他注册节点自己的节点 for (int i = 0; i < CountryCount; i++) for (uint j = 0; j < gw->mnodes.size(); j++) gw->mnodes.at(i)->mnodes.push_back(gw->mnodes.at(j)); return gw; } // 返回指定节点的路由节点数 static uint size(Node *_node) { uint size = 0; for (auto n : _node->mnodes) size += n->rnodes.size() + 1; return size; } // 收集所有路由节点 static vector<Node *> collectNodes(Node *_node) { vector<Node *> nodes; for (auto n : _node->mnodes) { nodes.push_back(n); for (auto n1 : n->rnodes) { nodes.push_back(n1); } } return nodes; } // 根据条件F从nodes中选出一个节点 template<typename F> static Node *pickNode(vector<Node *> &nodes, F fun) { Node *p = nullptr; for (int i = nodes.size() - 1; i >= 0; i--) { if (fun(nodes[i])) { p = nodes[i]; nodes.erase(nodes.begin() + i); break; } } return p; } // 根据输入的国家，找到对应的节点 static Node *findNodeByCountry(vector<Node *> &mnodes, uint contry) { return pickNode(mnodes, [contry](Node *n) -> bool { return n->country == contry; }); } // 返回所有的组合 static vector<vector<Node *>> getPermutation(vector<Node *> &nodes) { vector<vector<Node *>> res; vector<Node *> dstlist; traverse(dstlist, nodes, res); return res; } static void traverse(vector<Node *> &dstlist, vector<Node *> &srclist, vector<vector<Node *>> &res) { if (srclist.size() == 0) { vector<Node *> nodes; for (auto n : dstlist) nodes.push_back(n); res.push_back(nodes); } else { for (uint i = 0; i < srclist.size(); i++) { auto n = srclist[i]; srclist.erase(srclist.begin() + i); dstlist.push_back(n); traverse(dstlist, srclist, res); dstlist.erase(dstlist.begin() + dstlist.size() - 1); srclist.insert(srclist.begin() + i, n); } } } static double getLinkDistance(vector<Node *> &nodes, vector<Node *> &tars, int to_jumps) { double distance = 0; vector<Node *> link; for (auto n : nodes) link.push_back(n); for (int i = 0; i < tars.size(); i++) link.insert(link.begin() + to_jumps + i, tars[i]); for (int i = 0; i < link.size() - 1; i++) distance += link[i]->getDistance(link[i + 1]); return distance; } // TODO：从给定的注册节点中，根据某些条件，选择出cout个路由节点 static vector<Node *> getRNodes(Node *rnode, uint count) { vector<Node *> nodes; for (int i = 0; i < count; i++) nodes.push_back(rnode->rnodes[i]); return nodes; } // 从现有的国家中选择合适的区域。 static vector<Node *> selectCountries(vector<Node *> &mnodes, Condition con) { vector<Node *> link; // 结果列表 map<uint, Node *> nodemap; // 以IP为key, mnode为值的哈希表 for (auto n : mnodes) nodemap[n->ip] = n; // 输出查看，其中first 表示 key, second 表示 value for (auto it = nodemap.begin(); it != nodemap.end(); ++it) cout << it->first << " => " << it->second->toString() << '\n'; // 找到目标区域的注册节点 vector<Node *> tars; // 目标区域注册节点，可能是1个只有tar，也可能是2个,为 pre+tar Node *tar = findNodeByCountry(mnodes, con.tar_area); if (tar != nullptr) { tars.push_back(tar); cout << "target: " << tar->toString() << endl; } // 添加目标前一节点（如果存在） if (con.pre_area > 0) { Node *pre = findNodeByCountry(mnodes, con.pre_area); if (pre != nullptr) { tars.insert(tars.begin(), pre); cout << "pre: " << pre->toString() << endl; } } // 选择 total 个国家，并且保证政域差尽可能大 vector<Node *> cs; // 找到的候选国家列表 uint to = con.to_jumps; uint back = con.back_jumps; uint total = to + back; int count = 0; while (!checkCandiatesOk(cs) && ++count < 10) cs = selectCandiates(mnodes, total); if (count > 10) { cout << "failed to select nodes." << endl; return link; } auto nodes = getPermutation(cs); // 返回cs路径中，所有的节点的全排列的多条路径 //打印出nodes看结果 // for (int i = 0; i < nodes.size(); ++i) { // for (auto n: nodes[i]) // cout << n->ip << " "; // cout << endl; // } // 找到路径最短的节点 auto ns = nodes[0]; for (int i = 1; i < nodes.size(); i++) { double dis = getLinkDistance(ns, tars, to); double disi = getLinkDistance(nodes[i], tars, to); if (disi < dis) ns = nodes[i]; } // 将目标国家插入至结果中，例如将T插入： [A, B, C] -> [A, B, T, C] for (int i = 0; i < tars.size(); i++) cs.insert(cs.begin() + to + i, tars[i]); // 每个区域选择2个节点 int num = 2; for (int i = 0; i < cs.size(); i++) { if (cs[i]->ip == tars[0]->ip || cs[i]->ip == tars[tars.size() - 1]->ip) link.push_back(cs[i]); else { for (auto n : getRNodes(cs[i], num)) link.push_back(n); } } // TODO: 判断总个数是否满足要求 return link; } // 从给定的所有节点中，随机选择 count 个候选国家 // 筛选的规则是先添加所有节点，然后随机删除，直到个数与count相等 static vector<Node *> selectCandiates(vector<Node *> &nodes, uint count) { vector<Node *> res; // 先添加所有节点 for (auto n : nodes) res.push_back(n); // 随机删除，直到个数下count相等 while (res.size() > count) res.erase(res.begin() + nextInt(res.size())); // 随机删除一个 return res; } // 检测选中的国家列表是否满足条件，目前的条件是从只要有正有负即可 static bool checkCandiatesOk(vector<Node *> &cs) { int max = 0, min = 0; for (auto n : cs) { if (n->politics > max) max = n->politics; if (n->politics < min) min = n->politics; } return max > 0 && min < 0; } }; int main() { auto gw = algo::generate_network(); for (auto n : gw->mnodes) n->print(); // auto nodelist = algo::collectNodes(gw); Condition con1{USA, 5}; auto res = algo::selectCountries(gw->mnodes, con1); cout << "results:" << endl; for (auto n : res) cout << n->toString() << endl; } /* c++ map 操作 empty(), size(), erase 删除元素, insert 插入元素, swap 交换两个map容器内容, clear 清除容器 emplace 构造并插入元素, ref: https://blog.csdn.net/qq_39735236/article/details/82688904 * */
C:\Users\Hao\CLionProjects\test2\cmake-build-debug\netalgo.exe
------- ip= 1: China(politics= 9), # of rnodes=7 -------
2,1,3, 9,1,1860,173,116.79, 40.20
3,1,3, 9,0,1597, 33,116.67, 39.90
4,1,3, 9,1,1499,178,117.06, 40.43
5,1,3, 9,1, 894, 73,116.96, 40.55
6,1,3, 9,1, 354, 24,116.59, 40.78
7,1,3, 9,1,1649,190,117.09, 40.56
8,1,3, 9,1,1460, 75,116.52, 40.50
------- ip= 9: Japan(politics=-3), # of rnodes=9 -------
10,4,3,-3,1, 388,148,140.40, 36.54
11,4,3,-3,1, 871,167,140.37, 37.32
12,4,3,-3,1,1771,170,140.36, 37.25
13,4,3,-3,0, 211, 40,140.14, 36.84
14,4,3,-3,1, 427,139,139.47, 37.19
15,4,3,-3,1, 875,110,140.04, 37.17
16,4,3,-3,1,1112,147,139.73, 37.11
17,4,3,-3,1,1448,111,139.51, 37.23
18,4,3,-3,1, 590,172,139.57, 37.24
------- ip=19: Korea(politics=-2), # of rnodes=3 -------
20,5,3,-2,1,1963, 39,127.78, 36.86
21,5,3,-2,1,1835,153,127.64, 36.95
22,5,3,-2,1, 516,116,128.03, 36.52
------- ip=23: Amarica(politics=-9), # of rnodes=8 -------
24,6,3,-9,1,2046, 36,-76.41, 38.91
25,6,3,-9,1,1208,121,-75.69, 39.36
26,6,3,-9,1,1184, 24,-76.45, 39.61
27,6,3,-9,0,1619, 70,-76.09, 39.20
28,6,3,-9,1,1763, 23,-76.39, 39.61
29,6,3,-9,1,1349, 99,-76.20, 39.06
30,6,3,-9,1,1331,147,-76.42, 39.14
31,6,3,-9,1,2070, 64,-75.69, 38.87
------- ip=32: Russa(politics= 5), # of rnodes=3 -------
33,2,3, 5,1,1670, 70,-295.61, 59.15
34,2,3, 5,1, 169,115,-295.46, 59.07
35,2,3, 5,0, 742, 51,-295.58, 59.50
------- ip=36: Britain(politics=-7), # of rnodes=10 -------
37,7,3,-7,1,1750,163,-360.63, 53.31
38,7,3,-7,1,1426, 29,-360.68, 54.07
39,7,3,-7,1, 791, 50,-361.28, 54.14
40,7,3,-7,1,1218,141,-360.92, 53.95
41,7,3,-7,1, 878, 90,-360.73, 53.32
42,7,3,-7,1,1782,137,-361.06, 53.59
43,7,3,-7,1,1796, 98,-360.46, 53.98
44,7,3,-7,1, 295, 12,-361.16, 53.86
45,7,3,-7,1,1042, 84,-361.22, 53.97
46,7,3,-7,1, 706,154,-361.16, 54.15
------- ip=47: Italy(politics=-5), # of rnodes=8 -------
48,3,3,-5,1,1612, 15, 15.98, 41.03
49,3,3,-5,0,1302, 44, 15.46, 41.81
50,3,3,-5,1, 545,178, 15.57, 41.39
51,3,3,-5,1, 721,153, 15.74, 41.18
52,3,3,-5,1, 141, 71, 15.52, 41.24
53,3,3,-5,1,2092,183, 15.66, 41.35
54,3,3,-5,1, 388, 20, 16.20, 41.40
55,3,3,-5,1,2065,195, 15.64, 41.16
------- ip=56: Spain(politics=-5), # of rnodes=3 -------
57,8,3,-5,1,1135,115, -2.82, 39.70
58,8,3,-5,1, 803,187, -2.60, 40.11
59,8,3,-5,1, 147, 75, -2.86, 39.58
1 => ip= 1: China(politics= 9), # of rnodes=7
9 => ip= 9: Japan(politics=-3), # of rnodes=9
19 => ip=19: Korea(politics=-2), # of rnodes=3
23 => ip=23: Amarica(politics=-9), # of rnodes=8
32 => ip=32: Russa(politics= 5), # of rnodes=3
36 => ip=36: Britain(politics=-7), # of rnodes=10
47 => ip=47: Italy(politics=-5), # of rnodes=8
56 => ip=56: Spain(politics=-5), # of rnodes=3
target: ip=23: Amarica(politics=-9), # of rnodes=8
results:
ip= 2: China(politics= 9), # of rnodes=0
ip= 3: China(politics= 9), # of rnodes=0
ip=10: Japan(politics=-3), # of rnodes=0
ip=11: Japan(politics=-3), # of rnodes=0
ip=23: Amarica(politics=-9), # of rnodes=8
ip=33: Russa(politics= 5), # of rnodes=0
ip=34: Russa(politics= 5), # of rnodes=0
ip=57: Spain(politics=-5), # of rnodes=0
ip=58: Spain(politics=-5), # of rnodes=0
Process finished with exit code 0