代码版权归大赛组委会所有，请勿转载。
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;
}