组网算法单机原型（C++实现） 郝伟 2020/09/15 [TOC]
1. 说明
本文通过C++代码，介绍了组网算法的核心思想，并提供了单机版C++实现代码，用于演示了组网算法的主要逻辑。由于需求或需求理解可能有变化，所以以下代码根据实际情况会有一定调整。
2. 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
* */
3. 运行结果
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