代码版权归大赛组委会所有,请勿转载。
3 月 4 日开始的华为软件精英挑战赛区域复赛落下帷幕,最终止步 16 强,5000 多行的代码发上来留个纪念。
题目如下,一道类似 TSP 问题的图论题:
代码的 Makefile 如下:
# This file is part of 2016 Huawei CodeCraft solution <http://codecraft.huawei.com> OBJS = Graph.o Yen.o StringParse.o FileIO.o Ant.o main.o CC = g++ CFLAGS = -Wall -g -std=c++11 future_net: $(OBJS) $(CC) -o $@ $^ Graph.o: Graph.cxx Graph.hxx $(CC) $(CFLAGS) -c $< Yen.o: Yen.cxx Yen.hxx Graph.hxx $(CC) $(CFLAGS) -c $< StringParse.o: StringParse.cxx StringParse.hxx $(CC) $(CFLAGS) -c $< FileIO.o: FileIO.cxx FileIO.hxx StringParse.hxx $(CC) $(CFLAGS) -c $< Ant.o: Ant.cxx Ant.hxx Yen.hxx Graph.hxx FiloIO.hxx StringParse.hxx $(CC) $(CFLAGS) -c $< main.o: main.cxx Ant.hxx Yen.hxx Graph.hxx FileIO.hxx StringParse.hxx $(CC) $(CFLAGS) -c $< .PHONY: clean clean: rm *.o
以下各个代码文件就懒得解释了,需要者可参考有用部分代码:
Graph.hxx:
/************************************************************************************* * @author: Lv chon chon * * @email: xmutongxinXuLe@163.com * * This file is part of 2016 Huawei CodeCraft solution <http://codecraft.huawei.com> * *************************************************************************************/ #ifndef __GRAPH_HXX__ #define __GRAPH_HXX__ #include <cstdlib> #include <vector> #include <list> #include <stack> #include <queue> #include <set> #include <unordered_map> #define INF 0x00ffffff #define USE_REVERSE_GRAPH 0 typedef enum { White = 0, Gray, Black } colortype; class Arc { public: Arc() : ArcID(0), SourceID(0), DestinationID(0), cost(INF), nextArc(NULL) {} int ArcID; // int SourceID; // int DestinationID; // int cost; Arc *nextArc; }; #if USE_REVERSE_GRAPH class rArc { public: rArc() : ArcID(0), SourceID(0), DestinationID(0), cost(INF), nextArc(NULL) {} int ArcID; // int SourceID; // int DestinationID; // int cost; rArc *nextArc; }; #endif class Node { public: Node() : ID(0), firstArc(NULL) {} int ID; std::vector<Arc*> previous; Arc *firstArc; }; #if USE_REVERSE_GRAPH class rNode { public: rNode() : ID(0), firstArc(NULL) {} int ID; std::vector<rArc*> previous; rArc *firstArc; }; #endif struct cmp { bool operator()(std::pair<int, int> a, std::pair<int, int> b) { return a.second > b.second; } }; void tarjan(Node *NodeList, int u); void reconstructGraph(Node *NodeList, int NodeNum); void BFS(Node *NodeList, int NodeNum, int SourceID); void dijkstra(Node *NodeList, int NodeNum, int SourceID); #if USE_REVERSE_GRAPH void rBFS(rNode *rNodeList, int NodeNum, int SourceID); void rDijkstra(rNode *rNodeList, int NodeNum, int SourceID); #endif void recordDirectRouteForNode(std::vector<int>& route, int *path, int src, int dst, bool pop_back = true); void recordDirectRouteForArc(std::vector<int>& route, int *path, int* pathHelper, int src, int dst); void removeSpecifiedNodes(Node *NodeList, const std::vector<int>& specifiedNode, bool *isRemoved); void removeListOfNodes(Node *NodeList, const std::vector<int>& removeList, bool *isRemoved); void restoreSpecifiedNodes(Node *NodeList, const std::vector<int>& specifiedNode, bool *isRemoved); void restoreListOfNodes(Node *NodeList, const std::vector<int>& restoreList, bool *isRemoved); void removeSpecifiedArcs(const std::vector<int>& specifiedArc); void restoreSpecifiedArcs(const std::vector<int>& specifiedArc); #if USE_REVERSE_GRAPH void rRemoveSpecifiedNodes(rNode *rNodeList, const std::vector<int>& specifiedNode, bool *isRemoved); void rRemoveListOfNodes(rNode *rNodeList, const std::vector<int>& removeList, bool *isRemoved); void rRestoreSpecifiedNodes(rNode *rNodeList, const std::vector<int>& specifiedNode, bool *isRemoved); void rRestoreListOfNodes(rNode *rNodeList, const std::vector<int>& restoreList, bool *isRemoved); void rRemoveSpecifiedArcs(const std::vector<int>& specifiedArc); void rRestoreSpecifiedArcs(const std::vector<int>& specifiedArc); #endif #endif
Yen.hxx:
/************************************************************************************* * @author: Lv chon chon * * @email: xmutongxinXuLe@163.com * * This file is part of 2016 Huawei CodeCraft solution <http://codecraft.huawei.com> * *************************************************************************************/ #ifndef __YEN_HXX__ #define __YEN_HXX__ #include "Graph.hxx" #define USE_KSHORTESTPATH_ALGORITHM 0 class Path { public: // Constructor Path(); Path(int d); Path(const Path& rhs); // Destructor ~Path(); // operator override Path& operator=(const Path& rhs); Path operator+(const Path& rhs); Path& operator+=(const Path& rhs); void clear(); std::vector<int> nodePath; std::vector<int> arcPath; int costSum; unsigned int visitingSpecifiedNodes; #if USE_REVERSE_GRAPH #if USE_KSHORTESTPATH_ALGORITHM int deviation; int deviationFromWhichPath; #endif #endif }; void recordNodeRoute(Path& route, int *path, int src, int dst); void recordArcRoute(Path& route, int *path, int* pathHelper, int src, int dst); bool computeAnotherBestPath(Node *NodeList, int NodeNum, int src, int dst, Path& bestPath1, Path& bestPath2); bool computeBothBestPaths(Node *NodeList, int NodeNum, int src, int dst, Path& bestPath1, Path& bestPath2); #if USE_REVERSE_GRAPH #if USE_KSHORTESTPATH_ALGORITHM bool pathCmp(const Path* lhs, const Path* rhs); void rDijkstra(rNode *rNodeList, int *Pi, int NodeNum, int SourceID); void correctLabels(Node *NodeList, int *Pi, int v_i_k, std::vector<bool>& isRemoved); void correctLabelsReverseGraph(rNode *rNodeList, int *Pi, int v_i_k, std::vector<bool>& isRemoved); void kShortestPath(Path *pathArray, Path *admissiblePath, Node *NodeList, rNode *rNodeList, int NodeNum, int src, int dst, unsigned int K = 1, bool isShortestPathCaculate = true, unsigned int requiredPathNum = INF); #endif #endif #endif
StringParse.hxx:
/************************************************************************************* * @author: Lv chon chon * * @email: xmutongxinXuLe@163.com * * This file is part of 2016 Huawei CodeCraft solution <http://codecraft.huawei.com> * *************************************************************************************/ #ifndef __STRINGPARSE_HXX__ #define __STRINGPARSE_HXX__ #include <iostream> #include <fstream> #include <cstdlib> #include <cstring> #include <string> #include <sstream> namespace std { class StringParse { public: // Constructor explicit StringParse(string& s); StringParse(StringParse& rhs); StringParse& operator=(const StringParse& rhs); class CurrentPosition { public: inline explicit CurrentPosition(const StringParse& sp) : mSP(sp) {} operator const char*() const { return mSP.mPosition; } const char& operator*() const { return *mSP.mPosition; } const StringParse& mSP; }; CurrentPosition position() const { return CurrentPosition(*this); } CurrentPosition skipWhitespace(); CurrentPosition skipChar(char c); CurrentPosition skipToChar(char c); CurrentPosition skipToEnd(); bool eof() const { return mPosition >= mEnd; } void getValue(string &str, const char *start) const; private: string mString; const char* mStart; const char* mPosition; const char* mEnd; }; } #endif
FileIO.hxx:
/************************************************************************************* * @author: Lv chon chon * * @email: xmutongxinXuLe@163.com * * This file is part of 2016 Huawei CodeCraft solution <http://codecraft.huawei.com> * *************************************************************************************/ #ifndef __FILEIO_HXX__ #define __FILEIO_HXX__ #include "StringParse.hxx" #include <vector> #include <list> #include <set> #include <unordered_set> #include <unordered_map> #include <algorithm> #include <iterator> #define RANDOM_FACTOR_FOR_BFS_PATH 19 class Tuple { public: Tuple(int st, int nd, int rd, int th) : first(st), second(nd), third(rd), four(th) {} Tuple(const Tuple& rhs) : first(rhs.first), second(rhs.second), third(rhs.third), four(rhs.four) {} int first; int second; int third; int four; }; int sourceCompare(const Tuple left, const Tuple right); int sourceCompareReverse(const Tuple left, const Tuple right); int sourceCompareRandom(const Tuple left, const Tuple right); int terminalCompare(const Tuple left, const Tuple right); void inputFromTopoFile(const char *topoFile, std::list<Tuple>& AllUnion); void inputFromDemandFile(const char *demandFile, int& SourceID, int& DestinationID, std::vector<int>& specifiedNode1, std::vector<int>& specifiedNode2); void outputSolutionToFile(const char *resultFile, std::vector<int>& resultPath1, std::vector<int>& resultPath2); void outputNAToFile(const char *resultFile); bool isReplicate(std::vector<int>& vec); bool binarySearch(const std::vector<int>& vec, const int e); int identicalElementNum(std::vector<int>& vec1, std::vector<int>& vec2); int identicalElementNum(std::list<int>& li1, std::list<int>& li2); void identicalElements(std::list<int>& li, std::list<int>& li1, std::list<int>& li2); unsigned int mergeVector(std::vector<int>& vec, std::vector<int>& vec1, std::vector<int>& vec2); void obtainUniqueSourceAndDestination(std::list<Tuple>& AllUnion, std::vector<int>& Source, std::vector<int>& Destination); #endif
Ant.hxx:
/************************************************************************************* * @author: Lv chon chon * * @email: xmutongxinXuLe@163.com * * This file is part of 2016 Huawei CodeCraft solution <http://codecraft.huawei.com> * *************************************************************************************/ #ifndef __ANT_HXX__ #define __ANT_HXX__ #include <cmath> #include "Yen.hxx" #include "FileIO.hxx" #define FILE_INFO 0 #define CONSOLE_INFO 1 #define TIMMING_INFO 1 #define CONSOLE_DEBUG 0 #define USE_FORWARD_BFS_PATH 0 #define USE_REVERSE_BFS_PATH 0 #define USE_RANDOM_BFS_PATH 1 #define USE_MU_TO_REDUCE_IDENTICAL_ARCS 0 #ifndef WIN32 const char * const INFO_FILE_PATH = "./info_file"; #else const char * const INFO_FILE_PATH = "C:\\Users\\acer\\Desktop\\info_file.txt"; #endif typedef enum { VeryEasy = 1, Easy, General, Hard, VeryHard, ExtremelyHard } ComplexityDescription; class Ant { public: Ant(); Ant(const Ant& rhs); Ant& operator=(const Ant& rhs); void reset(); void clear(); bool visited[100]; bool noNodeToGo; bool specifiedNodeEnough; Path route; std::vector<int> routeRecord; }; class AntArc { public: AntArc() : eta(0.0), tau(1.0), delta_tau(0.0), mu(1.0) {} AntArc(const AntArc& rhs); double eta; double tau; double delta_tau; double mu; }; class TSPPath { public: TSPPath() : from(0), to(0) {} TSPPath(int f, int t) : from(f), to(t) {} TSPPath(const TSPPath& rhs); TSPPath& operator=(const TSPPath& rhs); bool operator==(const TSPPath& rhs) const { return from == rhs.from && to == rhs.to; } int from; int to; }; void printVector(const std::vector<int>& vec, const char *str); void printList(const std::list<int>& li, const char *str); ComplexityDescription defineComplexity(int NodeNum, size_t Vs); ComplexityDescription defineComplexity(int NodeNum, size_t Vs1, size_t Vs2); void adjustParameters(ComplexityDescription complexity); void obtainPathFromSrcToSpecifiedNodes(Node *NodeList, int NodeNum, int src, Path *P_s_v_i, std::vector<int>& specifiedNode, bool USE_DIJKSTRA = false); void obtainPathBetweenSpecifiedNodes(Node *NodeList, int NodeNum, Path **P_i_j, std::vector<int>& specifiedNode, bool USE_DIJKSTRA = false); void obtainForbiddenPath(Node *NodeList, Path **P_i_j, std::vector<int>& specifiedNode, std::set<std::pair<size_t, size_t> >& forbiddenPath, int src); void expandForbiddenPath(Path **P_i_j, size_t Vs, std::vector<int>& specifiedNode, std::set<std::pair<size_t, size_t> >& forbiddenPath); #if USE_MU_TO_REDUCE_IDENTICAL_ARCS void initArcID2InPath(Path *P_s_v_i1, Path *P_s_v_i2, Path **P_i_j1, Path **P_i_j2, size_t Vs1, size_t Vs2); #endif void antGroupAlgorithm(Node *NodeList, int NodeNum, int src, int dst, std::vector<int>& specifiedNode, Path &bestPath, bool USE_DIJKSTRA = false, unsigned int seed = 1); void antGroupAlgorithm(Node *NodeList, int NodeNum, int src, int dst, std::vector<int>& specifiedNode1, std::vector<int>& specifiedNode2, Path &bestPath1, Path &bestPath2, bool USE_DIJKSTRA = false, unsigned int seed = 1); #endif
Graph.cxx:
/************************************************************************************* * @author: Lv chon chon * * @email: xmutongxinXuLe@163.com * * This file is part of 2016 Huawei CodeCraft solution <http://codecraft.huawei.com> * *************************************************************************************/ #include "Graph.hxx" using namespace std; colortype color[2000]; int dist[2000]; int pi[2000]; int arcRecord[2000]; extern unordered_map<int, int> arcID2Cost; extern unordered_map<int, Arc*> arcID2Arc; #if USE_REVERSE_GRAPH extern unordered_map<int, rArc*> arcID2rArc; #endif static int timeStamp = 0; static int low[2000]; int dfn[2000]; static bool inStack[2000]; stack<int> tarjanStack; extern list<set<int>* > block; extern list<pair<int, int> > bridge; void tarjan(Node *NodeList, int u) { dfn[u] = low[u] = ++timeStamp; tarjanStack.push(u); inStack[u] = true; Arc *parc = NodeList[u].firstArc; while (parc != NULL) { int v = parc->DestinationID; if (dfn[v] == 0) { tarjan(NodeList, v); low[u] = (low[u] < low[v]) ? low[u] : low[v]; // low[u] = min(low[u], low[v]); if (low[v] > dfn[u]) // bridge bridge.push_back(make_pair(u, v)); } else if (inStack[v] == true) low[u] = (low[u] < dfn[v]) ? low[u] : dfn[v]; // low[u] = min(low[u], dfn[v]); parc = parc->nextArc; } if (dfn[u] == low[u]) { set<int> *blockSet = new set<int>; int vtx; do { vtx = tarjanStack.top(); tarjanStack.pop(); inStack[vtx] = false; blockSet->insert(vtx); } while(vtx != u); block.push_back(blockSet); } } void reconstructGraph(Node *NodeList, int NodeNum) { Arc *firstarc = NULL, *parc = NULL, *qarc = NULL; for (int i = 0; i < NodeNum; i++) { firstarc = NodeList[i].firstArc; parc = NULL; while (firstarc != NULL) { qarc = firstarc->nextArc; firstarc->nextArc = parc; parc = firstarc; firstarc = qarc; } NodeList[i].firstArc = parc; } } void BFS(Node *NodeList, int NodeNum, int SourceID) { int i, u, v; for (i = 0; i < NodeNum; i++) { if (SourceID != i) { color[i] = White; dist[i] = INF; pi[i] = 0; } } color[SourceID] = Gray; dist[SourceID] = 0; pi[SourceID] = 0; arcRecord[SourceID] = 0; queue<int> Q; Q.push(SourceID); while (Q.empty() != true) { u = Q.front(); Q.pop(); Arc *parc; parc = NodeList[u].firstArc; while (parc != NULL) { v = parc->DestinationID; if (color[v] == White && parc->cost != INF) { color[v] = Gray; dist[v] = dist[u] + 1; pi[v] = u; arcRecord[v] = parc->ArcID; Q.push(v); } parc = parc->nextArc; } color[u] = Black; } } void dijkstra(Node *NodeList, int NodeNum, int SourceID) { int i, u, v; // set<int> S; priority_queue<pair<int, int>, vector<pair<int, int> >, cmp > priorityQ; for (i = 0; i < NodeNum; i++) { if (SourceID != i) { dist[i] = INF; pi[i] = 0; } } dist[SourceID] = 0; pi[SourceID] = 0; arcRecord[SourceID] = 0; priorityQ.push(make_pair(SourceID, 0)); while (priorityQ.empty() != true) { u = priorityQ.top().first; priorityQ.pop(); // S.insert(u); Arc *parc; parc = NodeList[u].firstArc; while (parc != NULL) { v = parc->DestinationID; if (dist[v] > dist[u] + parc->cost) { dist[v] = dist[u] + parc->cost; pi[v] = u; arcRecord[v] = parc->ArcID; priorityQ.push(make_pair(v, dist[v])); } parc = parc->nextArc; } } } #if USE_REVERSE_GRAPH void rBFS(rNode *rNodeList, int NodeNum, int SourceID) { int i, u, v; for (i = 0; i < NodeNum; i++) { if (SourceID != i) { color[i] = White; dist[i] = INF; pi[i] = 0; } } color[SourceID] = Gray; dist[SourceID] = 0; pi[SourceID] = 0; arcRecord[SourceID] = 0; queue<int> Q; Q.push(SourceID); while (Q.empty() != true) { u = Q.front(); Q.pop(); rArc *rparc; rparc = rNodeList[u].firstArc; while (rparc != NULL) { v = rparc->DestinationID; if (color[v] == White && rparc->cost != INF) { color[v] = Gray; dist[v] = dist[u] + 1; pi[v] = u; arcRecord[v] = rparc->ArcID; Q.push(v); } rparc = rparc->nextArc; } color[u] = Black; } } void rDijkstra(rNode *rNodeList, int NodeNum, int SourceID) { int i, u, v; // set<int> S; priority_queue<pair<int, int>, vector<pair<int, int> >, cmp > priorityQ; for (i = 0; i < NodeNum; i++) if (SourceID != i) { dist[i] = INF; pi[i] = 0; } dist[SourceID] = 0; pi[SourceID] = 0; arcRecord[SourceID] = 0; priorityQ.push(make_pair(SourceID, 0)); while (priorityQ.empty() != true) { u = priorityQ.top().first; priorityQ.pop(); // S.insert(u); rArc *rparc; rparc = rNodeList[u].firstArc; while (rparc != NULL) { v = rparc->DestinationID; if (dist[v] > dist[u] + rparc->cost) { dist[v] = dist[u] + rparc->cost; pi[v] = u; arcRecord[v] = rparc->ArcID; priorityQ.push(make_pair(v, dist[v])); } rparc = rparc->nextArc; } } } #endif void recordDirectRouteForNode(vector<int>& route, int *path, int src, int dst, bool pop_back) { stack<int> S; while (dst != src) { S.push(dst); dst = path[dst]; } S.push(dst); while (S.empty() != true) { route.push_back(S.top()); S.pop(); } if (pop_back == true) route.pop_back(); } void recordDirectRouteForArc(vector<int>& route, int *path, int* pathHelper, int src, int dst) { stack<int> S; int temp; while (dst != src) { temp = dst; dst = path[dst]; S.push(dst); dst = pathHelper[temp]; } while (S.empty() != true) { route.push_back(S.top()); S.pop(); } } void removeSpecifiedNodes(Node *NodeList, const vector<int>& specifiedNode, bool *isRemoved) { Arc *parc = NULL, *qarc = NULL; for (unsigned int m = 0; m < specifiedNode.size(); m++) // remove Vs first { int removing = specifiedNode[m]; // forward graph, out-degree parc = NodeList[removing].firstArc; while (parc != NULL) { parc->cost = INF; // equivalent to remove from the network parc = parc->nextArc; } // forward graph, in-degree for (unsigned int n = 0; n < NodeList[removing].previous.size(); n++) { qarc = NodeList[removing].previous[n]; qarc->cost = INF; // equivalent to remove from the network } isRemoved[removing] = true; } } void removeListOfNodes(Node *NodeList, const vector<int>& removeList, bool *isRemoved) { Arc *parc = NULL, *qarc = NULL; // m starts from 1 to avoid removing source node, size()-1 due to last node must in Vs // m starts from 1 and size()-1 due to the first and last node must in Vs // m starts from 1 due to first node must in Vs, size()-1 is to avoid removing destination node for (unsigned int m = 1; m < removeList.size()-1; m++) { int removing = removeList[m]; if (isRemoved[removing] == true) // skip node that has been removed to save time continue; // forward graph, out-degree parc = NodeList[removing].firstArc; while (parc != NULL) { parc->cost = INF; // equivalent to remove from the network parc = parc->nextArc; } // forward graph, in-degree for (unsigned int n = 0; n < NodeList[removing].previous.size(); n++) { qarc = NodeList[removing].previous[n]; qarc->cost = INF; // equivalent to remove from the network } isRemoved[removing] = true; } } void restoreSpecifiedNodes(Node *NodeList, const vector<int>& specifiedNode, bool *isRemoved) { Arc *parc = NULL, *qarc = NULL; for (unsigned int m = 0; m < specifiedNode.size(); m++) // restore Vs first { int restoring = specifiedNode[m]; // forward graph, out-degree parc = NodeList[restoring].firstArc; while (parc != NULL) { parc->cost = arcID2Cost.at(parc->ArcID); // equivalent to restore in the network parc = parc->nextArc; } // forward graph, in-degree for (unsigned int n = 0; n < NodeList[restoring].previous.size(); n++) { qarc = NodeList[restoring].previous[n]; qarc->cost = arcID2Cost.at(qarc->ArcID); // equivalent to restore in the network } isRemoved[restoring] = false; } } void restoreListOfNodes(Node *NodeList, const vector<int>& restoreList, bool *isRemoved) { Arc *parc = NULL, *qarc = NULL; // m starts from 1 to avoid restoring source node, size()-1 due to last node must in Vs // m starts from 1 and size()-1 due to the first and last node must in Vs // m starts from 1 due to first node must in Vs, size()-1 is to avoid restoring destination node for (unsigned int m = 1; m < restoreList.size()-1; m++) { int restoring = restoreList[m]; if (isRemoved[restoring] == false) // skip node that has been restored to save time continue; // forward graph, out-degree parc = NodeList[restoring].firstArc; while (parc != NULL) { parc->cost = arcID2Cost.at(parc->ArcID); // equivalent to restore in the network parc = parc->nextArc; } // forward graph, in-degree for (unsigned int n = 0; n < NodeList[restoring].previous.size(); n++) { qarc = NodeList[restoring].previous[n]; qarc->cost = arcID2Cost.at(qarc->ArcID); // equivalent to restore in the network } isRemoved[restoring] = false; } } void removeSpecifiedArcs(const vector<int>& specifiedArc) { Arc *parc = NULL; for (unsigned int m = 0; m < specifiedArc.size(); m++) { parc = arcID2Arc.at(specifiedArc[m]); parc->cost = INF; } } void restoreSpecifiedArcs(const vector<int>& specifiedArc) { Arc *parc = NULL; for (unsigned int m = 0; m < specifiedArc.size(); m++) { parc = arcID2Arc.at(specifiedArc[m]); parc->cost = arcID2Cost.at(parc->ArcID); } } #if USE_REVERSE_GRAPH void rRemoveSpecifiedNodes(rNode *rNodeList, const vector<int>& specifiedNode, bool *isRemoved) { rArc *rparc = NULL, *rqarc = NULL; for (unsigned int m = 0; m < specifiedNode.size(); m++) // remove Vs first { int removing = specifiedNode[m]; // reverse graph, out-degree rparc = rNodeList[removing].firstArc; while (rparc != NULL) { rparc->cost = INF; // equivalent to remove from the network rparc = rparc->nextArc; } // reverse graph, in-degree for (unsigned int n = 0; n < rNodeList[removing].previous.size(); n++) { rqarc = rNodeList[removing].previous[n]; rqarc->cost = INF; // equivalent to remove from the network } isRemoved[removing] = true; } } void rRemoveListOfNodes(rNode *rNodeList, const vector<int>& removeList, bool *isRemoved) { rArc *rparc = NULL, *rqarc = NULL; // m starts from 1 to avoid removing source node, size()-1 due to last node must in Vs // m starts from 1 and size()-1 due to the first and last node must in Vs // m starts from 1 due to first node must in Vs, size()-1 is to avoid removing destination node for (unsigned int m = 1; m < removeList.size()-1; m++) { int removing = removeList[m]; if (isRemoved[removing] == true) // skip node that has been removed to save time continue; // reverse graph, out-degree rparc = rNodeList[removing].firstArc; while (rparc != NULL) { rparc->cost = INF; // equivalent to remove from the network rparc = rparc->nextArc; } // reverse graph, in-degree for (unsigned int n = 0; n < rNodeList[removing].previous.size(); n++) { rqarc = rNodeList[removing].previous[n]; rqarc->cost = INF; // equivalent to remove from the network } isRemoved[removing] = true; } } void rRestoreSpecifiedNodes(rNode *rNodeList, const vector<int>& specifiedNode, bool *isRemoved) { rArc *rparc = NULL, *rqarc = NULL; for (unsigned int m = 0; m < specifiedNode.size(); m++) // restore Vs first { int restoring = specifiedNode[m]; // reverse graph, out-degree rparc = rNodeList[restoring].firstArc; while (rparc != NULL) { rparc->cost = arcID2Cost.at(rparc->ArcID); // equivalent to restore in the network rparc = rparc->nextArc; } // reverse graph, in-degree for (unsigned int n = 0; n < rNodeList[restoring].previous.size(); n++) { rqarc = rNodeList[restoring].previous[n]; rqarc->cost = arcID2Cost.at(rqarc->ArcID); // equivalent to restore in the network } isRemoved[restoring] = false; } } void rRestoreListOfNodes(rNode *rNodeList, const vector<int>& restoreList, bool *isRemoved) { rArc *rparc = NULL, *rqarc = NULL; // m starts from 1 to avoid restoring source node, size()-1 due to last node must in Vs // m starts from 1 and size()-1 due to the first and last node must in Vs // m starts from 1 due to first node must in Vs, size()-1 is to avoid restoring destination node for (unsigned int m = 1; m < restoreList.size()-1; m++) { int restoring = restoreList[m]; if (isRemoved[restoring] == false) // skip node that has been restored to save time continue; // reverse graph, out-degree rparc = rNodeList[restoring].firstArc; while (rparc != NULL) { rparc->cost = arcID2Cost.at(rparc->ArcID); // equivalent to restore in the network rparc = rparc->nextArc; } // reverse graph, in-degree for (unsigned int n = 0; n < rNodeList[restoring].previous.size(); n++) { rqarc = rNodeList[restoring].previous[n]; rqarc->cost = arcID2Cost.at(rqarc->ArcID); // equivalent to restore in the network } isRemoved[restoring] = false; } } void rRemoveSpecifiedArcs(const vector<int>& specifiedArc) { rArc *rparc = NULL; for (unsigned int m = 0; m < specifiedArc.size(); m++) { rparc = arcID2rArc.at(specifiedArc[m]); rparc->cost = INF; } } void rRestoreSpecifiedArcs(const vector<int>& specifiedArc) { rArc *rparc = NULL; for (unsigned int m = 0; m < specifiedArc.size(); m++) { rparc = arcID2rArc.at(specifiedArc[m]); rparc->cost = arcID2Cost.at(rparc->ArcID); } } #endif
Yen.cxx:
/************************************************************************************* * @author: Lv chon chon * * @email: xmutongxinXuLe@163.com * * This file is part of 2016 Huawei CodeCraft solution <http://codecraft.huawei.com> * *************************************************************************************/ #include "Yen.hxx" using namespace std; extern int dist[]; extern int pi[]; extern int arcRecord[]; extern unordered_map<int, int> arcID2Cost; Path::Path() : costSum(0), visitingSpecifiedNodes(0) { #if USE_REVERSE_GRAPH #if USE_KSHORTESTPATH_ALGORITHM deviation = 0; deviationFromWhichPath = 0; #endif #endif } Path::Path(int d) : costSum(0), visitingSpecifiedNodes(0) { #if USE_REVERSE_GRAPH #if USE_KSHORTESTPATH_ALGORITHM deviation = d; deviationFromWhichPath = 0; #endif #endif } Path::Path(const Path& rhs) { nodePath.assign(rhs.nodePath.begin(), rhs.nodePath.end()); arcPath.assign(rhs.arcPath.begin(), rhs.arcPath.end()); costSum = rhs.costSum; visitingSpecifiedNodes = rhs.visitingSpecifiedNodes; #if USE_REVERSE_GRAPH #if USE_KSHORTESTPATH_ALGORITHM deviation = rhs.deviation; deviationFromWhichPath = rhs.deviationFromWhichPath; #endif #endif } Path::~Path() { nodePath.clear(); arcPath.clear(); } Path& Path::operator=(const Path& rhs) { if (this == &rhs) return *this; nodePath.assign(rhs.nodePath.begin(), rhs.nodePath.end()); arcPath.assign(rhs.arcPath.begin(), rhs.arcPath.end()); costSum = rhs.costSum; visitingSpecifiedNodes = rhs.visitingSpecifiedNodes; #if USE_REVERSE_GRAPH #if USE_KSHORTESTPATH_ALGORITHM deviation = rhs.deviation; deviationFromWhichPath = rhs.deviationFromWhichPath; #endif #endif return *this; } Path Path::operator+(const Path& rhs) { Path temp(*this); temp.nodePath.insert(temp.nodePath.end(), rhs.nodePath.begin()+1, rhs.nodePath.end()); temp.arcPath.insert(temp.arcPath.end(), rhs.arcPath.begin(), rhs.arcPath.end()); temp.costSum += rhs.costSum; temp.visitingSpecifiedNodes += rhs.visitingSpecifiedNodes-1; return temp; } Path& Path::operator+=(const Path& rhs) { nodePath.insert(nodePath.end(), rhs.nodePath.begin()+1, rhs.nodePath.end()); arcPath.insert(arcPath.end(), rhs.arcPath.begin(), rhs.arcPath.end()); costSum += rhs.costSum; visitingSpecifiedNodes += rhs.visitingSpecifiedNodes-1; return *this; } void Path::clear() { nodePath.clear(); arcPath.clear(); nodePath.shrink_to_fit(); arcPath.shrink_to_fit(); costSum = 0; visitingSpecifiedNodes = 0; } void recordNodeRoute(Path& route, int *path, int src, int dst) { stack<int> S; while (dst != src) { S.push(dst); dst = path[dst]; } S.push(dst); while (S.empty() != true) { route.nodePath.push_back(S.top()); S.pop(); } } void recordArcRoute(Path& route, int *path, int* pathHelper, int src, int dst) { stack<int> S; int temp; while (dst != src) { temp = dst; dst = path[dst]; S.push(dst); dst = pathHelper[temp]; } while (S.empty() != true) { route.arcPath.push_back(S.top()); route.costSum += arcID2Cost.at(S.top()); S.pop(); } } bool computeAnotherBestPath(Node *NodeList, int NodeNum, int src, int dst, Path& bestPath1, Path& bestPath2) { bool isFirstToCompute = (bestPath1.costSum == INF) ? true : false; if (isFirstToCompute == true) { bestPath1.costSum = 0; removeSpecifiedArcs(bestPath2.arcPath); dijkstra(NodeList, NodeNum, src); if (dist[dst] != INF) { recordNodeRoute(bestPath1, pi, src, dst); recordArcRoute(bestPath1, arcRecord, pi, src, dst); restoreSpecifiedArcs(bestPath2.arcPath); return false; } else { restoreSpecifiedArcs(bestPath2.arcPath); dijkstra(NodeList, NodeNum, src); recordNodeRoute(bestPath1, pi, src, dst); recordArcRoute(bestPath1, arcRecord, pi, src, dst); return true; } } else { bestPath2.costSum = 0; removeSpecifiedArcs(bestPath1.arcPath); dijkstra(NodeList, NodeNum, src); if (dist[dst] != INF) { recordNodeRoute(bestPath2, pi, src, dst); recordArcRoute(bestPath2, arcRecord, pi, src, dst); restoreSpecifiedArcs(bestPath1.arcPath); return false; } else { restoreSpecifiedArcs(bestPath1.arcPath); dijkstra(NodeList, NodeNum, src); recordNodeRoute(bestPath2, pi, src, dst); recordArcRoute(bestPath2, arcRecord, pi, src, dst); return true; } } } bool computeBothBestPaths(Node *NodeList, int NodeNum, int src, int dst, Path& bestPath1, Path& bestPath2) { bestPath1.costSum = 0; bestPath2.costSum = 0; dijkstra(NodeList, NodeNum, src); recordNodeRoute(bestPath1, pi, src, dst); recordArcRoute(bestPath1, arcRecord, pi, src, dst); removeSpecifiedArcs(bestPath1.arcPath); dijkstra(NodeList, NodeNum, src); if (dist[dst] != INF) { recordNodeRoute(bestPath2, pi, src, dst); recordArcRoute(bestPath2, arcRecord, pi, src, dst); restoreSpecifiedArcs(bestPath1.arcPath); return false; } else { restoreSpecifiedArcs(bestPath1.arcPath); BFS(NodeList, NodeNum, src); recordNodeRoute(bestPath2, pi, src, dst); recordArcRoute(bestPath2, arcRecord, pi, src, dst); return true; } } #if USE_REVERSE_GRAPH #if USE_KSHORTESTPATH_ALGORITHM bool pathCmp(const Path* lhs, const Path* rhs) { if (lhs->costSum == rhs->costSum) { if (lhs->nodePath.size() == rhs->nodePath.size()) //if (lhs->deviationFromWhichPath == rhs->deviationFromWhichPath) // return lhs->visitingSpecifiedNodes < rhs->visitingSpecifiedNodes; return lhs->deviationFromWhichPath < rhs->deviationFromWhichPath; return lhs->nodePath.size() < rhs->nodePath.size(); } return lhs->costSum < rhs->costSum; } void rDijkstra(rNode *rNodeList, int *Pi, int NodeNum, int SourceID) { int i, u, v; // set<int> S; priority_queue<pair<int, int>, vector<pair<int, int> >, cmp > priorityQ; for (i = 0; i < NodeNum; i++) if (SourceID != i) { Pi[i] = INF; pi[i] = 0; } Pi[SourceID] = 0; pi[SourceID] = 0; arcRecord[SourceID] = 0; priorityQ.push(make_pair(SourceID, 0)); while (priorityQ.empty() != true) { u = priorityQ.top().first; priorityQ.pop(); // S.insert(u); rArc *rparc; rparc = rNodeList[u].firstArc; while (rparc != NULL) { v = rparc->DestinationID; if (Pi[v] > Pi[u] + rparc->cost) { Pi[v] = Pi[u] + rparc->cost; pi[v] = u; arcRecord[v] = rparc->ArcID; priorityQ.push(make_pair(v, Pi[v])); } rparc = rparc->nextArc; } } } void correctLabels(Node *NodeList, int *Pi, int v_i_k, vector<bool>& isRemoved) { unsigned int i; queue<int> Q; Q.push(v_i_k); int x; do { x = Q.front(); Q.pop(); int priv; for (i = 0; i < NodeList[x].previous.size(); i++) { priv = NodeList[x].previous[i]->SourceID; if (isRemoved[priv] == true) // skip removed node to save time continue; if (Pi[priv] > Pi[x] + NodeList[x].previous[i]->cost) { Pi[priv] = Pi[x] + NodeList[x].previous[i]->cost; // pi_j <-- pi_i + c_{ji} Q.push(priv); // list <-- list U {j} } } } while (Q.empty() != true); } void correctLabelsReverseGraph(rNode *rNodeList, int *Pi, int v_i_k, vector<bool>& isRemoved) { queue<int> Q; Q.push(v_i_k); int x; do { x = Q.front(); Q.pop(); rArc *rparc = rNodeList[x].firstArc; while (rparc != NULL) { if (isRemoved[rparc->DestinationID] == true) // skip removed node to save time { rparc = rparc->nextArc; continue; } if (Pi[rparc->DestinationID] > Pi[x] + rparc->cost) { Pi[rparc->DestinationID] = Pi[x] + rparc->cost; // pi_j <-- pi_i + c_{ji} Q.push(rparc->DestinationID); // list <-- list U {j} } rparc = rparc->nextArc; } } while (Q.empty() != true); } void kShortestPath(Path *pathArray, Path *admissiblePath, Node *NodeList, rNode *rNodeList, int NodeNum, int src, int dst, unsigned int K, bool isShortestPathCaculate, unsigned int requiredPathNum) { if (isShortestPathCaculate == true) { dijkstra(NodeList, NodeNum, src); if (dist[dst] != INF) { recordNodeRoute(pathArray[0], pi, src, dst); recordArcRoute(pathArray[0], arcRecord, pi, src, dst); } else { pathArray[0].costSum = INF; return; } } if (K == 1) return; unsigned int i, j; unsigned int k = 1; int *Pi = new int[NodeNum]; vector<bool> isRemoved; vector<bool> is_in_d; for (i = 0; i < (unsigned int)NodeNum; i++) { isRemoved.push_back(false); is_in_d.push_back(false); } bool (*path_func_ptr)(const Path*, const Path*) = pathCmp; set<Path*, bool (*)(const Path*, const Path*)> X(path_func_ptr); set<Path*, bool (*)(const Path*, const Path*)>::iterator itx; // avoid memory leak X.insert(&pathArray[0]); set<int> *determinedStartingArcs = new set<int>[NodeNum]; vector<int> nodePathTemp; vector<int> nodePath_t_2_v_i_k, arcPath_t_2_v_i_k;; // store path Tt(v_i^k) vector<Path*> erasedPath; for (i = 0; i < K-1; i++) erasedPath.push_back(new Path(src)); Path path(src), path_k(src); int *d_p_k = new int[K]; int deviationFrom; unsigned int requiredNum = 0; // =============== While (X != empty and k < K) Do =============== while (X.empty() != true && k < K) { d_p_k[k-1] = (*X.begin())->deviation; // d_p_k[0] is src, for "d.insert(make_pair(&path, src));" path_k = **X.begin(); // p_k <-- shortest loopless path in X if (k != 1) { pathArray[k-1] = path_k; itx = X.begin(); delete *itx; // prevent memory leak } X.erase(X.begin()); // X <-- X - {p_k} *erasedPath[k-1] = path_k; // erasedPath[k-1] is the k Shortest Path path = path_k; // ========== Remove loopless path pk, except node t, from the network ========== Arc *parc = NULL, *qarc = NULL; rArc *rparc = NULL, *rqarc = NULL; for (i = 0; i < path_k.nodePath.size()-1; i++) // size()-1 due to except node t { int removing = path_k.nodePath[i]; // forward graph, out-degree parc = NodeList[removing].firstArc; while (parc != NULL) { parc->cost = INF; // equivalent to remove from the network parc = parc->nextArc; } // forward graph, in-degree for (j = 0; j < NodeList[removing].previous.size(); j++) { qarc = NodeList[removing].previous[j]; qarc->cost = INF; } // reverse graph, out-degree rparc = rNodeList[removing].firstArc; while (rparc != NULL) { rparc->cost = INF; // equivalent to remove from the network rparc = rparc->nextArc; } // reverse graph, in-degree for (j = 0; j < rNodeList[removing].previous.size(); j++) { rqarc = rNodeList[removing].previous[j]; rqarc->cost = INF; } isRemoved[removing] = true; } // ========== Remove arc(d(p_k), i), i in N, of p1, ..., p_{k-1} from the network ========== if (k != 1) { for (i = 0; i < k-1; i++) { for (j = 0; j < erasedPath[i]->nodePath.size() && j < path_k.nodePath.size(); j++) { if (erasedPath[i]->nodePath[j] != path_k.nodePath[j]) { deviationFrom = path_k.nodePath[j-1]; break; } } if (j != erasedPath[i]->nodePath.size() && j != path_k.nodePath.size()) determinedStartingArcs[deviationFrom].insert(erasedPath[i]->nodePath[j]); } } // ========== Tt <-- shortest tree rooted at t in the network ========== rDijkstra(rNodeList, Pi, NodeNum, dst); // ========== For (v_i^k in { v_{l_k-1}^k, ..., d(p_k)}) Do ========== nodePathTemp.assign(path_k.nodePath.begin(), path_k.nodePath.end()); int v_i_k, v_ip1_k; // v_ip1_k is v_{i+1}^k v_ip1_k = nodePathTemp.back(); nodePathTemp.pop_back(); do { v_i_k = nodePathTemp.back(); nodePathTemp.pop_back(); // ========== Restore node v_i^k in the network ========== // forward graph, out-degree parc = NodeList[v_i_k].firstArc; while (parc != NULL) { // when analysing d(p_k) the arcs starting in d(p_k) which belong to other loopless paths already determined should not be used. if (is_in_d[v_i_k] == true && determinedStartingArcs[v_i_k].count(parc->DestinationID) != 0) // this arc has belong to another loopless path { parc = parc->nextArc; continue; } if (parc->DestinationID != v_ip1_k && isRemoved[parc->DestinationID] == false) // arc (v_i^k, v_{i+1}^k) restore after { parc->cost = arcID2Cost.at(parc->ArcID); // equivalent to restore in the network if (Pi[v_i_k] > Pi[parc->DestinationID] + parc->cost) Pi[v_i_k] = Pi[parc->DestinationID] + parc->cost; // Calculate pi_{v_i^k} using forward star form } parc = parc->nextArc; } // forward graph, in-degree for (i = 0; i < NodeList[v_i_k].previous.size(); i++) { qarc = NodeList[v_i_k].previous[i]; if (isRemoved[qarc->SourceID] == false) qarc->cost = arcID2Cost.at(qarc->ArcID); // equivalent to restore in the network } // reverse graph, out-degree rparc = rNodeList[v_i_k].firstArc; while (rparc != NULL) { if (isRemoved[rparc->DestinationID] == false) rparc->cost = arcID2Cost.at(rparc->ArcID); rparc = rparc->nextArc; } // reverse graph, in-degree for (i = 0; i < rNodeList[v_i_k].previous.size(); i++) { rqarc = rNodeList[v_i_k].previous[i]; // when analysing d(p_k) the arcs starting in d(p_k) which belong to other loopless paths already determined should not be used. if (is_in_d[v_i_k] == true && determinedStartingArcs[v_i_k].count(rqarc->SourceID) != 0) // this arc has belong to another loopless path continue; if (rqarc->SourceID != v_ip1_k && isRemoved[rqarc->SourceID] == false) // arc (v_i^k, v_{i+1}^k) restore after { rqarc->cost = arcID2Cost.at(rqarc->ArcID); // equivalent to restore in the network if (Pi[v_i_k] > Pi[rqarc->SourceID] + rqarc->cost) Pi[v_i_k] = Pi[rqarc->SourceID] + rqarc->cost; // Calculate pi_{v_i^k} using forward star form } } isRemoved[v_i_k] = false; // Restore node v_i^k in the network // ========== If (pi_{v_i^k} is defined) Then ========== if (Pi[v_i_k] != INF) { // ===== Correct labels of v_i^k successors using backward star form ===== correctLabels(NodeList, Pi, v_i_k, isRemoved); correctLabelsReverseGraph(rNodeList, Pi, v_i_k, isRemoved); // ===== p <-- sub_{p_k}(s, v_i^k) square T_t(v_i^k) ===== rDijkstra(rNodeList, Pi, NodeNum, dst); recordDirectRouteForNode(nodePath_t_2_v_i_k, pi, dst, v_i_k, false); recordDirectRouteForArc(arcPath_t_2_v_i_k, arcRecord, pi, dst, v_i_k); for (i = path.nodePath.size()-1; ; i--) { if (path.nodePath[i] == v_i_k) break; path.nodePath.pop_back(); path.arcPath.pop_back(); } for (i = nodePath_t_2_v_i_k.size()-1; i > 0; i--) { path.nodePath.push_back(nodePath_t_2_v_i_k[i-1]); path.arcPath.push_back(arcPath_t_2_v_i_k[i-1]); } // ===== d(p) <-- v_i^k ===== is_in_d[v_i_k] = true; nodePath_t_2_v_i_k.clear(); arcPath_t_2_v_i_k.clear(); // X <-- X U {p} path.costSum = 0; for (i = 0; i < path.arcPath.size(); i++) path.costSum += arcID2Cost.at(path.arcPath[i]); path.deviation = v_i_k; path.deviationFromWhichPath = k - 1; admissiblePath[requiredNum++] = path; if (requiredNum == requiredPathNum) { for (set<Path*, bool (*)(const Path*, const Path*)>::iterator its = X.begin(); its != X.end(); ++its) delete *its; X.clear(); for (vector<Path*>::iterator itv = erasedPath.begin(); itv != erasedPath.end(); ++itv) delete *itv; erasedPath.clear(); delete []determinedStartingArcs; delete []d_p_k; delete []Pi; return; } Path *newPath = new Path(src); *newPath = path; X.insert(newPath); } // EndIf // ========== Restore (v_i^k, v_{i+1}^k) in the network ========== // forward graph, out-degree parc = NodeList[v_i_k].firstArc; while (parc != NULL) { if (parc->DestinationID == v_ip1_k) // now, arc (v_i^k, v_{i+1}^k) restore { parc->cost = arcID2Cost.at(parc->ArcID); // equivalent to restore in the network if (Pi[v_i_k] > Pi[v_ip1_k] + parc->cost) Pi[v_i_k] = Pi[v_ip1_k] + parc->cost; // Calculate pi_{v_i^k} using forward star form // Correct labels of v_i^k successors using backward star form correctLabels(NodeList, Pi, v_i_k, isRemoved); break; } parc = parc->nextArc; } // reverse graph, in-degree for (i = 0; i < rNodeList[v_i_k].previous.size(); i++) { rqarc = rNodeList[v_i_k].previous[i]; if (rqarc->SourceID == v_ip1_k) // now, arc (v_i^k, v_{i+1}^k) restore { rqarc->cost = arcID2Cost.at(rqarc->ArcID); // equivalent to restore in the network correctLabelsReverseGraph(rNodeList, Pi, v_i_k, isRemoved); break; } } v_ip1_k = v_i_k; } while (v_i_k != d_p_k[k-1]); // EndFor // ========== Restore nodes and arcs of path p_k from s to d(p_k) in the network ========== for (i = 0; i < path_k.nodePath.size(); i++) // sub_{p_k}(s, v_i^k), because d[k] = v_i^k { int restoring = path_k.nodePath[i]; if (isRemoved[restoring] == false) // if it has been restored, skip it to save time continue; // forward graph, out-degree parc = NodeList[restoring].firstArc; while (parc != NULL) { parc->cost = arcID2Cost.at(parc->ArcID); // equivalent to restore in the network parc = parc->nextArc; } // forward graph, in-degree for (j = 0; j < NodeList[restoring].previous.size(); j++) { qarc = NodeList[restoring].previous[j]; qarc->cost = arcID2Cost.at(qarc->ArcID); // equivalent to restore in the network } // reverse graph, out-degree rparc = rNodeList[restoring].firstArc; while (rparc != NULL) { rparc->cost = arcID2Cost.at(rparc->ArcID); // equivalent to restore in the network rparc = rparc->nextArc; } // reverse graph, in-degree for (j = 0; j < rNodeList[restoring].previous.size(); j++) { rqarc = rNodeList[restoring].previous[j]; rqarc->cost = arcID2Cost.at(rqarc->ArcID); // equivalent to restore in the network } isRemoved[restoring] = false; } // ========== Restore arcs (d(p_k), i), i in N, of p_1, ..., p_{k-1} in the network ========== if (k != 1) { for (i = 0; i < k-1; i++) { for (j = 0; j < erasedPath[i]->nodePath.size() && j < path_k.nodePath.size(); j++) { if (erasedPath[i]->nodePath[j] != path_k.nodePath[j]) { deviationFrom = path_k.nodePath[j-1]; break; } } if (j != erasedPath[i]->nodePath.size() && j != path_k.nodePath.size()) determinedStartingArcs[deviationFrom].erase(erasedPath[i]->nodePath[j]); } } // ========== Restore arcs starting in d(p_k) which belong to other loopless paths in the network ========== nodePathTemp.assign(path_k.nodePath.begin(), path_k.nodePath.end()); v_ip1_k = nodePathTemp.back(); nodePathTemp.pop_back(); do { v_i_k = nodePathTemp.back(); nodePathTemp.pop_back(); // forward graph, out-degree parc = NodeList[v_i_k].firstArc; while (parc != NULL) { if (parc->DestinationID != v_ip1_k && isRemoved[parc->DestinationID] == false) // arc (v_i^k, v_{i+1}^k) restore after parc->cost = arcID2Cost.at(parc->ArcID); // equivalent to restore in the network parc = parc->nextArc; } // reverse graph, in-degree for (i = 0; i < rNodeList[v_i_k].previous.size(); i++) { rqarc = rNodeList[v_i_k].previous[i]; if (rqarc->SourceID != v_ip1_k && isRemoved[rqarc->SourceID] == false) // arc (v_i^k, v_{i+1}^k) restore after rqarc->cost = arcID2Cost.at(rqarc->ArcID); // equivalent to restore in the network } v_ip1_k = v_i_k; } while (v_i_k != d_p_k[k-1]); // EndFor k++; if (X.empty() == true) { pathArray[k-1].costSum = -1; for (vector<Path*>::iterator itv = erasedPath.begin(); itv != erasedPath.end(); ++itv) delete *itv; erasedPath.clear(); delete []determinedStartingArcs; delete []d_p_k; delete []Pi; return; } } pathArray[k-1] = **X.begin(); for (set<Path*, bool (*)(const Path*, const Path*)>::iterator its = X.begin(); its != X.end(); ++its) delete *its; X.clear(); for (vector<Path*>::iterator itv = erasedPath.begin(); itv != erasedPath.end(); ++itv) delete *itv; erasedPath.clear(); delete []determinedStartingArcs; delete []d_p_k; delete []Pi; } #endif #endif
StringParse.cxx:
/************************************************************************************* * @author: Lv chon chon * * @email: xmutongxinXuLe@163.com * * This file is part of 2016 Huawei CodeCraft solution <http://codecraft.huawei.com> * *************************************************************************************/ #include "StringParse.hxx" using namespace std; StringParse::StringParse(string& s) : mString(s), mStart(s.data()), mPosition(mStart), mEnd(mStart + s.size()) { } StringParse::StringParse(StringParse& rhs) : mString(rhs.mString), mStart(rhs.mStart), mPosition(rhs.mPosition), mEnd(rhs.mEnd) { } StringParse& StringParse::operator=(const StringParse& rhs) { if (this == &rhs) return *this; mString = rhs.mString; mStart = rhs.mStart; mPosition = rhs.mPosition; mEnd = rhs.mEnd; return *this; } StringParse::CurrentPosition StringParse::skipWhitespace() { while (mPosition < mEnd) { switch (*mPosition) { case ' ' : case '\t' : case '\r' : case '\n' : { mPosition++; break; } default : return CurrentPosition(*this); } } return CurrentPosition(*this); } StringParse::CurrentPosition StringParse::skipChar(char c) { if (*mPosition != c) { cerr << "skipChar failed!" << endl; exit(EXIT_FAILURE); } ++mPosition; return CurrentPosition(*this); } StringParse::CurrentPosition StringParse::skipToChar(char c) { mPosition = (const char*)memchr(mPosition, c, mEnd - mPosition); if (!mPosition) { mPosition = mEnd; } return CurrentPosition(*this); } StringParse::CurrentPosition StringParse::skipToEnd() { mPosition = mEnd; return CurrentPosition(*this); } void StringParse::getValue(string &str, const char *start) const { if (!(mStart <= start && start <= mPosition)) { cerr << "getValue failed!" << endl; exit(EXIT_FAILURE); } str.assign(const_cast<char*>(start)); str.resize((unsigned int)(mPosition - start)); }
FileIO.cxx:
/************************************************************************************* * @author: Lv chon chon * * @email: xmutongxinXuLe@163.com * * This file is part of 2016 Huawei CodeCraft solution <http://codecraft.huawei.com> * *************************************************************************************/ #include "FileIO.hxx" using namespace std; extern unordered_map<int, int> arcID2Cost; int sourceCompare(const Tuple left, const Tuple right) { if (left.second == right.second) { if (left.third == right.third) return left.four < right.four; return left.third < right.third; } return left.second < right.second; } int sourceCompareReverse(const Tuple left, const Tuple right) { if (left.second == right.second) { if (left.third == right.third) return left.four < right.four; return left.third > right.third; } return left.second < right.second; } int sourceCompareRandom(const Tuple left, const Tuple right) { if (left.second == right.second) { if (left.third == right.third) return left.four < right.four; return (left.third % RANDOM_FACTOR_FOR_BFS_PATH) < (right.third % RANDOM_FACTOR_FOR_BFS_PATH); } return left.second < right.second; } int terminalCompare(const Tuple left, const Tuple right) { if (left.third == right.third) return left.second < right.second; return left.third < right.third; } void inputFromTopoFile(const char *topoFile, std::list<Tuple>& AllUnion) { ifstream fin; fin.open(topoFile, ios_base::in); if (!fin.is_open()) { cerr << "Cannot open " << topoFile << "!" << endl; exit(EXIT_FAILURE); } else { string inputLine; string field1, field2, field3, field4; int fieldValue1 = 0, fieldValue2 = 0, fieldValue3 = 0, fieldValue4 = 0; const char *pos; while (getline(fin, inputLine)) { StringParse sp(inputLine); sp.skipWhitespace(); pos = sp.position(); sp.skipToChar(','); sp.getValue(field1, pos); sp.skipChar(','); sp.skipWhitespace(); pos = sp.position(); sp.skipToChar(','); sp.getValue(field2, pos); sp.skipChar(','); sp.skipWhitespace(); pos = sp.position(); sp.skipToChar(','); sp.getValue(field3, pos); sp.skipChar(','); sp.skipWhitespace(); pos = sp.position(); sp.skipToEnd(); sp.getValue(field4, pos); fieldValue1 = atoi(field1.c_str()); fieldValue2 = atoi(field2.c_str()); fieldValue3 = atoi(field3.c_str()); fieldValue4 = atoi(field4.c_str()); arcID2Cost.insert(make_pair(fieldValue1, fieldValue4)); AllUnion.push_back(Tuple(fieldValue1, fieldValue2, fieldValue3, fieldValue4)); } } fin.close(); } void inputFromDemandFile(const char *demandFile, int& SourceID, int& DestinationID, vector<int>& specifiedNode1, vector<int>& specifiedNode2) { ifstream fin; fin.open(demandFile, ios_base::in); if (!fin.is_open()) { cerr << "Cannot open " << demandFile << "!" << endl; exit(EXIT_FAILURE); } else { string inputLine; string field, fieldSourceID, fieldDestinationID; const char *pos; // ========== read the first line in demandfile ========== getline(fin, inputLine); StringParse sp1(inputLine); sp1.skipToChar(','); sp1.skipChar(','); sp1.skipWhitespace(); pos = sp1.position(); sp1.skipToChar(','); sp1.getValue(fieldSourceID, pos); sp1.skipChar(','); SourceID = atoi(fieldSourceID.c_str()); sp1.skipWhitespace(); pos = sp1.position(); sp1.skipToChar(','); sp1.getValue(fieldDestinationID, pos); sp1.skipChar(','); DestinationID = atoi(fieldDestinationID.c_str()); sp1.skipWhitespace(); pos = sp1.position(); sp1.skipToEnd(); sp1.getValue(field, pos); if (field != string("NA")) { StringParse fsp(field); string subfield; pos = fsp.position(); fsp.skipToChar('|'); fsp.getValue(subfield, pos); specifiedNode1.push_back(atoi(subfield.c_str())); while (!fsp.eof()) { fsp.skipChar('|'); fsp.skipWhitespace(); pos = fsp.position(); fsp.skipToChar('|'); fsp.getValue(subfield, pos); specifiedNode1.push_back(atoi(subfield.c_str())); } } // ========== read the second line in demandfile ========== getline(fin, inputLine); StringParse sp2(inputLine); sp2.skipToChar(','); sp2.skipChar(','); sp2.skipToChar(','); sp2.skipChar(','); sp2.skipToChar(','); sp2.skipChar(','); sp2.skipWhitespace(); pos = sp2.position(); sp2.skipToEnd(); sp2.getValue(field, pos); if (field != string("NA")) { StringParse fsp(field); string subfield; pos = fsp.position(); fsp.skipToChar('|'); fsp.getValue(subfield, pos); specifiedNode2.push_back(atoi(subfield.c_str())); while (!fsp.eof()) { fsp.skipChar('|'); fsp.skipWhitespace(); pos = fsp.position(); fsp.skipToChar('|'); fsp.getValue(subfield, pos); specifiedNode2.push_back(atoi(subfield.c_str())); } } } fin.close(); } void outputSolutionToFile(const char *resultFile, vector<int>& resultPath1, vector<int>& resultPath2) { // =============== convert vector to output string =============== unsigned int i; string outputString1, outputString2; stringstream ss; for (i = 0; i < resultPath1.size() - 1; i++) { ss << resultPath1[i]; outputString1.append(ss.str()); outputString1.append("|"); ss.str(""); } ss << resultPath1[i]; outputString1.append(ss.str()); ss.str(""); for (i = 0; i < resultPath2.size() - 1; i++) { ss << resultPath2[i]; outputString2.append(ss.str()); outputString2.append("|"); ss.str(""); } ss << resultPath2[i]; outputString2.append(ss.str()); // =============== output to file =============== ofstream fout; fout.open(resultFile, ios_base::out | ios_base::trunc); if (!fout.is_open()) { cerr << "Cannot open " << resultFile << "!" << endl; exit(EXIT_FAILURE); } else { fout << outputString1 << endl << outputString2 << endl; } fout.close(); } void outputNAToFile(const char *resultFile) { string outputString("NA"); // =============== output to file =============== ofstream fout; fout.open(resultFile, ios_base::out | ios_base::trunc); if (!fout.is_open()) { cerr << "Cannot open " << resultFile << "!" << endl; exit(EXIT_FAILURE); } else { fout << outputString << endl; } fout.close(); } bool isReplicate(vector<int>& vec) { unordered_map<int, int> hashMap; for (vector<int>::reverse_iterator itv = vec.rbegin(); itv != vec.rend(); ++itv) if (++hashMap[*itv] > 1) return true; hashMap.clear(); return false; } bool binarySearch(const vector<int>& vec, const int e) { int low = 0, high = (int)vec.size()-1, mid; while (low <= high) { mid = low + ((high - low) >> 1); if (e == vec[mid]) return true; else if (e < vec[mid]) high = mid - 1; else low = mid + 1; } return false; } int identicalElementNum(vector<int>& vec1, vector<int>& vec2) { int count = 0; size_t i; unordered_set<int> hashSet; for (i = 0; i < vec1.size(); i++) hashSet.insert(vec1[i]); for (i = 0; i < vec2.size(); i++) if (hashSet.count(vec2[i]) != 0) count++; hashSet.clear(); return count; } int identicalElementNum(list<int>& li1, list<int>& li2) { int count = 0; list<int>::iterator it; unordered_set<int> hashSet; for (it = li1.begin(); it != li1.end(); ++it) hashSet.insert(*it); for (it = li2.begin(); it != li2.end(); ++it) if (hashSet.count(*it) != 0) count++; hashSet.clear(); return count; } void identicalElements(list<int>& li, list<int>& li1, list<int>& li2) { list<int>::iterator it; unordered_set<int> hashSet; for (it = li1.begin(); it != li1.end(); ++it) hashSet.insert(*it); for (it = li2.begin(); it != li2.end(); ++it) if (hashSet.count(*it) != 0) li.push_back(*it); hashSet.clear(); } unsigned int mergeVector(vector<int>& vec, vector<int>& vec1, vector<int>& vec2) // Complexity O(L1 + L2) { unsigned int pos1 = 0, pos2 = 0; if (vec1[0] <= vec2[0]) { vec.push_back(vec1[0]); pos1++; } else { vec.push_back(vec2[0]); pos2++; } for (; pos1 < vec1.size() && pos2 < vec2.size();) { if (vec1[pos1] <= vec2[pos2]) { if (vec.back() != vec1[pos1]) vec.push_back(vec1[pos1]); pos1++; } else { if (vec.back() != vec2[pos2]) vec.push_back(vec2[pos2]); pos2++; } } if (pos1 == vec1.size()) { if (vec.back() != vec2[pos2]) vec.push_back(vec2[pos2]); pos2++; for (; pos2 < vec2.size(); pos2++) vec.push_back(vec2[pos2]); } else // pos2 == vec2.size() { if (vec.back() != vec1[pos1]) vec.push_back(vec1[pos1]); pos1++; for (; pos1 < vec1.size(); pos1++) vec.push_back(vec1[pos1]); } return vec.size(); } void obtainUniqueSourceAndDestination(list<Tuple>& AllUnion, vector<int>& Source, vector<int>& Destination) { size_t i; vector<int> repeatSource, repeatDestination; for (list<Tuple>::iterator itU = AllUnion.begin(); itU != AllUnion.end(); ++itU) { repeatSource.push_back((*itU).second); repeatDestination.push_back((*itU).third); } Source.push_back(repeatSource[0]); for (i = 1; i < repeatSource.size(); i++) if (repeatSource[i] != repeatSource[i-1]) Source.push_back(repeatSource[i]); sort(repeatDestination.begin(), repeatDestination.end()); Destination.push_back(repeatDestination[0]); for (i = 1; i < repeatDestination.size(); i++) if (repeatDestination[i] != repeatDestination[i-1]) Destination.push_back(repeatDestination[i]); repeatSource.clear(); repeatDestination.clear(); }
Ant.cxx:
/************************************************************************************* * @author: Lv chon chon * * @email: xmutongxinXuLe@163.com * * This file is part of 2016 Huawei CodeCraft solution <http://codecraft.huawei.com> * *************************************************************************************/ #include "Ant.hxx" using namespace std; Ant::Ant() : noNodeToGo(false), specifiedNodeEnough(false) { memset(visited, false, sizeof(visited)); } Ant::Ant(const Ant& rhs) { for (int i = 0; i < 100; i++) visited[i] = rhs.visited[i]; noNodeToGo = rhs.noNodeToGo; specifiedNodeEnough = rhs.specifiedNodeEnough; route = rhs.route; routeRecord.assign(rhs.routeRecord.begin(), rhs.routeRecord.end()); } Ant& Ant::operator=(const Ant& rhs) { if (this == &rhs) return *this; for (int i = 0; i < 100; i++) visited[i] = rhs.visited[i]; noNodeToGo = rhs.noNodeToGo; specifiedNodeEnough = rhs.specifiedNodeEnough; route = rhs.route; routeRecord.assign(rhs.routeRecord.begin(), rhs.routeRecord.end()); return *this; } void Ant::reset() { memset(visited, false, sizeof(visited)); noNodeToGo = false; specifiedNodeEnough = false; route.clear(); routeRecord.clear(); routeRecord.shrink_to_fit(); } void Ant::clear() { route.clear(); routeRecord.clear(); routeRecord.shrink_to_fit(); } AntArc::AntArc(const AntArc& rhs) { eta = rhs.eta; tau = rhs.tau; delta_tau = rhs.delta_tau; #if USE_MU_TO_REDUCE_IDENTICAL_ARCS mu = rhs.mu; #endif } TSPPath::TSPPath(const TSPPath& rhs) { from = rhs.from; to = rhs.to; } TSPPath& TSPPath::operator=(const TSPPath& rhs) { if (this == &rhs) return *this; from = rhs.from; to = rhs.to; return *this; } extern colortype color[]; extern int dist[]; extern int pi[]; extern int arcRecord[]; /************************************************************************** *************** parameters used by ant group algorithm *************** **************************************************************************/ static unsigned int ANTS_EACH_SPECIFIED_NODE = 2; // initial status, there is certain number of ants start at each specified node static unsigned int MAX_ITERATION_FOR_ANT_ALGORITHM = 10; // no need to explain static unsigned int MIN_RESULT_PATH_NUM_FOR_ANT1 = 0; // once there is certain number of ants have visited all specified nodes set1, exiting the iteration static unsigned int MIN_RESULT_PATH_NUM_FOR_ANT2 = 0; // once there is certain number of ants have visited all specified nodes set2, exiting the iteration static const double tao_min = 0.05; // lower bound of pheromone static const double tao_max = 30.0; // upper bound of pheromone static const double alpha = 1.6; // pow(tau, alpha) static const double beta = 0.8; // pow(eta, beta) static const double nu = 2.0; // pow(mu, nu) static const double rho = 0.1; // pheromone volatile factor static const double antQ1 = 46.0; // positive feed back pheromone intensity for ant who has visited all specified nodes static const double antQ2 = 22.0; // positive feed back pheromone intensity for ant who hasn't visited all specified nodes static const double antQ3 = 32.0; // negative feed back pheromone intensity for ant who hasn't visited all specified nodes static const double mu_attenuation = 0.05; // mu's attenuation factor according to the scale of the graph static double eta0 = 500.0; // eta's initial value according to the scale of the graph #if USE_MU_TO_REDUCE_IDENTICAL_ARCS unordered_map<int, int> arcID2InPath; #endif struct hash_func { size_t operator()(const TSPPath& path) const { return path.from * 30 + path.to; } }; unordered_map<TSPPath, AntArc, hash_func> TSPPath2AntArc; unordered_map<TSPPath, AntArc, hash_func> TSPPath2AntArc1; unordered_map<TSPPath, AntArc, hash_func> TSPPath2AntArc2; void printVector(const vector<int>& vec, const char *str) { #if CONSOLE_INFO cout << str; copy(vec.begin(), vec.end(), ostream_iterator<int>(cout, " ")); cout << endl; #endif } void printList(const list<int>& li, const char *str) { #if CONSOLE_INFO cout << str; copy(li.begin(), li.end(), ostream_iterator<int>(cout, " ")); cout << endl; #endif } ComplexityDescription defineComplexity(int NodeNum, size_t Vs) { if (Vs >= 80) return ExtremelyHard; if (Vs >= 60 || NodeNum >= 1500) return VeryHard; if (Vs >= 45 || NodeNum >= 1000) return Hard; if (Vs >= 30 || NodeNum >= 600) return General; if (Vs >= 20 || NodeNum >= 300) return Easy; return VeryEasy; } ComplexityDescription defineComplexity(int NodeNum, size_t Vs1, size_t Vs2) { if (Vs1 >= 60 || Vs2 >= 60) return ExtremelyHard; if (Vs1 >= 45 || Vs2 >= 45 || NodeNum >= 1500) return VeryHard; if (Vs1 >= 30 || Vs2 >= 30 || NodeNum >= 1000) return Hard; if (Vs1 >= 20 || Vs2 >= 20 || NodeNum >= 500) return General; if (Vs1 >= 10 || Vs2 >= 10 || NodeNum >= 200) return Easy; return VeryEasy; } void adjustParameters(ComplexityDescription complexity) { ANTS_EACH_SPECIFIED_NODE = 4 - (unsigned int)complexity / 2; // 4 3 3 2 2 1 eta0 = (double)complexity * 150.0 + 50.0; switch (complexity) { case VeryEasy: case Easy: case General: MAX_ITERATION_FOR_ANT_ALGORITHM = 10; break; case Hard: MAX_ITERATION_FOR_ANT_ALGORITHM = 9; break; case VeryHard: MAX_ITERATION_FOR_ANT_ALGORITHM = 8; break; case ExtremelyHard: MAX_ITERATION_FOR_ANT_ALGORITHM = 7; break; default: break; } } void obtainPathFromSrcToSpecifiedNodes(Node *NodeList, int NodeNum, int src, Path *P_s_v_i, vector<int>& specifiedNode, bool USE_DIJKSTRA) { if (USE_DIJKSTRA == true) dijkstra(NodeList, NodeNum, src); else BFS(NodeList, NodeNum, src); for (size_t i = 0; i < specifiedNode.size(); i++) { recordNodeRoute(P_s_v_i[i], pi, src, specifiedNode[i]); recordArcRoute(P_s_v_i[i], arcRecord, pi, src, specifiedNode[i]); } } void obtainPathBetweenSpecifiedNodes(Node *NodeList, int NodeNum, Path **P_i_j, vector<int>& specifiedNode, bool USE_DIJKSTRA) { for (size_t i = 0; i < specifiedNode.size(); i++) { if (USE_DIJKSTRA == true) dijkstra(NodeList, NodeNum, specifiedNode[i]); else BFS(NodeList, NodeNum, specifiedNode[i]); for (size_t j = 0; j < specifiedNode.size(); j++) { if (i != j) { if (dist[specifiedNode[j]] != INF) { recordNodeRoute(P_i_j[i][j], pi, specifiedNode[i], specifiedNode[j]); recordArcRoute(P_i_j[i][j], arcRecord, pi, specifiedNode[i], specifiedNode[j]); } else P_i_j[i][j].costSum = INF; for (size_t k = 0; k < P_i_j[i][j].nodePath.size(); k++) if (binarySearch(specifiedNode, P_i_j[i][j].nodePath[k]) == true) P_i_j[i][j].visitingSpecifiedNodes++; } } } } void obtainForbiddenPath(Node *NodeList, Path **P_i_j, vector<int>& specifiedNode, set<pair<size_t, size_t> >& forbiddenPath, int src) { size_t i, j, k, Vs = specifiedNode.size(); list<int>::iterator itl; vector<list<int> > rightSubpaths; for (i = 0; i < Vs; i++) { if (NodeList[specifiedNode[i]].previous.size() == 1) { Arc *parc = NodeList[specifiedNode[i]].previous[0]; list<int> rightSubpath; rightSubpath.push_front(specifiedNode[i]); rightSubpath.push_front(parc->SourceID); while (NodeList[parc->SourceID].previous.size() == 1 && parc->SourceID != src && binarySearch(specifiedNode, parc->SourceID) == false) { parc = NodeList[parc->SourceID].previous[0]; rightSubpath.push_front(parc->SourceID); } rightSubpaths.push_back(rightSubpath); rightSubpath.clear(); #if CONSOLE_DEBUG cout << "qarc->ArcID: " << parc->ArcID << ",SourceID :" << parc->SourceID << ",DestinationID: " << parc->DestinationID << endl; #endif } } bool *hasAddedToHashMap = new bool[rightSubpaths.size()]; for (i = 0; i < rightSubpaths.size(); i++) hasAddedToHashMap[i] = false; unordered_map<int, int> hashMap; for (i = 0; i < rightSubpaths.size(); i++) { if (hasAddedToHashMap[i] == true) continue; int startOfSubpath = rightSubpaths[i].front(); size_t subpathLength = rightSubpaths[i].size(); size_t maxLengthSubpathIndex = i; for (j = 0; j < rightSubpaths.size(); j++) { if (i != j && startOfSubpath == rightSubpaths[j].front()) { hasAddedToHashMap[j] = true; if (subpathLength < rightSubpaths[j].size()) { subpathLength = rightSubpaths[j].size(); maxLengthSubpathIndex = j; } } } hashMap.insert(make_pair(startOfSubpath, (int)maxLengthSubpathIndex)); } delete []hasAddedToHashMap; vector<int> frontNodeOfRightSubpaths; for (i = 0; i < rightSubpaths.size(); i++) frontNodeOfRightSubpaths.push_back(rightSubpaths[i].front()); sort(frontNodeOfRightSubpaths.begin(), frontNodeOfRightSubpaths.end()); #if CONSOLE_INFO for (i = 0; i < rightSubpaths.size(); i++) { cout << "rightSubpaths[" << i << "]: "; for (itl = rightSubpaths[i].begin(); itl != rightSubpaths[i].end(); ++itl) cout << *itl << ' '; cout << endl; } #endif for (i = 0; i < Vs; i++) { for (j = 0; j < Vs; j++) { if (i != j) { if (P_i_j[i][j].costSum == INF) { forbiddenPath.insert(make_pair(i, j)); continue; } bool isForbidden = false; for (k = 1; k < P_i_j[i][j].nodePath.size(); k++) { if (binarySearch(frontNodeOfRightSubpaths, P_i_j[i][j].nodePath[k]) == true) { int whichSubpath = hashMap.at(P_i_j[i][j].nodePath[k]); for (itl = rightSubpaths[whichSubpath].begin(); itl != rightSubpaths[whichSubpath].end() && k < P_i_j[i][j].nodePath.size(); ++itl, k++) { if (P_i_j[i][j].nodePath[k] != *itl) { isForbidden = true; break; } } } if (isForbidden == true) break; } if (isForbidden == true) forbiddenPath.insert(make_pair(i, j)); } } } hashMap.clear(); for (i = 0; i < rightSubpaths.size(); i++) rightSubpaths[i].clear(); rightSubpaths.clear(); rightSubpaths.shrink_to_fit(); frontNodeOfRightSubpaths.clear(); frontNodeOfRightSubpaths.shrink_to_fit(); #if CONSOLE_INFO cout << "forbiddenPath: "; for (set<pair<size_t, size_t> >::iterator itf = forbiddenPath.begin(); itf != forbiddenPath.end(); ++itf) cout << '(' << (*itf).first << ',' << (*itf).second << "), "; cout << endl; #endif } void expandForbiddenPath(Path **P_i_j, size_t Vs, vector<int>& specifiedNode, set<pair<size_t, size_t> >& forbiddenPath) { for (size_t i = 0; i < Vs; i++) { for (size_t j = 0; j < Vs; j++) { if (i != j) { int cnt = 0; for (size_t k = 0; k < specifiedNode.size(); k++) if (binarySearch(P_i_j[i][j].nodePath, specifiedNode[k]) == true) cnt++; #if CONSOLE_INFO cout << cnt << ' '; #endif if (cnt >= 5) forbiddenPath.insert(make_pair(i, j)); } } } } #if USE_MU_TO_REDUCE_IDENTICAL_ARCS void initArcID2InPath(Path *P_s_v_i1, Path *P_s_v_i2, Path **P_i_j1, Path **P_i_j2, size_t Vs1, size_t Vs2) { size_t i, j; list<int> arcList; vector<int>::iterator itv; for (i = 0; i < Vs1; i++) for (itv = P_s_v_i1[i].arcPath.begin(); itv != P_s_v_i1[i].arcPath.end(); ++itv) arcList.push_back(*itv); for (i = 0; i < Vs2; i++) for (itv = P_s_v_i2[i].arcPath.begin(); itv != P_s_v_i2[i].arcPath.end(); ++itv) arcList.push_back(*itv); for (i = 0; i < Vs1; i++) for (j = 0; j < Vs1; j++) for (itv = P_i_j1[i][j].arcPath.begin(); itv != P_i_j1[i][j].arcPath.end(); ++itv) arcList.push_back(*itv); for (i = 0; i < Vs2; i++) for (j = 0; j < Vs2; j++) for (itv = P_i_j2[i][j].arcPath.begin(); itv != P_i_j2[i][j].arcPath.end(); ++itv) arcList.push_back(*itv); arcList.sort(); arcList.unique(); for (list<int>::iterator itl = arcList.begin(); itl != arcList.end(); ++itl) arcID2InPath.insert(make_pair(*itl, 0)); arcList.clear(); } #endif void antGroupAlgorithm(Node *NodeList, int NodeNum, int src, int dst, vector<int>& specifiedNode, Path &bestPath, bool USE_DIJKSTRA, unsigned int seed) { #if FILE_INFO ofstream fout; fout.open(INFO_FILE_PATH, ios_base::out | ios_base::trunc); if (!fout.is_open()) { cerr << "Cannot open info_file.txt!" << endl; return; } #endif size_t i, j, k; size_t Vs = specifiedNode.size(); size_t antNum = ANTS_EACH_SPECIFIED_NODE * Vs; size_t MIN_RESULT_PATH_NUM_FOR_ANT = 0; if (Vs < 25) MIN_RESULT_PATH_NUM_FOR_ANT = 27 - Vs / 5 * 3; // 27 24 21 18 15 else if (Vs >= 25 && Vs < 50) MIN_RESULT_PATH_NUM_FOR_ANT = 18 - Vs / 5; // 13 12 11 10 9 else MIN_RESULT_PATH_NUM_FOR_ANT = 12 - Vs / 10; // 7 6 5 4 3 2 // =============== define complexity of the problem, according to the scale of this graph =============== ComplexityDescription complexity = defineComplexity(NodeNum, Vs); adjustParameters(complexity); bool *isRemoved = new bool[NodeNum]; for (i = 0; i < (size_t)NodeNum; i++) isRemoved[i] = false; unordered_map<int, size_t> specifiedPosition; for (i = 0; i < specifiedNode.size(); i++) specifiedPosition.insert(make_pair(specifiedNode[i], i)); Path *P_s_v_i = new Path[Vs]; Path *P_v_i_v_j = new Path[Vs*Vs]; Path **P_i_j = new Path*[Vs]; // a point array, convenient to use form P_i_j[i][j] for (i = 0; i < Vs; i++) P_i_j[i] = P_v_i_v_j + i*Vs; removeSpecifiedNodes(NodeList, vector<int>(1, dst), isRemoved); obtainPathFromSrcToSpecifiedNodes(NodeList, NodeNum, src, P_s_v_i, specifiedNode, USE_DIJKSTRA); removeSpecifiedNodes(NodeList, vector<int>(1, src), isRemoved); obtainPathBetweenSpecifiedNodes(NodeList, NodeNum, P_i_j, specifiedNode, USE_DIJKSTRA); #if CONSOLE_DEBUG for (i = 0; i < Vs; i++) for (j = 0; j < Vs; j++) printVector(P_i_j[i][j].nodePath, "P_i_j[i][j].nodePath: "); #endif AntArc antArc, *pAntArc; for (i = 0; i < Vs; i++) { for (j = 0; j < Vs; j++) { if (i != j && P_i_j[i][j].costSum != INF) { antArc.eta = eta0 / P_i_j[i][j].costSum; TSPPath2AntArc.insert(make_pair(TSPPath(i, j), antArc)); } } } vector<int>::iterator itv; set<pair<size_t, size_t> > forbiddenPath; obtainForbiddenPath(NodeList, P_i_j, specifiedNode, forbiddenPath, src); // ========== initialize all the ants ========== Ant *ant = new Ant[antNum]; Ant *backup = new Ant[antNum]; for (i = 0; i < antNum; i++) { for (itv = P_s_v_i[i % Vs].nodePath.begin(); itv != P_s_v_i[i % Vs].nodePath.end(); ++itv) { ant[i].route.nodePath.push_back(*itv); if (specifiedPosition.find(*itv) != specifiedPosition.end()) // if (binarySearch(specifiedNode, *itv) == true) { ant[i].visited[specifiedPosition.at(*itv)] = true; ant[i].route.visitingSpecifiedNodes++; ant[i].routeRecord.push_back(specifiedPosition.at(*itv)); } } ant[i].route.arcPath.assign(P_s_v_i[i % Vs].arcPath.begin(), P_s_v_i[i % Vs].arcPath.end()); ant[i].route.costSum = P_s_v_i[i % Vs].costSum; } #if FILE_INFO fout << "=============== ant[i]: ===============" << endl; for (i = 0; i < Vs; i++) { fout << "ant[i].route[" << i << "].nodePath: "; for (k = 0; k < ant[i].route.nodePath.size(); k++) fout << ant[i].route.nodePath[k] << ' '; fout << "\tvisitingSpecifiedNodes: " << ant[i].route.visitingSpecifiedNodes << endl; fout << "ant[i].route[" << i << "].arcPath: "; for (k = 0; k < ant[i].route.arcPath.size(); k++) fout << ant[i].route.arcPath[k] << ' '; fout << "\tcostSum: " << ant[i].route.costSum << endl; } fout << endl; #endif for (i = 0; i < antNum; i++) backup[i] = ant[i]; // ======================================================== // =============== Iteration begins ... =============== // ======================================================== srand(seed); vector<int> routeValidator; vector<Path> resultAntsPath; for (unsigned int Nc = 1; Nc <= MAX_ITERATION_FOR_ANT_ALGORITHM; Nc++) { size_t I; size_t currentPosition; double numerator, denominator, drand; // =============== ants aiming for specified nodes set 1 start to go !!! =============== for (I = 0; I < antNum; I++) { if (Nc != 1) ant[I] = backup[I]; if (resultAntsPath.size() >= MIN_RESULT_PATH_NUM_FOR_ANT) // its order after renew state is to avoid update pheromone break; i = I % Vs; while (true) { numerator = 0.0; denominator = 0.0; drand = (double)(rand() % 10000) / 10001.0; bool alreadyGreaterThandrand = false; currentPosition = specifiedPosition.at(ant[I].route.nodePath.back()); for (j = 0; j < Vs; j++) // permitted { if (currentPosition != j && ant[I].visited[j] == false && forbiddenPath.count(make_pair(currentPosition, j)) == 0) { antArc = TSPPath2AntArc.at(TSPPath(currentPosition, j)); denominator += pow(antArc.tau, alpha) * pow(antArc.eta, beta); } } for (j = 0; j < Vs; j++) // permitted { if (currentPosition != j && ant[I].visited[j] == false && forbiddenPath.count(make_pair(currentPosition, j)) == 0) { antArc = TSPPath2AntArc.at(TSPPath(currentPosition, j)); if (alreadyGreaterThandrand == false) numerator += pow(antArc.tau, alpha) * pow(antArc.eta, beta) / denominator; if (numerator > drand) { alreadyGreaterThandrand = true; routeValidator.assign(ant[I].route.nodePath.begin(), ant[I].route.nodePath.end()); routeValidator.insert(routeValidator.end(), P_i_j[currentPosition][j].nodePath.begin()+1, P_i_j[currentPosition][j].nodePath.end()); if (isReplicate(routeValidator) == false) // it indicates loopless { ant[I].route += P_i_j[currentPosition][j]; itv = P_i_j[currentPosition][j].nodePath.begin(); ++itv; for (; itv != P_i_j[currentPosition][j].nodePath.end(); ++itv) { if (specifiedPosition.find(*itv) != specifiedPosition.end()) // if (binarySearch(specifiedNode, *itv) == true) { ant[I].visited[specifiedPosition.at(*itv)] = true; ant[I].routeRecord.push_back(specifiedPosition.at(*itv)); } } break; } } } // end if } // end for if (ant[I].route.visitingSpecifiedNodes == Vs) { ant[I].specifiedNodeEnough = true; break; } if (j == Vs) // it indicates can't find a loopless path join for any j fits numerator > drand { ant[I].noNodeToGo = true; break; } } // end while (true) if (ant[I].specifiedNodeEnough == true) { for (k = 0; k < resultAntsPath.size(); k++) if (resultAntsPath[k].costSum == ant[I].route.costSum && resultAntsPath[k].nodePath.size() == ant[I].route.nodePath.size()) break; if (k == resultAntsPath.size()) resultAntsPath.push_back(ant[I].route); } } if (resultAntsPath.size() >= MIN_RESULT_PATH_NUM_FOR_ANT) break; #if CONSOLE_INFO cout << "========== In iteration " << Nc << " ==========" << endl << "ant: "; for (i = 0; i < antNum; i++) cout << ant[i].noNodeToGo << ' '; cout << endl; #endif // =============== update delta tau for ant =============== for (i = 0; i < antNum; i++) { if (ant[i].noNodeToGo == false) for (k = 0; k < ant[i].routeRecord.size()-1; k++) TSPPath2AntArc.at(TSPPath(ant[i].routeRecord[k], ant[i].routeRecord[k+1])).delta_tau += antQ1 / ant[i].route.costSum; else { if (ant[i].routeRecord.size() < 3) continue; for (k = 0; k < ant[i].routeRecord.size()-3; k++) TSPPath2AntArc.at(TSPPath(ant[i].routeRecord[k], ant[i].routeRecord[k+1])).delta_tau += antQ2 / ant[i].route.costSum; for (k = ant[i].routeRecord.size()-3; k < ant[i].routeRecord.size()-1; k++) TSPPath2AntArc.at(TSPPath(ant[i].routeRecord[k], ant[i].routeRecord[k+1])).delta_tau -= antQ3 / ant[i].route.costSum; } } // =============== update tau for ant =============== for (i = 0; i < Vs; i++) { for (j = 0; j < Vs; j++) { if (i != j && P_i_j[i][j].costSum != INF) { pAntArc = &TSPPath2AntArc.at(TSPPath(i, j)); pAntArc->tau = (1 - rho)*pAntArc->tau + pAntArc->delta_tau; pAntArc->tau = (pAntArc->tau < tao_min) ? tao_min : pAntArc->tau; pAntArc->tau = (pAntArc->tau > tao_max) ? tao_max : pAntArc->tau; } } } // =============== clear delta tau for ant =============== for (i = 0; i < antNum; i++) for (k = 0; k < ant[i].routeRecord.size()-1; k++) TSPPath2AntArc.at(TSPPath(ant[i].routeRecord[k], ant[i].routeRecord[k+1])).delta_tau = 0.0; } // =============== Iteration ends ... =============== forbiddenPath.clear(); TSPPath2AntArc.clear(); // ================================================================================================================================== // =============== join the path from src to ant route's back node and the path from ant route's back node to dst =============== // ================================================================================================================================== vector<Path> admissiblePath; Path antRouteBack2dst, P_s_t; P_s_t.costSum = INF; int routeBack; vector<int> nodePathBackup; restoreSpecifiedNodes(NodeList, vector<int>(1, dst), isRemoved); // restore dst in the graph, src hasn't been restored yet // =============== join the last path to dst for resultAntsPath =============== for (i = 0; i < resultAntsPath.size(); i++) { nodePathBackup.assign(resultAntsPath[i].nodePath.begin(), resultAntsPath[i].nodePath.end()); routeBack = nodePathBackup.back(); removeListOfNodes(NodeList, nodePathBackup, isRemoved); if (NodeNum < 1000) dijkstra(NodeList, NodeNum, routeBack); else BFS(NodeList, NodeNum, routeBack); if (dist[dst] != INF) { recordNodeRoute(antRouteBack2dst, pi, routeBack, dst); recordArcRoute(antRouteBack2dst, arcRecord, pi, routeBack, dst); resultAntsPath[i] += antRouteBack2dst; admissiblePath.push_back(resultAntsPath[i]); if (P_s_t.costSum > resultAntsPath[i].costSum) P_s_t = resultAntsPath[i]; antRouteBack2dst.clear(); } restoreListOfNodes(NodeList, nodePathBackup, isRemoved); removeSpecifiedNodes(NodeList, vector<int>(1, src), isRemoved); // avoid restoring src wrongly by restoreListOfNodes(NodeList, nodePathBackup, isRemoved) } restoreSpecifiedNodes(NodeList, vector<int>(1, src), isRemoved); // =============== free memory =============== for (i = 0; i < resultAntsPath.size(); i++) resultAntsPath[i].clear(); resultAntsPath.clear(); resultAntsPath.shrink_to_fit(); bestPath = P_s_t; #if CONSOLE_INFO cout << "========== P_s_t(" << admissiblePath.size() << "): ==========" << endl; cout << "P_s_t.nodePath: "; for (k = 0; k < P_s_t.nodePath.size(); k++) cout << P_s_t.nodePath[k] << ' '; cout << endl << "P_s_t.arcPath: "; for (k = 0; k < P_s_t.arcPath.size(); k++) cout << P_s_t.arcPath[k] << ' '; cout << endl << "P_s_t.costSum: " << P_s_t.costSum << endl; #endif // =============== free memory =============== for (i = 0; i < antNum; i++) ant[i].clear(); for (i = 0; i < antNum; i++) backup[i].clear(); for (i = 0; i < admissiblePath.size(); i++) admissiblePath[i].clear(); admissiblePath.clear(); admissiblePath.shrink_to_fit(); specifiedPosition.clear(); #if FILE_INFO fout.close(); #endif delete []P_s_v_i; delete []P_i_j; delete []P_v_i_v_j; delete []ant; // !!!!!!!!!! there exists a problem, sometimes it will failed !!!!!!!!!! delete []backup; delete []isRemoved; } void antGroupAlgorithm(Node *NodeList, int NodeNum, int src, int dst, vector<int>& specifiedNode1, vector<int>& specifiedNode2, Path &bestPath1, Path &bestPath2, bool USE_DIJKSTRA, unsigned int seed) { #if FILE_INFO ofstream fout; fout.open(INFO_FILE_PATH, ios_base::out | ios_base::trunc); if (!fout.is_open()) { cerr << "Cannot open info_file.txt!" << endl; return; } #endif size_t i, j, k; size_t Vs1 = specifiedNode1.size(), Vs2 = specifiedNode2.size(); size_t antNum1 = ANTS_EACH_SPECIFIED_NODE * Vs1; size_t antNum2 = ANTS_EACH_SPECIFIED_NODE * Vs2; if (Vs1 < 25) MIN_RESULT_PATH_NUM_FOR_ANT1 = 27 - Vs1 / 5 * 3; // 27 24 21 18 15 else if (Vs1 >= 25 && Vs1 < 50) MIN_RESULT_PATH_NUM_FOR_ANT1 = 18 - Vs1 / 5; // 13 12 11 10 9 else MIN_RESULT_PATH_NUM_FOR_ANT1 = 12 - Vs1 / 10; // 7 6 5 4 3 2 if (Vs2 < 25) MIN_RESULT_PATH_NUM_FOR_ANT2 = 27 - Vs2 / 5 * 3; // 27 24 21 18 15 else if (Vs2 >= 25 && Vs2 < 50) MIN_RESULT_PATH_NUM_FOR_ANT2 = 18 - Vs2 / 5; // 13 12 11 10 9 else MIN_RESULT_PATH_NUM_FOR_ANT2 = 12 - Vs2 / 10; // 7 6 5 4 3 2 // =============== define complexity of the problem, according to the scale of this graph =============== ComplexityDescription complexity = defineComplexity(NodeNum, Vs1, Vs2); adjustParameters(complexity); bool *isRemoved = new bool[NodeNum]; for (i = 0; i < (size_t)NodeNum; i++) isRemoved[i] = false; unordered_map<int, size_t> specifiedPosition1, specifiedPosition2; for (i = 0; i < specifiedNode1.size(); i++) specifiedPosition1.insert(make_pair(specifiedNode1[i], i)); for (i = 0; i < specifiedNode2.size(); i++) specifiedPosition2.insert(make_pair(specifiedNode2[i], i)); Path *P_s_v_i1 = new Path[Vs1]; Path *P_s_v_i2 = new Path[Vs2]; Path *P_v_i_v_j1 = new Path[Vs1*Vs1]; Path *P_v_i_v_j2 = new Path[Vs2*Vs2]; Path **P_i_j1 = new Path*[Vs1]; // a point array, convenient to use form P_i_j1[i][j] Path **P_i_j2 = new Path*[Vs2]; // a point array, convenient to use form P_i_j2[i][j] for (i = 0; i < Vs1; i++) P_i_j1[i] = P_v_i_v_j1 + i*Vs1; for (i = 0; i < Vs2; i++) P_i_j2[i] = P_v_i_v_j2 + i*Vs2; removeSpecifiedNodes(NodeList, vector<int>(1, dst), isRemoved); obtainPathFromSrcToSpecifiedNodes(NodeList, NodeNum, src, P_s_v_i1, specifiedNode1, USE_DIJKSTRA); obtainPathFromSrcToSpecifiedNodes(NodeList, NodeNum, src, P_s_v_i2, specifiedNode2, USE_DIJKSTRA); removeSpecifiedNodes(NodeList, vector<int>(1, src), isRemoved); obtainPathBetweenSpecifiedNodes(NodeList, NodeNum, P_i_j1, specifiedNode1, USE_DIJKSTRA); obtainPathBetweenSpecifiedNodes(NodeList, NodeNum, P_i_j2, specifiedNode2, USE_DIJKSTRA); #if CONSOLE_DEBUG for (i = 0; i < Vs1; i++) for (j = 0; j < Vs1; j++) printVector(P_i_j1[i][j].nodePath, "P_i_j1[i][j].nodePath: "); for (i = 0; i < Vs2; i++) for (j = 0; j < Vs2; j++) printVector(P_i_j2[i][j].nodePath, "P_i_j2[i][j].nodePath: "); #endif #if USE_MU_TO_REDUCE_IDENTICAL_ARCS initArcID2InPath(P_s_v_i1, P_s_v_i2, P_i_j1, P_i_j2, Vs1, Vs2); #endif AntArc antArc, *pAntArc; for (i = 0; i < Vs1; i++) { for (j = 0; j < Vs1; j++) { if (i != j || P_i_j1[i][j].costSum != INF) { antArc.eta = eta0 / P_i_j1[i][j].costSum; TSPPath2AntArc1.insert(make_pair(TSPPath(i, j), antArc)); } } } for (i = 0; i < Vs2; i++) { for (j = 0; j < Vs2; j++) { if (i != j || P_i_j2[i][j].costSum != INF) { antArc.eta = eta0 / P_i_j2[i][j].costSum; TSPPath2AntArc2.insert(make_pair(TSPPath(i, j), antArc)); } } } vector<int>::iterator itv; set<pair<size_t, size_t> > forbiddenPath1, forbiddenPath2; obtainForbiddenPath(NodeList, P_i_j1, specifiedNode1, forbiddenPath1, src); obtainForbiddenPath(NodeList, P_i_j2, specifiedNode2, forbiddenPath2, src); #if USE_MU_TO_REDUCE_IDENTICAL_ARCS #if CONSOLE_INFO cout << "cnt1: "; #endif expandForbiddenPath(P_i_j1, Vs1, specifiedNode2, forbiddenPath1); #if CONSOLE_INFO cout << endl << "cnt2: "; #endif expandForbiddenPath(P_i_j2, Vs2, specifiedNode1, forbiddenPath2); #if CONSOLE_INFO cout << endl; #endif #endif // ========== initialize all the ants ========== Ant *ant1 = new Ant[antNum1]; Ant *ant2 = new Ant[antNum2]; Ant *backup1 = new Ant[antNum1]; Ant *backup2 = new Ant[antNum2]; for (i = 0; i < antNum1; i++) { for (itv = P_s_v_i1[i % Vs1].nodePath.begin(); itv != P_s_v_i1[i % Vs1].nodePath.end(); ++itv) { ant1[i].route.nodePath.push_back(*itv); if (specifiedPosition1.find(*itv) != specifiedPosition1.end()) // if (binarySearch(specifiedNode1, *itv) == true) { ant1[i].visited[specifiedPosition1.at(*itv)] = true; ant1[i].route.visitingSpecifiedNodes++; ant1[i].routeRecord.push_back(specifiedPosition1.at(*itv)); } } ant1[i].route.arcPath.assign(P_s_v_i1[i % Vs1].arcPath.begin(), P_s_v_i1[i % Vs1].arcPath.end()); ant1[i].route.costSum = P_s_v_i1[i % Vs1].costSum; } for (i = 0; i < antNum2; i++) { for (itv = P_s_v_i2[i % Vs2].nodePath.begin(); itv != P_s_v_i2[i % Vs2].nodePath.end(); ++itv) { ant2[i].route.nodePath.push_back(*itv); if (specifiedPosition2.find(*itv) != specifiedPosition2.end()) // if (binarySearch(specifiedNode2, *itv) == true) { ant2[i].visited[specifiedPosition2.at(*itv)] = true; ant2[i].route.visitingSpecifiedNodes++; ant2[i].routeRecord.push_back(specifiedPosition2.at(*itv)); } } ant2[i].route.arcPath.assign(P_s_v_i2[i % Vs2].arcPath.begin(), P_s_v_i2[i % Vs2].arcPath.end()); ant2[i].route.costSum = P_s_v_i2[i % Vs2].costSum; } #if FILE_INFO fout << "=============== ant1[i]: ===============" << endl; for (i = 0; i < Vs1; i++) { fout << "ant1[i].route[" << i << "].nodePath: "; for (k = 0; k < ant1[i].route.nodePath.size(); k++) fout << ant1[i].route.nodePath[k] << ' '; fout << "\tvisitingSpecifiedNodes: " << ant1[i].route.visitingSpecifiedNodes << endl; fout << "ant1[i].route[" << i << "].arcPath: "; for (k = 0; k < ant1[i].route.arcPath.size(); k++) fout << ant1[i].route.arcPath[k] << ' '; fout << "\tcostSum: " << ant1[i].route.costSum << endl; } fout << endl << "=============== ant2[i]: ===============" << endl; for (i = 0; i < Vs2; i++) { fout << "ant2[i].route[" << i << "].nodePath: "; for (k = 0; k < ant2[i].route.nodePath.size(); k++) fout << ant2[i].route.nodePath[k] << ' '; fout << "\tvisitingSpecifiedNodes: " << ant2[i].route.visitingSpecifiedNodes << endl; fout << "ant2[i].route[" << i << "].arcPath: "; for (k = 0; k < ant2[i].route.arcPath.size(); k++) fout << ant2[i].route.arcPath[k] << ' '; fout << "\tcostSum: " << ant2[i].route.costSum << endl; } #endif for (i = 0; i < antNum1; i++) backup1[i] = ant1[i]; for (i = 0; i < antNum2; i++) backup2[i] = ant2[i]; // ======================================================== // =============== Iteration begins ... =============== // ======================================================== srand(seed); vector<int> routeValidator; vector<Path> resultAntsPath1, resultAntsPath2; for (unsigned int Nc = 1; Nc <= MAX_ITERATION_FOR_ANT_ALGORITHM; Nc++) { size_t I; size_t currentPosition; double numerator, denominator, drand; // =============== ants aiming for specified nodes set 1 start to go !!! =============== for (I = 0; I < antNum1; I++) { if (Nc != 1) ant1[I] = backup1[I]; if (resultAntsPath1.size() >= MIN_RESULT_PATH_NUM_FOR_ANT1) // its order after renew state is to avoid update pheromone break; i = I % Vs1; while (true) { numerator = 0.0; denominator = 0.0; drand = (double)(rand() % 10000) / 10001.0; bool alreadyGreaterThandrand = false; currentPosition = specifiedPosition1.at(ant1[I].route.nodePath.back()); for (j = 0; j < Vs1; j++) // permitted { if (currentPosition != j && ant1[I].visited[j] == false && forbiddenPath1.count(make_pair(currentPosition, j)) == 0) { antArc = TSPPath2AntArc1.at(TSPPath(currentPosition, j)); #if USE_MU_TO_REDUCE_IDENTICAL_ARCS denominator += pow(antArc.tau, alpha) * pow(antArc.eta, beta) * pow(antArc.mu, nu); #else denominator += pow(antArc.tau, alpha) * pow(antArc.eta, beta); #endif } } for (j = 0; j < Vs1; j++) // permitted { if (currentPosition != j && ant1[I].visited[j] == false && forbiddenPath1.count(make_pair(currentPosition, j)) == 0) { antArc = TSPPath2AntArc1.at(TSPPath(currentPosition, j)); if (alreadyGreaterThandrand == false) { #if USE_MU_TO_REDUCE_IDENTICAL_ARCS numerator += pow(antArc.tau, alpha) * pow(antArc.eta, beta) * pow(antArc.mu, nu) / denominator; #else numerator += pow(antArc.tau, alpha) * pow(antArc.eta, beta) / denominator; #endif } if (numerator > drand) { alreadyGreaterThandrand = true; routeValidator.assign(ant1[I].route.nodePath.begin(), ant1[I].route.nodePath.end()); routeValidator.insert(routeValidator.end(), P_i_j1[currentPosition][j].nodePath.begin()+1, P_i_j1[currentPosition][j].nodePath.end()); if (isReplicate(routeValidator) == false) // it indicates loopless { ant1[I].route += P_i_j1[currentPosition][j]; itv = P_i_j1[currentPosition][j].nodePath.begin(); ++itv; for (; itv != P_i_j1[currentPosition][j].nodePath.end(); ++itv) { if (specifiedPosition1.find(*itv) != specifiedPosition1.end()) // if (binarySearch(specifiedNode1, *itv) == true) { ant1[I].visited[specifiedPosition1.at(*itv)] = true; ant1[I].routeRecord.push_back(specifiedPosition1.at(*itv)); } } break; } } } // end if } // end for if (ant1[I].route.visitingSpecifiedNodes == Vs1) { ant1[I].specifiedNodeEnough = true; break; } if (j == Vs1) // it indicates can't find a loopless path join for any j fits numerator > drand { ant1[I].noNodeToGo = true; break; } } // end while (true) if (ant1[I].specifiedNodeEnough == true) { for (k = 0; k < resultAntsPath1.size(); k++) if (resultAntsPath1[k].costSum == ant1[I].route.costSum && resultAntsPath1[k].nodePath.size() == ant1[I].route.nodePath.size()) break; if (k == resultAntsPath1.size()) resultAntsPath1.push_back(ant1[I].route); } } // =============== ants aiming for specified nodes set 2 start to go !!! =============== for (I = 0; I < antNum2; I++) { if (Nc != 1) ant2[I] = backup2[I]; if (resultAntsPath2.size() >= MIN_RESULT_PATH_NUM_FOR_ANT2) // its order after renew state is to avoid update pheromone break; i = I % Vs2; while (true) { numerator = 0.0; denominator = 0.0; drand = (double)(rand() % 10000) / 10001.0; bool alreadyGreaterThandrand = false; currentPosition = specifiedPosition2.at(ant2[I].route.nodePath.back()); for (j = 0; j < Vs2; j++) // permitted { if (currentPosition != j && ant2[I].visited[j] == false && forbiddenPath2.count(make_pair(currentPosition, j)) == 0) { antArc = TSPPath2AntArc2.at(TSPPath(currentPosition, j)); #if USE_MU_TO_REDUCE_IDENTICAL_ARCS denominator += pow(antArc.tau, alpha) * pow(antArc.eta, beta) * pow(antArc.mu, nu); #else denominator += pow(antArc.tau, alpha) * pow(antArc.eta, beta); #endif } } for (j = 0; j < Vs2; j++) // permitted { if (currentPosition != j && ant2[I].visited[j] == false && forbiddenPath2.count(make_pair(currentPosition, j)) == 0) { antArc = TSPPath2AntArc2.at(TSPPath(currentPosition, j)); if (alreadyGreaterThandrand == false) { #if USE_MU_TO_REDUCE_IDENTICAL_ARCS numerator += pow(antArc.tau, alpha) * pow(antArc.eta, beta) * pow(antArc.mu, nu) / denominator; #else numerator += pow(antArc.tau, alpha) * pow(antArc.eta, beta) / denominator; #endif } if (numerator > drand) { alreadyGreaterThandrand = true; routeValidator.assign(ant2[I].route.nodePath.begin(), ant2[I].route.nodePath.end()); routeValidator.insert(routeValidator.end(), P_i_j2[currentPosition][j].nodePath.begin()+1, P_i_j2[currentPosition][j].nodePath.end()); if (isReplicate(routeValidator) == false) // it indicates loopless { ant2[I].route += P_i_j2[currentPosition][j]; itv = P_i_j2[currentPosition][j].nodePath.begin(); ++itv; for (; itv != P_i_j2[currentPosition][j].nodePath.end(); ++itv) { if (specifiedPosition2.find(*itv) != specifiedPosition2.end()) // if (binarySearch(specifiedNode2, *itv) == true) { ant2[I].visited[specifiedPosition2.at(*itv)] = true; ant2[I].routeRecord.push_back(specifiedPosition2.at(*itv)); } } break; } } } // end if } // end for if (ant2[I].route.visitingSpecifiedNodes == Vs2) { ant2[I].specifiedNodeEnough = true; break; } if (j == Vs2) // it indicates can't find a loopless path join for any j fits numerator > drand { ant2[I].noNodeToGo = true; break; } } // end while (true) if (ant2[I].specifiedNodeEnough == true) { for (k = 0; k < resultAntsPath2.size(); k++) if (resultAntsPath2[k].costSum == ant2[I].route.costSum && resultAntsPath2[k].nodePath.size() == ant2[I].route.nodePath.size()) break; if (k == resultAntsPath2.size()) resultAntsPath2.push_back(ant2[I].route); } } if (resultAntsPath1.size() >= MIN_RESULT_PATH_NUM_FOR_ANT1 && resultAntsPath2.size() >= MIN_RESULT_PATH_NUM_FOR_ANT2) break; #if CONSOLE_INFO cout << "========== In iteration " << Nc << " ==========" << endl << "ant1: "; for (i = 0; i < antNum1; i++) cout << ant1[i].noNodeToGo << ' '; cout << endl << "ant2: "; for (i = 0; i < antNum2; i++) cout << ant2[i].noNodeToGo << ' '; cout << endl; #endif // =============== update delta tau for ant1 =============== for (i = 0; i < antNum1; i++) { if (ant1[i].noNodeToGo == false) for (k = 0; k < ant1[i].routeRecord.size()-1; k++) TSPPath2AntArc1.at(TSPPath(ant1[i].routeRecord[k], ant1[i].routeRecord[k+1])).delta_tau += antQ1 / ant1[i].route.costSum; else { if (ant1[i].routeRecord.size() < 3) continue; for (k = 0; k < ant1[i].routeRecord.size()-3; k++) TSPPath2AntArc1.at(TSPPath(ant1[i].routeRecord[k], ant1[i].routeRecord[k+1])).delta_tau += antQ2 / ant1[i].route.costSum; for (k = ant1[i].routeRecord.size()-3; k < ant1[i].routeRecord.size()-1; k++) TSPPath2AntArc1.at(TSPPath(ant1[i].routeRecord[k], ant1[i].routeRecord[k+1])).delta_tau -= antQ3 / ant1[i].route.costSum; } } // =============== update delta tau for ant2 =============== for (i = 0; i < antNum2; i++) { if (ant2[i].noNodeToGo == false) for (k = 0; k < ant2[i].routeRecord.size()-1; k++) TSPPath2AntArc2.at(TSPPath(ant2[i].routeRecord[k], ant2[i].routeRecord[k+1])).delta_tau += antQ1 / ant2[i].route.costSum; else { if (ant2[i].routeRecord.size() < 3) continue; for (k = 0; k < ant2[i].routeRecord.size()-3; k++) TSPPath2AntArc2.at(TSPPath(ant2[i].routeRecord[k], ant2[i].routeRecord[k+1])).delta_tau += antQ2 / ant2[i].route.costSum; for (k = ant2[i].routeRecord.size()-3; k < ant2[i].routeRecord.size()-1; k++) TSPPath2AntArc2.at(TSPPath(ant2[i].routeRecord[k], ant2[i].routeRecord[k+1])).delta_tau -= antQ3 / ant2[i].route.costSum; } } // =============== update tau for ant1 =============== for (i = 0; i < Vs1; i++) { for (j = 0; j < Vs1; j++) { if (i != j && P_i_j1[i][j].costSum != INF) { pAntArc = &TSPPath2AntArc1.at(TSPPath(i, j)); pAntArc->tau = (1 - rho)*pAntArc->tau + pAntArc->delta_tau; pAntArc->tau = (pAntArc->tau < tao_min) ? tao_min : pAntArc->tau; pAntArc->tau = (pAntArc->tau > tao_max) ? tao_max : pAntArc->tau; } } } // =============== update tau for ant2 =============== for (i = 0; i < Vs2; i++) { for (j = 0; j < Vs2; j++) { if (i != j && P_i_j2[i][j].costSum != INF) { pAntArc = &TSPPath2AntArc2.at(TSPPath(i, j)); pAntArc->tau = (1 - rho)*pAntArc->tau + pAntArc->delta_tau; pAntArc->tau = (pAntArc->tau < tao_min) ? tao_min : pAntArc->tau; pAntArc->tau = (pAntArc->tau > tao_max) ? tao_max : pAntArc->tau; } } } // =============== clear delta tau for ant1 =============== for (i = 0; i < antNum1; i++) for (k = 0; k < ant1[i].routeRecord.size()-1; k++) TSPPath2AntArc1.at(TSPPath(ant1[i].routeRecord[k], ant1[i].routeRecord[k+1])).delta_tau = 0.0; // =============== clear delta tau for ant2 =============== for (i = 0; i < antNum2; i++) for (k = 0; k < ant2[i].routeRecord.size()-1; k++) TSPPath2AntArc2.at(TSPPath(ant2[i].routeRecord[k], ant2[i].routeRecord[k+1])).delta_tau = 0.0; #if USE_MU_TO_REDUCE_IDENTICAL_ARCS // =============== update mu for ant1 =============== for (i = 0; i < antNum1; i++) { for (k = 0; k < ant1[i].route.arcPath.size(); k++) arcID2InPath.at(ant1[i].route.arcPath[k]) = 1; for (j = 0; j < antNum2; j++) { for (k = 0; k < ant2[j].routeRecord.size()-1; k++) { int from = ant2[j].routeRecord[k], to = ant2[j].routeRecord[k+1]; int repassArcCount = 0; for (itv = P_i_j2[from][to].arcPath.begin(); itv != P_i_j2[from][to].arcPath.end(); ++itv) repassArcCount += arcID2InPath.at(*itv); TSPPath2AntArc2.at(TSPPath(from, to)).mu *= (1.0 - (double)repassArcCount * mu_attenuation); } } for (k = 0; k < ant1[i].route.arcPath.size(); k++) arcID2InPath.at(ant1[i].route.arcPath[k]) = 0; } // =============== update mu for ant2 =============== for (i = 0; i < antNum2; i++) { for (k = 0; k < ant2[i].route.arcPath.size(); k++) arcID2InPath.at(ant2[i].route.arcPath[k]) = 1; for (j = 0; j < antNum1; j++) { for (k = 0; k < ant1[j].routeRecord.size()-1; k++) { int from = ant1[j].routeRecord[k], to = ant1[j].routeRecord[k+1]; int repassArcCount = 0; for (itv = P_i_j1[from][to].arcPath.begin(); itv != P_i_j1[from][to].arcPath.end(); ++itv) repassArcCount += arcID2InPath.at(*itv); TSPPath2AntArc1.at(TSPPath(from, to)).mu *= (1.0 - (double)repassArcCount * mu_attenuation); } } for (k = 0; k < ant2[i].route.arcPath.size(); k++) arcID2InPath.at(ant2[i].route.arcPath[k]) = 0; } #endif } // =============== Iteration ends ... =============== forbiddenPath1.clear(); forbiddenPath2.clear(); TSPPath2AntArc1.clear(); TSPPath2AntArc2.clear(); #if USE_MU_TO_REDUCE_IDENTICAL_ARCS arcID2InPath.clear(); #endif // ================================================================================================================================== // =============== join the path from src to ant route's back node and the path from ant route's back node to dst =============== // ================================================================================================================================== vector<Path> admissiblePath1, admissiblePath2; Path antRouteBack2dst, P_s_t1, P_s_t2; P_s_t1.costSum = INF; P_s_t2.costSum = INF; int routeBack; vector<int> nodePathBackup; restoreSpecifiedNodes(NodeList, vector<int>(1, dst), isRemoved); // restore dst in the graph, src hasn't been restored yet // =============== join the last path to dst for resultAntsPath1 =============== for (i = 0; i < resultAntsPath1.size(); i++) { nodePathBackup.assign(resultAntsPath1[i].nodePath.begin(), resultAntsPath1[i].nodePath.end()); routeBack = nodePathBackup.back(); removeListOfNodes(NodeList, nodePathBackup, isRemoved); if (NodeNum < 1000) dijkstra(NodeList, NodeNum, routeBack); else BFS(NodeList, NodeNum, routeBack); if (dist[dst] != INF) { recordNodeRoute(antRouteBack2dst, pi, routeBack, dst); recordArcRoute(antRouteBack2dst, arcRecord, pi, routeBack, dst); resultAntsPath1[i] += antRouteBack2dst; admissiblePath1.push_back(resultAntsPath1[i]); if (P_s_t1.costSum > resultAntsPath1[i].costSum) P_s_t1 = resultAntsPath1[i]; antRouteBack2dst.clear(); } restoreListOfNodes(NodeList, nodePathBackup, isRemoved); removeSpecifiedNodes(NodeList, vector<int>(1, src), isRemoved); // avoid restoring src wrongly by restoreListOfNodes(NodeList, nodePathBackup, isRemoved) } // =============== join the last path to dst for resultAntsPath2 =============== for (i = 0; i < resultAntsPath2.size(); i++) { nodePathBackup.assign(resultAntsPath2[i].nodePath.begin(), resultAntsPath2[i].nodePath.end()); routeBack = nodePathBackup.back(); removeListOfNodes(NodeList, nodePathBackup, isRemoved); if (NodeNum < 1000) dijkstra(NodeList, NodeNum, routeBack); else BFS(NodeList, NodeNum, routeBack); if (dist[dst] != INF) { recordNodeRoute(antRouteBack2dst, pi, routeBack, dst); recordArcRoute(antRouteBack2dst, arcRecord, pi, routeBack, dst); resultAntsPath2[i] += antRouteBack2dst; admissiblePath2.push_back(resultAntsPath2[i]); if (P_s_t2.costSum > resultAntsPath2[i].costSum) P_s_t2 = resultAntsPath2[i]; antRouteBack2dst.clear(); } restoreListOfNodes(NodeList, nodePathBackup, isRemoved); removeSpecifiedNodes(NodeList, vector<int>(1, src), isRemoved); // avoid restoring src wrongly by restoreListOfNodes(NodeList, nodePathBackup, isRemoved) } restoreSpecifiedNodes(NodeList, vector<int>(1, src), isRemoved); // =============== free memory =============== for (i = 0; i < resultAntsPath1.size(); i++) resultAntsPath1[i].clear(); for (i = 0; i < resultAntsPath2.size(); i++) resultAntsPath2[i].clear(); resultAntsPath1.clear(); resultAntsPath2.clear(); resultAntsPath1.shrink_to_fit(); resultAntsPath2.shrink_to_fit(); // ====================================================================================================================== // =============== select the best combaination path pair between admissiblePath1 and admissiblePath2 =============== // ====================================================================================================================== size_t admissiblePathCount1 = admissiblePath1.size(), admissiblePathCount2 = admissiblePath2.size(); int minIdenticalArcNum = INF, minCostAddedup = INF; for (i = 0; i < admissiblePathCount1; i++) { for (j = 0; j < admissiblePathCount2; j++) { int currentIdenticalArcNum = identicalElementNum(admissiblePath1[i].arcPath, admissiblePath2[j].arcPath); int currentCostAddedup = admissiblePath1[i].costSum + admissiblePath2[j].costSum; if (minIdenticalArcNum > currentIdenticalArcNum || (minIdenticalArcNum == currentIdenticalArcNum && minCostAddedup > currentCostAddedup)) { P_s_t1 = admissiblePath1[i]; P_s_t2 = admissiblePath2[j]; minIdenticalArcNum = currentIdenticalArcNum; minCostAddedup = currentCostAddedup; } } } bestPath1 = P_s_t1; bestPath2 = P_s_t2; #if CONSOLE_INFO cout << "========== P_s_t1(" << admissiblePathCount1 << "): ==========" << endl; cout << "P_s_t1.nodePath: "; for (k = 0; k < P_s_t1.nodePath.size(); k++) cout << P_s_t1.nodePath[k] << ' '; cout << endl << "P_s_t1.arcPath: "; for (k = 0; k < P_s_t1.arcPath.size(); k++) cout << P_s_t1.arcPath[k] << ' '; cout << endl << "P_s_t1.costSum: " << P_s_t1.costSum << endl; cout << "========== P_s_t2(" << admissiblePathCount2 << "): ==========" << endl; cout << "P_s_t2.nodePath: "; for (k = 0; k < P_s_t2.nodePath.size(); k++) cout << P_s_t2.nodePath[k] << ' '; cout << endl << "P_s_t2.arcPath: "; for (k = 0; k < P_s_t2.arcPath.size(); k++) cout << P_s_t2.arcPath[k] << ' '; cout << endl << "P_s_t2.costSum: " << P_s_t2.costSum << endl; cout << "identical ArcNum: " << minIdenticalArcNum << "\t\t\t\tcostSum - Added up: " << P_s_t1.costSum + P_s_t2.costSum << endl << endl; #endif // =============== free memory =============== for (i = 0; i < antNum1; i++) ant1[i].clear(); for (i = 0; i < antNum1; i++) backup1[i].clear(); for (i = 0; i < admissiblePath1.size(); i++) admissiblePath1[i].clear(); for (i = 0; i < admissiblePath2.size(); i++) admissiblePath2[i].clear(); admissiblePath1.clear(); admissiblePath2.clear(); admissiblePath1.shrink_to_fit(); admissiblePath2.shrink_to_fit(); specifiedPosition1.clear(); specifiedPosition2.clear(); #if FILE_INFO fout.close(); #endif delete []P_s_v_i1; delete []P_s_v_i2; delete []P_i_j1; delete []P_i_j2; delete []P_v_i_v_j1; delete []P_v_i_v_j2; delete []ant1; delete []ant2; // !!!!!!!!!! there exists a problem, sometimes it will failed !!!!!!!!!! delete []backup1; delete []backup2; delete []isRemoved; }
main.cxx:
/************************************************************************************* * @author: Lv chon chon * * @email: xmutongxinXuLe@163.com, 276843223@qq.com * * This file is part of 2016 Huawei CodeCraft solution <http://codecraft.huawei.com> * *************************************************************************************/ #define RUNNING_TIME_HIGH_PRECISION 0 #if RUNNING_TIME_HIGH_PRECISION #include <sys/time.h> #else #include <time.h> #endif #include "Ant.hxx" using namespace std; #define RELEASE 0 #define USE_DIJKSTRA_FIRST 1 #define EXTRA_HOP_COUNT 3 #define MAX_ROLLBACK_HOP_COUNT 3 #define MAX_GO_AHEAD_HOP_COUNT 3 #define REPLACE_WORK_PATH_ACTION(nodePath, arcPath, itNodeStart, itNodeEnd, itArcStart, itArcEnd, nodePathHashSet) \ while (itNodeStart != itNodeEnd) \ { \ nodePathHashSet.erase(*itNodeStart); \ itNodeStart = nodePath.erase(itNodeStart); \ } \ for (itrl = replacedNodeID.rbegin(); itrl != replacedNodeID.rend(); ++itrl) \ { \ nodePathHashSet.insert(*itrl); \ itNodeStart = nodePath.insert(itNodeStart, *itrl); \ } \ int pos = arcPathHashMap1.at(*itArcStart); \ while (itArcStart != itArcEnd1) \ { \ costSum1 -= arcID2Cost.at(*itArcStart); \ arcPathHashMap1.erase(*itArcStart); \ itArcStart = arcPath.erase(itArcStart); \ } \ pos += (int)replacedArcID.size() - 1; \ for (itrl = replacedArcID.rbegin(); itrl != replacedArcID.rend(); ++itrl, pos--) \ { \ costSum1 += arcID2Cost.at(*itrl); \ arcPathHashMap1.insert(make_pair(*itrl, pos)); \ itArcStart = arcPath.insert(itArcStart, *itrl); \ } \ pos += (int)replacedArcID.size() + 1; \ for (itl = itArcEnd; itl != arcPath.end(); ++itl, pos++) \ arcPathHashMap1.at(*itl) = pos; #define REPLACE_BACK_PATH_ACTION(nodePath, arcPath, itNodeStart, itNodeEnd, itArcStart, itArcEnd, nodePathHashSet) \ while (itNodeStart != itNodeEnd) \ { \ nodePathHashSet.erase(*itNodeStart); \ itNodeStart = nodePath.erase(itNodeStart); \ } \ for (itrl = replacedNodeID.rbegin(); itrl != replacedNodeID.rend(); ++itrl) \ { \ nodePathHashSet.insert(*itrl); \ itNodeStart = nodePath.insert(itNodeStart, *itrl); \ } \ while (itArcStart != itArcEnd) \ { \ costSum2 -= arcID2Cost.at(*itArcStart); \ itArcStart = arcPath.erase(itArcStart); \ } \ for (itrl = replacedArcID.rbegin(); itrl != replacedArcID.rend(); ++itrl) \ { \ costSum2 += arcID2Cost.at(*itrl); \ itArcStart = arcPath.insert(itArcStart, *itrl); \ } extern colortype color[]; extern int dist[]; extern int pi[]; extern int arcRecord[]; unordered_map<int, int> arcID2Cost; unordered_map<int, Arc*> arcID2Arc; #if USE_REVERSE_GRAPH unordered_map<int, rArc*> arcID2rArc; #endif unordered_map<int, int> workArcID2BackArcID; extern int dfn[]; list<set<int>* > block; list<pair<int, int> > bridge; int replacedByDijkstra(Node *NodeList, int NodeNum, int src, int dst, vector<int>& specifiedNodes1, vector<int>& specifiedNodes2, list<int>& nodePath1, list<int>& nodePath2, list<int>& arcPath1, list<int>& arcPath2, int& costSum1, int& costSum2) { size_t i, k; size_t Vs1 = specifiedNodes1.size(), Vs2 = specifiedNodes2.size(); list<int>::iterator itl, itl1, itl2; int identicalArcNum = identicalElementNum(arcPath1, arcPath2); // 1 =============== obtain specified nodes sequence in order in optimizeNeededPath =============== vector<int> specifiedNode1, specifiedNode2; unordered_map<int, unsigned int> specifiedPosition1, specifiedPosition2; itl = nodePath1.begin(); ++itl; for (i = 1; i < nodePath1.size()-1; ++itl, i++) { if (binarySearch(specifiedNodes1, *itl) == true) { specifiedNode1.push_back(*itl); specifiedPosition1.insert(make_pair(*itl, i)); } } itl = nodePath2.begin(); ++itl; for (i = 1; i < nodePath2.size()-1; ++itl, i++) { if (binarySearch(specifiedNodes2, *itl) == true) { specifiedNode2.push_back(*itl); specifiedPosition2.insert(make_pair(*itl, i)); } } // 2 =============== P(v_i, v_j), both v_i and v_j are in Vs =============== bool *isRemoved = new bool[NodeNum]; for (i = 0; i < (unsigned int)NodeNum; i++) isRemoved[i] = false; Path *P_i_j1 = new Path[Vs1-1]; Path *P_i_j2 = new Path[Vs2-1]; removeSpecifiedNodes(NodeList, vector<int>(1, src), isRemoved); removeSpecifiedNodes(NodeList, vector<int>(1, dst), isRemoved); #if TIMMING_INFO clock_t tBeginTime = clock(); #endif for (i = 0; i < Vs1-1; i++) { dijkstra(NodeList, NodeNum, specifiedNode1[i]); recordNodeRoute(P_i_j1[i], pi, specifiedNode1[i], specifiedNode1[i+1]); recordArcRoute(P_i_j1[i], arcRecord, pi, specifiedNode1[i], specifiedNode1[i+1]); } for (i = 0; i < Vs2-1; i++) { dijkstra(NodeList, NodeNum, specifiedNode2[i]); recordNodeRoute(P_i_j2[i], pi, specifiedNode2[i], specifiedNode2[i+1]); recordArcRoute(P_i_j2[i], arcRecord, pi, specifiedNode2[i], specifiedNode2[i+1]); } #if TIMMING_INFO clock_t tEndTime = clock(); double fCostTime = (double)(tEndTime - tBeginTime)/CLOCKS_PER_SEC; cout << "[clock] Dijkstra algorithm time = " << fCostTime << 's' << endl; #endif restoreSpecifiedNodes(NodeList, vector<int>(1, src), isRemoved); restoreSpecifiedNodes(NodeList, vector<int>(1, dst), isRemoved); // 3 =============== replace BFS path by dijkstra path =============== unsigned int begin, end; vector<int>::iterator itv; unordered_map<int, int> hashMap; #if CONSOLE_INFO cout << "Path1 could replace:"; #endif begin = specifiedPosition1.at(specifiedNode1[0]); for (i = 0; i < Vs1-1; i++) { bool couldReplace = true; end = specifiedPosition1.at(specifiedNode1[i+1]); if (P_i_j1[i].arcPath.size() == (end - begin)) // need to judge if the subpath is the same, if it is same, there is no need to replace { itl = arcPath1.begin(); for (k = 0; k < begin; k++) ++itl; for (itv = P_i_j1[i].arcPath.begin(); k < end; ++itv, ++itl, k++) if (*itl != *itv) break; if (k == end) // is same couldReplace = false; } if (couldReplace == true) // test if the replace action will lead to loop { for (itv = P_i_j1[i].nodePath.begin(); itv != P_i_j1[i].nodePath.end(); ++itv) ++hashMap[*itv]; for (itl = nodePath1.begin(), k = 0; k < begin && couldReplace == true; ++itl, k++) if (++hashMap[*itl] > 1) couldReplace = false; } if (couldReplace == true) // test if the replace action will lead to loop { itl = nodePath1.begin(); for (k = 0; k < end+1; k++) ++itl; for (; k < nodePath1.size() && couldReplace == true; ++itl, k++) if (++hashMap[*itl] > 1) couldReplace = false; } if (couldReplace == true) // test if identical arc num will increase { int identicalArcNumTemp = 0; unordered_set<int> identicalHelper; itl1 = arcPath1.begin(); advance(itl1, begin); itl2 = itl1; advance(itl2, end-begin); for (itl = arcPath1.begin(); itl != itl1; ++itl) identicalHelper.insert(*itl); for (itl = itl2; itl != arcPath1.end(); ++itl) identicalHelper.insert(*itl); for (itv = P_i_j1[i].arcPath.begin(); itv != P_i_j1[i].arcPath.end(); ++itv) identicalHelper.insert(*itv); for (itl = arcPath2.begin(); itl != arcPath2.end(); ++itl) if (identicalHelper.find(*itl) != identicalHelper.end()) identicalArcNumTemp++; if (identicalArcNumTemp > identicalArcNum) couldReplace = false; else identicalArcNum = identicalArcNumTemp; identicalHelper.clear(); } if (couldReplace == true) // replace action { int difference = (int)P_i_j1[i].arcPath.size() - (int)(end - begin); itl = arcPath1.begin(); for (k = 0; k < begin; k++) ++itl; for (; k < end; ++itl, k++) // minus BFS path's cost costSum1 -= arcID2Cost.at(*itl); costSum1 += P_i_j1[i].costSum; // plus dijkstra path's cost itl1 = nodePath1.begin(); advance(itl1, begin+1); itl2 = itl1; advance(itl2, end-begin-1); itl1 = nodePath1.erase(itl1, itl2); // itl1 points now to end nodePath1.insert(itl1, P_i_j1[i].nodePath.begin()+1, P_i_j1[i].nodePath.end()-1); itl1 = arcPath1.begin(); advance(itl1, begin); itl2 = itl1; advance(itl2, end-begin); itl1 = arcPath1.erase(itl1, itl2); // itl1 points now to end arcPath1.insert(itl1, P_i_j1[i].arcPath.begin(), P_i_j1[i].arcPath.end()); if (difference > 0) for (k = i+2; k < Vs1; k++) specifiedPosition1.at(specifiedNode1[k]) += (unsigned int)difference; else if (difference < 0) for (k = i+2; k < Vs1; k++) specifiedPosition1.at(specifiedNode1[k]) -= (unsigned int)(0 - difference); if (difference > 0) end += (unsigned int)difference; else if (difference < 0) end -= (unsigned int)(0 - difference); } #if CONSOLE_INFO cout << ' ' << couldReplace; #endif begin = end; hashMap.clear(); } delete []P_i_j1; #if CONSOLE_INFO cout << endl << "Path2 could replace:"; #endif begin = specifiedPosition2.at(specifiedNode2[0]); for (i = 0; i < Vs2-1; i++) { bool couldReplace = true; end = specifiedPosition2.at(specifiedNode2[i+1]); if (P_i_j2[i].arcPath.size() == (end - begin)) // need to judge if the subpath is the same, if it is same, there is no need to replace { itl = arcPath2.begin(); for (k = 0; k < begin; k++) ++itl; for (itv = P_i_j2[i].arcPath.begin(); k < end; ++itv, ++itl, k++) if (*itl != *itv) break; if (k == end) // is same couldReplace = false; } if (couldReplace == true) // test if the replace action will lead to loop { for (itv = P_i_j2[i].nodePath.begin(); itv != P_i_j2[i].nodePath.end(); ++itv) ++hashMap[*itv]; for (itl = nodePath2.begin(), k = 0; k < begin && couldReplace == true; ++itl, k++) if (++hashMap[*itl] > 1) couldReplace = false; } if (couldReplace == true) // test if the replace action will lead to loop { itl = nodePath2.begin(); for (k = 0; k < end+1; k++) ++itl; for (; k < nodePath2.size() && couldReplace == true; ++itl, k++) if (++hashMap[*itl] > 1) couldReplace = false; } if (couldReplace == true) // test if identical arc num will increase { int identicalArcNumTemp = 0; unordered_set<int> identicalHelper; itl1 = arcPath2.begin(); advance(itl1, begin); itl2 = itl1; advance(itl2, end-begin); for (itl = arcPath2.begin(); itl != itl1; ++itl) identicalHelper.insert(*itl); for (itl = itl2; itl != arcPath2.end(); ++itl) identicalHelper.insert(*itl); for (itv = P_i_j2[i].arcPath.begin(); itv != P_i_j2[i].arcPath.end(); ++itv) identicalHelper.insert(*itv); for (itl = arcPath1.begin(); itl != arcPath1.end(); ++itl) if (identicalHelper.find(*itl) != identicalHelper.end()) identicalArcNumTemp++; if (identicalArcNumTemp > identicalArcNum) couldReplace = false; else identicalArcNum = identicalArcNumTemp; identicalHelper.clear(); } if (couldReplace == true) // replace action { int difference = (int)P_i_j2[i].arcPath.size() - (int)(end - begin); itl = arcPath2.begin(); for (k = 0; k < begin; k++) ++itl; for (; k < end; ++itl, k++) // minus BFS path's cost costSum2 -= arcID2Cost.at(*itl); costSum2 += P_i_j2[i].costSum; // plus dijkstra path's cost itl1 = nodePath2.begin(); advance(itl1, begin+1); itl2 = itl1; advance(itl2, end-begin-1); itl1 = nodePath2.erase(itl1, itl2); // itl1 points now to end nodePath2.insert(itl1, P_i_j2[i].nodePath.begin()+1, P_i_j2[i].nodePath.end()-1); itl1 = arcPath2.begin(); advance(itl1, begin); itl2 = itl1; advance(itl2, end-begin); itl1 = arcPath2.erase(itl1, itl2); // itl1 points now to end arcPath2.insert(itl1, P_i_j2[i].arcPath.begin(), P_i_j2[i].arcPath.end()); if (difference > 0) for (k = i+2; k < Vs2; k++) specifiedPosition2.at(specifiedNode2[k]) += (unsigned int)difference; else if (difference < 0) for (k = i+2; k < Vs2; k++) specifiedPosition2.at(specifiedNode2[k]) -= (unsigned int)(0 - difference); if (difference > 0) end += (unsigned int)difference; else if (difference < 0) end -= (unsigned int)(0 - difference); } #if CONSOLE_INFO cout << ' ' << couldReplace; #endif begin = end; hashMap.clear(); } delete []P_i_j2; #if CONSOLE_INFO cout << endl; #endif // 4 =============== free memory =============== specifiedNode1.clear(); specifiedNode2.clear(); specifiedNode1.shrink_to_fit(); specifiedNode2.shrink_to_fit(); specifiedPosition1.clear(); specifiedPosition2.clear(); delete []isRemoved; return identicalArcNum; } bool findReplacedPath(Node *NodeList, Arc *currArc, int& endNode, int& maxHop, list<int>& replacedNodeID, list<int>& replacedArcID, unordered_set<int>& pathNode, unordered_set<int>& arcInSamePath) { if (arcInSamePath.count(currArc->ArcID) != 0) return false; if (currArc->DestinationID == endNode) { replacedArcID.push_back(currArc->ArcID); return true; } if (pathNode.count(currArc->DestinationID) != 0) // lead to loop return false; bool hasReplacedPath = false; static int hopCount = 0; if (++hopCount < maxHop) { Arc *nextArc = NodeList[currArc->DestinationID].firstArc; replacedNodeID.push_back(currArc->DestinationID); replacedArcID.push_back(currArc->ArcID); pathNode.insert(currArc->DestinationID); while (nextArc != NULL && hasReplacedPath == false) { if (findReplacedPath(NodeList, nextArc, endNode, maxHop, replacedNodeID, replacedArcID, pathNode, arcInSamePath) == true) hasReplacedPath = true; else nextArc = nextArc->nextArc; } if (hasReplacedPath == false) { replacedNodeID.pop_back(); replacedArcID.pop_back(); pathNode.erase(currArc->DestinationID); } } --hopCount; return hasReplacedPath; } void optimizeAdmissiblePathPair(Node *NodeList, int NodeNum, int src, int dst, vector<int>& specifiedNodes1, vector<int>& specifiedNodes2, Path& optimizeNeededPath1, Path& optimizeNeededPath2, bool executeDijkstra = true) { #if CONSOLE_INFO cout << endl << "=============== Function optimizeAdmissiblePathPair() ===============" << endl; #endif size_t i; size_t Vs1 = specifiedNodes1.size(), Vs2 = specifiedNodes2.size(); list<int> nodePath1, nodePath2, arcPath1, arcPath2; list<int>::iterator itl, itl1, itl2; // 1 =============== read data from optimizeNeededPath, organized as list form for the convenience of insert and erase =============== int costSum1 = optimizeNeededPath1.costSum; int costSum2 = optimizeNeededPath2.costSum; for (i = 0; i < optimizeNeededPath1.nodePath.size(); i++) nodePath1.push_back(optimizeNeededPath1.nodePath[i]); for (i = 0; i < optimizeNeededPath2.nodePath.size(); i++) nodePath2.push_back(optimizeNeededPath2.nodePath[i]); for (i = 0; i < optimizeNeededPath1.arcPath.size(); i++) arcPath1.push_back(optimizeNeededPath1.arcPath[i]); for (i = 0; i < optimizeNeededPath2.arcPath.size(); i++) arcPath2.push_back(optimizeNeededPath2.arcPath[i]); // 2 =============== replace BFS path by dijkstra path =============== int identicalArcNum; ComplexityDescription complexity = defineComplexity(NodeNum, Vs1, Vs2); // decide whether to execute this algorithm according to its time consuming, for the most time is on calculating dijkstra path if ((complexity == VeryEasy || complexity == Easy || complexity == General || complexity == Hard) && Vs1 > 1 && Vs2 > 1 && executeDijkstra == true) // avoid particular occasion when only exists one specified node or even no specified node require identicalArcNum = replacedByDijkstra(NodeList, NodeNum, src, dst, specifiedNodes1, specifiedNodes2, nodePath1, nodePath2, arcPath1, arcPath2, costSum1, costSum2); else // complexity == VeryHard || complexity == ExtremelyHard identicalArcNum = identicalElementNum(arcPath1, arcPath2); #if CONSOLE_INFO cout << "After replaced by dijkstra, identical ArcNum: " << identicalArcNum << endl; #endif // 3 =============== replace work arc by back arc =============== list<int> identicalArcs; identicalElements(identicalArcs, arcPath1, arcPath2); for (itl1 = identicalArcs.begin(); itl1 != identicalArcs.end();) { for (itl2 = arcPath2.begin(); itl2 != arcPath2.end(); ++itl2) { if (*itl1 == *itl2) { if (workArcID2BackArcID.find(*itl2) != workArcID2BackArcID.end()) // has a back arc, replace the work arc { int backArcID = workArcID2BackArcID.at(*itl2); costSum2 -= arcID2Cost.at(*itl2); *itl2 = backArcID; costSum2 += arcID2Cost.at(*itl2); --identicalArcNum; } ++itl1; if (itl1 == identicalArcs.end()) break; } } } #if CONSOLE_INFO cout << "After replaced by back arc, identical ArcNum: " << identicalArcNum << endl; #endif printList(nodePath1, "nodePath1: "); printList(nodePath2, "nodePath2: "); // 4 =============== find replaceable subpath only to reduce the identical arc num =============== #if TIMMING_INFO clock_t tBeginTime = clock(); #endif unordered_set<int> specifiedNodesHashSet1; unordered_set<int> specifiedNodesHashSet2; for (i = 0; i < specifiedNodes1.size(); ++i) specifiedNodesHashSet1.insert(specifiedNodes1[i]); for (i = 0; i < specifiedNodes2.size(); ++i) specifiedNodesHashSet2.insert(specifiedNodes2[i]); unordered_set<int> nodePathHashSet1; unordered_set<int> nodePathHashSet2; for (itl = nodePath1.begin(); itl != nodePath1.end(); ++itl) nodePathHashSet1.insert(*itl); for (itl = nodePath2.begin(); itl != nodePath2.end(); ++itl) nodePathHashSet2.insert(*itl); unordered_map<int, int> arcPathHashMap1; unordered_map<int, int>::iterator itum; for (itl = arcPath1.begin(), i = 0; itl != arcPath1.end(); ++itl, i++) arcPathHashMap1.insert(make_pair(*itl, i)); bool hasSpecifiedNodes1 = false, hasSpecifiedNodes2 = false; bool hasFoundReplacedPath = false; int startNode = -1, endNode = -1; int maxHop = EXTRA_HOP_COUNT; int lastArcID = arcPath2.back(); Arc *curArc = NULL; list<int> replacedNodeID, replacedArcID, originPathNode; list<int>::iterator itNodeStart1, itArcStart1, itNodeStart2, itArcStart2; list<int>::iterator itNodeEnd1, itArcEnd1, itNodeEnd2, itArcEnd2; list<int>::iterator tmpNode, specifiedNode1Loc, specifiedArc1Loc, specifiedNode2Loc, specifiedArc2Loc; list<int>::reverse_iterator itrl; unordered_set<int> arcInSamePath; #if CONSOLE_INFO cout << endl << "========== find replaceable subpath without rollback or go ahead ==========" << endl; #endif for (itl1 = nodePath2.begin(), itl2 = arcPath2.begin(), i = 0; itl2 != arcPath2.end(); ++itl1, ++itl2) { if ((itum = arcPathHashMap1.find(*itl2)) != arcPathHashMap1.end()) { if (startNode == -1) { #if CONSOLE_INFO cout << endl << "[1]. The same arcPath is: " << *itl2; #endif startNode = *itl1; itNodeStart2 = itl1; ++itNodeStart2; itArcStart2 = itl2; itNodeStart1 = nodePath1.begin(); advance(itNodeStart1, itum->second + 1); itArcStart1 = arcPath1.begin(); advance(itArcStart1, itum->second); } else { #if CONSOLE_INFO cout << ' '<< *itl2; #endif if (specifiedNodesHashSet1.count(*itl1) != 0) { specifiedNode1Loc = itl1; specifiedArc1Loc = itl2; #if CONSOLE_INFO cout << " {1:" << *itl1 << '}'; #endif hasSpecifiedNodes1 = true; } if (specifiedNodesHashSet2.count(*itl1) != 0) { specifiedNode2Loc = itl1; specifiedArc2Loc = itl2; #if CONSOLE_INFO cout << " {2:" << *itl1 << '}'; #endif hasSpecifiedNodes2 = true; } } ++maxHop; arcInSamePath.insert(*itl2); if (hasSpecifiedNodes1 == true && specifiedNodesHashSet2.count(*itl1) != 0) { --maxHop; endNode = *itl1; curArc = NodeList[startNode].firstArc; hasFoundReplacedPath = false; tmpNode = itNodeStart2; while (tmpNode != itl1) { originPathNode.push_back(*tmpNode); nodePathHashSet2.erase(*tmpNode); ++tmpNode; } while (curArc != NULL) { if (findReplacedPath(NodeList, curArc, endNode, maxHop, replacedNodeID, replacedArcID, nodePathHashSet2, arcInSamePath) == true) { printList(replacedNodeID, "\nReplaced node ID path: "); printList(replacedArcID, "Replaced arc ID path: "); hasFoundReplacedPath = true; // ===== update nodePath2 and arcPath2 ===== REPLACE_BACK_PATH_ACTION(nodePath2, arcPath2, itNodeStart2, itl1, itArcStart2, itl2, nodePathHashSet2) break; } else curArc = curArc->nextArc; } if (hasFoundReplacedPath == true) { replacedNodeID.clear(); replacedArcID.clear(); arcInSamePath.clear(); maxHop = EXTRA_HOP_COUNT; startNode = -1; hasSpecifiedNodes1 = false; hasSpecifiedNodes2 = false; } else { while (originPathNode.empty() == false) { nodePathHashSet2.insert(originPathNode.front()); originPathNode.pop_front(); } tmpNode = itNodeStart1; while (*tmpNode != *specifiedNode1Loc) { originPathNode.push_back(*tmpNode); nodePathHashSet1.erase(*tmpNode); ++tmpNode; } tmpNode = specifiedArc1Loc; while (tmpNode != itl2) { --maxHop; ++tmpNode; } endNode = *specifiedNode1Loc; curArc = NodeList[startNode].firstArc; while (curArc != NULL) { if (findReplacedPath(NodeList, curArc, endNode, maxHop, replacedNodeID, replacedArcID, nodePathHashSet1, arcInSamePath) == true) { printList(replacedNodeID, "\nReplaced node ID path: "); printList(replacedArcID, "Replaced arc ID path: "); hasFoundReplacedPath = true; // ===== move the end iterator to the right position ===== itNodeEnd1 = itNodeStart1; itArcEnd1 = itArcStart1; while (*itNodeEnd1 != *specifiedNode1Loc) { ++itNodeEnd1; ++itArcEnd1; } ++itArcEnd1; // ===== update nodePath1 and arcPath1 ===== REPLACE_WORK_PATH_ACTION(nodePath1, arcPath1, itNodeStart1, itNodeEnd1, itArcStart1, itArcEnd1, nodePathHashSet1) break; } else curArc = curArc->nextArc; } if (hasFoundReplacedPath == false) { while (originPathNode.empty() == false) { nodePathHashSet1.insert(originPathNode.front()); originPathNode.pop_front(); } } itNodeStart2 = specifiedNode1Loc; itArcStart2 = specifiedArc1Loc; ++itNodeStart2; ++itArcStart2; maxHop = EXTRA_HOP_COUNT; tmpNode = specifiedArc1Loc; while (tmpNode != itl2) { ++maxHop; ++tmpNode; } hasSpecifiedNodes1 = false; startNode = *specifiedNode1Loc; itum = arcPathHashMap1.find(*specifiedArc1Loc); itNodeStart1 = nodePath1.begin(); advance(itNodeStart1, itum->second + 1); itArcStart1 = arcPath1.begin(); advance(itArcStart1, itum->second); } --itl1; --itl2; originPathNode.clear(); } else if (hasSpecifiedNodes2 == true && specifiedNodesHashSet1.count(*itl1) != 0) { --maxHop; endNode = *itl1; curArc = NodeList[startNode].firstArc; hasFoundReplacedPath = false; tmpNode = itNodeStart1; while (*tmpNode != *itl1) { originPathNode.push_back(*tmpNode); nodePathHashSet1.erase(*tmpNode); ++tmpNode; } while (curArc != NULL) { if (findReplacedPath(NodeList, curArc, endNode, maxHop, replacedNodeID, replacedArcID, nodePathHashSet1, arcInSamePath) == true) { printList(replacedNodeID, "\nReplaced node ID path: "); printList(replacedArcID, "Replaced arc ID path: "); hasFoundReplacedPath = true; // ===== move the end iterator to the right position ===== itNodeEnd1 = itNodeStart1; itArcEnd1 = itArcStart1; advance(itNodeEnd1, maxHop - EXTRA_HOP_COUNT - 1); advance(itArcEnd1, maxHop - EXTRA_HOP_COUNT); // ===== update nodePath1 and arcPath1 ===== REPLACE_WORK_PATH_ACTION(nodePath1, arcPath1, itNodeStart1, itNodeEnd1, itArcStart1, itArcEnd1, nodePathHashSet1) break; } else curArc = curArc->nextArc; } if (hasFoundReplacedPath == true) { replacedNodeID.clear(); replacedArcID.clear(); arcInSamePath.clear(); maxHop = EXTRA_HOP_COUNT; startNode = -1; hasSpecifiedNodes1 = false; hasSpecifiedNodes2 = false; } else { while (originPathNode.empty() == false) { nodePathHashSet1.insert(originPathNode.front()); originPathNode.pop_front(); } tmpNode = itNodeStart2; while (*tmpNode != *specifiedNode2Loc) { originPathNode.push_back(*tmpNode); nodePathHashSet1.erase(*tmpNode); ++tmpNode; } tmpNode = specifiedArc2Loc; while (tmpNode != itl2) { --maxHop; ++tmpNode; } endNode = *specifiedNode2Loc; curArc = NodeList[startNode].firstArc; // For the case that there is not alternate path from startNode to specifiedNode2Loc while (curArc != NULL) { if (findReplacedPath(NodeList, curArc, endNode, maxHop, replacedNodeID, replacedArcID, nodePathHashSet2, arcInSamePath) == true) { printList(replacedNodeID, "\nReplaced node ID path: "); printList(replacedArcID, "Replaced arc ID path: "); hasFoundReplacedPath = true; // ===== update nodePath2 and arcPath2 ===== REPLACE_BACK_PATH_ACTION(nodePath2, arcPath2, itNodeStart2, specifiedNode2Loc, itArcStart2, specifiedArc2Loc, nodePathHashSet2) break; } else curArc = curArc->nextArc; } if (hasFoundReplacedPath == false) { while (originPathNode.empty() == false) { nodePathHashSet2.insert(originPathNode.front()); originPathNode.pop_front(); } } maxHop = EXTRA_HOP_COUNT; tmpNode = specifiedNode2Loc; while (tmpNode != itl1) { ++maxHop; ++tmpNode; } itNodeStart2 = specifiedNode2Loc; ++itNodeStart2; itArcStart2 = specifiedArc2Loc; hasSpecifiedNodes2 = false; startNode = *specifiedNode2Loc; } --itl1; --itl2; originPathNode.clear(); } else if (*itl2 == lastArcID) { ++itl1; endNode = *itl1; curArc = NodeList[startNode].firstArc; hasFoundReplacedPath = false; if (hasSpecifiedNodes1 == false) { tmpNode = itNodeStart1; while (*tmpNode != endNode) { originPathNode.push_back(*tmpNode); nodePathHashSet1.erase(*tmpNode); ++tmpNode; } while (curArc != NULL) { if (findReplacedPath(NodeList, curArc, endNode, maxHop, replacedNodeID, replacedArcID, nodePathHashSet1, arcInSamePath) == true) { printList(replacedNodeID, "Replaced node ID path: "); printList(replacedArcID, "Replaced arc ID path: "); hasFoundReplacedPath = true; // ===== move the end iterator to the right position ===== itNodeEnd1 = itNodeStart1; itArcEnd1 = itArcStart1; advance(itNodeEnd1, maxHop - EXTRA_HOP_COUNT - 1); advance(itArcEnd1, maxHop - EXTRA_HOP_COUNT); // ===== update nodePath1 and arcPath1 ===== REPLACE_WORK_PATH_ACTION(nodePath1, arcPath1, itNodeStart1, itNodeEnd1, itArcStart1, itArcEnd1, nodePathHashSet1) break; } else curArc = curArc->nextArc; } if (hasFoundReplacedPath == false) { while (originPathNode.empty() == false) { nodePathHashSet1.insert(originPathNode.front()); originPathNode.pop_front(); } } } else if (hasSpecifiedNodes1 == true && hasSpecifiedNodes2 == false) { hasFoundReplacedPath = false; tmpNode = itNodeStart2; while (*tmpNode != endNode) { originPathNode.push_back(*tmpNode); nodePathHashSet2.erase(*tmpNode); ++tmpNode; } while (curArc != NULL) { if (findReplacedPath(NodeList, curArc, endNode, maxHop, replacedNodeID, replacedArcID, nodePathHashSet2, arcInSamePath) == true) { printList(replacedNodeID, "\nReplaced node ID path: "); printList(replacedArcID, "Replaced arc ID path: "); hasFoundReplacedPath = true; // ===== update nodePath2 and arcPath2 ===== REPLACE_BACK_PATH_ACTION(nodePath2, arcPath2, itNodeStart2, itl1, itArcStart2, arcPath2.end(), nodePathHashSet2) break; } else curArc = curArc->nextArc; } if (hasFoundReplacedPath == false) { while (originPathNode.empty() == false) { nodePathHashSet2.insert(originPathNode.front()); originPathNode.pop_front(); } } } replacedNodeID.clear(); replacedArcID.clear(); arcInSamePath.clear(); break; } } else if (startNode != -1) { #if CONSOLE_INFO cout << endl; #endif endNode = *itl1; curArc = NodeList[startNode].firstArc; hasFoundReplacedPath = false; if (hasSpecifiedNodes1 == false) { tmpNode = itNodeStart1; while (*tmpNode != *itl1) { originPathNode.push_back(*tmpNode); nodePathHashSet1.erase(*tmpNode); ++tmpNode; } while (curArc != NULL) { if (findReplacedPath(NodeList, curArc, endNode, maxHop, replacedNodeID, replacedArcID, nodePathHashSet1, arcInSamePath) == true) { printList(replacedNodeID, "\nReplaced node ID path: "); printList(replacedArcID, "Replaced arc ID path: "); hasFoundReplacedPath = true; // ===== move the end iterator to the right position ===== itNodeEnd1 = itNodeStart1; itArcEnd1 = itArcStart1; advance(itNodeEnd1, maxHop - EXTRA_HOP_COUNT - 1); advance(itArcEnd1, maxHop - EXTRA_HOP_COUNT); // ===== update nodePath1 and arcPath1 ===== REPLACE_WORK_PATH_ACTION(nodePath1, arcPath1, itNodeStart1, itNodeEnd1, itArcStart1, itArcEnd1, nodePathHashSet1) break; } else curArc = curArc->nextArc; } if (hasFoundReplacedPath == false) { while (originPathNode.empty() == false) { nodePathHashSet1.insert(originPathNode.front()); originPathNode.pop_front(); } } } else if (hasSpecifiedNodes1 == true && hasSpecifiedNodes2 == false) { tmpNode = itNodeStart2; while (tmpNode != itl1) { originPathNode.push_back(*tmpNode); nodePathHashSet2.erase(*tmpNode); ++tmpNode; } while (curArc != NULL) { if (findReplacedPath(NodeList, curArc, endNode, maxHop, replacedNodeID, replacedArcID, nodePathHashSet2, arcInSamePath) == true) { printList(replacedNodeID, "\nReplaced node ID path: "); printList(replacedArcID, "Replaced arc ID path: "); hasFoundReplacedPath = true; // ===== update nodePath2 and arcPath2 ===== REPLACE_BACK_PATH_ACTION(nodePath2, arcPath2, itNodeStart2, itl1, itArcStart2, itl2, nodePathHashSet2) break; } else curArc = curArc->nextArc; } if (hasFoundReplacedPath == false) { while (originPathNode.empty() == false) { nodePathHashSet2.insert(originPathNode.front()); originPathNode.pop_front(); } } } originPathNode.clear(); replacedNodeID.clear(); replacedArcID.clear(); arcInSamePath.clear(); maxHop = EXTRA_HOP_COUNT; startNode = -1; hasSpecifiedNodes1 = false; hasSpecifiedNodes2 = false; } } #if CONSOLE_INFO cout << endl << "========== find replaceable subpath with rollback or go ahead ==========" << endl; #endif unsigned int I, J; hasSpecifiedNodes1 = hasSpecifiedNodes2 = false; startNode = -1; maxHop = EXTRA_HOP_COUNT; lastArcID = arcPath2.back(); for (itl1 = nodePath2.begin(), itl2 = arcPath2.begin(); itl2 != arcPath2.end(); ++itl1, ++itl2) { if ((itum = arcPathHashMap1.find(*itl2)) != arcPathHashMap1.end()) { if (startNode == -1) { #if CONSOLE_INFO cout << endl << "[2]. The same arcPath is: " << *itl2; #endif startNode = *itl1; itNodeStart2 = itl1; ++itNodeStart2; itArcStart2 = itl2; itNodeStart1 = nodePath1.begin(); advance(itNodeStart1, itum->second + 1); itArcStart1 = arcPath1.begin(); advance(itArcStart1, itum->second); } else { #if CONSOLE_INFO cout << ' '<< *itl2; #endif if (hasSpecifiedNodes1 == false && specifiedNodesHashSet1.count(*itl1) != 0) hasSpecifiedNodes1 = true; else if (hasSpecifiedNodes2 == false && specifiedNodesHashSet2.count(*itl1) != 0) hasSpecifiedNodes2 = true; } ++maxHop; arcInSamePath.insert(*itl2); if (*itl2 == lastArcID) { ++itl1; endNode = *itl1; hasFoundReplacedPath = false; if (hasSpecifiedNodes1 == false) { tmpNode = itNodeStart1; while (*tmpNode != endNode) { nodePathHashSet1.erase(*tmpNode); ++tmpNode; } for (I = 0; I < MAX_ROLLBACK_HOP_COUNT && hasFoundReplacedPath == false; I++) { --itNodeStart1; if (specifiedNodesHashSet1.count(*itNodeStart1) == 0 && itNodeStart1 != nodePath1.begin()) { --itNodeStart1; startNode = *itNodeStart1; ++itNodeStart1; if (specifiedNodesHashSet1.count(startNode) != 0 || startNode == src) I = MAX_ROLLBACK_HOP_COUNT; --itArcStart1; arcInSamePath.insert(*itArcStart1); ++maxHop; } else { ++itNodeStart1; I = MAX_ROLLBACK_HOP_COUNT; } curArc = NodeList[startNode].firstArc; while (curArc != NULL && hasFoundReplacedPath == false) { if (findReplacedPath(NodeList, curArc, endNode, maxHop, replacedNodeID, replacedArcID, nodePathHashSet1, arcInSamePath) == true) { printList(replacedNodeID, "Replaced node ID path: "); printList(replacedArcID, "Replaced arc ID path: "); hasFoundReplacedPath = true; // ===== move the end iterator to the right position ===== itNodeEnd1 = itNodeStart1, itArcEnd1 = itArcStart1; advance(itNodeEnd1, maxHop - EXTRA_HOP_COUNT - 1); advance(itArcEnd1, maxHop - EXTRA_HOP_COUNT); // ===== update nodePath1 and arcPath1 ===== itNodeStart1 = nodePath1.erase(itNodeStart1, itNodeEnd1); nodePath1.insert(itNodeStart1, replacedNodeID.begin(), replacedNodeID.end()); while (itArcStart1 != itArcEnd1) // itArcStart1 = arcPath1.erase(itArcStart1, itArcEnd1); { costSum1 -= arcID2Cost.at(*itArcStart1); itArcStart1 = arcPath1.erase(itArcStart1); } for (list<int>::reverse_iterator itrl = replacedArcID.rbegin(); itrl != replacedArcID.rend(); ++itrl) // arcPath1.insert(itArcStart1, replacedArcID.begin(), replacedArcID.end()); { costSum1 += arcID2Cost.at(*itrl); itArcStart1 = arcPath1.insert(itArcStart1, *itrl); } } else curArc = curArc->nextArc; } } } if (hasSpecifiedNodes2 == false && hasFoundReplacedPath == false) { tmpNode = itNodeStart2; while (tmpNode != itl1) { nodePathHashSet2.erase(*tmpNode); ++tmpNode; } hasFoundReplacedPath = false; for (I = 0; I < MAX_ROLLBACK_HOP_COUNT && hasFoundReplacedPath == false; I++) { --itNodeStart2; if (specifiedNodesHashSet2.count(*itNodeStart2) == 0 && itNodeStart2 != nodePath2.begin()) { --itNodeStart2; startNode = *itNodeStart2; ++itNodeStart2; if (specifiedNodesHashSet2.count(startNode) != 0 || startNode == src) I = MAX_ROLLBACK_HOP_COUNT; --itArcStart2; arcInSamePath.insert(*itArcStart2); ++maxHop; } else { ++itNodeStart2; I = MAX_ROLLBACK_HOP_COUNT; } curArc = NodeList[startNode].firstArc; while (curArc != NULL && hasFoundReplacedPath == false) { if (findReplacedPath(NodeList, curArc, endNode, maxHop, replacedNodeID, replacedArcID, nodePathHashSet2, arcInSamePath) == true) { printList(replacedNodeID, "Replaced node ID path: "); printList(replacedArcID, "Replaced arc ID path: "); hasFoundReplacedPath = true; // ===== update nodePath2 and arcPath2 ===== itNodeStart2 = nodePath2.erase(itNodeStart2, itl1); nodePath2.insert(itNodeStart2, replacedNodeID.begin(), replacedNodeID.end()); while (itArcStart2 != arcPath2.end()) // itArcStart2 = arcPath2.erase(itArcStart2, itl2); { costSum2 -= arcID2Cost.at(*itArcStart2); itArcStart2 = arcPath2.erase(itArcStart2); } for (list<int>::reverse_iterator itrl = replacedArcID.rbegin(); itrl != replacedArcID.rend(); ++itrl) // arcPath2.insert(itArcStart2, replacedArcID.begin(), replacedArcID.end()); { costSum2 += arcID2Cost.at(*itrl); itArcStart2 = arcPath2.insert(itArcStart2, *itrl); } } else curArc = curArc->nextArc; } } } replacedNodeID.clear(); replacedArcID.clear(); arcInSamePath.clear(); break; } } else if (startNode != -1) { #if CONSOLE_INFO cout << endl; #endif bool hasReachedEnd = false; hasFoundReplacedPath = false; if (hasSpecifiedNodes1 == false) { endNode = *itl1; // ===== move the end iterator to the right position ===== itNodeEnd1 = itNodeStart1, itArcEnd1 = itArcStart1; advance(itNodeEnd1, maxHop - EXTRA_HOP_COUNT - 1); advance(itArcEnd1, maxHop - EXTRA_HOP_COUNT); tmpNode = itNodeStart1; while (*tmpNode != *itl1) { originPathNode.push_back(*tmpNode); nodePathHashSet1.erase(*tmpNode); ++tmpNode; } for (I = 0; I < MAX_ROLLBACK_HOP_COUNT && hasFoundReplacedPath == false; I++) { --itNodeStart1; if (specifiedNodesHashSet1.count(*itNodeStart1) == 0 && itNodeStart1 != nodePath1.begin()) { --itNodeStart1; startNode = *itNodeStart1; ++itNodeStart1; if (specifiedNodesHashSet1.count(startNode) != 0 || startNode == src) I = MAX_ROLLBACK_HOP_COUNT; --itArcStart1; arcInSamePath.insert(*itArcStart1); ++maxHop; } else { ++itNodeStart1; I = MAX_ROLLBACK_HOP_COUNT; } hasReachedEnd = false; for (J = 0; J < MAX_GO_AHEAD_HOP_COUNT; J++) { curArc = NodeList[startNode].firstArc; while (curArc != NULL && hasFoundReplacedPath == false) { if (findReplacedPath(NodeList, curArc, endNode, maxHop, replacedNodeID, replacedArcID, nodePathHashSet1, arcInSamePath) == true) { printList(replacedNodeID, "Replaced node ID path: "); printList(replacedArcID, "Replaced arc ID path: "); hasFoundReplacedPath = true; // ===== update nodePath1 and arcPath1 ===== REPLACE_WORK_PATH_ACTION(nodePath1, arcPath1, itNodeStart1, itNodeEnd1, itArcStart1, itArcEnd1, nodePathHashSet1) } else curArc = curArc->nextArc; } if (hasFoundReplacedPath == true) break; if (++itNodeEnd1 == nodePath1.end() || specifiedNodesHashSet1.count(endNode) != 0) { --itNodeEnd1; hasReachedEnd = true; for (; J > 0; J--) { --maxHop; --itArcEnd1; arcInSamePath.erase(*itArcEnd1); --itNodeEnd1; } endNode = *itNodeEnd1; break; } endNode = *itNodeEnd1; arcInSamePath.insert(*itArcEnd1); ++itArcEnd1; ++maxHop; } if (hasFoundReplacedPath == false && hasReachedEnd == false) { for (; J > 0; J--) { --maxHop; --itArcEnd1; arcInSamePath.erase(*itArcEnd1); --itNodeEnd1; } endNode = *itNodeEnd1; } } if (hasFoundReplacedPath == false) { while (originPathNode.empty() == false) { nodePathHashSet1.insert(originPathNode.front()); originPathNode.pop_front(); } } } if (hasSpecifiedNodes2 == false && hasFoundReplacedPath == false) { endNode = *itl1; // ===== move the end iterator to the right position ===== itNodeEnd2 = itl1, itArcEnd2 = itl2; hasFoundReplacedPath = false; tmpNode = itNodeStart2; while (tmpNode != itl1) { originPathNode.push_back(*tmpNode); nodePathHashSet2.erase(*tmpNode); ++tmpNode; } for (I = 0; I < MAX_ROLLBACK_HOP_COUNT && hasFoundReplacedPath == false; I++) { --itNodeStart2; if (specifiedNodesHashSet2.count(*itNodeStart2) == 0 && itNodeStart2 != nodePath2.begin()) { --itNodeStart2; startNode = *itNodeStart2; ++itNodeStart2; if (specifiedNodesHashSet2.count(startNode) != 0 || startNode == src) I = MAX_ROLLBACK_HOP_COUNT; --itArcStart2; arcInSamePath.insert(*itArcStart2); ++maxHop; } else { ++itNodeStart2; I = MAX_ROLLBACK_HOP_COUNT; } hasReachedEnd = false; for (J = 0; J < MAX_GO_AHEAD_HOP_COUNT; J++) { curArc = NodeList[startNode].firstArc; while (curArc != NULL && hasFoundReplacedPath == false) { if (findReplacedPath(NodeList, curArc, endNode, maxHop, replacedNodeID, replacedArcID, nodePathHashSet2, arcInSamePath) == true) { printList(replacedNodeID, "Replaced node ID path: "); printList(replacedArcID, "Replaced arc ID path: "); hasFoundReplacedPath = true; // ===== update nodePath2 and arcPath2 ===== REPLACE_BACK_PATH_ACTION(nodePath2, arcPath2, itNodeStart2, itNodeEnd2, itArcStart2, itArcEnd2, nodePathHashSet2) itl1 = itNodeEnd2; itl2 = itArcEnd2; } else curArc = curArc->nextArc; } if (hasFoundReplacedPath == true) break; if (++itNodeEnd2 == nodePath2.end() || specifiedNodesHashSet2.count(endNode) != 0) { hasReachedEnd = true; for (; J > 0; J--) { --maxHop; --itArcEnd2; arcInSamePath.erase(*itArcEnd2); } break; } endNode = *itNodeEnd2; arcInSamePath.insert(*itArcEnd2); ++itArcEnd2; ++maxHop; } if (hasFoundReplacedPath == false && hasReachedEnd == false) { for (; J > 0; J--) { --maxHop; --itArcEnd2; arcInSamePath.erase(*itArcEnd2); } } itNodeEnd2 = itl1; endNode = *itNodeEnd2; } if (hasFoundReplacedPath == false) { while (originPathNode.empty() == false) { nodePathHashSet2.insert(originPathNode.front()); originPathNode.pop_front(); } } } originPathNode.clear(); replacedNodeID.clear(); replacedArcID.clear(); arcInSamePath.clear(); maxHop = EXTRA_HOP_COUNT; startNode = -1; hasSpecifiedNodes1 = hasSpecifiedNodes2 = false; } } specifiedNodesHashSet1.clear(); specifiedNodesHashSet2.clear(); nodePathHashSet1.clear(); nodePathHashSet2.clear(); arcPathHashMap1.clear(); #if TIMMING_INFO clock_t tEndTime = clock(); double fCostTime = (double)(tEndTime - tBeginTime)/CLOCKS_PER_SEC; cout << endl << "[clock] Find replaceable path time = " << fCostTime << 's' << endl; #endif identicalArcs.clear(); identicalElements(identicalArcs, arcPath1, arcPath2); printList(identicalArcs, "Final identicalArcs: "); // 5 =============== write back to optimizeNeededPath =============== optimizeNeededPath1.nodePath.clear(); optimizeNeededPath2.nodePath.clear(); optimizeNeededPath1.arcPath.clear(); optimizeNeededPath2.arcPath.clear(); for (itl = nodePath1.begin(); itl != nodePath1.end(); ++itl) optimizeNeededPath1.nodePath.push_back(*itl); for (itl = nodePath2.begin(); itl != nodePath2.end(); ++itl) optimizeNeededPath2.nodePath.push_back(*itl); for (itl = arcPath1.begin(); itl != arcPath1.end(); ++itl) optimizeNeededPath1.arcPath.push_back(*itl); for (itl = arcPath2.begin(); itl != arcPath2.end(); ++itl) optimizeNeededPath2.arcPath.push_back(*itl); optimizeNeededPath1.costSum = costSum1; optimizeNeededPath2.costSum = costSum2; // 6 =============== free memory =============== identicalArcs.clear(); nodePath1.clear(); nodePath2.clear(); arcPath1.clear(); arcPath2.clear(); } bool checkValidityOfSolution(Node *NodeList, int NodeNum, int src, int dst, vector<int>& specifiedNodes1, vector<int>& specifiedNodes2, Path& bestPath1, Path& bestPath2) { size_t i; Arc *parc = NULL; if (bestPath1.nodePath.front() != src || bestPath2.nodePath.front() != src) { cerr << "Wrong src node!" << endl; return false; } if (bestPath1.nodePath.back() != dst || bestPath2.nodePath.back() != dst) { cerr << "Wrong dst node!" << endl; return false; } unordered_map<int, Arc*> hashMap; for (i = 0; i < bestPath1.nodePath.size()-1; i++) { if (workArcID2BackArcID.find(bestPath1.arcPath[i]) != workArcID2BackArcID.end()) { int backArcID = workArcID2BackArcID.at(bestPath1.arcPath[i]); hashMap.insert(make_pair(backArcID, arcID2Arc.at(bestPath1.arcPath[i]))); } parc = NodeList[bestPath1.nodePath[i]].firstArc; while (parc != NULL) { if (parc->ArcID == bestPath1.arcPath[i]) { if (parc->DestinationID != bestPath1.nodePath[i+1]) { cerr << "Work path link " << parc->ArcID << " wrong!" << endl; return false; } else break; } parc = parc->nextArc; } } for (i = 0; i < bestPath2.nodePath.size()-1; i++) { if (hashMap.find(bestPath2.arcPath[i]) != hashMap.end()) { parc = hashMap.at(bestPath2.arcPath[i]); if (parc->SourceID != bestPath2.nodePath[i] || parc->DestinationID != bestPath2.nodePath[i+1]) { cerr << "Back path link " << parc->ArcID << " wrong!" << endl; return false; } continue; } parc = NodeList[bestPath2.nodePath[i]].firstArc; while (parc != NULL) { if (parc->ArcID == bestPath2.arcPath[i]) { if (parc->DestinationID != bestPath2.nodePath[i+1]) { cerr << "Back path link " << parc->ArcID << " wrong!" << endl; return false; } else break; } parc = parc->nextArc; } } hashMap.clear(); if (isReplicate(bestPath1.nodePath) == true) { cerr << "Work path has loop!" << endl; return false; } if (isReplicate(bestPath2.nodePath) == true) { cerr << "Back path has loop!" << endl; return false; } vector<int> nodePath1, nodePath2; nodePath1.assign(bestPath1.nodePath.begin(), bestPath1.nodePath.end()); nodePath2.assign(bestPath2.nodePath.begin(), bestPath2.nodePath.end()); sort(nodePath1.begin(), nodePath1.end()); sort(nodePath2.begin(), nodePath2.end()); for (i = 0; i < specifiedNodes1.size(); i++) { if (binarySearch(nodePath1, specifiedNodes1[i]) == false) { cerr << "Work path omit a specified node " << specifiedNodes1[i] << " !" << endl; return false; } } for (i = 0; i < specifiedNodes2.size(); i++) { if (binarySearch(nodePath2, specifiedNodes2[i]) == false) { cerr << "Back path omit a specified node " << specifiedNodes2[i] << " !" << endl; return false; } } int costSum1 = 0, costSum2 = 0; for (i = 0; i < bestPath1.arcPath.size(); i++) costSum1 += arcID2Cost.at(bestPath1.arcPath[i]); for (i = 0; i < bestPath2.arcPath.size(); i++) costSum2 += arcID2Cost.at(bestPath2.arcPath[i]); cout << "Total cost: " << costSum1+costSum2 << endl; return true; } int main(int argc, char *argv[]) { #if RELEASE const char *topoFile = argv[1]; const char *demandFile = argv[2]; const char *resultFile = argv[3]; #else const char *topoFile = "topo.csv"; const char *demandFile = "demand.csv"; const char *resultFile = "result.csv"; #endif #if RUNNING_TIME_HIGH_PRECISION struct timeval beginTime, endTime; gettimeofday(&beginTime, NULL); #else clock_t tBeginTime = clock(); #endif /******************************************************************* ******************** Time elapsing ... ******************** *******************************************************************/ size_t i, j; int SourceID, DestinationID; list<Tuple> AllUnion; vector<int> specifiedNode1, specifiedNode2; unordered_map<int, int> nodeID2Index, nodeIndex2ID; // =========================================================== // 1. =============== read data from topofile =============== // =========================================================== inputFromTopoFile(topoFile, AllUnion); // ============================================================================================================================================= // 2. =============== unique AllUnion, get total node number and sort AllUnion by Node index for convenience to construct graph =============== // ============================================================================================================================================= #if USE_FORWARD_BFS_PATH AllUnion.sort(sourceCompare); // forward sort #elif USE_REVERSE_BFS_PATH AllUnion.sort(sourceCompareReverse); // reverse sort #else // #elif USE_RANDOM_BFS_PATH AllUnion.sort(sourceCompareRandom); // random sort #endif list<Tuple>::iterator itU1 = AllUnion.begin(); list<Tuple>::iterator itU2 = AllUnion.begin(); while (true) { bool isBackArc = true; ++itU2; if (itU2 == AllUnion.end()) break; while ((*itU1).second == (*itU2).second && (*itU1).third == (*itU2).third) { if (isBackArc == true) { workArcID2BackArcID.insert(make_pair((*itU1).first, (*itU2).first)); isBackArc = false; } itU2 = AllUnion.erase(itU2); // delete arcs that from same src to same dst if (itU2 == AllUnion.end()) // avoid the case that the last record in AllUnion have to be delete break; } if (itU2 == AllUnion.end()) break; ++itU1; } // ============================================================= // 3. =============== read data from demandfile =============== // ============================================================= inputFromDemandFile(demandFile, SourceID, DestinationID, specifiedNode1, specifiedNode2); vector<int> Source, Destination; obtainUniqueSourceAndDestination(AllUnion, Source, Destination); if (AllUnion.size() > 1000) { // ========== remove the nodes that have no in-degree or no out-degree [ first time ] ========== for (itU1 = AllUnion.begin(); itU1 != AllUnion.end(); ++itU1) { while ((binarySearch(Destination, (*itU1).second) == false && SourceID != (*itU1).second) || (binarySearch(Source, (*itU1).third) == false && DestinationID != (*itU1).third)) { itU1 = AllUnion.erase(itU1); if (itU1 == AllUnion.end()) // avoid the case that the last record in AllUnion have to be delete break; } if (itU1 == AllUnion.end()) break; } Source.clear(); Destination.clear(); obtainUniqueSourceAndDestination(AllUnion, Source, Destination); } if (AllUnion.size() > 2000) { // ========== remove the nodes that have no in-degree or no out-degree [ second time ] ========== for (itU1 = AllUnion.begin(); itU1 != AllUnion.end(); ++itU1) { while ((binarySearch(Destination, (*itU1).second) == false && SourceID != (*itU1).second) || (binarySearch(Source, (*itU1).third) == false && DestinationID != (*itU1).third)) { itU1 = AllUnion.erase(itU1); if (itU1 == AllUnion.end()) // avoid the case that the last record in AllUnion have to be delete break; } if (itU1 == AllUnion.end()) break; } Source.clear(); Destination.clear(); obtainUniqueSourceAndDestination(AllUnion, Source, Destination); } if (AllUnion.size() > 5000) { // ========== remove the nodes that have no in-degree or no out-degree [ third time ] ========== for (itU1 = AllUnion.begin(); itU1 != AllUnion.end(); ++itU1) { while ((binarySearch(Destination, (*itU1).second) == false && SourceID != (*itU1).second) || (binarySearch(Source, (*itU1).third) == false && DestinationID != (*itU1).third)) { itU1 = AllUnion.erase(itU1); if (itU1 == AllUnion.end()) // avoid the case that the last record in AllUnion have to be delete break; } if (itU1 == AllUnion.end()) break; } Source.clear(); Destination.clear(); obtainUniqueSourceAndDestination(AllUnion, Source, Destination); } vector<int> nodeTypes; unsigned int NodeNum = mergeVector(nodeTypes, Source, Destination); unsigned int ArcNum = AllUnion.size(); #if CONSOLE_INFO cout << "NodeNum: " << NodeNum << ", ArcNum: " << ArcNum << endl; #endif for (i = 0; i < NodeNum; i++) { nodeIndex2ID.insert(make_pair(i, nodeTypes[i])); nodeID2Index.insert(make_pair(nodeTypes[i], i)); } unsigned int Vs1 = specifiedNode1.size(); // Vs1 is specified nodes number of P' unsigned int Vs2 = specifiedNode2.size(); // Vs2 is specified nodes number of P'' bool hasSpecifiedRequire1 = (Vs1 > 0) ? true : false; bool hasSpecifiedRequire2 = (Vs2 > 0) ? true : false; #if CONSOLE_INFO cout << "Vs1: " << Vs1 << ", Vs2: " << Vs2 << endl; #endif // ============================================================== // 4. =============== transvert node ID to index =============== // ============================================================== for (itU1 = AllUnion.begin(); itU1 != AllUnion.end(); ++itU1) { (*itU1).second = nodeID2Index.at((*itU1).second); (*itU1).third = nodeID2Index.at((*itU1).third); } for (i = 0; i < Vs1; i++) specifiedNode1[i] = nodeID2Index.at(specifiedNode1[i]); for (i = 0; i < Vs2; i++) specifiedNode2[i] = nodeID2Index.at(specifiedNode2[i]); if (hasSpecifiedRequire1 == true) sort(specifiedNode1.begin(), specifiedNode1.end()); if (hasSpecifiedRequire2 == true) sort(specifiedNode2.begin(), specifiedNode2.end()); SourceID = nodeID2Index.at(SourceID); DestinationID = nodeID2Index.at(DestinationID); #if CONSOLE_DEBUG cout << "SourceID: " << SourceID << ", DestinationID: " << DestinationID << endl; #endif // =========================================================== // 5. =============== construct forward graph =============== // =========================================================== Node *NodeList = new Node[NodeNum]; vector<bool> arcIsAdded(NodeNum, false); unsigned int NodeId = 0; unsigned int rank = 2; itU1 = AllUnion.begin(); Arc *firstarc = new Arc, *parc = NULL, *qarc = NULL; firstarc->ArcID = (*itU1).first; firstarc->SourceID = (*itU1).second; firstarc->DestinationID = (*itU1).third; firstarc->cost = (*itU1).four; firstarc->nextArc = NULL; NodeId = (*itU1).second; // node index start with 0 arcIsAdded[NodeId] = true; NodeList[NodeId].ID = nodeIndex2ID.at(firstarc->SourceID); NodeList[NodeId].firstArc = firstarc; NodeList[firstarc->DestinationID].previous.push_back(firstarc); arcID2Arc.insert(make_pair(firstarc->ArcID, firstarc)); while (true) { itU2 = itU1; // itU2 is always a forword element of itU1 ++itU2; if (itU2 == AllUnion.end()) break; if ((*itU2).second == (*itU1).second) { if (rank % 2 == 0) { parc = new Arc; parc->ArcID = (*itU2).first; parc->SourceID = (*itU2).second; parc->DestinationID = (*itU2).third; parc->cost = (*itU2).four; parc->nextArc = NULL; if (rank == 2) firstarc->nextArc = parc; else qarc->nextArc = parc; NodeList[parc->DestinationID].previous.push_back(parc); arcID2Arc.insert(make_pair(parc->ArcID, parc)); } else { qarc = new Arc; qarc->ArcID = (*itU2).first; qarc->SourceID = (*itU2).second; qarc->DestinationID = (*itU2).third; qarc->cost = (*itU2).four; qarc->nextArc = NULL; parc->nextArc = qarc; NodeList[qarc->DestinationID].previous.push_back(qarc); arcID2Arc.insert(make_pair(qarc->ArcID, qarc)); } rank++; } else { rank = 2; NodeId = (*itU2).second; arcIsAdded[NodeId] = true; firstarc = new Arc; firstarc->ArcID = (*itU2).first; firstarc->SourceID = NodeId; firstarc->DestinationID = (*itU2).third; firstarc->cost = (*itU2).four; firstarc->nextArc = NULL; NodeList[NodeId].ID = nodeIndex2ID.at(NodeId); NodeList[NodeId].firstArc = firstarc; NodeList[firstarc->DestinationID].previous.push_back(firstarc); arcID2Arc.insert(make_pair(firstarc->ArcID, firstarc)); } ++itU1; } for (i = 0; i < NodeNum; i++) { if (arcIsAdded[i] == false) { NodeList[i].ID = nodeIndex2ID.at(i); NodeList[i].firstArc = NULL; } } // =================================================================================================================== // 6. =============== use breadth-first search algorithm to see hop count among these specified nodes =============== // =================================================================================================================== bool *isRemoved = new bool[NodeNum]; for (i = 0; i < (unsigned int)NodeNum; i++) isRemoved[i] = false; removeSpecifiedNodes(NodeList, vector<int>(1, SourceID), isRemoved); // src node has been removed removeSpecifiedNodes(NodeList, vector<int>(1, DestinationID), isRemoved); // dst node has been removed if (hasSpecifiedRequire1 == true) { int *D_v_i_v_j1 = new int[Vs1*Vs1]; int **D_i_j1 = new int*[Vs1]; // a point array, convenient to use form D_i_j1[i][j] for (i = 0; i < Vs1; i++) D_i_j1[i] = D_v_i_v_j1 + i*Vs1; for (i = 0; i < Vs1; i++) { BFS(NodeList, NodeNum, specifiedNode1[i]); for (j = 0; j < Vs1; j++) D_i_j1[i][j] = dist[specifiedNode1[j]]; } #if CONSOLE_INFO cout << "===== BFS1[i][j]: =====" << endl; for (i = 0; i < Vs1; i++) { for (j = 0; j < Vs1; j++) cout << D_i_j1[i][j] << ' '; cout << endl; } #endif delete []D_i_j1; delete []D_v_i_v_j1; } if (hasSpecifiedRequire2 == true) { int *D_v_i_v_j2 = new int[Vs2*Vs2]; int **D_i_j2 = new int*[Vs2]; // a point array, convenient to use form D_i_j2[i][j] for (i = 0; i < Vs2; i++) D_i_j2[i] = D_v_i_v_j2 + i*Vs2; for (i = 0; i < Vs2; i++) { BFS(NodeList, NodeNum, specifiedNode2[i]); for (j = 0; j < Vs2; j++) D_i_j2[i][j] = dist[specifiedNode2[j]]; } #if CONSOLE_INFO cout << "===== BFS2[i][j]: =====" << endl; for (i = 0; i < Vs2; i++) { for (j = 0; j < Vs2; j++) cout << D_i_j2[i][j] << ' '; cout << endl; } #endif delete []D_i_j2; delete []D_v_i_v_j2; } restoreSpecifiedNodes(NodeList, vector<int>(1, SourceID), isRemoved); // src node has been restored restoreSpecifiedNodes(NodeList, vector<int>(1, DestinationID), isRemoved); // dst node has been restored delete []isRemoved; // =========================================================== // 7. =============== construct reverse graph =============== // =========================================================== #if USE_REVERSE_GRAPH rNode *rNodeList = new rNode[NodeNum]; AllUnion.sort(terminalCompare); itU1 = AllUnion.begin(); for (i = 0; i < NodeNum; i++) arcIsAdded[i] = false; NodeId = 0; rank = 2; rArc *rfirstarc = new rArc, *rparc = NULL, *rqarc = NULL; rfirstarc->ArcID = (*itU1).first; rfirstarc->SourceID = (*itU1).third; rfirstarc->DestinationID = (*itU1).second; rfirstarc->cost = (*itU1).four; rfirstarc->nextArc = NULL; NodeId = (*itU1).third; // NodeId ?= 0, maybe not, but it doesn't matters arcIsAdded[NodeId] = true; rNodeList[NodeId].ID = nodeIndex2ID.at(rfirstarc->SourceID); rNodeList[NodeId].firstArc = rfirstarc; rNodeList[rfirstarc->DestinationID].previous.push_back(rfirstarc); arcID2rArc.insert(make_pair(rfirstarc->ArcID, rfirstarc)); while (true) { itU2 = itU1; // itU2 is always a forword element of itU1 ++itU2; if (itU2 == AllUnion.end()) break; if ((*itU2).third == (*itU1).third) { if (rank % 2 == 0) { rparc = new rArc; rparc->ArcID = (*itU2).first; rparc->SourceID = (*itU2).third; rparc->DestinationID = (*itU2).second; rparc->cost = (*itU2).four; rparc->nextArc = NULL; if (rank == 2) rfirstarc->nextArc = rparc; else rqarc->nextArc = rparc; rNodeList[rparc->DestinationID].previous.push_back(rparc); arcID2rArc.insert(make_pair(rparc->ArcID, rparc)); } else { rqarc = new rArc; rqarc->ArcID = (*itU2).first; rqarc->SourceID = (*itU2).third; rqarc->DestinationID = (*itU2).second; rqarc->cost = (*itU2).four; rqarc->nextArc = NULL; rparc->nextArc = rqarc; rNodeList[rqarc->DestinationID].previous.push_back(rqarc); arcID2rArc.insert(make_pair(rqarc->ArcID, rqarc)); } rank++; } else { rank = 2; NodeId = (*itU2).third; arcIsAdded[NodeId] = true; rfirstarc = new rArc; rfirstarc->ArcID = (*itU2).first; rfirstarc->SourceID = NodeId; rfirstarc->DestinationID = (*itU2).second; rfirstarc->cost = (*itU2).four; rfirstarc->nextArc = NULL; rNodeList[NodeId].ID = nodeIndex2ID.at(NodeId); rNodeList[NodeId].firstArc = rfirstarc; rNodeList[rfirstarc->DestinationID].previous.push_back(rfirstarc); arcID2rArc.insert(make_pair(rfirstarc->ArcID, rfirstarc)); } ++itU1; } for (i = 0; i < NodeNum; i++) { if (arcIsAdded[i] == false) { rNodeList[i].ID = nodeIndex2ID.at(i); rNodeList[i].firstArc = NULL; } } #endif AllUnion.clear(); arcIsAdded.clear(); arcIsAdded.shrink_to_fit(); // ========================================================= // 8. =============== display forward graph =============== // ========================================================= #if CONSOLE_DEBUG cout << "Forward graph displays: " << endl; for (i = 0; i < NodeNum; i++) { Arc *darc; cout << "node: " << NodeList[i].ID << "; arc: "; darc = NodeList[i].firstArc; while (darc != NULL) { cout << '(' << darc->DestinationID << ", " << darc->cost << ')' << " | "; darc = darc->nextArc; } cout << endl; } cout << "Forward graph previous nodes displays: " << endl; for (i = 0; i < NodeNum; i++) { for (j = 0; j < NodeList[i].previous.size(); j++) cout << NodeList[i].previous[j]->SourceID << ' '; cout << endl; } #endif // ========================================================= // 9. =============== display reverse graph =============== // ========================================================= #if USE_REVERSE_GRAPH #if CONSOLE_DEBUG cout << "Reverse graph displays: " << endl; for (i = 0; i < NodeNum; i++) { rArc *rdarc; cout << "node: " << rNodeList[i].ID << "; arc: "; rdarc = rNodeList[i].firstArc; while (rdarc != NULL) { cout << '(' << rdarc->DestinationID << ", " << rdarc->cost << ')' << " | "; rdarc = rdarc->nextArc; } cout << endl; } cout << "Reverse graph previous nodes displays: " << endl; for (i = 0; i < NodeNum; i++) { for (j = 0; j < rNodeList[i].previous.size(); j++) cout << rNodeList[i].previous[j]->SourceID << ' '; cout << endl; } #endif #endif // ===================================================================================== // 10. =============== use tarjan algorithm obtain bridges that in graph =============== // ===================================================================================== for (i = 0; i < NodeNum; i++) if (dfn[i] == 0) tarjan(NodeList, (int)i); list<set<int>* >::iterator itBlock; list<pair<int, int> >::iterator itBridge; #if CONSOLE_DEBUG for (itBlock = block.begin(); itBlock != block.end(); ++itBlock) { cout << "vertexs in block[i]: "; for (set<int>::iterator its = (*itBlock)->begin(); its != (*itBlock)->end(); ++its) cout << nodeIndex2ID.at(*its) << ' '; cout << endl; } #endif // ========== delete the bridges that cross between blocks one of which's size less than 5 ========== for (itBlock = block.begin(); itBlock != block.end(); ++itBlock) { if ((*itBlock)->size() < 5) { for (itBridge = bridge.begin(); itBridge != bridge.end(); ++itBridge) { while ((*itBlock)->count(itBridge->first) != 0 || (*itBlock)->count(itBridge->second) != 0) { itBridge = bridge.erase(itBridge); if (itBridge == bridge.end()) break; } if (itBridge == bridge.end()) break; } } } // ========== delete the blocks whose size less than 5 ========== for (itBlock = block.begin(); itBlock != block.end(); ++itBlock) { while ((*itBlock)->size() < 5) { (*itBlock)->clear(); delete *itBlock; itBlock = block.erase(itBlock); if (itBlock == block.end()) break; } if (itBlock == block.end()) break; } #if CONSOLE_INFO for (itBlock = block.begin(); itBlock != block.end(); ++itBlock) { cout << "vertexs in block[i]: "; for (set<int>::iterator its = (*itBlock)->begin(); its != (*itBlock)->end(); ++its) cout << nodeIndex2ID.at(*its) << ' '; cout << endl; } #endif // ========== delete the bridges whose two terminals are in the same block ========== for (itBlock = block.begin(); itBlock != block.end(); ++itBlock) { for (itBridge = bridge.begin(); itBridge != bridge.end(); ++itBridge) { while ((*itBlock)->count(itBridge->first) != 0 && (*itBlock)->count(itBridge->second) != 0) { itBridge = bridge.erase(itBridge); if (itBridge == bridge.end()) break; } if (itBridge == bridge.end()) break; } } #if CONSOLE_INFO cout << "bridge: "; for (itBridge = bridge.begin(); itBridge != bridge.end(); ++itBridge) cout << nodeIndex2ID.at(itBridge->first) << ',' << nodeIndex2ID.at(itBridge->second) << ' '; cout << endl; #endif // ========== add src, dst and specified nodes into blocks that reserved to avoid wrongly removing ========== bool hasInsert = false; parc = NodeList[SourceID].firstArc; while (parc != NULL) { for (itBlock = block.begin(); itBlock != block.end(); ++itBlock) { if ((*itBlock)->count(parc->DestinationID) != 0) { (*itBlock)->insert(SourceID); hasInsert = true; break; } } if (hasInsert == true) break; parc = parc->nextArc; } hasInsert = false; for (i = 0; i < NodeList[DestinationID].previous.size(); i++) { for (itBlock = block.begin(); itBlock != block.end(); ++itBlock) { if ((*itBlock)->count(NodeList[DestinationID].previous[i]->SourceID) != 0) { (*itBlock)->insert(DestinationID); hasInsert = true; break; } } if (hasInsert == true) break; } vector<Arc*> bridgeArc1, bridgeArc2; vector<vector<int> > specifiedNodeArray1, specifiedNodeArray2; if (bridge.size() != 0) // it indicates this graph exists bridge { vector<bool> isBlockCounted(block.size(), false); vector<bool> hasSpecifiedNode1(block.size(), true); vector<bool> hasSpecifiedNode2(block.size(), true); vector<Arc*> bridgeArc; queue<int> bridgeQ; bridgeQ.push(SourceID); unordered_map<int, unsigned int> fromWhichBlock; for (i = bridge.size()+1; i > 0; i--) { int nodeToSearch = bridgeQ.front(); bridgeQ.pop(); vector<int> specifiedNodeTemp; for (itBlock = block.begin(), j = 0; itBlock != block.end(); ++itBlock, j++) { if ((*itBlock)->count(nodeToSearch) != 0 && isBlockCounted[j] == false) { isBlockCounted[j] = true; // ========== obtain the bridge arc pointer ========== for (itBridge = bridge.begin(); itBridge != bridge.end(); ++itBridge) { if ((*itBlock)->count(itBridge->first) != 0) { parc = NodeList[itBridge->first].firstArc; while (parc != NULL) { if (parc->DestinationID == itBridge->second) { bridgeArc.push_back(parc); break; } parc = parc->nextArc; } bridgeQ.push(itBridge->second); fromWhichBlock.insert(make_pair(itBridge->second, j)); } // end if } // end for (itBridge ...) // ========== obtain the specified nodes in this block ========== vector<int>::iterator itv; for (itv = specifiedNode1.begin(); itv != specifiedNode1.end(); ++itv) if ((*itBlock)->count(*itv) != 0) specifiedNodeTemp.push_back(*itv); if (specifiedNodeTemp.empty() == false) specifiedNodeArray1.push_back(specifiedNodeTemp); else hasSpecifiedNode1[j] = false; specifiedNodeTemp.clear(); for (itv = specifiedNode2.begin(); itv != specifiedNode2.end(); ++itv) if ((*itBlock)->count(*itv) != 0) specifiedNodeTemp.push_back(*itv); if (specifiedNodeTemp.empty() == false) specifiedNodeArray2.push_back(specifiedNodeTemp); else hasSpecifiedNode2[j] = false; specifiedNodeTemp.clear(); } // end if } // end for (itBlock ...) } // ========== obtain the bridges needed to cross for P' and P'' ========== for (i = 0; i < bridgeArc.size(); i++) { parc = bridgeArc[i]; for (itBlock = block.begin(), j = 0; itBlock != block.end(); ++itBlock, j++) { if ((*itBlock)->count(parc->DestinationID) != 0) { if (hasSpecifiedNode1[j] == true && hasSpecifiedNode1[fromWhichBlock.at(parc->DestinationID)] == true) bridgeArc1.push_back(parc); if (hasSpecifiedNode2[j] == true && hasSpecifiedNode2[fromWhichBlock.at(parc->DestinationID)] == true) bridgeArc2.push_back(parc); break; } } } bridgeArc.clear(); fromWhichBlock.clear(); isBlockCounted.clear(); hasSpecifiedNode1.clear(); hasSpecifiedNode2.clear(); } else { specifiedNodeArray1.push_back(specifiedNode1); specifiedNodeArray2.push_back(specifiedNode2); } // ========== free memory ========== for (itBlock = block.begin(); itBlock != block.end(); ++itBlock) { (*itBlock)->clear(); delete *itBlock; } block.clear(); bridge.clear(); // ================================================================================ // 11. =============== use ant group algorithm to solve the problem =============== // ================================================================================ Path bestPath1, bestPath2, subBestPath1, subBestPath2; bestPath1.costSum = bestPath2.costSum = INF; int src, src1, src2, dst, dst1, dst2; if (hasSpecifiedRequire1 == true && hasSpecifiedRequire2 == true) { src = src1 = src2 = SourceID; for (i = 0, j = 0; i < bridgeArc1.size() || j < bridgeArc2.size();) { if (bridgeArc1[i]->ArcID == bridgeArc2[j]->ArcID) { subBestPath1.costSum = subBestPath2.costSum = INF; dst = bridgeArc1[i]->SourceID; antGroupAlgorithm(NodeList, (int)NodeNum, src, dst, specifiedNodeArray1[i], specifiedNodeArray2[j], subBestPath1, subBestPath2); if (subBestPath1.costSum == INF || subBestPath2.costSum == INF) reconstructGraph(NodeList, (int)NodeNum); if (subBestPath1.costSum == INF && subBestPath2.costSum == INF) antGroupAlgorithm(NodeList, (int)NodeNum, src, dst, specifiedNodeArray1[i], specifiedNodeArray2[j], subBestPath1, subBestPath2); else if (subBestPath1.costSum == INF && subBestPath2.costSum != INF) antGroupAlgorithm(NodeList, (int)NodeNum, src, dst, specifiedNodeArray1[i], subBestPath1); else if (subBestPath1.costSum != INF && subBestPath2.costSum == INF) antGroupAlgorithm(NodeList, (int)NodeNum, src, dst, specifiedNodeArray2[j], subBestPath2); src1 = src2 = src = bridgeArc1[i]->DestinationID; if (i == 0) bestPath1 = subBestPath1; else bestPath1 += subBestPath1; bestPath1.nodePath.push_back(bridgeArc1[i]->DestinationID); bestPath1.arcPath.push_back(bridgeArc1[i]->ArcID); bestPath1.costSum += arcID2Cost.at(bridgeArc1[i]->ArcID); if (j == 0) bestPath2 = subBestPath2; else bestPath2 += subBestPath2; bestPath2.nodePath.push_back(bridgeArc2[j]->DestinationID); bestPath2.arcPath.push_back(bridgeArc2[j]->ArcID); bestPath2.costSum += arcID2Cost.at(bridgeArc2[j]->ArcID); i++; j++; } else if (i < bridgeArc1.size()) { dst1 = bridgeArc1[i]->SourceID; antGroupAlgorithm(NodeList, (int)NodeNum, src1, dst1, specifiedNodeArray1[i], subBestPath1); src1 = bridgeArc1[i]->DestinationID; if (i == 0) bestPath1 = subBestPath1; else bestPath1 += subBestPath1; bestPath1.nodePath.push_back(bridgeArc1[i]->DestinationID); bestPath1.arcPath.push_back(bridgeArc1[i]->ArcID); bestPath1.costSum += arcID2Cost.at(bridgeArc1[i]->ArcID); i++; } else if (j < bridgeArc2.size()) { dst2 = bridgeArc2[i]->SourceID; antGroupAlgorithm(NodeList, (int)NodeNum, src2, dst2, specifiedNodeArray2[j], subBestPath2); src2 = bridgeArc2[i]->DestinationID; if (j == 0) bestPath2 = subBestPath2; else bestPath2 += subBestPath2; bestPath2.nodePath.push_back(bridgeArc2[j]->DestinationID); bestPath2.arcPath.push_back(bridgeArc2[j]->ArcID); bestPath2.costSum += arcID2Cost.at(bridgeArc2[j]->ArcID); j++; } } dst = dst1 = dst2 = DestinationID; subBestPath1.costSum = subBestPath2.costSum = INF; bool executeDijkstra = true; #if USE_DIJKSTRA_FIRST antGroupAlgorithm(NodeList, (int)NodeNum, src, dst, specifiedNodeArray1[i], specifiedNodeArray2[j], subBestPath1, subBestPath2, true); if (subBestPath1.costSum != INF && subBestPath2.costSum != INF && i == 0 && j == 0) executeDijkstra = false; if (subBestPath1.costSum == INF && subBestPath2.costSum == INF) antGroupAlgorithm(NodeList, (int)NodeNum, src, dst, specifiedNodeArray1[i], specifiedNodeArray2[j], subBestPath1, subBestPath2); else if (subBestPath1.costSum == INF && subBestPath2.costSum != INF) antGroupAlgorithm(NodeList, (int)NodeNum, src, dst, specifiedNodeArray1[i], subBestPath1); else if (subBestPath1.costSum != INF && subBestPath2.costSum == INF) antGroupAlgorithm(NodeList, (int)NodeNum, src, dst, specifiedNodeArray2[j], subBestPath2); #else antGroupAlgorithm(NodeList, (int)NodeNum, src, dst, specifiedNodeArray1[i], specifiedNodeArray2[j], subBestPath1, subBestPath2); #endif if (subBestPath1.costSum == INF || subBestPath2.costSum == INF) reconstructGraph(NodeList, (int)NodeNum); if (subBestPath1.costSum == INF && subBestPath2.costSum == INF) antGroupAlgorithm(NodeList, (int)NodeNum, src, dst, specifiedNodeArray1[i], specifiedNodeArray2[j], subBestPath1, subBestPath2); else if (subBestPath1.costSum == INF && subBestPath2.costSum != INF) antGroupAlgorithm(NodeList, (int)NodeNum, src, dst, specifiedNodeArray1[i], subBestPath1); else if (subBestPath1.costSum != INF && subBestPath2.costSum == INF) antGroupAlgorithm(NodeList, (int)NodeNum, src, dst, specifiedNodeArray2[j], subBestPath2); if (i == 0) bestPath1 = subBestPath1; else bestPath1 += subBestPath1; if (j == 0) bestPath2 = subBestPath2; else bestPath2 += subBestPath2; if (bestPath1.costSum != INF && bestPath2.costSum != INF) optimizeAdmissiblePathPair(NodeList, (int)NodeNum, SourceID, DestinationID, specifiedNode1, specifiedNode2, bestPath1, bestPath2, executeDijkstra); } else if (hasSpecifiedRequire1 == true && hasSpecifiedRequire2 == false) { src1 = SourceID; for (i = 0; i < bridgeArc1.size(); i++) { subBestPath1.costSum = INF; dst1 = bridgeArc1[i]->SourceID; antGroupAlgorithm(NodeList, (int)NodeNum, src1, dst1, specifiedNodeArray1[i], subBestPath1); if (subBestPath1.costSum == INF) { reconstructGraph(NodeList, (int)NodeNum); antGroupAlgorithm(NodeList, (int)NodeNum, src1, dst1, specifiedNodeArray1[i], subBestPath1); } src1 = bridgeArc1[i]->DestinationID; if (i == 0) bestPath1 = subBestPath1; else bestPath1 += subBestPath1; bestPath1.nodePath.push_back(bridgeArc1[i]->DestinationID); bestPath1.arcPath.push_back(bridgeArc1[i]->ArcID); bestPath1.costSum += arcID2Cost.at(bridgeArc1[i]->ArcID); } dst1 = DestinationID; subBestPath1.costSum = INF; antGroupAlgorithm(NodeList, (int)NodeNum, src1, dst1, specifiedNodeArray1[i], subBestPath1); if (subBestPath1.costSum == INF) { reconstructGraph(NodeList, (int)NodeNum); antGroupAlgorithm(NodeList, (int)NodeNum, src1, dst1, specifiedNodeArray1[i], subBestPath1); } if (i == 0) bestPath1 = subBestPath1; else bestPath1 += subBestPath1; if (computeAnotherBestPath(NodeList, (int)NodeNum, SourceID, DestinationID, bestPath1, bestPath2) == true) optimizeAdmissiblePathPair(NodeList, (int)NodeNum, SourceID, DestinationID, specifiedNode1, specifiedNode2, bestPath1, bestPath2, false); } else if (hasSpecifiedRequire1 == false && hasSpecifiedRequire2 == true) { src2 = SourceID; for (j = 0; j < bridgeArc2.size(); j++) { subBestPath2.costSum = INF; dst2 = bridgeArc2[j]->SourceID; antGroupAlgorithm(NodeList, (int)NodeNum, src2, dst2, specifiedNodeArray2[j], subBestPath2); if (subBestPath2.costSum == INF) { reconstructGraph(NodeList, (int)NodeNum); antGroupAlgorithm(NodeList, (int)NodeNum, src2, dst2, specifiedNodeArray2[j], subBestPath2); } src2 = bridgeArc2[j]->DestinationID; if (j == 0) bestPath2 = subBestPath2; else bestPath2 += subBestPath2; bestPath2.nodePath.push_back(bridgeArc2[j]->DestinationID); bestPath2.arcPath.push_back(bridgeArc2[j]->ArcID); bestPath2.costSum += arcID2Cost.at(bridgeArc2[j]->ArcID); } dst2 = DestinationID; subBestPath2.costSum = INF; antGroupAlgorithm(NodeList, (int)NodeNum, src2, dst2, specifiedNodeArray2[j], subBestPath2); if (subBestPath2.costSum == INF) { reconstructGraph(NodeList, (int)NodeNum); antGroupAlgorithm(NodeList, (int)NodeNum, src2, dst2, specifiedNodeArray2[j], subBestPath2); } if (j == 0) bestPath2 = subBestPath2; else bestPath2 += subBestPath2; if (computeAnotherBestPath(NodeList, (int)NodeNum, SourceID, DestinationID, bestPath1, bestPath2) == true) optimizeAdmissiblePathPair(NodeList, (int)NodeNum, SourceID, DestinationID, specifiedNode1, specifiedNode2, bestPath1, bestPath2, false); } else // hasSpecifiedRequire1 == false && hasSpecifiedRequire2 == false { if (computeBothBestPaths(NodeList, (int)NodeNum, SourceID, DestinationID, bestPath1, bestPath2) == true) optimizeAdmissiblePathPair(NodeList, (int)NodeNum, SourceID, DestinationID, specifiedNode1, specifiedNode2, bestPath1, bestPath2, false); } if (bestPath1.costSum != INF && bestPath2.costSum != INF) { outputSolutionToFile(resultFile, bestPath1.arcPath, bestPath2.arcPath); #if CONSOLE_INFO vector<int>::iterator itNode, itArc; cout << "*************** The best admissible Shortest Path1 ***************" << endl; cout << "bestPath1 - NodeRoute: "; for (itNode = bestPath1.nodePath.begin(); itNode != bestPath1.nodePath.end(); ++itNode) cout << nodeIndex2ID.at(*itNode) << " "; cout << endl << "bestPath1 - ArcRoute: "; for (itArc = bestPath1.arcPath.begin(); itArc != bestPath1.arcPath.end(); ++itArc) cout << *itArc << " "; cout << endl << "bestPath1 - CostSum: " << bestPath1.costSum << endl << endl; cout << "*************** The best admissible Shortest Path2 ***************" << endl; cout << "bestPath2 - NodeRoute: "; for (itNode = bestPath2.nodePath.begin(); itNode != bestPath2.nodePath.end(); ++itNode) cout << nodeIndex2ID.at(*itNode) << " "; cout << endl << "bestPath2 - ArcRoute: "; for (itArc = bestPath2.arcPath.begin(); itArc != bestPath2.arcPath.end(); ++itArc) cout << *itArc << " "; cout << endl << "bestPath2 - CostSum: " << bestPath2.costSum << endl << endl; cout << "identical ArcNum: " << identicalElementNum(bestPath1.arcPath, bestPath2.arcPath); cout << "\t\t\t\tCostSum - Added up: " << bestPath1.costSum + bestPath2.costSum << endl << endl; #endif } else { outputNAToFile(resultFile); #if CONSOLE_INFO cout << "NA" << endl; #endif } if (checkValidityOfSolution(NodeList, NodeNum, SourceID, DestinationID, specifiedNode1, specifiedNode2, bestPath1, bestPath2) == true) cout << "Congratulations! Solution is correct!!!" << endl; else cout << "Please check over! Solution is error!!!" << endl; // =============================================== // 12. =============== free memory =============== // =============================================== for (i = 0; i < NodeNum; i++) { rank = 0; Arc *freearc1, *freearc2 = NULL; freearc1 = NodeList[i].firstArc; if (freearc1 != NULL) freearc2 = freearc1->nextArc; while (freearc1 != NULL && freearc2 != NULL) { if (rank % 2 == 0) { delete freearc1; freearc1 = freearc2->nextArc; } else { delete freearc2; freearc2 = freearc1->nextArc; } rank++; } if (freearc1 != NULL) delete freearc1; if (freearc2 != NULL) delete freearc2; } for (i = 0; i < NodeNum; i++) NodeList[i].previous.clear(); delete []NodeList; #if USE_REVERSE_GRAPH for (i = 0; i < NodeNum; i++) { rank = 0; rArc *rfreearc1, *rfreearc2 = NULL; rfreearc1 = rNodeList[i].firstArc; if (rfreearc1 != NULL) rfreearc2 = rfreearc1->nextArc; while (rfreearc1 != NULL && rfreearc2 != NULL) { if (rank % 2 == 0) { delete rfreearc1; rfreearc1 = rfreearc2->nextArc; } else { delete rfreearc2; rfreearc2 = rfreearc1->nextArc; } rank++; } if (rfreearc1 != NULL) delete rfreearc1; if (rfreearc2 != NULL) delete rfreearc2; } for (i = 0; i < NodeNum; i++) rNodeList[i].previous.clear(); delete []rNodeList; #endif nodeID2Index.clear(); nodeIndex2ID.clear(); specifiedNode1.clear(); specifiedNode2.clear(); specifiedNode1.shrink_to_fit(); specifiedNode2.shrink_to_fit(); workArcID2BackArcID.clear(); arcID2Cost.clear(); arcID2Arc.clear(); #if USE_REVERSE_GRAPH arcID2rArc.clear(); #endif #if RUNNING_TIME_HIGH_PRECISION gettimeofday(&endTime, NULL); long secTime = endTime.tv_sec - beginTime.tv_sec; long usecTime = endTime.tv_usec - beginTime.tv_usec; cout << "Elapsed Time: SecTime = " << secTime << "s, UsecTime = " << usecTime << "us." << endl; #else clock_t tEndTime = clock(); double fCostTime = (double)(tEndTime - tBeginTime)/CLOCKS_PER_SEC; cout << "[clock] Cost Time = " << fCostTime << 's' << endl; #endif /******************************************************************* ******************** Time elapsing end ******************** *******************************************************************/ return 0; }