代码版权归大赛组委会所有，请勿转载！
4 月 25 号晚 9 点，复赛也完美谢幕，最终取得杭厦赛区第二的佳绩，代码量与初赛相当，修改了费用流的算法，不再采用 zkw，采用速度更快的网络单纯性算法（Network Simplex Algorithm），代码包已上传，下载地址：
2017-Huawei-Codecraft-Intermediary-CodePackage-Download
第二个中级用例获得了满分，赛区第一，第一个终极用例赛区第二，第一个高级用例赛区第三，第二个高级用例比较渣，赛区第七
复赛的题目在初赛题目的基础上添加了服务器的购买费用，不同档次的服务器输出带宽不同，输出能力越强的服务器的硬件成本也越高，此外网络结点的部署费用也不再单一了，有高有低，复赛题目与初赛题目完整的差别描述如下：
~~~~~ 华丽丽的分割线 ~~~~~
代码工程的 Makefile 与初赛的完全一致，下面只粘贴和初赛代码有较大差异的代码文件（缩进还是有问题，不知为啥，不打算调整了，将就着看吧）。
Utils.h：
/*************************************************************************************
* @copyright: Huawei Technologies Co. Ltd. *
* @file: Utils.h *
* @author: Xu Le *
* This file is part of 2017 Huawei CodeCraft solution <http://codecraft.huawei.com> *
*************************************************************************************/
#ifndef __UTILS_H__
#define __UTILS_H__
#include <cstdint>
#include <cstring>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <utility>
#include "Timer.h"
#define square(x) ((x)*(x))
/** structure used to store input lines' parsed result. */
struct LinkTuple
{
LinkTuple(int _src, int _dst, int _bandwidth, int _rental) : src(_src), dst(_dst), bandwidth(_bandwidth), rental(_rental) {}
LinkTuple(const LinkTuple& rhs) = default;
LinkTuple& operator=(const LinkTuple& rhs) = default;
int src; ///< first element in a single input line.
int dst; ///< second element in a single input line.
int bandwidth; ///< link bandwidth.
int rental; ///< link rental fee.
};
/** case complexity enum value space. */
enum class Complexity {
Oversimplified,
Simple,
General,
Hard,
VeryHard,
UltraHard,
Hell
};
/** parse input lines from case file. */
void parseInput(char *filename, std::list<struct LinkTuple>& linkTuples);
/** output flux path list to result file. */
void outputToFile(char *filename, std::list<std::vector<int> >& fluxPathList);
/** output NA to result file. */
void outputToFile(char *filename);
/** binary search in a certain std::vector, cost O(log n) */
bool binarySearch(const std::vector<int>& vec, const int key);
/** determine the highest server level to be used. */
void defineAvailableLevel();
/**
* locate the server level of which a network node should deployed according to node's connected link capacity,
* interval of nodeCap locate in [ oupcapTable[x], oupcapTable[x+1] ), note the function return 0
* when nodeCap < outcapTable[0], cost O(log n).
*/
int locateLevel(const int nodeCap);
/**
* fit the server level of which a network node should deployed according to node's actual output flux obtained by MCF,
* interval of outputFlux locate in ( oupcapTable[x], oupcapTable[x+1] ], note the function return hardwareLevelNum
* when nodeCap > outcapTable[hardwareLevelNum-1], cost O(log n).
*/
int fitLevel(const int outputFlux);
/** obtain the total purchase fee under the condition that all chosen network nodes deploy fitted server level. */
long obtainTotalPurchaseFee(std::vector<int>& serversOutputFlux, size_t serverNum);
/** define the default complexity of the case according to its size. */
Complexity defineDefaultComplexity();
/** convert enum value to its name string, only useful for debuging purpose. */
const char* complexityString(Complexity complexity);
//////////////// convenient functions of std::vector and std::list ////////////////
void printVector(std::vector<int>& _vector, const char *_note);
void printVector(std::vector<double>& _vector, const char *_note);
void printList(std::list<int>& _list, const char *_note);
void printList(std::list<double>& _list, const char *_note);
#endif /* __UTILS_H__ */
Utils.cpp：
/*************************************************************************************
* @copyright: Huawei Technologies Co. Ltd. *
* @file: Utils.cpp *
* @author: Xu Le *
* This file is part of 2017 Huawei CodeCraft solution <http://codecraft.huawei.com> *
*************************************************************************************/
#include "Utils.h"
extern int log_level;
extern int maxUnitRentalFee;
extern uint32_t networkNodeNum;
extern uint32_t linkNum;
extern uint32_t consumptionNodeNum;
extern uint32_t hardwareLevelNum;
extern std::vector<int> priceTable;
extern std::vector<int> outcapTable;
extern std::vector<int> deployTable;
extern std::vector<int> accessTable;
extern std::vector<int> demandTable;
extern std::unordered_map<int, int> provideTable;
void parseInput(char *filename, std::list<struct LinkTuple>& linkTuples)
{
FILE *fd = fopen(filename, "r");
if (fd == NULL)
{
error_log("Fail to open file %s.\n", filename);
exit(EXIT_FAILURE);
}
uint32_t i = 0;
int srcNode = 0, dstNode = 0, bandwidth = 0, rental = 0;
int deployFee = 0;
int level = 0, outcap = 0, price = 0;
int cspID = 0, netID = 0, demand = 0;
fscanf(fd, "%u %u %u\n", &networkNodeNum, &linkNum, &consumptionNodeNum);
char buf[100] = { '\0' };
while (true)
{
fgets(buf, 100, fd);
if (buf[0] == '\r' || buf[0] == '\n')
break;
sscanf(buf, "%d %d %d", &level, &outcap, &price);
outcapTable.push_back(outcap);
priceTable.push_back(price);
++hardwareLevelNum;
}
deployTable.resize(networkNodeNum);
accessTable.resize(consumptionNodeNum);
demandTable.resize(consumptionNodeNum);
for (i = 0; i < networkNodeNum; ++i)
{
fscanf(fd, "%d %d", &netID, &deployFee);
deployTable[netID] = deployFee;
}
fgetc(fd);
for (i = 0; i < linkNum; ++i)
{
fscanf(fd, "%d %d %d %d", &srcNode, &dstNode, &bandwidth, &rental);
linkTuples.emplace_back(srcNode, dstNode, bandwidth, rental);
if (maxUnitRentalFee < rental)
maxUnitRentalFee = rental;
}
fgetc(fd);
for (i = 0; i < consumptionNodeNum; ++i)
{
fscanf(fd, "%d %d %d", &cspID, &netID, &demand);
accessTable[cspID] = netID;
demandTable[cspID] = demand;
}
for (i = 0; i < consumptionNodeNum; ++i)
provideTable.insert(std::pair<int, int>(accessTable[i], i));
fclose(fd);
}
void outputToFile(char *filename, std::list<std::vector<int> >& fluxPathList)
{
FILE *fd = fopen(filename, "w");
if (fd == NULL)
{
error_log("Fail to open file %s.\n", filename);
exit(EXIT_FAILURE);
}
fprintf(fd, "%u\n\n", static_cast<uint32_t>(fluxPathList.size()));
for (std::list<std::vector<int> >::iterator iter = fluxPathList.begin(); iter != fluxPathList.end(); ++iter)
{
std::vector<int> &fluxPath = *iter; // alias
for (size_t i = 0; i < fluxPath.size()-1; ++i)
fprintf(fd, "%d ", fluxPath[i]);
fprintf(fd, "%d\n", fluxPath.back());
}
fclose(fd);
}
void outputToFile(char *filename)
{
FILE *fd = fopen(filename, "w");
if (fd == NULL)
{
error_log("Fail to open file %s.\n", filename);
exit(EXIT_FAILURE);
}
fprintf(fd, "NA\n");
fclose(fd);
}
bool binarySearch(const std::vector<int>& vec, const int key)
{
int low = 0, high = static_cast<int>(vec.size())-1, mid = 0;
while (low <= high)
{
mid = low + ((high - low) >> 1);
if (key == vec[mid])
return true;
else if (key < vec[mid])
high = mid - 1;
else
low = mid + 1;
}
return false;
}
void defineAvailableLevel()
{
uint32_t i = 0;
double sixthPosDeployFee = 0.0;
std::vector<double> unitOutputCapFee(hardwareLevelNum, 0.0);
std::vector<double> sortDeployFee;
sortDeployFee.reserve(networkNodeNum);
for (i = 0; i < networkNodeNum; ++i)
sortDeployFee.push_back(deployTable[i]);
std::sort(sortDeployFee.begin(), sortDeployFee.end());
sixthPosDeployFee = sortDeployFee[networkNodeNum/6];
info_log("sixth position deploy fee: %f\n", sixthPosDeployFee);
for (i = 0; i < hardwareLevelNum; ++i)
{
unitOutputCapFee[i] = (priceTable[i] + sixthPosDeployFee) / outcapTable[i];
info_log("level [%u]'s unit output capacity fee is %f\n", i, unitOutputCapFee[i]);
}
const uint32_t oldHardwareLevelNum = hardwareLevelNum;
const uint32_t L = 4;
if (hardwareLevelNum > L) // 5, 6, 7, 8, 9, 10
{
double *deltaUnitCapFee = new double[hardwareLevelNum-L];
double *deltaFeeRatio = NULL;
if (hardwareLevelNum > L+1)
deltaFeeRatio = new double[hardwareLevelNum-L-1];
for (i = L; i < hardwareLevelNum; ++i)
deltaUnitCapFee[i-L] = unitOutputCapFee[i] - unitOutputCapFee[i-1];
for (i = 0; i < hardwareLevelNum-L; ++i)
info_log("deltaUnitCapFee[%u]: %f\n", i+L-1, deltaUnitCapFee[i]);
if (hardwareLevelNum > L+1)
{
uint32_t maxDeltaIdx = 0;
double maxDeltaFeeRatio = -100.0;
for (i = 0; i < hardwareLevelNum-L-1; ++i)
{
deltaFeeRatio[i] = deltaUnitCapFee[i+1] - deltaUnitCapFee[i];
if (deltaFeeRatio[i] < 0)
deltaFeeRatio[i] = -deltaFeeRatio[i];
if (maxDeltaFeeRatio < deltaFeeRatio[i])
{
maxDeltaFeeRatio = deltaFeeRatio[i];
maxDeltaIdx = i+L-1;
}
info_log("deltaFeeRatio[%u]: %f\n", i+L-1, deltaFeeRatio[i]);
}
hardwareLevelNum = maxDeltaIdx + 2;
if (hardwareLevelNum > oldHardwareLevelNum)
hardwareLevelNum = oldHardwareLevelNum;
uncond_log("highest available server level limited to %u\n", hardwareLevelNum-1);
delete []deltaFeeRatio;
}
delete []deltaUnitCapFee;
}
}
int locateLevel(const int nodeCap)
{
int low = 0, high = static_cast<int>(hardwareLevelNum), mid = 0;
while (high - low > 1)
{
mid = low + ((high - low) >> 1);
if (nodeCap < outcapTable[mid])
high = mid;
else
low = mid;
}
return low;
}
int fitLevel(const int outputFlux)
{
if (outputFlux > outcapTable[hardwareLevelNum-1])
return hardwareLevelNum;
int low = -1, high = static_cast<int>(hardwareLevelNum)-1, mid = 0;
while (high - low > 1)
{
mid = low + ((high - low) >> 1);
if (outputFlux <= outcapTable[mid])
high = mid;
else
low = mid;
}
return high;
}
long obtainTotalPurchaseFee(std::vector<int>& serversOutputFlux, size_t serverNum)
{
long totalPurchaseFee = 0;
for (size_t i = 0; i < serverNum; ++i)
{
if (serversOutputFlux[i] > 0)
{
int level = fitLevel(serversOutputFlux[i]);
totalPurchaseFee += priceTable[level];
}
}
return totalPurchaseFee;
}
Complexity defineDefaultComplexity()
{
if (consumptionNodeNum > 300)
return Complexity::Hell;
if (consumptionNodeNum > 200 || networkNodeNum > 800)
return Complexity::UltraHard;
if (consumptionNodeNum > 100 || networkNodeNum > 500)
return Complexity::VeryHard;
if (consumptionNodeNum > 50 || networkNodeNum > 300)
return Complexity::Hard;
if (consumptionNodeNum > 20 || networkNodeNum > 100)
return Complexity::General;
if (consumptionNodeNum > 10 || networkNodeNum > 50)
return Complexity::Simple;
return Complexity::Oversimplified;
}
const char* complexityString(Complexity complexity)
{
switch (complexity)
{
case Complexity::Oversimplified:
return "oversimplified";
case Complexity::Simple:
return "simple";
case Complexity::General:
return "general";
case Complexity::Hard:
return "hard";
case Complexity::VeryHard:
return "very-hard";
case Complexity::UltraHard:
return "ultra-hard";
default:
return "hell";
}
}
//////////////// convenient functions of std::vector and std::list ////////////////
void printVector(std::vector<int>& _vector, const char *_note)
{
if (log_level >= INFO_LEVEL)
{
printf("%s", _note);
for (std::vector<int>::iterator iter = _vector.begin(); iter != _vector.end(); ++iter)
printf("%d ", *iter);
printf("\n");
}
}
void printVector(std::vector<double>& _vector, const char *_note)
{
if (log_level >= INFO_LEVEL)
{
printf("%s", _note);
for (std::vector<double>::iterator iter = _vector.begin(); iter != _vector.end(); ++iter)
printf("%f ", *iter);
printf("\n");
}
}
void printList(std::list<int>& _list, const char *_note)
{
if (log_level >= INFO_LEVEL)
{
printf("%s", _note);
for (std::list<int>::iterator iter = _list.begin(); iter != _list.end(); ++iter)
printf("%d ", *iter);
printf("\n");
}
}
void printList(std::list<double>& _list, const char *_note)
{
if (log_level >= INFO_LEVEL)
{
printf("%s", _note);
for (std::list<double>::iterator iter = _list.begin(); iter != _list.end(); ++iter)
printf("%f ", *iter);
printf("\n");
}
}
Graph.h：
/*************************************************************************************
* @copyright: Huawei Technologies Co. Ltd. *
* @file: Graph.h *
* @author: Xu Le, He Jianfan *
* This file is part of 2017 Huawei CodeCraft solution <http://codecraft.huawei.com> *
*************************************************************************************/
#ifndef __GRAPH_H__
#define __GRAPH_H__
#include "Utils.h"
#define INF 0x7fffffff
enum class ArcStatus {
T, ///< in T, 0 < arc.flow < bandwidth
L, ///< in L, arc.flow == 0
U ///< in U, arc.flow == bandwidth
};
enum class MCFStatus {
Unsolved, ///< optimal solution has not be found now.
Solved, ///< has found the optimal solution of problem.
Unfeasible, ///< problem is unfeasible.
Unbounded ///< problem is unbounded.
};
/** arc structure of graph. */
struct Arc
{
Arc();
int arcID; ///< ID of this arc.
int srcID; ///< tail of this arc.
int dstID; ///< head of this arc.
int bandwidth; ///< max capacity of this arc.
int rental; ///< cost weight of this arc.
int flow; ///< initial flow of this arc.
ArcStatus status; ///< tells if arc is deleted, closed, in T, L, or U.
struct Arc *nextArc; ///< next out degree arc of the node this arc derived.
};
/** node structure of graph. */
struct Node
{
Node();
int potential; ///< the node potential corresponding with the flow conservation constrait of this node.
int treeLevel; ///< the depth of the node in T as to T root.
int restrictedCap; ///< restricted output capacity due to imposed server's hardware level limitation.
struct Node *prev; ///< previous node in the order of the Post-Visit on T.
struct Node *next; ///< next node in the order of the Post-Visit on T.
struct Arc *enterArc; ///< entering tree arc of this node.
struct Arc *dummyArc; ///< artificial arcs are used to connect nodes with the dummy root node.
struct Arc *firstArc; ///< first out degree arc of this node.
struct Arc *lastArc; ///< last out degree arc of this node.
};
/** candidate structure used in minimum cost flow algorithm. */
struct Candidate
{
Candidate() : absReductC(0), arc(NULL) {}
int absReductC; ///< absolute value of the arc's reduced cost.
struct Arc *arc; ///< pointer to the violating primal bound arc.
};
/** adjacency list structure representing the graph. */
class Graph
{
public:
explicit Graph(uint32_t _node_num);
~Graph();
/** @name regular methods of Graph. */
///@{
void construct(std::list<struct LinkTuple>& linkTuples);
void undirectify(std::list<struct LinkTuple>& linkTuples);
void destruct();
void display();
///@}
/** @name API function members used by minimum cost flow algorithm. */
///@{
void addSuperSource(std::list<int>& servers);
void delSuperSource();
void displaySuperSource();
void preMinimumCostFlow();
long minimumCostFlow(std::vector<int>& serversOutputFlux);
void postMinimumCostFlow();
void recordFlowPath();
///@}
/** @name API member functions used by TopologyScanner. */
///@{
void BFS(int src);
void dijkstra(int src);
void recordNodePath(std::vector<int>& path, int src, int dst);
long recordArcPath(std::vector<struct Arc*>& path, int src, int dst);
///@}
public:
/** struct used by exchange operation in Greedy algorithm. */
class FluxFee
{
public:
int from;
int to;
int fee;
bool operator<(FluxFee rhs) const { return fee < rhs.fee; }
};
/** @name API member functions used by Greedy. */
///@{
void setExchangeOperation(bool _exchange_operation);
void setOutputFluxUpbound(uint32_t nodeIdx, int upbound);
///@}
private:
enum Colortype
{
White = 0, ///< denote this node has not been visited.
Gray, ///< denote this node has been visited but its all out degrees hasn't been visited.
Black ///< denote this node's all out degrees has been visited.
};
Graph(const Graph&);
Graph& operator=(const Graph&);
/** @name internal member functions used by minimum cost flow algorithm. */
///@{
struct Arc* _executeCandidateListPivot();
void _sortCandidateList(const uint32_t min, const uint32_t max);
int _reductCost(struct Arc *parc);
int _parent(int index, struct Arc *parc);
void _updateTree(struct Arc *k, const int h, const int k1, const int k2);
struct Node* _cutAndUpdateSubtree(struct Node *root, const int delta);
void _pasteSubtree(struct Node *root, struct Node *lastNode, struct Node *prevNode);
void _addSuperSink();
void _delSuperSink();
void _revertStatusToInitialization();
bool _DFS(int s, int t, std::vector<int>& path, int tmpFlow);
///@}
public:
uint32_t nodeNum; ///< maintaining the node number of the graph.
uint32_t arcNum; ///< maintaining the arc number of the graph.
struct Node *NodeList; ///< storing all the nodes in the graph.
int *dist; ///< recording the time when a node is discovered.
int *fluxThroughNode; ///< used by Greedy in exchange operation.
std::priority_queue<FluxFee> fluxFeeQueue; ///< used by Greedy.
std::list<std::vector<int> > fluxPathList; ///< stores all flux paths from super source to super sink, which is certainly the result of this program.
private:
enum Colortype *color; ///< recording a node's visited status when BFS or DFS traverse is called.
int *pi; ///< maintaining relationship of node's predecessor when BFS, DFS or dijkstra traverse is called.
struct Arc **arcRecord; ///< maintaining relationship of arc's predecessor when to call recordArcPath method after BFS or dijkstra traverse is called.
/** @name data members used by minimum cost maximum flow algorithm. */
///@{
MCFStatus mcfStatus; ///< maintaining MCF status
const uint32_t superSource; ///< the index of super source node, which is nodeNum.
const uint32_t superSink; ///< the index of super sink node, which is nodeNum + 1.
const uint32_t dummyRoot; ///< the index of dummy root node, which is nodeNum + 2.
const uint32_t sinkArcs; ///< start index of arcs pointing to super sink node.
const uint32_t sourceArcs; ///< start index of arcs pointing from super source node.
const uint32_t dummyArcs; ///< start index of artificial dummy arcs.
const uint32_t endDummyArcs; ///< beyond last index of artificial dummy arcs.
struct Candidate *candidate; ///< every element points to an element of the arcs vector which contains an arc violating dual bound
uint32_t groupNum; ///< number of the candidate lists
uint32_t groupPos; ///< contains the actual candidate list
uint32_t tmpCandidateListNum; ///< hot list dimension (it is variable)
uint32_t candidateListNum; ///< number of candidate lists
uint32_t hotListNum; ///< number of candidate lists and hot list dimension
bool exchangeOperation; ///< indicate whether the exchange operation in greedy algorithm has begun.
FluxFee *fluxFeeArray; ///< used by Greedy.
FluxFee **feeMatrix; ///< used by Greedy.
int sumFlux; ///< sum flux in graph, which is equals to sum up demand flux of all consumption node.
int minFlow; ///< used by _DFS function as a global variable.
uint32_t sourceNum; ///< stores the number of chosen nodes deployed with servers to maintain arcNum of graph.
///@}
};
bool verifyScheme(Graph& graph, long& totalRentalFee, long& totalPurchaseFee);
#endif /* __GRAPH_H__ */
Graph.cpp：
/*************************************************************************************
* @copyright: Huawei Technologies Co. Ltd. *
* @file: Graph.cpp *
* @author: Xu Le, He Jianfan *
* This file is part of 2017 Huawei CodeCraft solution <http://codecraft.huawei.com> *
*************************************************************************************/
#include "Graph.h"
extern int log_level;
uint32_t networkNodeNum = 0;
uint32_t linkNum = 0;
uint32_t consumptionNodeNum = 0;
uint32_t hardwareLevelNum = 0;
/**
* @brief maintaining the map from arc ID to the point to arc, cost only O(1).
*
* 1. range of links that between network nodes is [0, 2*linkNum), and all integer indices are filled;
* 2. range of links that between access network node super sink node is [2*linkNum, 2*linkNum+consumptionNodeNum);
* 3. range of links that between super source node and server deployment nodes is
* [2*linkNum+consumptionNodeNum, 2*linkNum+consumptionNodeNum+networkNodeNum);
* 4. range of artificial dummy arcs is [2*linkNum+consumptionNodeNum+networkNodeNum, 2*linkNum+2*consumptionNodeNum+2*networkNodeNum+2).
*/
static struct Arc *arcTable;
/** maintaining the map from server hardware level to its price, cost only O(1). */
std::vector<int> priceTable;
/** maintaining the map from server hardware level to its output capacity, cost only O(1). */
std::vector<int> outcapTable;
/** maintaining the map from network node ID to its deployment fee, cost only O(1). */
std::vector<int> deployTable;
/** maintaining the map from comsumption node ID to its access network node ID, cost only O(1). */
std::vector<int> accessTable;
/** maintaining the map from comsumption node ID to its bandwidth demand, cost only O(1). */
std::vector<int> demandTable;
/** maintaining the map from access node ID to its provide comsumption node ID (reverse table of accessTable), cost only O(1). */
std::unordered_map<int /* access node */, int /* consumption node */> provideTable;
/** automatically increase ID for all arcs. */
static int arcIDIncrement = 0;
/** ownID must less than 2*linkNum. */
struct Arc* oppositeArc(int ownID)
{
if (ownID % 2 == 0)
return &arcTable[ownID+1]; // 0 to 1
else
return &arcTable[ownID-1]; // 1 to 0
}
Arc::Arc() : arcID(arcIDIncrement), srcID(-1), dstID(-1), bandwidth(0), rental(INF), flow(0), status(ArcStatus::L), nextArc(NULL)
{
++arcIDIncrement;
}
Node::Node() : potential(0), treeLevel(1), restrictedCap(outcapTable[hardwareLevelNum-1]), prev(NULL), next(NULL), enterArc(NULL), dummyArc(NULL), firstArc(NULL), lastArc(NULL)
{
}
/**
* constructor of class Graph.
*/
Graph::Graph(uint32_t _node_num) : nodeNum(_node_num), arcNum(0), mcfStatus(MCFStatus::Unsolved),
superSource(_node_num), superSink(_node_num+1), dummyRoot(_node_num+2), sinkArcs(2*linkNum),
sourceArcs(sinkArcs+consumptionNodeNum), dummyArcs(sourceArcs+networkNodeNum), endDummyArcs(dummyArcs+_node_num+2),
exchangeOperation(false)
{
NodeList = new Node[nodeNum + 3]; // plus three, one for super source, one for super sink and one for dummy root
dist = new int[nodeNum + 2];
color = new Colortype[nodeNum + 2];
pi = new int[nodeNum + 2];
arcTable = new Arc[endDummyArcs]; // endDummyArcs == 2*linkNum + consumptionNodeNum + networkNodeNum + _node_num + 2
arcRecord = new Arc*[nodeNum + 2];
fluxThroughNode = new int[nodeNum];
}
/**
* destructor of class Graph.
*/
Graph::~Graph()
{
delete []fluxThroughNode;
delete []arcRecord;
delete []arcTable;
delete []pi;
delete []color;
delete []dist;
delete []NodeList;
}
/**
* construct the graph in the structure of adjacency list.
*/
void Graph::construct(std::list<struct LinkTuple>& linkTuples)
{
std::list<struct LinkTuple>::iterator iter1 = linkTuples.begin(), iter2;
uint32_t arcID = 0;
uint32_t curNode = 0;
uint32_t rank = 2;
struct Arc *firstarc = NULL, *parc = NULL, *qarc = NULL;
firstarc = &arcTable[arcID];
firstarc->srcID = iter1->src;
firstarc->dstID = iter1->dst;
firstarc->bandwidth = iter1->bandwidth;
firstarc->rental = iter1->rental;
firstarc->nextArc = NULL;
curNode = iter1->src; // node index start with 0
NodeList[curNode].firstArc = firstarc;
NodeList[curNode].lastArc = firstarc;
while (true)
{
iter2 = iter1; // iter2 is always a forword element of iter1
++iter2;
if (iter2 == linkTuples.end())
break;
if (iter2->src == iter1->src)
{
if (rank % 2 == 0)
{
arcID += 2;
parc = &arcTable[arcID];
parc->srcID = iter2->src;
parc->dstID = iter2->dst;
parc->bandwidth = iter2->bandwidth;
parc->rental = iter2->rental;
parc->nextArc = NULL;
if (rank == 2)
firstarc->nextArc = parc;
else
qarc->nextArc = parc;
NodeList[curNode].lastArc = parc;
}
else
{
arcID += 2;
qarc = &arcTable[arcID];
qarc->srcID = iter2->src;
qarc->dstID = iter2->dst;
qarc->bandwidth = iter2->bandwidth;
qarc->rental = iter2->rental;
qarc->nextArc = NULL;
parc->nextArc = qarc;
NodeList[curNode].lastArc = qarc;
}
rank++;
}
else
{
rank = 2;
curNode = iter2->src;
arcID += 2;
firstarc = &arcTable[arcID];
firstarc->srcID = curNode;
firstarc->dstID = iter2->dst;
firstarc->bandwidth = iter2->bandwidth;
firstarc->rental = iter2->rental;
firstarc->nextArc = NULL;
NodeList[curNode].firstArc = firstarc;
NodeList[curNode].lastArc = firstarc;
}
++iter1;
}
}
/**
* @brief tranform directed graph to be undirected graph.
*/
void Graph::undirectify(std::list<struct LinkTuple>& linkTuples)
{
std::list<struct LinkTuple>::iterator iter = linkTuples.begin();
struct Arc *parc = NULL;
uint32_t arcID = 1; // set arc x and x+1 be the same link with opposite direction, x is an even integer
for (; iter != linkTuples.end(); ++iter, arcID += 2)
{
uint32_t curNode = iter->dst; // alias
parc = &arcTable[arcID];
parc->srcID = curNode;
parc->dstID = iter->src;
parc->bandwidth = iter->bandwidth;
parc->rental = iter->rental;
parc->nextArc = NULL;
if (NodeList[curNode].firstArc == NULL)
NodeList[curNode].firstArc = parc;
else
NodeList[curNode].lastArc->nextArc = parc; // append to the last
NodeList[curNode].lastArc = parc; // update lastArc
}
}
/**
* destruct the graph and free memory.
*/
void Graph::destruct()
{
for (uint32_t i = 0; i < nodeNum; ++i)
{
NodeList[i].firstArc = NULL;
NodeList[i].lastArc = NULL;
}
}
/**
* display the graph whose structure is adjacency list.
*/
void Graph::display()
{
if (log_level < DEBUG_LEVEL)
return;
printf("Graph's adjacency list displays: \n");
for (uint32_t i = 0; i < nodeNum; i++)
{
struct Arc *darc = NULL;
printf("node: [%u]", i);
for (darc = NodeList[i].firstArc; darc != NULL; darc = darc->nextArc)
printf(" -> %d(%d,%d)", darc->dstID, darc->bandwidth, darc->rental);
printf("\n");
}
}
/** a collection of things to be done before executing minimum cost flow algorithm, this function called only once. */
void Graph::preMinimumCostFlow()
{
uint32_t i = 0;
sumFlux = 0;
for (i = 0; i < consumptionNodeNum; ++i)
sumFlux += demandTable[i];
candidateListNum = nodeNum > 1000 ? 50 : 30;
hotListNum = nodeNum > 1000 ? 10 : 6;
candidate = new Candidate[hotListNum + candidateListNum + 1];
uint32_t arcID = dummyArcs;
struct Arc *parc = &arcTable[arcID++];
parc->srcID = 0;
parc->dstID = dummyRoot;
parc->bandwidth = INF;
parc->rental = 10000000;
parc->status = ArcStatus::T;
NodeList[0].prev = &NodeList[dummyRoot];
NodeList[0].next = &NodeList[1];
NodeList[0].dummyArc = parc;
NodeList[0].enterArc = parc;
for (i = 1; i < nodeNum+1; ++i, ++arcID) // source nodes or transit node
{
parc = &arcTable[arcID];
parc->srcID = static_cast<int>(i);
parc->dstID = dummyRoot;
parc->bandwidth = INF;
parc->rental = 10000000;
parc->status = ArcStatus::T;
NodeList[i].prev = &NodeList[i-1];
NodeList[i].next = &NodeList[i+1];
NodeList[i].dummyArc = parc;
NodeList[i].enterArc = parc;
}
NodeList[superSource].potential = 0;
NodeList[superSource].dummyArc->flow = sumFlux;
parc = &arcTable[arcID];
parc->srcID = dummyRoot;
parc->dstID = superSink;
parc->bandwidth = INF;
parc->rental = 10000000;
parc->status = ArcStatus::T;
NodeList[superSink].potential = 20000000;
NodeList[superSink].prev = &NodeList[superSource];
NodeList[superSink].next = NULL;
NodeList[superSink].dummyArc = parc;
NodeList[superSink].enterArc = parc;
NodeList[superSink].dummyArc->flow = sumFlux;
NodeList[dummyRoot].potential = 10000000;
NodeList[dummyRoot].treeLevel = 0;
NodeList[dummyRoot].prev = NULL;
NodeList[dummyRoot].next = &NodeList[0];
// modify arcs from super source node to server deployment nodes, these status
// will stay constant in addSuperSource() or delSuperSource(), thus only do once here
for (i = sourceArcs; i < dummyArcs; ++i)
{
arcTable[i].srcID = superSource;
arcTable[i].bandwidth = outcapTable[hardwareLevelNum-1]; // throughput of network nodes are the highest level CDN server's output capacity
arcTable[i].rental = 0; // access link need no rental fee
}
/*
visited = new bool[nodeNum+2];
fluxFeeArray = new FluxFee[networkNodeNum*networkNodeNum];
feeMatrix = new FluxFee*[networkNodeNum]; // a point array, convenient to use form feeMatrix[i][j]
for (uint32_t k = 0; k < networkNodeNum; ++k)
feeMatrix[k] = fluxFeeArray + k*networkNodeNum;
for (int i = 0; i < static_cast<int>(networkNodeNum); ++i)
{
for (int j = 0; j < static_cast<int>(networkNodeNum); ++j)
{
feeMatrix[i][j].from = i;
feeMatrix[i][j].to = j;
}
}
*/
_addSuperSink();
}
/** API function for Greedy. */
void Graph::setExchangeOperation(bool _exchange_operation)
{
exchangeOperation = _exchange_operation;
}
/** API function for Greedy. */
void Graph::setOutputFluxUpbound(uint32_t nodeIdx, int upbound)
{
NodeList[nodeIdx].restrictedCap = upbound;
}
/** Network Primal Simplex Algorithm. */
long Graph::minimumCostFlow(std::vector<int>& serversOutputFlux)
{
long totalCost = 0;
mcfStatus = MCFStatus::Unsolved;
uint32_t i = 0;
struct Arc *enteringArc = NULL, *leavingArc = NULL, *parc = NULL;
groupNum = (arcNum-1)/candidateListNum + 1;
groupPos = 0;
tmpCandidateListNum = 0;
while (mcfStatus == MCFStatus::Unsolved)
{
enteringArc = _executeCandidateListPivot();
if (enteringArc != NULL)
{
int n1 = enteringArc->dstID, n2 = enteringArc->srcID;
int t = 0, tau = enteringArc->status != ArcStatus::U ? enteringArc->bandwidth - enteringArc->flow : enteringArc->flow;
if (enteringArc->status != ArcStatus::U)
std::swap(n1, n2);
leavingArc = NULL;
int storeN1 = n1, storeN2 = n2;
bool isLeave = false, isLeavingReductFlow = _reductCost(enteringArc) > 0;
while (n1 != n2)
{
int oldN1 = n1, oldN2 = n2;
if (NodeList[n1].treeLevel > NodeList[n2].treeLevel)
{
parc = NodeList[n1].enterArc;
t = parc->srcID == n1 ? parc->flow : parc->bandwidth - parc->flow;
isLeave = parc->srcID == n1;
n1 = _parent(n1, parc);
}
else
{
parc = NodeList[n2].enterArc;
t = parc->srcID != n2 ? parc->flow : parc->bandwidth - parc->flow;
isLeave = parc->srcID != n2;
n2 = _parent(n2, parc);
}
if (t < tau || (t <= tau && NodeList[oldN1].treeLevel <= NodeList[oldN2].treeLevel))
{
tau = t;
leavingArc = parc;
isLeavingReductFlow = isLeave;
}
}
if (leavingArc == NULL)
leavingArc = enteringArc;
if (tau >= INF)
{
mcfStatus = MCFStatus::Unbounded;
break;
}
n1 = storeN1;
n2 = storeN2;
if (tau != 0)
{
enteringArc->flow += (enteringArc->srcID != n1) ? -tau : tau;
while (n1 != n2)
{
if (NodeList[n1].treeLevel > NodeList[n2].treeLevel)
{
parc = NodeList[n1].enterArc;
parc->flow += (parc->srcID == n1) ? -tau : tau;
n1 = _parent(n1, NodeList[n1].enterArc);
}
else
{
parc = NodeList[n2].enterArc;
parc->flow += (parc->srcID != n2) ? -tau : tau;
n2 = _parent(n2, NodeList[n2].enterArc);
}
}
}
if (enteringArc != leavingArc)
{
bool isLeavingBringFlow = isLeavingReductFlow == (NodeList[leavingArc->srcID].treeLevel > NodeList[leavingArc->dstID].treeLevel);
bool isEnteringEqualsN1 = enteringArc->srcID == storeN1;
n1 = enteringArc->dstID;
n2 = enteringArc->srcID;
if (isEnteringEqualsN1 != isLeavingBringFlow)
std::swap(n1, n2);
}
leavingArc->status = isLeavingReductFlow ? ArcStatus::L : ArcStatus::U;
if (leavingArc != enteringArc)
{
enteringArc->status = ArcStatus::T;
if (NodeList[leavingArc->srcID].treeLevel < NodeList[leavingArc->dstID].treeLevel)
_updateTree(enteringArc, leavingArc->dstID, n1, n2);
else
_updateTree(enteringArc, leavingArc->srcID, n1, n2);
n2 = enteringArc->dstID;
int delta = _reductCost(enteringArc);
if (NodeList[enteringArc->srcID].treeLevel > NodeList[enteringArc->dstID].treeLevel)
{
delta = -delta;
n2 = enteringArc->srcID;
}
// execute add potential operation
int level = NodeList[n2].treeLevel;
struct Node *pnode = &NodeList[n2];
do {
pnode->potential += delta;
pnode = pnode->next;
}
while (pnode != NULL && pnode->treeLevel > level);
}
}
else
{
mcfStatus = MCFStatus::Solved;
for (i = dummyArcs; i < endDummyArcs; ++i)
if (arcTable[i].flow > 0)
mcfStatus = MCFStatus::Unfeasible;
}
}
if (mcfStatus == MCFStatus::Solved)
{
for (i = sourceArcs; i < arcNum; ++i)
serversOutputFlux[i-sourceArcs] = arcTable[i].flow; // adapt overlaying method other than clear() and push_back() method for efficiency
if (exchangeOperation)
{
memset(fluxThroughNode, 0, networkNodeNum*sizeof(int));
for (i = 0; i < networkNodeNum; ++i)
for (parc = NodeList[i].firstArc; parc != NULL; parc = parc->nextArc)
fluxThroughNode[i] += parc->flow;
}
}
if (mcfStatus == MCFStatus::Solved)
{
for (i = 0; i < sourceArcs; ++i)
if (arcTable[i].status == ArcStatus::T || arcTable[i].status == ArcStatus::U)
totalCost += arcTable[i].flow * arcTable[i].rental;
}
else
totalCost = -1;
return totalCost;
}
struct Arc* Graph::_executeCandidateListPivot()
{
uint32_t i = 0, next = 0, minimeValue = (hotListNum < tmpCandidateListNum) ? hotListNum : tmpCandidateListNum;
int reductC = 0;
struct Arc *parc = NULL;
for (i = 2; i <= minimeValue; ++i)
{
parc = candidate[i].arc;
reductC = _reductCost(parc);
if ((reductC < 0 && parc->status == ArcStatus::L) || (reductC > 0 && parc->status == ArcStatus::U))
{
++next;
candidate[next].arc = parc;
candidate[next].absReductC = (reductC >= 0) ? reductC : -reductC;
}
}
tmpCandidateListNum = next;
uint32_t oldGroupPos = groupPos;
do {
for (i = groupPos; i < arcNum; i += groupNum)
{
parc = &arcTable[i];
if (parc->status == ArcStatus::L)
{
reductC = _reductCost(parc);
if (reductC < 0)
{
++tmpCandidateListNum;
candidate[tmpCandidateListNum].arc = parc;
candidate[tmpCandidateListNum].absReductC = (reductC >= 0) ? reductC : -reductC;
}
}
else if (parc->status == ArcStatus::U)
{
reductC = _reductCost(parc);
if (reductC > 0)
{
++tmpCandidateListNum;
candidate[tmpCandidateListNum].arc = parc;
candidate[tmpCandidateListNum].absReductC = (reductC >= 0) ? reductC : -reductC;
}
}
}
if (++groupPos >= groupNum)
groupPos = 0;
}
while (tmpCandidateListNum < hotListNum && groupPos != oldGroupPos);
if (tmpCandidateListNum > 0)
_sortCandidateList(1, tmpCandidateListNum);
return tmpCandidateListNum > 0 ? candidate[1].arc : NULL;
}
void Graph::_sortCandidateList(const uint32_t min , const uint32_t max)
{
uint32_t low = min, high = max;
int cut = candidate[(low + high)/2].absReductC; // alias
do {
while (candidate[low].absReductC > cut)
++low;
while (candidate[high].absReductC < cut)
--high;
if (low < high)
std::swap(candidate[low], candidate[high]);
if (low <= high)
{
++low;
--high;
}
}
while ( low <= high );
if (min < high)
_sortCandidateList(min, high);
if (low < max && low <= hotListNum)
_sortCandidateList(low, max);
}
int Graph::_reductCost(struct Arc *parc)
{
return parc->rental + NodeList[parc->srcID].potential - NodeList[parc->dstID].potential;
}
int Graph::_parent(int index, struct Arc *parc)
{
if (parc == NULL)
{
error_log("parc is NULL when _parent() is called.\n");
return -1;
}
return (parc->srcID == index) ? parc->dstID : parc->srcID;
}
void Graph::_updateTree(struct Arc *enteringArc, const int n, const int n1, const int n2)
{
int delta = NodeList[n1].treeLevel + 1 - NodeList[n2].treeLevel;
int root = n2, parent = 0;
struct Node *prevNode = &NodeList[n1], *lastNode = NULL;
struct Arc *parc = enteringArc, *qarc = NULL;
bool ok = false;
while (ok == false)
{
ok = root == n;
parent = _parent(root, NodeList[root].enterArc);
lastNode = _cutAndUpdateSubtree(&NodeList[root], delta);
delta += 2;
_pasteSubtree(&NodeList[root], lastNode, prevNode);
prevNode = lastNode;
qarc = NodeList[root].enterArc;
NodeList[root].enterArc = parc;
parc = qarc;
root = parent;
}
}
struct Node* Graph::_cutAndUpdateSubtree(struct Node *root, const int delta)
{
int level = root->treeLevel;
struct Node *pnode = root;
while (pnode->next && pnode->next->treeLevel > level)
{
pnode = pnode->next;
pnode->treeLevel += delta;
}
root->treeLevel += delta;
if (root->prev != NULL)
root->prev->next = pnode->next;
if (pnode->next != NULL)
pnode->next->prev = root->prev;
return pnode;
}
void Graph::_pasteSubtree(struct Node *root, struct Node *lastNode, struct Node *prevNode)
{
struct Node *nextNode = prevNode->next;
root->prev = prevNode;
prevNode->next = root;
lastNode->next = nextNode;
if (nextNode != NULL)
nextNode->prev = lastNode;
}
/** a collection of things to be done after executing minimum cost flow algorithm, this function called only once. */
void Graph::postMinimumCostFlow()
{
_delSuperSink();
delete []candidate;
/*
delete []visited;
delete []feeMatrix;
delete []fluxFeeArray;
*/
}
/** used to record flow paths after minimum cost maximum flow algorithm finished, this function should be called only once. */
void Graph::recordFlowPath()
{
int source = superSource;
int sink = superSink;
std::vector<int> path;
path.reserve(16);
while ( _DFS(source, sink, path, INF) )
;
}
/** called by recordFlowPath(). */
bool Graph::_DFS(int s, int t, std::vector<int>& path, int tmpFlow)
{
if (s == t)
{
path.push_back(tmpFlow);
fluxPathList.push_back(path);
path.clear();
minFlow = tmpFlow;
return true;
}
struct Arc *parc = NodeList[s].firstArc;
while (parc != NULL)
{
if (parc->flow > 0)
{
if (parc->dstID != t)
path.push_back(parc->dstID);
if ( _DFS(parc->dstID, t, path, std::min(tmpFlow, parc->flow)) )
{
parc->flow -= minFlow;
return true;
}
}
parc = parc->nextArc;
}
return false;
}
/** add the super source node, this function should be called every time right before algorithm starts. */
void Graph::addSuperSource(std::list<int>& servers)
{
struct Arc *parc = NULL;
sourceNum = static_cast<uint32_t>(servers.size());
arcNum = sourceArcs + sourceNum;
uint32_t arcID = sourceArcs;
for (std::list<int>::iterator iter = servers.begin(); iter != servers.end(); ++iter, ++arcID)
{
parc = &arcTable[arcID];
parc->dstID = *iter; // network node which deploys a CDN server
parc->bandwidth = NodeList[parc->dstID].restrictedCap;
parc->nextArc = NULL;
if (NodeList[superSource].firstArc == NULL)
NodeList[superSource].firstArc = parc;
else
NodeList[superSource].lastArc->nextArc = parc; // append to the last
NodeList[superSource].lastArc = parc; // update lastArc too
}
}
/** delete the super source node, this function should be called every time right after minimumCostFlow() is called. */
void Graph::delSuperSource()
{
_revertStatusToInitialization();
NodeList[superSource].firstArc = NULL;
NodeList[superSource].lastArc = NULL;
for (uint32_t i = sourceArcs; i < sourceArcs+sourceNum; ++i)
arcTable[i].dstID = -1;
}
/** display arcs from super source to deployment node, only useful when debugging. */
void Graph::displaySuperSource()
{
if (log_level < DEBUG_LEVEL)
return;
printf("Super source node's adjacency list displays: \n");
struct Arc *darc = NULL;
printf("node: [%d]", superSource);
for (darc = NodeList[superSource].firstArc; darc != NULL; darc = darc->nextArc)
printf(" -> %d(%d,%d)", darc->dstID, darc->bandwidth, darc->rental);
printf("\n");
}
/** revert the status of all arcs to initialization, this function automatically called by delSuperSource(). */
void Graph::_revertStatusToInitialization()
{
uint32_t i;
// revert arcs' status
for (i = 0; i < arcNum; ++i)
{
arcTable[i].flow = 0;
arcTable[i].status = ArcStatus::L;
}
for (i = dummyArcs; i < endDummyArcs; ++i)
{
arcTable[i].flow = 0;
arcTable[i].status = ArcStatus::T;
}
arcTable[endDummyArcs-2].flow = sumFlux;
arcTable[endDummyArcs-1].flow = sumFlux;
// revert nodes' status
NodeList[0].potential = 0;
NodeList[0].treeLevel = 1;
NodeList[0].prev = &NodeList[dummyRoot];
NodeList[0].next = &NodeList[1];
NodeList[0].enterArc = NodeList[0].dummyArc;
for (i = 1; i < nodeNum+1; ++i) // source nodes or transit node
{
NodeList[i].potential = 0;
NodeList[i].treeLevel = 1;
NodeList[i].prev = &NodeList[i-1];
NodeList[i].next = &NodeList[i+1];
NodeList[i].enterArc = NodeList[i].dummyArc;
}
NodeList[superSink].potential = 20000000;
NodeList[superSink].treeLevel = 1;
NodeList[superSink].prev = &NodeList[superSource];
NodeList[superSink].next = NULL;
NodeList[superSink].enterArc = NodeList[superSink].dummyArc;
NodeList[dummyRoot].potential = 10000000;
NodeList[dummyRoot].treeLevel = 0;
NodeList[dummyRoot].prev = NULL;
NodeList[dummyRoot].next = &NodeList[0];
// revert candidates' status
for (i = 0; i <= hotListNum + candidateListNum; ++i)
{
candidate[i].absReductC = 0;
candidate[i].arc = NULL;
}
}
/** add the super sink node, this function is called by preMinimumCostFlow(). */
void Graph::_addSuperSink()
{
struct Arc *parc = NULL;
uint32_t arcID = sinkArcs;
for (uint32_t i = 0; i < consumptionNodeNum; ++i, ++arcID)
{
int curNode = accessTable[i]; // access node index
parc = &arcTable[arcID];
parc->srcID = curNode;
parc->dstID = superSink; // super sink node
parc->bandwidth = demandTable[i]; // demand bandwidth of each consumption node
parc->rental = 0; // access link need no rental fee
parc->nextArc = NULL;
if (NodeList[curNode].firstArc == NULL)
NodeList[curNode].firstArc = parc;
else
NodeList[curNode].lastArc->nextArc = parc; // append to the last
NodeList[curNode].lastArc = parc; // update lastArc too
}
}
/** delete the super sink node, this function is called by postMinimumCostFlow(). */
void Graph::_delSuperSink()
{
uint32_t i = 0;
for (i = 0; i < consumptionNodeNum; ++i)
{
int curNode = accessTable[i];
struct Arc *lastarc = NodeList[curNode].firstArc, *prevarc = NULL;
while (lastarc->nextArc != NULL)
{
prevarc = lastarc;
lastarc = lastarc->nextArc;
}
if (NodeList[curNode].firstArc->nextArc == NULL)
{
NodeList[curNode].firstArc = NULL;
NodeList[curNode].lastArc = NULL;
}
else
{
prevarc->nextArc = NULL;
NodeList[curNode].lastArc = prevarc;
}
}
for (i = sinkArcs; i < sourceArcs; ++i)
arcTable[i].srcID = -1;
}
/**
* use BFS algorithm to traverse the graph at the start node src.
*/
void Graph::BFS(int src)
{
int u, v;
for (uint32_t i = 0; i < nodeNum; ++i)
{
color[i] = Colortype::White;
dist[i] = INF;
pi[i] = -1;
}
color[src] = Colortype::Gray;
dist[src] = 0;
pi[src] = -1;
arcRecord[src] = NULL;
std::queue<int> Q;
Q.push(src);
while (!Q.empty())
{
u = Q.front();
Q.pop();
struct Arc *parc = NodeList[u].firstArc;
while (parc != NULL)
{
v = parc->dstID;
if (color[v] == Colortype::White && parc->rental != INF)
{
color[v] = Colortype::Gray;
dist[v] = dist[u] + 1;
pi[v] = u;
arcRecord[v] = parc;
Q.push(v);
}
parc = parc->nextArc;
}
color[u] = Colortype::Black;
}
}
/**
* use dijkstra algorithm to calculate the minimum distance from node src to other nodes.
*/
void Graph::dijkstra(int src)
{
int u, v;
for (uint32_t i = 0; i < nodeNum; ++i)
{
dist[i] = INF;
pi[i] = 0;
}
dist[src] = 0;
pi[src] = -1;
arcRecord[src] = NULL;
std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int> >, std::greater<std::pair<int, int> > > priorityQ;
priorityQ.push(std::pair<int, int>(0, src));
while (!priorityQ.empty())
{
u = priorityQ.top().second;
priorityQ.pop();
struct Arc *parc = NodeList[u].firstArc;
while (parc != NULL)
{
v = parc->dstID;
if (dist[v] > dist[u] + parc->rental)
{
dist[v] = dist[u] + parc->rental;
pi[v] = u;
arcRecord[v] = parc;
priorityQ.push(std::pair<int, int>(dist[v], v));
}
parc = parc->nextArc;
}
}
}
/**
* obtain the node path from src to dst after call BFS() or dijkstra().
*/
void Graph::recordNodePath(std::vector<int>& path, int src, int dst)
{
std::stack<int> S;
while (dst != src)
{
S.push(dst);
dst = pi[dst];
}
S.push(dst);
while (!S.empty())
{
path.push_back(S.top());
S.pop();
}
}
/**
* obtain the arc path from src to dst after call BFS() or dijkstra().
*/
long Graph::recordArcPath(std::vector<struct Arc*>& path, int src, int dst)
{
std::stack<int> S;
long costSum = 0;
while (dst != src)
{
int tmp = dst;
dst = arcRecord[dst]->arcID;
S.push(dst);
dst = pi[tmp];
}
while (!S.empty())
{
path.push_back(&arcTable[S.top()]);
costSum += arcTable[S.top()].rental;
S.pop();
}
return costSum;
}
/** verification of the final CDN server deployment scheme. */
bool verifyScheme(Graph& graph, long& totalRentalFee, long& totalPurchaseFee)
{
if (graph.fluxPathList.size() > 300000)
{
error_log("The number of flux paths has overstep the limits!\n");
return false;
}
uint32_t i = 0;
totalRentalFee = 0;
totalPurchaseFee = 0;
std::vector<int> arcLeftBandwidth(graph.arcNum, 0);
std::vector<int> demandSatified(consumptionNodeNum, 0);
std::unordered_set<int> serverNodeSet;
for (i = 0; i < graph.arcNum; ++i)
arcLeftBandwidth[i] = arcTable[i].bandwidth;
int fluxPathIdx = 1;
for (std::list<std::vector<int> >::iterator iter = graph.fluxPathList.begin(); iter != graph.fluxPathList.end(); ++iter, ++fluxPathIdx)
{
debug_log("verify flux path %d...\n", fluxPathIdx);
std::vector<int>& fluxPath = *iter; // alias
if (fluxPath.size() < 4)
{
error_log("The number of nodes in a flux path less than 3, it must be an invalid flux path!\n");
return false;
}
if (fluxPath.size() > 10000)
{
error_log("The number of nodes in a flux path has overstep the limits!\n");
return false;
}
int serverNodeID = fluxPath[0];
uint32_t accessNodeIdx = static_cast<uint32_t>(fluxPath.size()) - 4;
int consumptionNodeID = fluxPath[accessNodeIdx+1];
int consumptionBandwidth = fluxPath[accessNodeIdx+2];
int serverHardwareLevel = fluxPath.back();
if (fluxPath[accessNodeIdx] != accessTable[consumptionNodeID])
{
error_log("The access network node[%d] in the flux path is not the same with that required[%d]!\n", fluxPath[accessNodeIdx], accessTable[consumptionNodeID]);
return false;
}
demandSatified[consumptionNodeID] += consumptionBandwidth;
if (serverNodeSet.find(serverNodeID) == serverNodeSet.end())
{
serverNodeSet.insert(serverNodeID);
totalPurchaseFee += priceTable[serverHardwareLevel];
}
struct Arc *parc = graph.NodeList[serverNodeID].firstArc;
for (i = 1; i <= accessNodeIdx; ++i)
{
while (parc != NULL)
{
if (parc->dstID == fluxPath[i])
{
totalRentalFee += parc->rental*consumptionBandwidth;
arcLeftBandwidth[parc->arcID] -= consumptionBandwidth;
if (arcLeftBandwidth[parc->arcID] < 0)
{
error_log("The left bandwidth of arc[%d] which is %d -> %d belows zero!\n", parc->arcID, parc->srcID, parc->dstID);
return false;
}
parc = graph.NodeList[parc->dstID].firstArc;
break;
}
parc = parc->nextArc;
}
if (parc == NULL)
{
error_log("The flux path has an arc that is not in the graph!\n");
return false;
}
}
}
for (uint32_t k = 0; k < consumptionNodeNum; ++k)
{
if (demandSatified[k] < demandTable[k])
{
error_log("The flux scheme cannot satify the bandwidth requirement of consumption node[%u]!\n", k);
return false;
}
}
return true;
}
TopologyScanner.h：
/*************************************************************************************
* @copyright: Huawei Technologies Co. Ltd. *
* @file: TopologyScanner.h *
* @author: Xu Le *
* This file is part of 2017 Huawei CodeCraft solution <http://codecraft.huawei.com> *
*************************************************************************************/
#ifndef __TOPOLOGYSCANNER_H__
#define __TOPOLOGYSCANNER_H__
#include "Graph.h"
class Greedy; // forward declaration
/** A class undertaking to scan graph topology to find some useful results. */
class TopologyScanner
{
public:
explicit TopologyScanner(Graph& _graph);
~TopologyScanner();
TopologyScanner(const TopologyScanner& rhs) = delete;
TopologyScanner& operator=(const TopologyScanner& rhs) = delete;
void scan();
void recommend();
void resetRestrictedCap();
private:
/** description of the density of arcs in graph. */
enum class ArcDensity {
Unknown = 0,
UltraSparse,
VerySparse,
Sparse,
General,
Dense,
VeryDense,
UltraDense
};
/** description of the density of consumption nodes in graph. */
enum class CspDensity {
Unknown = 8,
UltraSparse,
VerySparse,
Sparse,
General,
Dense,
VeryDense,
UltraDense
};
const char* _arcDensityString();
const char* _cspDensityString();
void _defineDensity();
void _mustDeployOnAccess();
void _decideMultiplicativeFactor();
void _selectByScore();
private:
friend class Greedy;
Graph &graph; ///< reference to graph.
ArcDensity arcDensity; ///< stores the density of arcs in graph.
CspDensity cspDensity; ///< stores the density of consumption nodes in graph.
int mNetworkNodeNum; ///< equals to networkNodeNum, just get rid of annoying type incompatible warning.
/** @name status of all network nodes. */
///@{
int *outLinkCap; ///< the sum up capacity of all links of a network node.
int *nodeLevel; ///< the out link capacity level of a network node.
double *outLinkFee; ///< the weighted average rental fee of all links of a network node.
double *capRank; ///< the sum up capacity rank of a network node.
double *rentalFeeRank; ///< the weighted average rental fee rank of a network node.
double *deployFeeRank; ///< the deployment fee rank of a network node.
int *scoreTable; ///< stores score of all network nodes.
double capVariance; ///< variance of node output capacity
///@}
double multiplicativeFactor; ///< the result multiplied by consumption node num is the number of network nodes to be selected as possible servers' deployment location. (decided by cspDensity)
std::vector<int> possibleServers; ///< all network nodes with high score that are possibly chosen as where to deploy servers.
std::set<int> definiteServers; ///< set of access nodes that have to deploy a cdn server.
};
#endif /* __TOPOLOGYSCANNER_H__ */
TopologyScanner.cpp：
/*************************************************************************************
* @copyright: Huawei Technologies Co. Ltd. *
* @file: TopologyScanner.cpp *
* @author: Xu Le *
* This file is part of 2017 Huawei CodeCraft solution <http://codecraft.huawei.com> *
*************************************************************************************/
#include "TopologyScanner.h"
int maxUnitRentalFee = 0;
extern int log_level;
extern uint32_t networkNodeNum;
extern uint32_t linkNum;
extern uint32_t consumptionNodeNum;
extern uint32_t hardwareLevelNum;
extern std::vector<int> priceTable;
extern std::vector<int> outcapTable;
extern std::vector<int> deployTable;
extern std::vector<int> accessTable;
extern std::vector<int> demandTable;
extern std::unordered_map<int, int> provideTable;
TopologyScanner::TopologyScanner(Graph& _graph) : graph(_graph), arcDensity(ArcDensity::Unknown), cspDensity(CspDensity::Unknown), multiplicativeFactor(2.0)
{
mNetworkNodeNum = static_cast<int>(networkNodeNum);
outLinkCap = new int[networkNodeNum];
outLinkFee = new double[networkNodeNum];
nodeLevel = new int[networkNodeNum];
capRank = new double[networkNodeNum];
rentalFeeRank = new double[networkNodeNum];
deployFeeRank = new double[networkNodeNum];
scoreTable = new int[networkNodeNum];
std::fill(outLinkCap, outLinkCap + networkNodeNum, 0);
std::fill(outLinkFee, outLinkFee + networkNodeNum, 0.0);
}
TopologyScanner::~TopologyScanner()
{
delete []outLinkCap;
delete []outLinkFee;
delete []nodeLevel;
delete []capRank;
delete []rentalFeeRank;
delete []deployFeeRank;
delete []scoreTable;
}
/** scan the network topology of graph. */
void TopologyScanner::scan()
{
uncond_log("\n==================== Enter topology scanner category ====================\n");
_defineDensity();
uint32_t i = 0;
double capAverage = 0.0;
double capSquareSum = 0.0;
for (i = 0; i < networkNodeNum; ++i)
{
struct Arc *parc = graph.NodeList[i].firstArc;
while (parc != NULL)
{
// if (parc->dstID < static_cast<int>(networkNodeNum))
// {
outLinkCap[i] += parc->bandwidth;
outLinkFee[i] += parc->bandwidth*parc->rental;
// }
parc = parc->nextArc;
}
}
std::vector<std::pair<int, int> > sortLinkCap;
std::vector<std::pair<double, int> > sortLinkFee;
std::vector<std::pair<int, int> > sortDeployFee;
sortLinkCap.reserve(networkNodeNum);
sortLinkFee.reserve(networkNodeNum);
sortDeployFee.reserve(networkNodeNum);
for (i = 0; i < networkNodeNum; ++i)
{
capAverage += outLinkCap[i];
capSquareSum += square(outLinkCap[i]);
outLinkFee[i] /= outLinkCap[i];
nodeLevel[i] = locateLevel(outLinkCap[i]);
if (nodeLevel[i] < static_cast<int>(hardwareLevelNum-1) && outLinkCap[i] - outcapTable[nodeLevel[i]] < 5)
graph.NodeList[i].restrictedCap = outcapTable[nodeLevel[i]];
sortLinkCap.emplace_back(outLinkCap[i], i);
sortLinkFee.emplace_back(outLinkFee[i], i);
sortDeployFee.emplace_back(deployTable[i], i);
}
capAverage /= networkNodeNum;
capVariance = (capSquareSum - networkNodeNum * square(capAverage)) / networkNodeNum;
info_log("capAverage: %f, capVariance: %f\n", capAverage, capVariance);
std::sort(sortLinkCap.begin(), sortLinkCap.end(), std::greater<std::pair<int, int> >());
std::sort(sortLinkFee.begin(), sortLinkFee.end());
std::sort(sortDeployFee.begin(), sortDeployFee.end());
for (i = 0; i < networkNodeNum; ++i)
{
capRank[sortLinkCap[i].second] = 1.0 - static_cast<double>(i)/mNetworkNodeNum;
rentalFeeRank[sortLinkFee[i].second] = 1.0 - static_cast<double>(i)/mNetworkNodeNum;
}
uint32_t aheadRank = 0;
deployFeeRank[sortDeployFee[0].second] = 1.0;
for (i = 1; i < networkNodeNum; ++i)
{
if (sortDeployFee[i].first > sortDeployFee[i-1].first)
aheadRank = i;
deployFeeRank[sortDeployFee[i].second] = 1.0 - static_cast<double>(aheadRank)/mNetworkNodeNum;
}
for (i = 0; i < networkNodeNum; ++i)
{
debug_log("node[%u] -> outLinkCap: %d, outLinkFee: %f, capRank: %f, rentalFeeRank: %f\n", i, outLinkCap[i], outLinkFee[i], capRank[i], rentalFeeRank[i]);
}
for (i = 0; i < networkNodeNum; ++i)
scoreTable[i] = 200 * capRank[i] + 100 * rentalFeeRank[i] + 75 * deployFeeRank[i];
_mustDeployOnAccess();
}
/** recommend some network nodes that may be good as the input of Greedy algorithm. */
void TopologyScanner::recommend()
{
_selectByScore();
uint32_t i = 0, definiteNum = 0;
// std::vector<int> certainGroup;
debug_log("definite servers:");
for (size_t k = 0; k < possibleServers.size(); ++k)
{
if (scoreTable[possibleServers[k]] != INF)
break;
++definiteNum;
definiteServers.insert(possibleServers[k]);
if (log_level >= DEBUG_LEVEL)
printf(" %d", possibleServers[k]);
}
for (i = definiteNum; i < static_cast<uint32_t>(possibleServers.size()); ++i) // shift to overlaying definite servers
possibleServers[i-definiteNum] = possibleServers[i];
for (i = 0; i < definiteNum; ++i)
possibleServers.pop_back();
if (log_level >= DEBUG_LEVEL)
printf("\n");
debug_log("possible servers:");
if (log_level >= DEBUG_LEVEL) // print possible servers
{
for (i = 0; i < static_cast<uint32_t>(possibleServers.size()); ++i)
printf(" %d", possibleServers[i]);
printf("\n");
}
uncond_log("==================== Exit topology scanner category ====================\n\n");
}
void TopologyScanner::resetRestrictedCap()
{
for (uint32_t i = 0; i < networkNodeNum; ++i)
{
graph.NodeList[i].restrictedCap = outcapTable[hardwareLevelNum-1];
nodeLevel[i] = locateLevel(outLinkCap[i]);
if (nodeLevel[i] < static_cast<int>(hardwareLevelNum-1) && outLinkCap[i] - outcapTable[nodeLevel[i]] < 5)
graph.NodeList[i].restrictedCap = outcapTable[nodeLevel[i]];
}
}
const char* TopologyScanner::_arcDensityString()
{
switch (arcDensity)
{
case ArcDensity::UltraSparse:
return "ultra-sparse";
case ArcDensity::VerySparse:
return "very-sparse";
case ArcDensity::Sparse:
return "sparse";
case ArcDensity::General:
return "general";
case ArcDensity::Dense:
return "dense";
case ArcDensity::VeryDense:
return "very-dense";
case ArcDensity::UltraDense:
return "ultra-dense";
default:
return "unknown";
}
}
const char* TopologyScanner::_cspDensityString()
{
switch (cspDensity)
{
case CspDensity::UltraSparse:
return "ultra-sparse";
case CspDensity::VerySparse:
return "very-sparse";
case CspDensity::Sparse:
return "sparse";
case CspDensity::General:
return "general";
case CspDensity::Dense:
return "dense";
case CspDensity::VeryDense:
return "very-dense";
case CspDensity::UltraDense:
return "ultra-dense";
default:
return "unknown";
}
}
void TopologyScanner::_defineDensity()
{
double _arc_density = static_cast<double>(2*linkNum) / mNetworkNodeNum;
if (_arc_density < 2.0)
arcDensity = ArcDensity::UltraSparse;
else if (_arc_density >= 2.0 && _arc_density < 3.0)
arcDensity = ArcDensity::VerySparse;
else if (_arc_density >= 3.0 && _arc_density < 4.0)
arcDensity = ArcDensity::Sparse;
else if (_arc_density >= 4.0 && _arc_density < 6.0)
arcDensity = ArcDensity::General;
else if (_arc_density >= 6.0 && _arc_density < 9.0)
arcDensity = ArcDensity::Dense;
else if (_arc_density >= 9.0 && _arc_density < 14.0)
arcDensity = ArcDensity::VeryDense;
else // (_arc_density >= 14.0)
arcDensity = ArcDensity::UltraDense;
info_log("arc ratio: %f, its density level: %s\n", _arc_density, _arcDensityString());
double _csp_density = static_cast<double>(consumptionNodeNum) / mNetworkNodeNum;
if (_csp_density < 0.1)
cspDensity = CspDensity::UltraSparse;
else if (_csp_density >= 0.1 && _csp_density < 0.15)
cspDensity = CspDensity::VerySparse;
else if (_csp_density >= 0.15 && _csp_density < 0.2)
cspDensity = CspDensity::Sparse;
else if (_csp_density >= 0.2 && _csp_density < 0.3)
cspDensity = CspDensity::General;
else if (_csp_density >= 0.3 && _csp_density < 0.4)
cspDensity = CspDensity::Dense;
else if (_csp_density >= 0.4 && _csp_density < 0.5)
cspDensity = CspDensity::VeryDense;
else // (_csp_density >= 0.5)
cspDensity = CspDensity::UltraDense;
info_log("csp ratio: %f, its density level: %s\n", _csp_density, _cspDensityString());
}
void TopologyScanner::_mustDeployOnAccess()
{
std::vector<std::pair<int /* rental */, int /* bandwidth */> > feeCapPair;
feeCapPair.reserve(64);
for (uint32_t i = 0; i < consumptionNodeNum; ++i)
{
int accessNode = accessTable[i]; // alias
int demandFlux = demandTable[i]; // alias
if (outLinkCap[accessNode] < demandFlux)
{
scoreTable[accessNode] = INF; // large enough, indicating this network node must be deployed with a server
continue;
}
struct Arc *parc = graph.NodeList[accessNode].firstArc;
while (parc != NULL)
{
if (parc->dstID < mNetworkNodeNum)
feeCapPair.emplace_back(parc->rental, parc->bandwidth);
parc = parc->nextArc;
}
std::sort(feeCapPair.begin(), feeCapPair.end(), [](const std::pair<int, int>& lhs, const std::pair<int, int>& rhs) {
if (lhs.first == rhs.first)
return lhs.second > rhs.second;
return lhs.first < rhs.first;
});
int inputFlux = 0, inputRentalFee = 0;
size_t j = 0;
for (; inputFlux < demandFlux && j < feeCapPair.size(); ++j)
{
inputFlux += feeCapPair[j].second;
inputRentalFee += feeCapPair[j].first * feeCapPair[j].second;
}
inputRentalFee -= (inputFlux - demandFlux) * feeCapPair[j-1].first;
debug_log("minimum input rental fee of access node [%d] is %d\n", accessNode, inputRentalFee);
if (inputRentalFee >= deployTable[accessNode] + priceTable[0])
{
info_log("access node [%d] have to deploy a server.\n", accessNode);
scoreTable[accessNode] = INF; // large enough, indicating this network node must be deployed with a server
}
feeCapPair.clear();
}
}
void TopologyScanner::_decideMultiplicativeFactor()
{
switch (cspDensity)
{
case CspDensity::UltraSparse:
multiplicativeFactor = 5.0; break; // 5.0
case CspDensity::VerySparse:
multiplicativeFactor = 3.6; break; // 3.6
case CspDensity::Sparse:
multiplicativeFactor = 2.8; break; // 2.8
case CspDensity::General:
multiplicativeFactor = 2.0; break; // 2.0
case CspDensity::Dense:
multiplicativeFactor = 1.5; break; // 1.5
case CspDensity::VeryDense:
multiplicativeFactor = 1.2; break; // 1.2
case CspDensity::UltraDense:
multiplicativeFactor = 1.1; break; // 1.1
default:
multiplicativeFactor = 2.0; // the same as general case
}
}
void TopologyScanner::_selectByScore()
{
_decideMultiplicativeFactor();
std::vector<std::pair<int /* score */, int /* ID */> > scoreIDPair;
scoreIDPair.reserve(networkNodeNum);
uint32_t i = 0, nonAccessNum = 0, candidateNum = static_cast<uint32_t>(multiplicativeFactor*consumptionNodeNum);
for (i = 0; i < networkNodeNum; ++i)
scoreIDPair.emplace_back(scoreTable[i], i);
std::sort(scoreIDPair.begin(), scoreIDPair.end(), std::greater<std::pair<int, int> >());
debug_log("score sort from high to low: ");
possibleServers.reserve(candidateNum);
for (i = 0; i < networkNodeNum; ++i)
{
int nodeID = scoreIDPair[i].second; // alias
if (provideTable.find(nodeID) != provideTable.end())
{
if (log_level >= DEBUG_LEVEL)
printf("%d ", scoreIDPair[i].first);
possibleServers.push_back(nodeID);
}
else if (provideTable.find(nodeID) == provideTable.end() && nonAccessNum < candidateNum - consumptionNodeNum)
{
if (log_level >= DEBUG_LEVEL)
printf("%d ", scoreIDPair[i].first);
possibleServers.push_back(nodeID);
++nonAccessNum;
}
}
printf("\n");
}
Greedy.h：
/*************************************************************************************
* @copyright: Huawei Technologies Co. Ltd. *
* @file: Greedy.h *
* @author: Xu Le, He Jianfan *
* This file is part of 2017 Huawei CodeCraft solution <http://codecraft.huawei.com> *
*************************************************************************************/
#ifndef __GREEDY_H__
#define __GREEDY_H__
#include "TopologyScanner.h"
#define uuid(n1, n2) (n1 << 16) + n2
/** Greedy algorithm implemented by a finite state machine(FSM). */
class Greedy
{
public:
explicit Greedy(TopologyScanner& _scanner);
~Greedy();
Greedy(const Greedy& rhs) = delete;
Greedy& operator=(const Greedy& rhs) = delete;
void initialize(std::list<int>& servers);
bool optimize(std::list<int>& servers, std::vector<int>& serversOutputFlux, long justResultFee, long purchaseFee, long deploymentFee);
private:
enum Progress {
ZOM, ///< Zero Order Minus.
ZOP, ///< Zero Order Plus.
DL, ///< Decrease Level Operation.
DLSTEP, ///< Single Step Of Decrease Level Operation.
IL, ///< Increase Level Operation.
ILSTEP, ///< Single Step Of Increase Level Operation.
EX, ///< Exchange Operation.(neighbor)
EXSTEP, ///< Single Step Of Exchange Operation.(neighbor)
EX2, ///< Exchange Operation.(good)
EX2STEP, ///< Single Step Of Exchange Operation.(good)
RM ///< Remove Operation.
};
struct OverFluxTuple
{
OverFluxTuple(double _unitFee, int _nodeID, int _preLevel) : unitFee(_unitFee), nodeID(_nodeID), preLevel(_preLevel) {}
double unitFee; ///< unit over flux fee.
int nodeID; ///< node ID.
int preLevel; ///< hardware level before decrease operation.
};
private:
TopologyScanner &scanner; ///< reference to topologyScanner
enum Progress progress; ///< indicates current optimize progress.
uint32_t minusPlusTimes; ///< times of executed zero order minus and zero order plus progress.
const uint32_t MAX_MINUS_PLUS_TIMES; ///< max allowed times of executing zero order minus and zero order plus progress.
const int MAX_TRY_TIMES_IN_EX; ///< max allowed trying times of exchanging a certain pair of nodes.
int curIdx; ///< current possible consumption node index.
uint32_t curNBIdx; ///< current selected exchangeable neighbor node index.
uint32_t cspCN; ///< only count those possible consumption node.
uint32_t neighborCN; ///< only count those exchangeable neighbor node.
bool *deployed; ///< if node x has deployed a server, then deployed[i] is true, otherwise false.
int *cspRank; ///< consumption rank used in zero order plus and zero order minus progress.
bool hasExecutedZOP; ///< whether ZOP progress has been executed.
bool exchangeSwitch; ///< true indicates adapt flow through rule in EX2, false indicates adapt unit flux fee rule in EX2.
bool inDecreaseProgress; ///< control which part of code to be executed when state just switched to decrease progress.
bool inIncreaseProgress; ///< control which part of code to be executed when state just switched to increase progress.
bool inExchangeProgress; ///< control which part of code to be executed when state just switched to exchange progress.
bool inRemovingProgress; ///< control which part of code to be executed when state just switched to removing progress.
int tryDecreaseTimes; ///< store the number we have tried to decrease server level.
int tryIncreaseTimes; ///< store the number we have tried to increase server level.
int tryExchangeTimes; ///< store the number we have tried to exchange, it is used to resume curIdx when return to exchange operation.
uint32_t decreasableIdx; ///< current index of decreasable node.
uint32_t decreasableNum; ///< number of decreasable node.
uint32_t increasableIdx; ///< current index of increasable node.
uint32_t increasableNum; ///< number of increasable node.
uint32_t exchangeableIdx; ///< current index of exchangeable node.
uint32_t exchangeableCIdx; ///< current index of exchangeable node.
uint32_t exchangeableNum; ///< number of exchangeable node.
uint32_t exchangeableCN; ///< number of exchangeable node.
uint32_t removableIdx; ///< current index of removable node.
uint32_t removableNum; ///< number of removable node.
const uint32_t kDecreasableNum; ///< const number of decreasable node.
const uint32_t kIncreasableNum; ///< const number of increasable node.
const uint32_t kExchangeableNum; ///< const number of exchangeable node.
const uint32_t kExchangeableCN; ///< const number of exchangeable node.
const uint32_t kRemovableNum; ///< const number of removable node.
int lastChangedNode; ///< store the node in previous minus operation for undo operation.
long lastResultFee; ///< store the total fee result by previous operation for comparsion purpose.
std::vector<double> deltaPrice; ///< delta price of two neighbor level, deltaPrice[i] == priceTable[i+1] - priceTable[i], where i >= 0
std::vector<std::pair<int, int> > decreasableArray; ///< decreasable node array.
std::vector<std::pair<int, int> > increasableArray; ///< increasable node array.
std::vector<int> exchangeableArray; ///< exchangeable node array.
std::vector<int> neighborArray; ///< store exchangeable neighbors.
std::vector<int> exchangeableCArray; ///< exchangeable node array.
std::vector<int> removableArray; ///< removable node array.
std::unordered_set<int> serverHashset; ///< store current server deployment nodes.
std::unordered_map<int /* uuid */, int /* times */> exchangeTimes; ///< store how many times a pair of node was exchanged.
std::list<int>::iterator itS; ///< iterate servers list for remove a certain server.
};
#endif /* __GREEDY_H__ */
Greedy.cpp：
/*************************************************************************************
* @copyright: Huawei Technologies Co. Ltd. *
* @file: Greedy.cpp *
* @author: Xu Le, He Jianfan *
* This file is part of 2017 Huawei CodeCraft solution <http://codecraft.huawei.com> *
*************************************************************************************/
#include "Greedy.h"
#define REMOVE_ACCESS_NODE for (itS = servers.begin(); itS != servers.end(); ++itS) { if (*itS == cspRank[curIdx]) { servers.erase(itS); break; } }
#define REMOVE_CHANGED_NODE for (itS = servers.begin(); itS != servers.end(); ++itS) { if (*itS == lastChangedNode) { servers.erase(itS); break; } }
extern int log_level;
extern uint32_t networkNodeNum;
extern uint32_t linkNum;
extern uint32_t consumptionNodeNum;
extern uint32_t hardwareLevelNum;
extern std::vector<int> priceTable;
extern std::vector<int> outcapTable;
extern std::vector<int> deployTable;
extern std::vector<int> accessTable;
extern std::vector<int> demandTable;
extern std::unordered_map<int, int> provideTable;
extern std::list<int> curBestServers;
Greedy::Greedy(TopologyScanner& _scanner) : scanner(_scanner), progress(Progress::ZOM),
minusPlusTimes(0), MAX_MINUS_PLUS_TIMES(networkNodeNum/600+1), MAX_TRY_TIMES_IN_EX(15), curIdx(0), curNBIdx(0),
hasExecutedZOP(false), exchangeSwitch(false), inDecreaseProgress(false), inIncreaseProgress(false), inExchangeProgress(false), inRemovingProgress(false),
kDecreasableNum(networkNodeNum/20), kIncreasableNum(networkNodeNum/20), kExchangeableNum(networkNodeNum/20), kExchangeableCN(networkNodeNum/20), kRemovableNum(5)
{
deployed = new bool[networkNodeNum];
cspCN = static_cast<uint32_t>(scanner.possibleServers.size());
cspRank = new int[cspCN];
tryDecreaseTimes = static_cast<int>(networkNodeNum) / 6; // needn't to be changed
tryIncreaseTimes = static_cast<int>(networkNodeNum) / 6; // needn't to be changed
decreasableArray.resize(kDecreasableNum);
increasableArray.resize(kIncreasableNum);
exchangeableArray.resize(kExchangeableNum);
neighborArray.resize(1024);
exchangeableCArray.resize(kExchangeableCN);
removableArray.resize(kRemovableNum);
}
Greedy::~Greedy()
{
delete []deployed;
delete []cspRank;
}
/** API function of CDN server list initialization required by deploy.cpp. */
void Greedy::initialize(std::list<int>& servers)
{
printf("==================== Enter greedy category ====================\n");
uint32_t i = 0;
progress = Progress::ZOM;
minusPlusTimes = 0;
curIdx = 0;
curNBIdx = 0;
hasExecutedZOP = false;
exchangeSwitch = false;
inDecreaseProgress = false;
inIncreaseProgress = false;
inExchangeProgress = false;
inRemovingProgress = false;
tryDecreaseTimes = static_cast<int>(networkNodeNum) / 6; // needn't to be changed
tryIncreaseTimes = static_cast<int>(networkNodeNum) / 6; // needn't to be changed
for (i = 0; i < networkNodeNum; ++i)
deployed[i] = false;
deltaPrice.resize(hardwareLevelNum);
deltaPrice[0] = priceTable[0];
for (i = 1; i < hardwareLevelNum; ++i)
deltaPrice[i] = priceTable[i] - priceTable[i-1];
exchangeTimes.clear();
for (i = 0; i < cspCN; ++i)
cspRank[i] = scanner.possibleServers[cspCN-i-1];
info_log("==================== Progress::ZOM(1) starts ====================\n");
for (i = 1; i < cspCN; ++i) // the least rank node has been removed
{
servers.push_back(cspRank[i]);
deployed[cspRank[i]] = true;
}
for (std::set<int>::iterator itDef = scanner.definiteServers.begin(); itDef != scanner.definiteServers.end(); ++itDef)
{
servers.push_back(*itDef);
deployed[*itDef] = true;
}
lastChangedNode = cspRank[curIdx];
// set initial total fee to infinity so that optimize() progress can execute normally, though the lease rank node will be removed without examination
lastResultFee = INF;
}
/**
* @brief API function of CDN server list optimization required by deploy.cpp.
*
* 1. initial state is Progress::ZOM and bool variable hasExecutedZOP == false, thus starts at line 118, when it is time to exit this state, then go to line 127,137;
* 2. when state switched to Progress::ZOP, starts at line 163, when it is time to exit this state, set bool variable hasExecutedZOP = true, then go to line 180,184;
* 3. when state switched back to Progress::ZOM, starts at line 86, when it is time to exit this state, then go to line 111;
*/
bool Greedy::optimize(std::list<int>& servers, std::vector<int>& serversOutputFlux, long justRentalFee, long purchaseFee, long deploymentFee)
{
uint32_t i = 0;
long justResultFee = justRentalFee + purchaseFee + deploymentFee;
switch (progress)
{
case Progress::ZOM:
{
if (hasExecutedZOP) // usually will enter this part
{
if (lastResultFee <= justResultFee || justRentalFee == -1) // restore the most recently removed node
{
servers.push_front(lastChangedNode);
deployed[lastChangedNode] = true;
}
else
lastResultFee = justResultFee;
while (!deployed[cspRank[curIdx]] && curIdx < static_cast<int>(cspCN-1))
++curIdx;
if (curIdx < static_cast<int>(cspCN-1)) // quit above while loop due to the first condition
{
REMOVE_ACCESS_NODE
deployed[cspRank[curIdx]] = false;
lastChangedNode = cspRank[curIdx++];
}
else
{
if (++minusPlusTimes < MAX_MINUS_PLUS_TIMES)
curIdx = -1; // prepare to start ZOP progress
else
curIdx = -2; // prepare to start DL progress
hasExecutedZOP = false;
}
}
else if (curIdx > -1) // only the initial state ZOM will enter this part
{
if (lastResultFee <= justResultFee || justRentalFee == -1) // restore the most recently removed node
{
servers.push_front(lastChangedNode);
deployed[lastChangedNode] = true;
}
else
lastResultFee = justResultFee;
if (++curIdx >= static_cast<int>(cspCN-1))
curIdx = -1; // prepare to start ZOP progress
else
{
REMOVE_ACCESS_NODE
deployed[cspRank[curIdx]] = false;
lastChangedNode = cspRank[curIdx];
}
}
else if (curIdx > -2) // actually here is a transitional state when the next loop will switch to Progress::ZOP
{
lastResultFee = justResultFee;
info_log("Total fee after Progress::ZOM(%u) is %ld\n\n", minusPlusTimes, lastResultFee);
info_log("==================== Progress::ZOP(%u) starts ====================\n", minusPlusTimes);
curIdx = 0; // return to 0, loop restarts again
while (deployed[cspRank[curIdx]])
++curIdx;
servers.push_front(cspRank[curIdx]);
deployed[cspRank[curIdx]] = true;
lastChangedNode = cspRank[curIdx++];
progress = Progress::ZOP;
}
else // actually here is a transitional state when the next loop will switch to Progress::DL
{
lastResultFee = justResultFee;
servers = curBestServers;
info_log("Total fee after Progress::ZOM(%u) is %ld\n\n", minusPlusTimes, lastResultFee);
info_log("==================== Progress::DL starts ====================\n");
curIdx = 0;
progress = Progress::DL;
}
break;
}
case Progress::ZOP:
{
if (!hasExecutedZOP) // each time when state has just switched to zero order plus, hasExecutedZOP is always false, see line 116
{
if (lastResultFee <= justResultFee || justRentalFee == -1) // remove the most recently added node
{
servers.pop_front();
deployed[lastChangedNode] = false;
}
else
lastResultFee = justResultFee;
while (deployed[cspRank[curIdx]] && curIdx < static_cast<int>(cspCN-1))
++curIdx;
if (curIdx < static_cast<int>(cspCN-1)) // quit above while loop due to the first condition
{
servers.push_front(cspRank[curIdx]);
deployed[cspRank[curIdx]] = true;
lastChangedNode = cspRank[curIdx++];
}
else
hasExecutedZOP = true;
}
else
{
lastResultFee = justResultFee;
info_log("Total fee after Progress::ZOP(%u) is %ld\n\n", minusPlusTimes, lastResultFee);
info_log("==================== Progress::ZOM(%u) starts ====================\n", minusPlusTimes+1);
curIdx = 0; // return to 0, loop restarts again
while (!deployed[cspRank[curIdx]])
++curIdx;
REMOVE_ACCESS_NODE
deployed[cspRank[curIdx]] = false;
lastChangedNode = cspRank[curIdx++];
progress = Progress::ZOM;
}
break;
}
case Progress::DL:
{
if (!inDecreaseProgress)
{
inDecreaseProgress = true;
// info_log("==================== Progress::DL starts ====================\n");
// info_log("DL --- justResultFee: %ld\n", justResultFee);
--tryDecreaseTimes;
std::vector<struct OverFluxTuple> sortOverFluxFee;
sortOverFluxFee.reserve(servers.size());
for (itS = servers.begin(), i = 0; itS != servers.end(); ++itS, ++i)
{
int curLevel = fitLevel(serversOutputFlux[i]);
if (curLevel > 0 && serversOutputFlux[i] < outcapTable[curLevel])
{
int overFlux = serversOutputFlux[i] - outcapTable[curLevel-1];
sortOverFluxFee.emplace_back(deltaPrice[curLevel]/overFlux, *itS, curLevel);
}
}
std::sort(sortOverFluxFee.begin(), sortOverFluxFee.end(), [](const struct OverFluxTuple& lhs, const struct OverFluxTuple& rhs) { return lhs.unitFee > rhs.unitFee; });
decreasableNum = std::min(kDecreasableNum, static_cast<uint32_t>(sortOverFluxFee.size()));
for (i = 0; i < decreasableNum; ++i)
{
decreasableArray[i].first = sortOverFluxFee[i].nodeID;
decreasableArray[i].second = sortOverFluxFee[i].preLevel;
}
decreasableIdx = 0;
}
lastChangedNode = decreasableArray[decreasableIdx].first;
int postLevel = decreasableArray[decreasableIdx++].second - 1;
if (tryDecreaseTimes < 0)
{
printf("==================== Exit greedy category ====================\n\n");
return false;
}
scanner.graph.setOutputFluxUpbound(lastChangedNode, outcapTable[postLevel]);
progress = Progress::DLSTEP;
break;
}
case Progress::DLSTEP:
{
if (lastResultFee <= justResultFee || justRentalFee == -1) // revert to unrestricted output capacity
{
int preLevel = decreasableArray[decreasableIdx-1].second;
scanner.graph.setOutputFluxUpbound(lastChangedNode, outcapTable[preLevel]);
if (decreasableIdx < decreasableNum)
{
lastChangedNode = decreasableArray[decreasableIdx].first;
int postLevel = decreasableArray[decreasableIdx].second - 1;
scanner.graph.setOutputFluxUpbound(lastChangedNode, outcapTable[postLevel]);
++decreasableIdx;
}
else
{
inDecreaseProgress = false;
progress = networkNodeNum < 1000 ? Progress::IL : Progress::EX;
}
}
else
{
lastResultFee = justResultFee;
info_log("[%d]'s level decreased in Progress::DL\t--- %ld\n", lastChangedNode, justResultFee);
inDecreaseProgress = false;
progress = Progress::DL; // return back to Progress::DL and recalculate unit over flux fee
}
break;
}
case Progress::IL:
{
if (!inIncreaseProgress)
{
inIncreaseProgress = true;
// info_log("==================== Progress::IL starts ====================\n");
// info_log("IL --- justResultFee: %ld\n", justResultFee);
--tryIncreaseTimes;
decreasableIdx = 0;
std::vector<struct OverFluxTuple> sortOverFluxFee;
sortOverFluxFee.reserve(servers.size());
for (itS = servers.begin(), i = 0; itS != servers.end(); ++itS, ++i)
{
int curLevel = fitLevel(serversOutputFlux[i]);
if (curLevel < static_cast<int>(hardwareLevelNum)-1 && serversOutputFlux[i] == outcapTable[curLevel])
{
int overFlux = serversOutputFlux[i] - outcapTable[curLevel-1];
sortOverFluxFee.emplace_back(deltaPrice[curLevel]/overFlux, *itS, curLevel);
}
}
std::sort(sortOverFluxFee.begin(), sortOverFluxFee.end(), [](const struct OverFluxTuple& lhs, const struct OverFluxTuple& rhs) { return lhs.unitFee < rhs.unitFee; });
increasableNum = std::min(kIncreasableNum, static_cast<uint32_t>(sortOverFluxFee.size()));
for (i = 0; i < increasableNum; ++i)
{
increasableArray[i].first = sortOverFluxFee[i].nodeID;
increasableArray[i].second = sortOverFluxFee[i].preLevel;
}
}
lastChangedNode = decreasableArray[decreasableIdx].first;
int postDecreaseLevel = decreasableArray[decreasableIdx].second - 1;
if (++decreasableIdx > decreasableNum)
{
inIncreaseProgress = false;
progress = Progress::EX;
return true;
}
increasableIdx = 0;
if (lastChangedNode == increasableArray[increasableIdx].first)
++increasableIdx;
int curUpgradedNode = increasableArray[increasableIdx].first;
int postIncreaseLevel = increasableArray[increasableIdx].second + 1;
scanner.graph.setOutputFluxUpbound(lastChangedNode, outcapTable[postDecreaseLevel]);
scanner.graph.setOutputFluxUpbound(curUpgradedNode, outcapTable[postIncreaseLevel]);
++increasableIdx;
progress = Progress::ILSTEP;
break;
}
case Progress::ILSTEP:
{
int lastUpgradedNode = increasableArray[increasableIdx-1].first;
if (lastResultFee <= justResultFee || justRentalFee == -1) // revert to unrestricted output capacity and unupgrade output capacity
{
int preIncreaseLevel = increasableArray[increasableIdx-1].second;
scanner.graph.setOutputFluxUpbound(lastUpgradedNode, outcapTable[preIncreaseLevel]); // undo previous upgrade operation
if (lastChangedNode == increasableArray[increasableIdx].first)
++increasableIdx;
if (increasableIdx < increasableNum) // try to upgrade the next increasable node
{
int curUpgradedNode = increasableArray[increasableIdx].first;
int postIncreaseLevel = increasableArray[increasableIdx].second + 1;
scanner.graph.setOutputFluxUpbound(curUpgradedNode, outcapTable[postIncreaseLevel]);
++increasableIdx;
}
else
{
int preDecreaseLevel = decreasableArray[decreasableIdx-1].second;
scanner.graph.setOutputFluxUpbound(lastChangedNode, outcapTable[preDecreaseLevel]);
progress = Progress::IL; // return back to Progress::IL and try the next decreasable node
}
}
else
{
lastResultFee = justResultFee;
info_log("[%d]'s level decreased in Progress::IL\t--- %ld\n", lastChangedNode, justResultFee);
info_log("[%d]'s level increased in Progress::IL\t--- %ld\n", lastUpgradedNode, justResultFee);
inIncreaseProgress = false;
progress = Progress::EX; // go to Progress::DL and try to decrease server's level in new scheme
}
break;
}
case Progress::EX:
{
if (!inExchangeProgress)
{
inExchangeProgress = true;
// info_log("==================== Progress::EX starts ====================\n");
// info_log("EX --- justResultFee: %ld\n", justResultFee);
std::vector<std::pair<double /* unit flux fee */, int /* node ID */> > sortUnitFluxFee;
sortUnitFluxFee.reserve(servers.size());
serverHashset.clear();
for (itS = servers.begin(), i = 0; itS != servers.end(); ++itS, ++i)
{
serverHashset.insert(*itS);
int curLevel = fitLevel(serversOutputFlux[i]);
double totalNodeFee = priceTable[curLevel] + deployTable[*itS];
sortUnitFluxFee.emplace_back(totalNodeFee/serversOutputFlux[i], *itS);
// printf("%d[%.2f] ", *itS, totalNodeFee/serversOutputFlux[i]);
}
// printf("\n");
std::sort(sortUnitFluxFee.begin(), sortUnitFluxFee.end(), std::greater<std::pair<double, int> >());
exchangeableNum = std::min(kExchangeableNum, static_cast<uint32_t>(sortUnitFluxFee.size()));
for (i = 0; i < exchangeableNum; ++i)
exchangeableArray[i] = sortUnitFluxFee[i].second;
exchangeableIdx = 0;
}
lastChangedNode = exchangeableArray[exchangeableIdx];
if (++exchangeableIdx > exchangeableNum)
{
inExchangeProgress = false;
progress = Progress::EX2;
scanner.graph.setExchangeOperation(exchangeSwitch);
return true;
}
neighborCN = 0;
// printf("%d: ", lastChangedNode);
struct Arc *parc = NULL;
for (parc = scanner.graph.NodeList[lastChangedNode].firstArc; parc != NULL; parc = parc->nextArc)
{
if (parc->dstID < scanner.mNetworkNodeNum
&& deployTable[parc->dstID] <= deployTable[lastChangedNode]
&& scanner.nodeLevel[parc->dstID] >= scanner.nodeLevel[lastChangedNode]
&& serverHashset.find(parc->dstID) == serverHashset.end())
{
// printf("%d[%d] -> ", parc->dstID, scanner.nodeLevel[parc->dstID]);
neighborArray[neighborCN++] = parc->dstID;
}
}
// printf("\n");
if (neighborCN > 0)
{
curNBIdx = 0;
while (curNBIdx < neighborCN && ++exchangeTimes[uuid(lastChangedNode, neighborArray[curNBIdx])] > MAX_TRY_TIMES_IN_EX)
++curNBIdx;
if (curNBIdx < neighborCN)
{
REMOVE_CHANGED_NODE
deployed[lastChangedNode] = false;
servers.push_front(neighborArray[curNBIdx]);
deployed[neighborArray[curNBIdx]] = true;
++curNBIdx;
progress = Progress::EXSTEP; // go to Progress::EXSTEP and try to exchange with neighbors one by one
}
}
break;
}
case Progress::EXSTEP:
{
if (lastResultFee <= justResultFee || justRentalFee == -1) // try to exchange with another neighbor or restore the exchangeable node
{
servers.pop_front(); // remove the neighbor node added in previous exchange operation
deployed[neighborArray[curNBIdx-1]] = false;
while (curNBIdx < neighborCN && ++exchangeTimes[uuid(lastChangedNode, neighborArray[curNBIdx])] > MAX_TRY_TIMES_IN_EX)
++curNBIdx;
if (curNBIdx < neighborCN)
{
servers.push_front(neighborArray[curNBIdx]); // add another neighbor
deployed[neighborArray[curNBIdx]] = true;
++curNBIdx;
}
else
{
servers.push_front(lastChangedNode); // restore the exchangeable node removed in previous exchange operation
deployed[lastChangedNode] = true;
progress = Progress::EX; // return back to Progress::EX and try the next exchangeable node
}
}
else
{
lastResultFee = justResultFee;
info_log("node [%d] <-> [%d] in Progress::EX \t--- %ld\n", lastChangedNode, neighborArray[curNBIdx-1], justResultFee);
inExchangeProgress = false;
progress = Progress::DL; // go to Progress::DL and try to decrease server's level in new scheme
}
break;
}
case Progress::EX2:
{
if (!inExchangeProgress)
{
inExchangeProgress = true;
info_log("==================== Progress::EX2 starts ====================\n");
// info_log("EX2 --- justResultFee: %ld\n", justResultFee);
exchangeableIdx = 0;
if (exchangeSwitch)
{
scanner.graph.setExchangeOperation(false);
std::vector<std::pair<int /* flux through */, int /* node ID */> > sortFluxThrough;
sortFluxThrough.reserve(networkNodeNum-servers.size());
for (int l = 0; l < scanner.mNetworkNodeNum; ++l)
if (serverHashset.find(l) == serverHashset.end())
sortFluxThrough.emplace_back(scanner.graph.fluxThroughNode[l], l);
std::sort(sortFluxThrough.begin(), sortFluxThrough.end(), std::greater<std::pair<int, int> >());
exchangeableCN = std::min(kExchangeableCN, static_cast<uint32_t>(sortFluxThrough.size()));
for (i = 0; i < exchangeableCN; ++i)
exchangeableCArray[i] = sortFluxThrough[i].second;
}
else
{
std::vector<std::pair<double /* unit flux fee */, int /* node ID */> > sortUnitFluxFee;
sortUnitFluxFee.reserve(networkNodeNum-servers.size());
for (int l = 0; l < scanner.mNetworkNodeNum; ++l)
{
if (serverHashset.find(l) == serverHashset.end())
{
double totalNodeFee = priceTable[scanner.nodeLevel[l]] + deployTable[l];
sortUnitFluxFee.emplace_back(totalNodeFee/outcapTable[scanner.nodeLevel[l]], l);
}
}
std::sort(sortUnitFluxFee.begin(), sortUnitFluxFee.end());
exchangeableCN = std::min(kExchangeableCN, static_cast<uint32_t>(sortUnitFluxFee.size()));
for (i = 0; i < exchangeableCN; ++i)
exchangeableCArray[i] = sortUnitFluxFee[i].second;
}
exchangeSwitch = exchangeSwitch == false;
}
lastChangedNode = exchangeableArray[exchangeableIdx];
if (++exchangeableIdx > exchangeableNum)
{
inExchangeProgress = false;
progress = Progress::RM;
return true;
}
exchangeableCIdx = 0;
while (exchangeableCIdx < exchangeableCN && ++exchangeTimes[uuid(lastChangedNode, exchangeableCArray[exchangeableCIdx])] > MAX_TRY_TIMES_IN_EX)
++exchangeableCIdx;
if (exchangeableCIdx < exchangeableCN)
{
REMOVE_CHANGED_NODE
deployed[lastChangedNode] = false;
servers.push_front(exchangeableCArray[exchangeableCIdx]);
deployed[exchangeableCArray[exchangeableCIdx]] = true;
++exchangeableCIdx;
progress = Progress::EX2STEP; // go to Progress::EX2STEP and try to exchange with exchangeable candidate nodes one by one
}
break;
}
case Progress::EX2STEP:
{
if (lastResultFee <= justResultFee || justRentalFee == -1) // try to exchange with exchangeable candidate node or restore the exchangeable node
{
servers.pop_front(); // remove the exchangeable candidate node added in previous exchange operation
deployed[exchangeableCArray[exchangeableCIdx-1]] = false;
while (exchangeableCIdx < exchangeableCN && ++exchangeTimes[uuid(lastChangedNode, exchangeableCArray[exchangeableCIdx])] > MAX_TRY_TIMES_IN_EX)
++exchangeableCIdx;
if (exchangeableCIdx < exchangeableCN)
{
servers.push_front(exchangeableCArray[exchangeableCIdx]); // add another exchangeable candidate node
deployed[exchangeableCArray[exchangeableCIdx]] = true;
++exchangeableCIdx;
}
else
{
servers.push_front(lastChangedNode); // restore the exchangeable node removed in previous exchange operation
deployed[lastChangedNode] = true;
progress = Progress::EX2; // return back to Progress::EX2 and try the next exchangeable node
}
}
else
{
lastResultFee = justResultFee;
info_log("node [%d] <-> [%d] in Progress::EX2 \t--- %ld\n", lastChangedNode, exchangeableCArray[exchangeableCIdx-1], justResultFee);
inExchangeProgress = false;
progress = Progress::DL; // go to Progress::DL and try to decrease server's level in new scheme
}
break;
}
case Progress::RM:
{
if (!inRemovingProgress)
{
inRemovingProgress = true;
info_log("==================== Progress::RM starts ====================\n");
std::vector<std::pair<double /* unit flux fee */, int /* node ID */> > sortUnitFluxFee;
sortUnitFluxFee.reserve(servers.size());
for (itS = servers.begin(), i = 0; itS != servers.end(); ++itS, ++i)
{
int curLevel = fitLevel(serversOutputFlux[i]);
double totalNodeFee = priceTable[curLevel] + deployTable[*itS];
sortUnitFluxFee.emplace_back(totalNodeFee/serversOutputFlux[i], *itS);
// printf("%d[%.2f] ", *itS, totalNodeFee/serversOutputFlux[i]);
}
// printf("\n");
std::sort(sortUnitFluxFee.begin(), sortUnitFluxFee.end(), std::greater<std::pair<double, int> >());
removableNum = std::min(kRemovableNum, static_cast<uint32_t>(sortUnitFluxFee.size()));
for (i = 0; i < removableNum; ++i)
{
removableArray[i] = sortUnitFluxFee[i].second;
// printf("%f %d %d\n", sortUnitFluxFee[i].first, removableArray[i], scanner.nodeLevel[removableArray[i]]);
}
removableIdx = 0;
lastChangedNode = removableArray[removableIdx++];
REMOVE_CHANGED_NODE
deployed[lastChangedNode] = false;
}
else
{
if (lastResultFee <= justResultFee || justRentalFee == -1) // try to restore the removable node
{
servers.push_front(lastChangedNode);
deployed[lastChangedNode] = true;
if (removableIdx < removableNum)
{
lastChangedNode = removableArray[removableIdx++];
REMOVE_CHANGED_NODE
deployed[lastChangedNode] = false;
}
else
{
printf("==================== Exit greedy category ====================\n\n");
return false;
}
}
else
{
lastResultFee = justResultFee;
info_log("node [%d] is successfully removed in Progress::RM --- %ld\n", lastChangedNode, justResultFee);
inRemovingProgress = false;
progress = Progress::DL; // go to Progress::DL and try to decrease server's level in new scheme
}
}
break;
}
default:
error_log("Unknown progress!\n");
}
return true;
}
main.cpp：
/*************************************************************************************
* @copyright: Huawei Technologies Co. Ltd. *
* @file: main.cpp *
* @author: Xu Le, He Jianfan *
* This file is part of 2017 Huawei CodeCraft solution <http://codecraft.huawei.com> *
*************************************************************************************/
#include "Greedy.h"
extern int log_level;
extern uint32_t networkNodeNum;
extern uint32_t linkNum;
extern uint32_t consumptionNodeNum;
extern uint32_t hardwareLevelNum;
extern std::vector<int> priceTable;
extern std::vector<int> outcapTable;
extern std::vector<int> deployTable;
extern std::vector<int> accessTable;
extern std::vector<int> demandTable;
extern std::unordered_map<int, int> provideTable;
std::list<int> curBestServers;
int main(int argc, char *argv[])
{
/*************************************************************************************
* @copyright: Huawei Technologies Co. Ltd. *
* @file: main.cpp *
* @author: Xu Le, He Jianfan *
* This file is part of 2017 Huawei CodeCraft solution <http://codecraft.huawei.com> *
*************************************************************************************/
#include "Greedy.h"
extern int log_level;
extern uint32_t networkNodeNum;
extern uint32_t linkNum;
extern uint32_t consumptionNodeNum;
extern uint32_t hardwareLevelNum;
extern std::vector<int> priceTable;
extern std::vector<int> outcapTable;
extern std::vector<int> deployTable;
extern std::vector<int> accessTable;
extern std::vector<int> demandTable;
extern std::unordered_map<int, int> provideTable;
std::list<int> curBestServers;
int main(int argc, char *argv[])
{
Timer procedureTimer("Elapsed Time: ");
/*******************************************************************
******************** Time elapsing ... ********************
*******************************************************************/
// printf("current log level: %s\n\n", getLogLevel());
std::list<struct LinkTuple> linkTuples;
// 1. =============== parse input char* array ===============
parseInput(argv[1], linkTuples);
if (networkNodeNum > 1000)
defineAvailableLevel();
uint32_t bestRestrictedLevelNum = hardwareLevelNum;
debug_log("NetworkNodeNum: %u, LinkNum: %u, ConsumptionNodeNum: %u, HardwareLevelNum: %u\n", networkNodeNum, linkNum, consumptionNodeNum, hardwareLevelNum);
{
// Complexity defaultComplexity = defineDefaultComplexity(); // local variable, just print the complexity for debug, not used to optimize case according to its size
// info_log("default complexity: %s\n", complexityString(defaultComplexity));
}
linkTuples.sort([](const struct LinkTuple& lhs, const struct LinkTuple& rhs) { return lhs.src < rhs.src; });
// 2. =============== construct graph ===============
Graph graph(networkNodeNum);
graph.construct(linkTuples);
graph.undirectify(linkTuples);
linkTuples.clear(); // we don't need it anymore, release its memory
// 3. =============== display graph ===============
// graph.display(); // log control inside
// 4. =============== add minimum cost flow algorithm related components into graph ===============
graph.preMinimumCostFlow();
// 5. =============== critical part of finding a server deployment solution ===============
uint32_t i = 0;
std::list<int> newServers, bestServers;
std::vector<int> serversOutputFlux(networkNodeNum, 0);
std::vector<int> restrictedOutputCap(networkNodeNum, 0);
std::vector<int> gRestrictedOutputCap(networkNodeNum, 0);
// 5.1. ========== check whether the problen is unfeasible ==========
for (i = 0; i < networkNodeNum; ++i)
newServers.push_back(i);
// 5.1.1. ===== add the super source of all network nodes' union onto graph =====
graph.addSuperSource(newServers);
// 5.1.2. ===== calculate minimum cost flow using all network nodes =====
long lowboundRentalFee = graph.minimumCostFlow(serversOutputFlux);
// 5.1.3. ===== delete the super source from graph and revert the status of arc to initialization =====
graph.delSuperSource();
// 5.1.4. ===== check whether no feasible scheme can be found =====
if (lowboundRentalFee == -1)
{
uncond_log("This case is unfeasible, write NA to result file.\n");
// 5.1.5. ===== delete minimum cost flow algorithm related components from graph =====
graph.postMinimumCostFlow();
// 5.1.6. ===== destruct graph =====
graph.destruct();
// 5.1.7. ===== output NA to result file =====
outputToFile(argv[2]);
return 0; // no need to execute rest code, thus return here
}
else
newServers.clear();
// 5.2. ========== scan topology to obtain combinations of some carefully selected network nodes as initial scheme ==========
TopologyScanner topoScanner(graph);
topoScanner.scan();
topoScanner.recommend();
// 5.3. ========== deploy CDN servers on one of these combinations of network nodes ==========
Greedy greedy(topoScanner);
long gMinTotalFee = INF;
double elapsedTime = 0.0;
std::list<int>::iterator itS;
int LOOP = networkNodeNum < 1000 ? 3 : 1;
do {
greedy.initialize(newServers);
// info_log("initial servers: ");
// printList(newServers, "");
int loop = 1;
long minTotalFee = INF;
bool continueLoop = true;
while (true)
{
// 5.4. ========== add a super source onto graph ==========
graph.addSuperSource(newServers);
// 5.5. ========== execute minimum cost flow algorithm ==========
long rentalFee = graph.minimumCostFlow(serversOutputFlux);
long purchaseFee = 0;
long deploymentFee = 0;
if (rentalFee != -1)
{
for (itS = newServers.begin(); itS != newServers.end(); ++itS)
deploymentFee += deployTable[*itS];
purchaseFee = obtainTotalPurchaseFee(serversOutputFlux, newServers.size());
}
// info_log("Link fee is %ld, purchase fee is %ld, deploy fee is %ld, sum up %ld.\n", rentalFee, purchaseFee, deploymentFee, rentalFee + purchaseFee + deploymentFee);
// 5.6. ========== a better deployment solution ? ==========
if (minTotalFee > rentalFee + purchaseFee + deploymentFee && rentalFee != -1)
{
minTotalFee = rentalFee + purchaseFee + deploymentFee;
curBestServers = newServers;
for (i = 0; i < networkNodeNum; ++i)
restrictedOutputCap[i] = graph.NodeList[i].restrictedCap;
}
continueLoop = greedy.optimize(newServers, serversOutputFlux, rentalFee, purchaseFee, deploymentFee);
// 5.7. ========== time is not enough ==========
if (loop % 50 == 0)
elapsedTime = procedureTimer.elapsed();
if (loop % 1000 == 0)
uncond_log("Time elapsed: %fs\n", elapsedTime);
// how many loops do you want?
if (++loop > 20000 || !continueLoop || elapsedTime > 87.0) // we have to exit loop when only 3 seconds left
{
uncond_log("Exit loop: %d\n", loop);
info_log("current best servers: ");
printList(curBestServers, "");
// 5.7.1. ===== delete current super source from graph and revert the status of arc to initialization =====
graph.delSuperSource();
if (LOOP >= 2)
{
if (gMinTotalFee > minTotalFee)
{
gMinTotalFee = minTotalFee;
bestServers = curBestServers;
bestRestrictedLevelNum = hardwareLevelNum;
for (i = 0; i < networkNodeNum; ++i)
gRestrictedOutputCap[i] = restrictedOutputCap[i];
}
newServers.clear();
--hardwareLevelNum;
uncond_log("\nhighest available server level limited to %u\n", hardwareLevelNum-1);
topoScanner.resetRestrictedCap();
break;
}
if (gMinTotalFee > minTotalFee)
{
gMinTotalFee = minTotalFee;
bestServers = curBestServers;
for (i = 0; i < networkNodeNum; ++i)
gRestrictedOutputCap[i] = restrictedOutputCap[i];
}
else
hardwareLevelNum = bestRestrictedLevelNum;
// 5.7.2. ===== add the super source of best servers' union onto graph =====
for (i = 0; i < networkNodeNum; ++i)
graph.NodeList[i].restrictedCap = gRestrictedOutputCap[i];
graph.addSuperSource(bestServers);
// 5.7.3. ===== calculate minimum cost flow using best servers and then record corresponding flow path =====
graph.minimumCostFlow(serversOutputFlux);
graph.recordFlowPath();
// 5.7.4. ===== in fact, it is not must to revert status and delete super source =====
graph.delSuperSource();
break;
}
// 5.8. ========== delete the super source from graph and revert the status of arc to initialization ==========
graph.delSuperSource();
// info_log("new servers: ");
// printList(newServers, "");
}
}
while (--LOOP > 0);
// 6. =============== delete minimum cost flow algorithm related components from graph ===============
graph.postMinimumCostFlow();
info_log("Minimum total fee is %ld.\n", gMinTotalFee);
std::unordered_map<int /* deploy node */, int /* hardware level */> finalChosenLevel;
itS = bestServers.begin();
for (size_t l = 0; l < bestServers.size(); ++l, ++itS)
finalChosenLevel.insert(std::pair<int, int>(*itS, fitLevel(serversOutputFlux[l])));
// 7. =============== modify flux path list to meet output requirement ===============
for (std::list<std::vector<int> >::iterator itfp = graph.fluxPathList.begin(); itfp != graph.fluxPathList.end(); ++itfp)
{
std::vector<int>& fluxPath = *itfp; // alias
int storeFlux = fluxPath.back();
fluxPath.pop_back();
fluxPath.push_back(provideTable[fluxPath.back()]);
fluxPath.push_back(storeFlux);
fluxPath.push_back(finalChosenLevel[fluxPath.front()]);
// printVector(fluxPath, "");
}
// 8. =============== verify servers' deployment, purchase and flux paths scheme ===============
long totalRentalFee = 0, totalPurchaseFee = 0, totalDeploymentFee = 0;
bool schemeOK = verifyScheme(graph, totalRentalFee, totalPurchaseFee);
for (itS = bestServers.begin(); itS != bestServers.end(); ++itS)
totalDeploymentFee += deployTable[*itS];
if (schemeOK == true)
uncond_log("Congratulations! Total rental fee is %ld, purchase fee is %ld, deployment fee is %ld, sum up %ld.\n",
totalRentalFee, totalPurchaseFee, totalDeploymentFee, totalRentalFee + totalPurchaseFee + totalDeploymentFee);
else
error_log("Shit! The scheme failed to pass verification!\n");
// 9. =============== destruct graph ===============
graph.destruct();
// 10. =============== output flux path list to result file ===============
outputToFile(argv[2], graph.fluxPathList);
/*******************************************************************
******************** Time elapsing end ********************
*******************************************************************/
}
注：本文开头处的超链接提供下载的代码包中附带有 18 个测试用例，中级 (600 个点)、高级 (1200 个点) 的各 8 个。