【参考】Matching_Euler_Tours_and_the_Chinese_Postman
[REPRESENTATION]The edge-pairingrepresentation【表示方法】边对表示法
【核心方法】
void Model::findEuler(int index, Node * node, Edge * edge) { Node* node_a = node; Edge* edge_a = edge; while (true) { Node* node_b = edge_a->getInNode(); Edge* edge_b = NULL; for (auto &tmp_e : node_b->getOutEdges()) { if (!tmp_e->getMark()) { edge_b = tmp_e; break; } } if (edge_b != NULL) { pair<Edge*, Edge*> tmp_pair; tmp_pair.first = edge_a; tmp_pair.second = edge_b; edge_a->setMark(true); edge_b->setMark(true); _edgePairs.push_back(tmp_pair); } else//if(edge_b==NULL) { break; } node_a = node_b; edge_a = edge_b; } if (index != -1) { pair<Edge*, Edge*> tmp_pair; tmp_pair.first = edge_a; tmp_pair.second = _edgePairs[index].second; _edgePairs.push_back(tmp_pair); _edgePairs[index].second = edge; } return; } 【外层方法】
if (nodes.size() > 0) { Node* node_0 = nodes.front(); Edge* edge_0 = node_0->getOutEdges().front(); findEuler(-1, node_0, edge_0); for (auto &tmp_n : nodes) { for (auto &tmp_e : tmp_n->getOutEdges()) { if (!tmp_e->getMark()) { findEuler(getOneEdgePairIndex(tmp_n), tmp_n, tmp_e);//第一个参数为相交在tmp_n的一对边 } } } } cout << "# Edge pairs:" << _edgePairs.size() << endl; cout << "# Finish find the euler route" << endl; /*output the route*/ int pair_size = _edgePairs.size(); bool * print_mark = new bool[pair_size]; for (int i = 0; i < pair_size; ++i) { print_mark[i] = false; } Edge* cur_edge = _edgePairs[0].first; Edge* next_edge = _edgePairs[0].second; print_mark[0] = true; /*print*/ cur_edge->print(); while (next_edge != NULL) { /*print*/ next_edge->print(); cur_edge = next_edge; next_edge = NULL; /*find next edge*/ for (int i = 1; i < pair_size; ++i) { if (!print_mark[i]) { if (_edgePairs[i].first == cur_edge) { next_edge = _edgePairs[i].second; print_mark[i] = true; break; } } } }
