代码版权归大赛组委会所有，请勿转载！
一个多月的初赛终于在 4 月 5 号晚上 24:00 落下帷幕，最终取得杭厦赛区第三的佳绩，3500 行的代码发上来留个纪念，下载地址：
2017-Huawei-Codecraft-Preliminary-CodePackage-Download
吼吼 ~~ 初级用例和中级用例都拿到了满分，也就是用例成绩赛区第一！
今年初赛题目仍然和去年类似，是一道 NP 问题，解空间大小为 2^n – 1，看好了，直接上题目啦！
~~~~~ 华丽丽的分割线 ~~~~~
代码工程的 Makefile 如下：
# This file is part of 2017 Huawei CodeCraft solution <http://codecraft.huawei.com>
CC = g++
CXXFLAGS = -Wall -g -std=c++11
cdn: Log.o Utils.o Graph.o TopologyScanner.o Greedy.o main.o
$(CC) -o $@ $^
main.o: main.cpp Greedy.h Graph.h
$(CC) $(CXXFLAGS) -c $<
Greedy.o: Greedy.cpp Greedy.h TopologyScanner.h Graph.h
$(CC) $(CXXFLAGS) -c $<
TopologyScanner.o: TopologyScanner.cpp TopologyScanner.h Graph.h Utils.h
$(CC) $(CXXFLAGS) -c $<
Graph.o: Graph.cpp Graph.h Utils.h Timer.h
$(CC) $(CXXFLAGS) -c $<
Utils.o: Utils.cpp Utils.h Timer.h
$(CC) $(CXXFLAGS) -c $<
Log.o: Log.cpp Log.h
$(CC) $(CXXFLAGS) -c $<
.PHONY: clean
clean:
rm -f *.o
rm -f cdn
各个代码文件就不解释了，代码全部粘贴如下。
Log.h：
/*************************************************************************************
* @copyright: Huawei Technologies Co. Ltd. *
* @file: Log.h *
* @author: Xu Le *
* This file is part of 2017 Huawei CodeCraft solution <http://codecraft.huawei.com> *
*************************************************************************************/
#ifndef __LOG_H__
#define __LOG_H__
#define _CRT_SECURE_NO_WARNINGS
#include <stdarg.h>
#include <stdio.h>
#define LOG_NEED_MACRO_FILE_LINE 0
#ifdef __GNUC__
#define ERROR_LEVEL 1
#define WARNING_LEVEL 2
#define INFO_LEVEL 3
#define DEBUG_LEVEL 4
#if LOG_NEED_MACRO_FILE_LINE
#define uncond_log(...) do { printf("%s: %d | ", __FILE__, __LINE__); printf(__VA_ARGS__); } while(0)
#define error_log(...) do { if (log_level >= ERROR_LEVEL) { printf("ERROR | %s: %d | ", __FILE__, __LINE__); printf(__VA_ARGS__); } } while(0)
#define warning_log(...) do { if (log_level >= WARNING_LEVEL) { printf("WARN | %s: %d | ", __FILE__, __LINE__); printf(__VA_ARGS__); } } while(0)
#define info_log(...) do { if (log_level >= INFO_LEVEL) { printf("INFO | %s: %d | ", __FILE__, __LINE__); printf(__VA_ARGS__); } } while(0)
#define debug_log(...) do { if (log_level >= DEBUG_LEVEL) { printf("DEBUG | %s: %d | ", __FILE__, __LINE__); printf(__VA_ARGS__); } } while(0)
#else
#define uncond_log(...) do { printf(__VA_ARGS__); } while(0)
#define error_log(...) do { if (log_level >= ERROR_LEVEL) { printf("ERROR | "); printf(__VA_ARGS__); } } while(0)
#define warning_log(...) do { if (log_level >= WARNING_LEVEL) { printf("WARN | "); printf(__VA_ARGS__); } } while(0)
#define info_log(...) do { if (log_level >= INFO_LEVEL) { printf("INFO | "); printf(__VA_ARGS__); } } while(0)
#define debug_log(...) do { if (log_level >= DEBUG_LEVEL) { printf("DEBUG | "); printf(__VA_ARGS__); } } while(0)
#endif
const char* getLogLevel();
#else /* __GNUC__ */
enum class LogLevel {
uncond,
error,
warning,
info,
debug
};
#if LOG_NEED_MACRO_FILE_LINE
void log(LogLevel level, const char *file, const int line, const char *fmt, ...);
#else
void log(LogLevel level, const char *fmt, ...);
#endif
#endif
#endif /* __LOG_H__ */
Log.cpp：
/*************************************************************************************
* @copyright: Huawei Technologies Co. Ltd. *
* @file: Log.cpp *
* @author: Xu Le *
* This file is part of 2017 Huawei CodeCraft solution <http://codecraft.huawei.com> *
*************************************************************************************/
#include "Log.h"
int log_level = 3;
#ifdef __GNUC__
const char* getLogLevel()
{
switch (log_level)
{
case 1:
return "ERROR";
case 2:
return "WARNNING";
case 3:
return "INFO";
case 4:
return "DEBUG";
default:
return "UNKNOWN";
}
}
#else
static void printudec(unsigned int udec)
{
if (udec == 0)
return;
printudec(udec/10);
putchar((char)(udec%10 + '0'));
}
static void printdec(int dec)
{
if (dec < 0)
{
putchar('-');
dec = -dec;
}
printudec((unsigned int)dec);
}
static void printdbl(double dbl)
{
int tmpint = (int)dbl;
printdec(tmpint);
putchar('.');
dbl -= tmpint;
tmpint = (int)(dbl * 1000000);
printdec(tmpint);
}
static void printstr(const char *str)
{
while (*str)
putchar(*str++);
}
static void printbin(int bin)
{
if (bin == 0)
{
printstr("0b");
return;
}
printbin(bin/2);
putchar((char)(bin%2 + '0'));
}
static void printhex(int hex)
{
if (hex == 0)
{
printstr("0x");
return;
}
printhex(hex/16);
if (hex < 10)
putchar((char)(hex%16 + '0'));
else
putchar((char)(hex%16 - 10 + 'a' ));
}
#if LOG_NEED_MACRO_FILE_LINE
void log(LogLevel level, const char *file, const int line, const char *fmt, ...)
#else
void log(LogLevel level, const char *fmt, ...)
#endif
{
switch (level)
{
case LogLevel::uncond:
#if LOG_NEED_MACRO_FILE_LINE
printf("%s: %d | ", file, line);
#endif
break;
case LogLevel::error:
if (log_level >= static_cast<int>(LogLevel::error))
#if LOG_NEED_MACRO_FILE_LINE
printf("ERROR | %s: %d | ", file, line);
#else
printf("ERROR | ");
#endif
else
return;
break;
case LogLevel::warning:
if (log_level >= static_cast<int>(LogLevel::warning))
#if LOG_NEED_MACRO_FILE_LINE
printf("WARN | %s: %d | ", file, line);
#else
printf("WARN | ");
#endif
else
return;
break;
case LogLevel::info:
if (log_level >= static_cast<int>(LogLevel::info))
#if LOG_NEED_MACRO_FILE_LINE
printf("INFO | %s: %d | ", file, line);
#else
printf("INFO | ");
#endif
else
return;
break;
case LogLevel::debug:
if (log_level >= static_cast<int>(LogLevel::debug))
#if LOG_NEED_MACRO_FILE_LINE
printf("DEBUG | %s: %d | ", file, line);
#else
printf("DEBUG | ");
#endif
else
return;
break;
default:
fprintf(stderr, "Log level undefined!\n");
return;
}
va_list vl;
va_start(vl, fmt);
char vargch = 0;
int vargint = 0;
unsigned int varguint = 0;
double vargdbl = 0.0;
char *vargpch = NULL;
char *pfmt = const_cast<char*>(fmt);
while (*pfmt)
{
if (*pfmt == '%')
{
switch (*(++pfmt))
{
case 'c':
vargch = va_arg(vl, int);
putchar(vargch);
break;
case 'd':
case 'i':
vargint = va_arg(vl, int);
printdec(vargint);
break;
case 'u':
varguint = va_arg(vl, unsigned int);
printudec(varguint);
break;
case 'f':
vargdbl = va_arg(vl, double);
printdbl(vargdbl);
break;
case 's':
vargpch = va_arg(vl, char*);
printstr(vargpch);
break;
case 'b':
case 'B':
vargint = va_arg(vl, int);
printbin(vargint);
break;
case 'x':
case 'X':
vargint = va_arg(vl, int);
printhex(vargint);
break;
case '%':
putchar('%');
break;
default:
break;
}
++pfmt;
}
else
{
putchar(*pfmt++);
}
}
va_end(vl);
}
#endif
Timer.h：
/*************************************************************************************
* @copyright: Huawei Technologies Co. Ltd. *
* @file: Timer.h *
* @author: Xu Le *
* This file is part of 2017 Huawei CodeCraft solution <http://codecraft.huawei.com> *
*************************************************************************************/
#ifndef __TIMER_H__
#define __TIMER_H__
#define RUNNING_TIME_HIGH_PRECISION 1
#if defined(__GNUC__) && RUNNING_TIME_HIGH_PRECISION
#include <sys/time.h>
#else
#include <time.h>
#endif
#include <string>
#include "Log.h"
#if defined(__GNUC__) && RUNNING_TIME_HIGH_PRECISION
class Timer
{
public:
explicit Timer(const char *s) : _note(s) { gettimeofday(&_start_time, NULL); }
~Timer()
{
struct timeval _end_time;
gettimeofday(&_end_time, NULL);
printf("%ssecTime = %lds, usecTime = %ldus.\n", _note.c_str(), _end_time.tv_sec - _start_time.tv_sec, _end_time.tv_usec - _start_time.tv_usec);
}
double elapsed()
{
struct timeval _cur_time;
gettimeofday(&_cur_time, NULL);
double secTime = _cur_time.tv_sec - _start_time.tv_sec;
double usecTime = _cur_time.tv_usec - _start_time.tv_usec;
return secTime + usecTime/1000000;
}
private:
Timer(const Timer&);
Timer& operator=(const Timer&);
private:
std::string _note;
struct timeval _start_time;
};
#else
class Timer
{
public:
explicit Timer(const char *s) : _note(s) { _start_time = clock(); }
~Timer() { printf("%s%fs.\n", _note.c_str(), elapsed()); }
inline double elapsed() { return static_cast<double>(clock() - _start_time) / CLOCKS_PER_SEC; }
private:
Timer(const Timer&);
Timer& operator=(const Timer&);
private:
std::string _note;
clock_t _start_time;
};
#endif
#endif /* __TIMER_H__ */
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"
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;
int dst;
int bandwidth;
int rental;
};
enum class Complexity {
Oversimplified,
Simple,
General,
Hard,
VeryHard,
UltraHard,
Hell
};
void parseInput(char *filename, std::list<struct LinkTuple>& linkTuples);
void outputToFile(char *filename, std::list<std::vector<int> >& fluxPathList);
bool binarySearch(const std::vector<int>& vec, const int key);
Complexity defineDefaultComplexity();
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 uint32_t networkNodeNum;
extern uint32_t linkNum;
extern uint32_t consumptionNodeNum;
extern uint32_t serverDeploymentFee;
extern std::vector<int> accessTable;
extern std::vector<int> demandTable;
void parseInput(char *filename, std::list<struct LinkTuple>& linkTuples)
{
FILE *fp = fopen(filename, "r");
if (fp == NULL)
{
error_log("Fail to open file %s.\n", filename);
exit(EXIT_FAILURE);
}
int srcNode = 0, dstNode = 0, bandwidth = 0, rental = 0;
int cspID = 0, netID = 0, demand = 0;
fscanf(fp, "%u %u %u", &networkNodeNum, &linkNum, &consumptionNodeNum);
fgetc(fp);
fscanf(fp, "%u", &serverDeploymentFee);
fgetc(fp);
accessTable.resize(consumptionNodeNum);
demandTable.resize(consumptionNodeNum);
uint32_t _linkNum = linkNum;
uint32_t _consumptionNodeNum = consumptionNodeNum;
while (_linkNum-- > 0)
{
fscanf(fp, "%d %d %d %d", &srcNode, &dstNode, &bandwidth, &rental);
linkTuples.emplace_back(srcNode, dstNode, bandwidth, rental);
}
fgetc(fp);
while (_consumptionNodeNum-- > 0)
{
fscanf(fp, "%d %d %d", &cspID, &netID, &demand);
accessTable[cspID] = netID;
demandTable[cspID] = demand;
}
fclose(fp);
}
void outputToFile(char *filename, std::list<std::vector<int> >& fluxPathList)
{
FILE *fp = fopen(filename, "w");
if (fp == NULL)
{
error_log("Fail to open file %s.\n", filename);
exit(EXIT_FAILURE);
}
fprintf(fp, "%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(fp, "%d ", fluxPath[i]);
fprintf(fp, "%d\n", fluxPath.back());
}
fclose(fp);
}
bool binarySearch(const std::vector<int>& vec, const int key)
{
int low = 0, high = (int)vec.size()-1, mid;
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;
}
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
/** 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 initialCap; ///< initial capacity of this arc.
int initialCost; ///< initial cost of this arc.
Arc *nextArc; ///< next out degree arc of the node this arc derived.
Arc *reverseArc; ///< reverse arc used by minimum cost maximum flow algorithm.
};
/** node structure of graph. */
struct Node
{
Node() : ID(0), firstArc(NULL), lastArc(NULL) {}
int ID; ///< ID of this node.
Arc *firstArc; ///< first out degree arc of this node.
Arc *lastArc; ///< last out degree arc of this node.
};
/** 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 maximum flow algorithm. */
///@{
void preferZKW(bool _useZKW);
void addSuperSource(std::list<int>& servers);
void delSuperSource();
void displaySuperSource();
void preMinimumCostMaximumFlow();
long minimumCostMaximumFlow(std::list<int>& servers);
void postMinimumCostMaximumFlow();
void revertStatusToInitialization();
void recordFlowPath();
///@}
/** @name API function members 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; }
};
std::priority_queue<FluxFee> fluxFeeQueue; ///< used by Greedy.
void setExchangeOperation(bool _exchange_operation);
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 function members used by minimum cost maximum flow algorithm. */
///@{
long _SPFA();
long _ZKW();
int _augment(int u, int f, int from, long& totalCost);
bool _modifyLabel();
void _addSuperSink();
void _delSuperSink();
void _revertCapacityToInitialization();
void _revertCostToInitialization();
bool _DFS(int s, int t, std::vector<int>& path, int tmpFlow);
///@}
public:
uint32_t nodeNum; ///< maintaining the node number of the graph.
struct Node *NodeList; ///< storing all the nodes in the graph.
Colortype *color; ///< recording a node's visited status when BFS or DFS traverse is called.
int *dist; ///< recording the time when a node is discovered.
int *f; ///< recording the time when a node's all out degrees has been visited.
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. */
///@{
bool useZKW; ///< true: use zkw algorithm as minimum cost flow algorithm, false: use spfa algorithm as minimum cost flow algorithm.
bool exchangeOperation; ///< indicate whether the exchange operation in greedy algorithm has begun.
bool *visited; ///< used by zkw.
long cost; ///< used by zkw.
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.
int superSourceID; ///< ID of super source.
int superSinkID; ///< ID of super sink.
uint32_t sourceNum; ///< stores the number of chosen nodes where will be deployed with a server for reverting capacity of arcs that from super source to these chosen nodes.
std::list<std::vector<int> > fluxPathList; ///< stores all flux paths from super source to super sink, which is certainly the result of this program.
///@}
};
bool verifyScheme(Graph& graph, std::list<std::vector<int> >& fluxPathList, long& totalRentalFee);
#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;
extern uint32_t networkNodeNum;
extern uint32_t linkNum;
extern uint32_t consumptionNodeNum;
extern uint32_t serverDeploymentFee;
/**
* @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, 4*linkNum-1], and all integer indices are filled;
* 2. range of links that between access network node and consumption node is
* [4*linkNum, 4*linkNum+4*consumptionNodeNum-2], and all even indices are filled;
* 3. range of links that between consumption nodes and super sink node is
* [4*linkNum+4*consumptionNodeNum, 4*linkNum+8*consumptionNodeNum-2], and all even indices are filled;
* 4. range of links that between super source node and server deployment nodes is
* [4*linkNum+1, 4*linkNum+4*sourceNum-1], and all odd indices are filled.
*/
static std::vector<struct Arc*> arcTable;
/** 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;
/** automatically increase ID for all arcs. */
static int arcIDIncrement = 0;
struct Arc* oppositeArc(int ownID) // ownID must less than 4*linkNum
{
if (ownID % 4 == 0)
return arcTable[ownID+1]; // 0 to 1
else
return arcTable[ownID-1]; // 1 to 0
}
struct Arc* oppositeReverseArc(int ownID) // ownID must less than 4*linkNum
{
if (ownID % 4 == 0)
return arcTable[ownID+3]; // 0 to 3
else
return arcTable[ownID+1]; // 1 to 2
}
Arc::Arc() : arcID(arcIDIncrement), srcID(0), dstID(0), bandwidth(0), rental(INF), initialCap(0), initialCost(0), nextArc(NULL), reverseArc(NULL)
{
arcIDIncrement += 2;
}
/**
* constructor of class Graph.
*/
Graph::Graph(uint32_t _node_num) : nodeNum(_node_num), useZKW(false), exchangeOperation(false), cost(0), sumFlux(0)
{
NodeList = new Node[_node_num + 2]; // plus two, one for super source, one for super sink
color = new Colortype[_node_num + 2];
dist = new int[_node_num + 2];
f = new int[_node_num + 2];
pi = new int[_node_num + 2];
arcRecord = new Arc*[_node_num + 2];
}
/**
* destructor of class Graph.
*/
Graph::~Graph()
{
delete []arcRecord;
delete []pi;
delete []dist;
delete []f;
delete []color;
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;
std::vector<bool> arcIsAdded(nodeNum, false);
uint32_t curNode = 0;
uint32_t i = 0, rank = 2;
struct Arc *firstarc = NULL, *parc = NULL, *qarc = NULL, *rarc = NULL;
uint32_t arcTableSizeDecider = 4 * std::max(networkNodeNum, 2*consumptionNodeNum);
arcTable.resize(4*linkNum + arcTableSizeDecider);
firstarc = new Arc;
firstarc->srcID = iter1->src;
firstarc->dstID = iter1->dst;
firstarc->bandwidth = iter1->bandwidth;
firstarc->rental = iter1->rental;
firstarc->initialCap = iter1->bandwidth;
firstarc->initialCost = iter1->rental;
firstarc->nextArc = NULL;
rarc = new Arc;
rarc->srcID = firstarc->dstID;
rarc->dstID = firstarc->srcID;
rarc->rental = -firstarc->rental;
rarc->initialCost = rarc->rental;
firstarc->reverseArc = rarc;
rarc->reverseArc = firstarc;
curNode = iter1->src; // node index start with 0
arcIsAdded[curNode] = true;
NodeList[curNode].ID = firstarc->srcID;
NodeList[curNode].firstArc = firstarc;
NodeList[curNode].lastArc = firstarc;
arcTable[firstarc->arcID] = firstarc;
arcTable[rarc->arcID] = rarc;
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)
{
parc = new Arc;
parc->srcID = iter2->src;
parc->dstID = iter2->dst;
parc->bandwidth = iter2->bandwidth;
parc->rental = iter2->rental;
parc->initialCap = iter2->bandwidth;
parc->initialCost = iter2->rental;
parc->nextArc = NULL;
rarc = new Arc;
rarc->srcID = parc->dstID;
rarc->dstID = parc->srcID;
rarc->rental = -parc->rental;
rarc->initialCost = rarc->rental;
parc->reverseArc = rarc;
rarc->reverseArc = parc;
if (rank == 2)
firstarc->nextArc = parc;
else
qarc->nextArc = parc;
NodeList[curNode].lastArc = parc;
arcTable[parc->arcID] = parc;
arcTable[rarc->arcID] = rarc;
}
else
{
qarc = new Arc;
qarc->srcID = iter2->src;
qarc->dstID = iter2->dst;
qarc->bandwidth = iter2->bandwidth;
qarc->rental = iter2->rental;
qarc->initialCap = iter2->bandwidth;
qarc->initialCost = iter2->rental;
qarc->nextArc = NULL;
rarc = new Arc;
rarc->srcID = qarc->dstID;
rarc->dstID = qarc->srcID;
rarc->rental = -qarc->rental;
rarc->initialCost = rarc->rental;
qarc->reverseArc = rarc;
rarc->reverseArc = qarc;
parc->nextArc = qarc;
NodeList[curNode].lastArc = qarc;
arcTable[qarc->arcID] = qarc;
arcTable[rarc->arcID] = rarc;
}
rank++;
}
else
{
rank = 2;
curNode = iter2->src;
arcIsAdded[curNode] = true;
firstarc = new Arc;
firstarc->srcID = curNode;
firstarc->dstID = iter2->dst;
firstarc->bandwidth = iter2->bandwidth;
firstarc->rental = iter2->rental;
firstarc->initialCap = iter2->bandwidth;
firstarc->initialCost = iter2->rental;
firstarc->nextArc = NULL;
rarc = new Arc;
rarc->srcID = firstarc->dstID;
rarc->dstID = firstarc->srcID;
rarc->rental = -firstarc->rental;
rarc->initialCost = rarc->rental;
firstarc->reverseArc = rarc;
rarc->reverseArc = firstarc;
NodeList[curNode].ID = curNode;
NodeList[curNode].firstArc = firstarc;
NodeList[curNode].lastArc = firstarc;
arcTable[firstarc->arcID] = firstarc;
arcTable[rarc->arcID] = rarc;
}
++iter1;
}
for (i = 0; i < consumptionNodeNum; ++i)
{
curNode = accessTable[i]; // access network node
arcIsAdded[curNode] = true;
parc = new Arc;
parc->srcID = curNode;
parc->dstID = networkNodeNum + i; // consumption node index
parc->bandwidth = demandTable[i]; // demand bandwidth of each consumption node
parc->rental = 0; // access link need no rental fee
parc->initialCap = demandTable[i];
parc->initialCost = 0;
parc->nextArc = NULL;
rarc = new Arc;
rarc->srcID = parc->dstID;
rarc->dstID = parc->srcID;
rarc->rental = 0;
parc->reverseArc = rarc;
rarc->reverseArc = parc;
NodeList[curNode].ID = curNode;
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
arcTable[parc->arcID] = parc;
arcTable[rarc->arcID] = rarc;
}
for (i = 0; i < nodeNum; ++i)
if (arcIsAdded[i] == false)
NodeList[i].ID = i;
}
/**
* @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, *rarc = NULL;
uint32_t curNode = 0;
arcIDIncrement = 1; // set arc x and x+1 be the same link with opposite direction, x is an even integer
for (; iter != linkTuples.end(); ++iter)
{
curNode = iter->dst; // alias
parc = new Arc;
parc->srcID = curNode;
parc->dstID = iter->src;
parc->bandwidth = iter->bandwidth;
parc->rental = iter->rental;
parc->initialCap = iter->bandwidth;
parc->initialCost = iter->rental;
parc->nextArc = NULL;
rarc = new Arc;
rarc->srcID = parc->dstID;
rarc->dstID = parc->srcID;
rarc->rental = -parc->rental;
rarc->initialCost = rarc->rental;
parc->reverseArc = rarc;
rarc->reverseArc = parc;
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
arcTable[parc->arcID] = parc;
arcTable[rarc->arcID] = rarc;
}
}
/**
* destruct the graph and free memory.
*/
void Graph::destruct()
{
for (uint32_t i = 0; i < nodeNum; ++i)
{
uint32_t rank = 0;
struct Arc *freearc1 = NodeList[i].firstArc, *freearc2 = (freearc1 != NULL) ? freearc1->nextArc : NULL;
while (freearc1 != NULL && freearc2 != NULL)
{
if (rank % 2 == 0)
{
delete freearc1->reverseArc;
delete freearc1;
freearc1 = freearc2->nextArc;
}
else
{
delete freearc2->reverseArc;
delete freearc2;
freearc2 = freearc1->nextArc;
}
++rank;
}
if (freearc1 != NULL)
{
delete freearc1->reverseArc;
delete freearc1;
}
if (freearc2 != NULL)
{
delete freearc2->reverseArc;
delete freearc2;
}
}
}
/**
* 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;
printf("node: [%d]", NodeList[i].ID);
darc = NodeList[i].firstArc;
while (darc != NULL)
{
printf(" -> %d(%d,%d)", darc->dstID, darc->bandwidth, darc->rental);
darc = darc->nextArc;
}
printf("\n");
}
}
/** are you prefer ZKW algorithm to SPFA algorithm? */
void Graph::preferZKW(bool _useZKW)
{
useZKW = _useZKW;
}
/** a collection of things to be done before executing minimum cost maximum flow algorithm, this function called only once. */
void Graph::preMinimumCostMaximumFlow()
{
superSourceID = static_cast<int>(networkNodeNum + consumptionNodeNum);
superSinkID = static_cast<int>(networkNodeNum + consumptionNodeNum + 1);
NodeList[superSourceID].ID = superSourceID;
NodeList[superSinkID].ID = superSinkID;
for (uint32_t l = 0; l < consumptionNodeNum; ++l)
sumFlux += demandTable[l];
if (useZKW)
{
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;
}
/** decide which concrete minimum cost maximum flow algorithm to be executed by bool variable useZKW. */
long Graph::minimumCostMaximumFlow(std::list<int>& servers)
{
if (useZKW)
return _ZKW();
else
return _SPFA();
}
/** a minimum cost maximum flow algorithm using priority queue. */
long Graph::_SPFA()
{
long totalCost = 0;
int sumFlow = sumFlux;
int u, v;
uint32_t totalNodeNum = nodeNum + 2;
struct Arc *parc = NULL, *rarc = NULL;
std::vector<int> h(totalNodeNum, 0);
std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int> >, std::greater<std::pair<int, int> > > priorityQ;
while (sumFlow > 0)
{
std::fill(dist, dist + totalNodeNum, INF);
dist[superSourceID] = 0;
priorityQ.push(std::pair<int, int>(0, superSourceID));
while (!priorityQ.empty())
{
std::pair<int, int> qTop = priorityQ.top();
priorityQ.pop();
u = qTop.second;
if (dist[u] < qTop.first)
continue;
parc = NodeList[u].firstArc;
while (parc != NULL)
{
if (parc->arcID < 4*static_cast<int>(linkNum)) // only arcs that between network nodes have opposite arc
{
rarc = oppositeReverseArc(parc->arcID);
if (parc->arcID % 2 == 0) // itself first, reverse arc of its opposite arc second
{
v = parc->dstID;
if (parc->initialCap > 0 && dist[v] > dist[u] + parc->rental + h[u] - h[v])
{
dist[v] = dist[u] + parc->rental + h[u] - h[v];
pi[v] = u;
arcRecord[v] = parc;
priorityQ.push(std::pair<int, int>(dist[v], v));
}
v = rarc->dstID;
if (rarc->initialCap > 0 && dist[v] > dist[u] + rarc->rental + h[u] - h[v])
{
dist[v] = dist[u] + rarc->rental + h[u] - h[v];
pi[v] = u;
arcRecord[v] = rarc;
priorityQ.push(std::pair<int, int>(dist[v], v));
}
}
else // reverse arc of its opposite arc first, itself second
{
v = rarc->dstID;
if (rarc->initialCap > 0 && dist[v] > dist[u] + rarc->rental + h[u] - h[v])
{
dist[v] = dist[u] + rarc->rental + h[u] - h[v];
pi[v] = u;
arcRecord[v] = rarc;
priorityQ.push(std::pair<int, int>(dist[v], v));
}
v = parc->dstID;
if (parc->initialCap > 0 && dist[v] > dist[u] + parc->rental + h[u] - h[v])
{
dist[v] = dist[u] + parc->rental + h[u] - h[v];
pi[v] = u;
arcRecord[v] = parc;
priorityQ.push(std::pair<int, int>(dist[v], v));
}
}
}
else
{
if (u >= static_cast<int>(networkNodeNum) && u < static_cast<int>(networkNodeNum + consumptionNodeNum)) // u is a consumption node
{
rarc = NodeList[accessTable[u-(int)networkNodeNum]].firstArc;
while (rarc != NULL)
{
if (rarc->dstID == u)
break;
rarc = rarc->nextArc;
}
rarc = rarc->reverseArc;
v = rarc->dstID;
if (rarc->initialCap > 0 && dist[v] > dist[u] + rarc->rental + h[u] - h[v])
{
dist[v] = dist[u] + rarc->rental + h[u] - h[v];
pi[v] = u;
arcRecord[v] = rarc;
priorityQ.push(std::pair<int, int>(dist[v], v));
}
}
v = parc->dstID;
if (parc->initialCap > 0 && dist[v] > dist[u] + parc->rental + h[u] - h[v])
{
dist[v] = dist[u] + parc->rental + h[u] - h[v];
pi[v] = u;
arcRecord[v] = parc;
priorityQ.push(std::pair<int, int>(dist[v], v));
}
}
parc = parc->nextArc;
}
}
if (dist[superSinkID] == INF)
return -1;
for (u = 0; u < (int)totalNodeNum; ++u)
h[u] += dist[u];
int d = sumFlow;
for (u = superSinkID; u != superSourceID; u = pi[u])
{
parc = arcRecord[u];
d = std::min(d, parc->initialCap);
}
for (u = superSinkID; u != superSourceID; u = pi[u])
{
parc = arcRecord[u];
totalCost += d*parc->rental;
}
sumFlow -= d;
for (u = superSinkID; u != superSourceID; u = pi[u])
{
parc = arcRecord[u];
parc->initialCap -= d;
parc->reverseArc->initialCap += d;
}
}
return totalCost;
}
/** https://artofproblemsolving.com/community/c1368h1020435 */
long Graph::_ZKW()
{
long totalCost = 0;
int i = 0, j = 0;
int augFlow = 0;
int sumFlow = sumFlux;
cost = 0;
for (i = 0; i < static_cast<int>(networkNodeNum); ++i)
for (j = 0; j < static_cast<int>(networkNodeNum); ++j)
feeMatrix[i][j].fee = 0;
do {
do {
memset(visited, false, (nodeNum+2) * sizeof(bool));
augFlow = _augment(superSourceID, INF, superSourceID, totalCost);
sumFlow -= augFlow;
}
while ( augFlow );
}
while ( _modifyLabel() );
if (exchangeOperation)
{
while (!fluxFeeQueue.empty())
fluxFeeQueue.pop();
for (i = 0; i < static_cast<int>(networkNodeNum); ++i)
for (j = 0; j < static_cast<int>(networkNodeNum); ++j)
if (feeMatrix[i][j].fee > 0)
fluxFeeQueue.push(feeMatrix[i][j]);
}
return sumFlow > 0 ? -1 : totalCost;
}
/** find a augment path in graph, this function is called by _ZKW(). */
int Graph::_augment(int u, int f, int from, long& totalCost)
{
if (u == superSinkID)
{
totalCost += cost * f;
// debug_log("totalCost: %ld, cost: %ld, f: %d\n", totalCost, cost, f);
return f;
}
visited[u] = true;
int left = f;
int v = -1;
struct Arc *parc = NodeList[u].firstArc, *rarc = NULL;
while (parc != NULL)
{
if (parc->arcID < 4*static_cast<int>(linkNum)) // only arcs that between network nodes have opposite arc
{
rarc = oppositeReverseArc(parc->arcID);
if (parc->arcID % 2 == 0) // itself first, reverse arc of its opposite arc second
{
v = parc->dstID;
if (parc->initialCap > 0 && !parc->initialCost && visited[v] == false)
{
if (u == superSourceID)
from = v;
int delta = _augment(v, left < parc->initialCap ? left : parc->initialCap, from, totalCost);
if (v == superSinkID)
feeMatrix[from][accessTable[u-(int)networkNodeNum]].fee += cost * (left < parc->initialCap ? left : parc->initialCap);
parc->initialCap -= delta;
parc->reverseArc->initialCap += delta;
left -= delta;
if (left == 0)
return f;
}
v = rarc->dstID;
if (rarc->initialCap > 0 && !rarc->initialCost && visited[v] == false)
{
if (u == superSourceID)
from = v;
int delta = _augment(v, left < rarc->initialCap ? left : rarc->initialCap, from, totalCost);
if (v == superSinkID)
feeMatrix[from][accessTable[u-(int)networkNodeNum]].fee += cost * (left < parc->initialCap ? left : parc->initialCap);
rarc->initialCap -= delta;
rarc->reverseArc->initialCap += delta;
left -= delta;
if (left == 0)
return f;
}
}
else // reverse arc of its opposite arc first, itself second
{
v = rarc->dstID;
if (rarc->initialCap > 0 && !rarc->initialCost && visited[v] == false)
{
if (u == superSourceID)
from = v;
int delta = _augment(v, left < rarc->initialCap ? left : rarc->initialCap, from, totalCost);
if (v == superSinkID)
feeMatrix[from][accessTable[u-(int)networkNodeNum]].fee += cost * (left < parc->initialCap ? left : parc->initialCap);
rarc->initialCap -= delta;
rarc->reverseArc->initialCap += delta;
left -= delta;
if (left == 0)
return f;
}
v = parc->dstID;
if (parc->initialCap > 0 && !parc->initialCost && visited[v] == false)
{
if (u == superSourceID)
from = v;
int delta = _augment(v, left < parc->initialCap ? left : parc->initialCap, from, totalCost);
if (v == superSinkID)
feeMatrix[from][accessTable[u-(int)networkNodeNum]].fee += cost * (left < parc->initialCap ? left : parc->initialCap);
parc->initialCap -= delta;
parc->reverseArc->initialCap += delta;
left -= delta;
if (left == 0)
return f;
}
}
}
else
{
v = parc->dstID;
if (parc->initialCap > 0 && !parc->initialCost && visited[v] == false)
{
if (u == superSourceID)
from = v;
int delta = _augment(v, left < parc->initialCap ? left : parc->initialCap, from, totalCost);
if (v == superSinkID)
feeMatrix[from][accessTable[u-(int)networkNodeNum]].fee += cost * (left < parc->initialCap ? left : parc->initialCap);
parc->initialCap -= delta;
parc->reverseArc->initialCap += delta;
left -= delta;
if (left == 0)
return f;
}
}
parc = parc->nextArc;
}
return f - left;
}
/** modify arcs' status in graph, this function is called by _ZKW(). */
bool Graph::_modifyLabel()
{
int delta = INF;
uint32_t u = 0;
int v = 0;
struct Arc *parc = NULL, *rarc = NULL;
for (u = 0; u < nodeNum + 2; ++u)
{
if (visited[u])
{
for (parc = NodeList[u].firstArc; parc != NULL; parc = parc->nextArc)
{
if (parc->arcID < 4*static_cast<int>(linkNum)) // only arcs that between network nodes have opposite arc
{
rarc = oppositeReverseArc(parc->arcID);
if (parc->arcID % 2 == 0) // itself first, reverse arc of its opposite arc second
{
v = parc->dstID;
if (parc->initialCap > 0 && visited[v] == false && delta > parc->initialCost)
delta = parc->initialCost;
v = rarc->dstID;
if (rarc->initialCap > 0 && visited[v] == false && delta > rarc->initialCost)
delta = rarc->initialCost;
}
else // reverse arc of its opposite arc first, itself second
{
v = rarc->dstID;
if (rarc->initialCap > 0 && visited[v] == false && delta > rarc->initialCost)
delta = rarc->initialCost;
v = parc->dstID;
if (parc->initialCap > 0 && visited[v] == false && delta > parc->initialCost)
delta = parc->initialCost;
}
}
else
{
v = parc->dstID;
if (parc->initialCap > 0 && visited[v] == false && delta > parc->initialCost)
delta = parc->initialCost;
}
}
}
}
// info_log("delta: %d\n", delta);
if (delta == INF)
return false;
for (u = 0; u < nodeNum + 2; ++u)
{
if (visited[u])
{
for (parc = NodeList[u].firstArc; parc != NULL; parc = parc->nextArc)
{
if (parc->arcID < 4*static_cast<int>(linkNum)) // only arcs that between network nodes have opposite arc
{
rarc = oppositeReverseArc(parc->arcID);
if (parc->arcID % 2 == 0) // itself first, reverse arc of its opposite arc second
{
parc->initialCost -= delta;
parc->reverseArc->initialCost += delta;
rarc->initialCost -= delta;
rarc->reverseArc->initialCost += delta;
}
else // reverse arc of its opposite arc first, itself second
{
rarc->initialCost -= delta;
rarc->reverseArc->initialCost += delta;
parc->initialCost -= delta;
parc->reverseArc->initialCost += delta;
}
}
else
{
parc->initialCost -= delta;
parc->reverseArc->initialCost += delta;
}
}
}
}
if (delta > 0)
cost += delta; // TODO: handle the situation when delta < 0, try to avoid this happened.
return true;
}
/** a collection of things to be done after executing minimum cost maximum flow algorithm, this function called only once. */
void Graph::postMinimumCostMaximumFlow()
{
_delSuperSink();
if (useZKW)
{
delete []visited;
delete []feeMatrix;
delete []fluxFeeArray;
}
}
/** revert the status of all arcs to initialization, this function should be called every time right after algorithm finished. */
void Graph::revertStatusToInitialization()
{
_revertCapacityToInitialization();
if (useZKW)
_revertCostToInitialization();
}
/** revert the capacity of all arcs to initialization, this function is called by revertStatusToInitialization(). */
void Graph::_revertCapacityToInitialization()
{
uint32_t i;
for (i = 0; i < 4*linkNum; ++i)
arcTable[i]->initialCap = arcTable[i]->bandwidth;
for (i = 4*linkNum; i < 4*linkNum+8*consumptionNodeNum; i += 2)
arcTable[i]->initialCap = arcTable[i]->bandwidth;
for (i = 4*linkNum + 1; i < 4*linkNum+4*sourceNum; i += 2)
arcTable[i]->initialCap = arcTable[i]->bandwidth;
}
/** revert the cost of all arcs to initialization, this function is called by revertStatusToInitialization(). */
void Graph::_revertCostToInitialization()
{
uint32_t i;
for (i = 0; i < 4*linkNum; ++i)
arcTable[i]->initialCost = arcTable[i]->rental;
for (i = 4*linkNum; i < 4*linkNum+8*consumptionNodeNum; i += 2)
arcTable[i]->initialCost = arcTable[i]->rental;
for (i = 4*linkNum + 1; i < 4*linkNum+4*sourceNum; i += 2)
arcTable[i]->initialCost = arcTable[i]->rental;
}
/** used to record flow paths after minimum cost maximum flow algorithm finished, this function should be called only once. */
void Graph::recordFlowPath()
{
int source = superSourceID;
int terminal = superSinkID;
std::vector<int> path;
path.reserve(16);
while ( _DFS(source, terminal, 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->bandwidth - parc->initialCap > 0)
{
if (parc->dstID != t)
path.push_back(parc->dstID);
if ( _DFS(parc->dstID, t, path, std::min(tmpFlow, parc->bandwidth - parc->initialCap)) )
{
parc->initialCap += 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, *rarc = NULL;
sourceNum = static_cast<uint32_t>(servers.size());
/*
* 1. range of links that between network nodes is [0, 4*linkNum-1], and all integer indices are filled;
* 2. range of links that between access network node and consumption node is
* [4*linkNum, 4*linkNum+4*consumptionNodeNum-2], and all even indices are filled;
* 3. range of links that between consumption nodes and super sink node is
* [4*linkNum+4*consumptionNodeNum, 4*linkNum+8*consumptionNodeNum-2], and all even indices are filled;
* 4. in order to use unfilled indices effectively, let range of links that between
* super source node and server deployment nodes be [4*linkNum+1, 4*linkNum+4*sourceNum-1].
*/
arcIDIncrement = 4*linkNum + 1;
for (std::list<int>::iterator iter = servers.begin(); iter != servers.end(); ++iter)
{
parc = new Arc;
parc->srcID = superSourceID;
parc->dstID = *iter; // network node which deploys a CDN server
parc->bandwidth = INF; // throughput of the CDN server is infinite
parc->rental = 0; // access link need no rental fee
parc->initialCap = INF;
parc->initialCost = 0;
parc->nextArc = NULL;
rarc = new Arc;
rarc->srcID = parc->dstID;
rarc->dstID = parc->srcID;
rarc->rental = 0;
parc->reverseArc = rarc;
rarc->reverseArc = parc;
if (NodeList[superSourceID].firstArc == NULL)
NodeList[superSourceID].firstArc = parc;
else
NodeList[superSourceID].lastArc->nextArc = parc; // append to the last
NodeList[superSourceID].lastArc = parc; // update lastArc too
arcTable[parc->arcID] = parc;
arcTable[rarc->arcID] = rarc;
}
}
/** delete the super source node, this function should be called every time right after algorithm finished. */
void Graph::delSuperSource()
{
struct Arc *freearc1 = NodeList[superSourceID].firstArc, *freearc2 = NULL;
if (freearc1 != NULL)
freearc2 = freearc1->nextArc;
else
warning_log("have you add super source before? Or are you trying to delete super source twice?\n");
uint32_t rank = 0;
while (freearc1 != NULL && freearc2 != NULL)
{
if (rank % 2 == 0)
{
delete freearc1->reverseArc;
delete freearc1;
freearc1 = freearc2->nextArc;
}
else
{
delete freearc2->reverseArc;
delete freearc2;
freearc2 = freearc1->nextArc;
}
++rank;
}
if (freearc1 != NULL)
{
delete freearc1->reverseArc;
delete freearc1;
}
if (freearc2 != NULL)
{
delete freearc2->reverseArc;
delete freearc2;
}
NodeList[superSourceID].firstArc = NULL;
NodeList[superSourceID].lastArc = NULL;
for (uint32_t i = 4*linkNum + 1; i < 4*linkNum+4*sourceNum; i += 2)
arcTable[i] = NULL;
}
/** 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;
printf("node: [%d]", NodeList[superSourceID].ID);
darc = NodeList[superSourceID].firstArc;
while (darc != NULL)
{
printf(" -> %d(%d,%d)", darc->dstID, darc->bandwidth, darc->rental);
darc = darc->nextArc;
}
printf("\n");
}
/** add the super sink node, this function is called by preMinimumCostMaximumFlow(). */
void Graph::_addSuperSink()
{
struct Arc *parc = NULL, *rarc = NULL;
arcIDIncrement = 4*linkNum + 4*consumptionNodeNum;
for (uint32_t i = 0; i < consumptionNodeNum; ++i)
{
uint32_t curNode = networkNodeNum + i; // consumption node index
parc = new Arc;
parc->srcID = curNode;
parc->dstID = superSinkID; // super sink node
parc->bandwidth = demandTable[i]; // demand bandwidth of each consumption node
parc->rental = 0; // access link need no rental fee
parc->initialCap = demandTable[i];
parc->initialCost = 0;
parc->nextArc = NULL;
rarc = new Arc;
rarc->srcID = parc->dstID;
rarc->dstID = parc->srcID;
rarc->rental = 0;
parc->reverseArc = rarc;
rarc->reverseArc = parc;
NodeList[curNode].firstArc = parc; // consumption node firstArc must be NULL before
NodeList[curNode].lastArc = parc; // update lastArc too
arcTable[parc->arcID] = parc;
arcTable[rarc->arcID] = rarc;
}
}
/** delete the super sink node, this function is called by postMinimumCostMaximumFlow(). */
void Graph::_delSuperSink()
{
uint32_t i = 0;
for (i = 0; i < consumptionNodeNum; ++i)
{
struct Arc *freearc = NodeList[networkNodeNum+i].firstArc;
if (freearc != NULL) // avoid crashing when repeat call this function
{
delete freearc->reverseArc;
delete freearc;
}
NodeList[networkNodeNum+i].firstArc = NULL;
NodeList[networkNodeNum+i].lastArc = NULL;
}
for (i = 4*linkNum+4*consumptionNodeNum; i < 4*linkNum+8*consumptionNodeNum; i += 2)
arcTable[i] = NULL;
}
/**
* use BFS algorithm to traverse the graph at the start node src.
*/
void Graph::BFS(int src)
{
int i, u, v;
for (i = 0; i < static_cast<int>(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 i, u, v;
for (i = 0; i < static_cast<int>(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, std::list<std::vector<int> >& fluxPathList, long& totalRentalFee)
{
if (fluxPathList.size() > 50000)
{
error_log("The number of flux paths has overstep the limits!\n");
return false;
}
size_t i = 0;
totalRentalFee = 0;
std::vector<int> demandSatified(consumptionNodeNum, 0);
std::vector<int> arcLeftBandwidth(arcTable.size(), 0);
for (i = 0; i < arcTable.size(); ++i)
if (arcTable[i] != NULL)
arcLeftBandwidth[i] = arcTable[i]->bandwidth;
int fluxPathIdx = 1;
for (std::list<std::vector<int> >::iterator iter = fluxPathList.begin(); iter != fluxPathList.end(); ++iter, ++fluxPathIdx)
{
debug_log("verify flux path %d...\n", fluxPathIdx);
std::vector<int>& fluxPath = *iter; // alias
if (fluxPath.size() < 3)
{
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() > 1000)
{
error_log("The number of nodes in a flux path has overstep the limits!\n");
return false;
}
struct Arc *parc = graph.NodeList[fluxPath[0]].firstArc;
size_t accessNodeIdx = fluxPath.size() - 3;
int consumptionNodeID = fluxPath[accessNodeIdx+1];
int consumptionBandwidth = fluxPath.back();
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;
}
}
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;
}
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"
/** 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(std::list<std::vector<int> >& initialServerGroups);
/** API for Greedy. */
int* getOutLinkCap() { return outLinkCap; }
/** API for Greedy. */
double* getRentalDeployFeeRatio() { return rentalDeployFeeRatio; }
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:
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.
int mServerDeploymentFee; ///< equals to serverDeploymentFee, just get rid of annoying type incompatible warning.
int lowerBoundNum; ///< lower bound number of network nodes needed to deploy server.
int upBoundNum; ///< up bound number of network nodes needed to deploy server.
/** @name status of all network nodes. */
///@{
int *outLinkNum; ///< the number of links of a network node.
int *outLinkCap; ///< the sum up capacity of all links 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 *feeRank; ///< the weighted average rental fee rank of a network node.
int *scoreTable; ///< stores score of all network nodes.
///@}
/** @name status of access network nodes. */
///@{
double *rentalDeployFeeRatio; ///< when an access node doesn't deploy server, it will need a minimum link rental fee X, this ratio value certainly is X/singleServerFee.
///@}
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.
};
#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"
extern int log_level;
extern uint32_t networkNodeNum;
extern uint32_t linkNum;
extern uint32_t consumptionNodeNum;
extern uint32_t serverDeploymentFee;
extern std::vector<int> accessTable;
extern std::vector<int> demandTable;
TopologyScanner::TopologyScanner(Graph& _graph) : graph(_graph), arcDensity(ArcDensity::Unknown), cspDensity(CspDensity::Unknown), lowerBoundNum(0), multiplicativeFactor(1.0)
{
mNetworkNodeNum = static_cast<int>(networkNodeNum);
mServerDeploymentFee = static_cast<int>(serverDeploymentFee);
upBoundNum = static_cast<int>(consumptionNodeNum);
outLinkNum = new int[networkNodeNum];
outLinkCap = new int[networkNodeNum];
outLinkFee = new double[networkNodeNum];
capRank = new double[networkNodeNum];
feeRank = new double[networkNodeNum];
scoreTable = new int[networkNodeNum];
rentalDeployFeeRatio = new double[consumptionNodeNum];
std::fill(outLinkNum, outLinkNum + networkNodeNum, 0);
std::fill(outLinkCap, outLinkCap + networkNodeNum, 0);
std::fill(outLinkFee, outLinkFee + networkNodeNum, 0.0);
}
TopologyScanner::~TopologyScanner()
{
delete []outLinkNum;
delete []outLinkCap;
delete []outLinkFee;
delete []capRank;
delete []feeRank;
delete []scoreTable;
delete []rentalDeployFeeRatio;
}
/** scan the network topology of graph. */
void TopologyScanner::scan()
{
printf("\n==================== Enter topology scanner category ====================\n");
_defineDensity();
uint32_t i = 0;
for (i = 0; i < networkNodeNum; ++i)
{
struct Arc *parc = graph.NodeList[i].firstArc;
while (parc != NULL)
{
if (parc->dstID < mNetworkNodeNum)
{
++outLinkNum[i];
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;
for (i = 0; i < networkNodeNum; ++i)
{
outLinkFee[i] /= outLinkCap[i];
sortLinkCap.emplace_back(outLinkCap[i], i);
sortLinkFee.emplace_back(outLinkFee[i], i);
}
std::sort(sortLinkCap.begin(), sortLinkCap.end(), std::greater<std::pair<int, int> >());
std::sort(sortLinkFee.begin(), sortLinkFee.end());
for (i = 0; i < networkNodeNum; ++i)
{
capRank[sortLinkCap[i].second] = 1.0 - static_cast<double>(i)/mNetworkNodeNum;
feeRank[sortLinkFee[i].second] = 1.0 - static_cast<double>(i)/mNetworkNodeNum;
}
for (i = 0; i < networkNodeNum; ++i)
{
debug_log("node[%u] -> outLinkCap: %d, outLinkFee: %f, capRank: %f, feeRank: %f\n", i, outLinkCap[i], outLinkFee[i], capRank[i], feeRank[i]);
}
for (i = 0; i < networkNodeNum; ++i)
scoreTable[i] = 200 * capRank[i] + 200 * feeRank[i];
_mustDeployOnAccess();
_selectByScore();
}
/** recommend some node groups, combinations of them may be good as the input of the next algorithm. */
void TopologyScanner::recommend(std::list<std::vector<int> >& initialServerGroups)
{
uint32_t i = 0, j = 0, definiteNum = 0;
std::vector<int> certainGroup;
info_log("definite servers:");
for (size_t k = 0; k < possibleServers.size(); ++k)
{
if (scoreTable[possibleServers[k]] != INF)
break;
++definiteNum;
certainGroup.push_back(possibleServers[k]);
printf(" %d", possibleServers[k]);
}
for (i = definiteNum; i < static_cast<uint32_t>(possibleServers.size()); ++i) // shift to overlaying definite servers, pop_back() operation is not necessary
possibleServers[i-definiteNum] = possibleServers[i];
printf("\n");
info_log("possible servers:");
if (log_level >= INFO_LEVEL) // print possible servers
{
for (i = 0; i < static_cast<uint32_t>(possibleServers.size())-definiteNum; ++i)
printf(" %d", possibleServers[i]);
printf("\n");
}
if (definiteNum == 0)
certainGroup.push_back(-1); // indicates there is no network nodes have to deploy a server
initialServerGroups.push_back(certainGroup);
certainGroup.clear();
// divide possible servers into groups in order to use different combination of them,
// obviously, different combination lead to different link rental fee
uint32_t CN = static_cast<uint32_t>(possibleServers.size()) - definiteNum; // alias of short name "CandidateNumber"
int *hopAmongCandidates = new int[CN*CN];
int **hopAmong = new int*[CN]; // a point array, convenient to use form hopAmong[i][j]
for (i = 0; i < CN; ++i)
hopAmong[i] = hopAmongCandidates + i*CN;
int *minimumHop = new int[CN];
double *averageHop = new double[CN];
std::unordered_set<int> accessNodeSet;
for (i = 0; i < consumptionNodeNum; ++i)
accessNodeSet.insert(accessTable[i]);
std::vector<std::pair<int /* group */, bool /* determined */> > partion;
partion.reserve(CN);
for (i = 0; i < CN; ++i)
{
partion.emplace_back(0, false);
minimumHop[i] = INF;
averageHop[i] = 0.0;
graph.BFS(possibleServers[i]);
for (j = 0; j < CN; ++j)
{
int hops = graph.dist[possibleServers[j]]; // alias
hopAmong[i][j] = hops;
averageHop[i] += hops;
if (minimumHop[i] > hops && j != i)
minimumHop[i] = hops;
if (log_level >= DEBUG_LEVEL)
printf("%d ", hops);
}
averageHop[i] /= (CN-1);
if (log_level >= DEBUG_LEVEL)
printf(" --- %d,%f\n", minimumHop[i], averageHop[i]);
}
int curGroup = 1;
for (i = 0; i < CN; ++i)
{
if (partion[i].second == false)
{
partion[i].first = curGroup;
for (j = i+1; j < CN; ++j)
{
if (partion[j].second == false && hopAmong[i][j] == 1 && (accessNodeSet.find(possibleServers[i]) == accessNodeSet.end() || accessNodeSet.find(possibleServers[j]) == accessNodeSet.end()))
{
partion[j].first = curGroup;
partion[j].second = true;
}
}
++curGroup;
}
}
if (log_level >= DEBUG_LEVEL)
{
for (i = 0; i < CN; ++i)
printf("%d ", partion[i].first);
printf("\n");
}
for (int groupIdx = 1; groupIdx < curGroup; ++groupIdx)
{
for (i = 0; i < CN; ++i)
{
if (partion[i].first == groupIdx)
certainGroup.push_back(possibleServers[i]);
}
// info_log("group %d:", groupIdx);
// printVector(certainGroup, " ");
initialServerGroups.push_back(certainGroup);
certainGroup.clear();
}
delete []minimumHop;
delete []averageHop;
delete []hopAmong;
delete []hopAmongCandidates;
printf("==================== Exit topology scanner category ====================\n\n");
}
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(32); // 2^5 > 20
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;
rentalDeployFeeRatio[i] = static_cast<double>(inputRentalFee) / mServerDeploymentFee;
debug_log("minimum input rental fee of access node [%d] is %d, rental deploy ratio %f\n", accessNode, inputRentalFee, rentalDeployFeeRatio[i]);
if (inputRentalFee >= mServerDeploymentFee)
{
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();
}
for (uint32_t k = 0; k < consumptionNodeNum; ++k)
if (scoreTable[accessTable[k]] != INF) // avoid int type overflow
scoreTable[accessTable[k]] += 1000 * rentalDeployFeeRatio[k];
}
void TopologyScanner::_decideMultiplicativeFactor()
{
switch (cspDensity)
{
case CspDensity::UltraSparse:
multiplicativeFactor = 4.0; break;
case CspDensity::VerySparse:
multiplicativeFactor = 3.0; break;
case CspDensity::Sparse:
multiplicativeFactor = 2.5; break;
case CspDensity::General:
multiplicativeFactor = 2.0; break;
case CspDensity::Dense:
multiplicativeFactor = 1.0; break;
case CspDensity::VeryDense:
multiplicativeFactor = 0.8; break;
case CspDensity::UltraDense:
multiplicativeFactor = 0.6; break;
default:
multiplicativeFactor = 2.0; // the same as general case
}
}
void TopologyScanner::_selectByScore()
{
_decideMultiplicativeFactor();
std::vector<std::pair<int /* score */, int /* ID */> > scoreIDPair;
uint32_t i = 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: ");
for (i = 0; i < candidateNum; ++i)
{
if (log_level >= DEBUG_LEVEL)
printf("%d ", scoreIDPair[i].first);
possibleServers.push_back(scoreIDPair[i].second);
}
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"
/** Greedy algorithm implemented by a finite state machine(FSM). */
class Greedy
{
public:
Greedy(Graph& _graph, std::list<std::vector<int> >& _serverGroups);
~Greedy();
Greedy(const Greedy& rhs) = delete;
Greedy& operator=(const Greedy& rhs) = delete;
void initialize(std::list<int>& servers);
bool optimize(std::list<int>& servers, long justResultFee);
void obtainOutLinkCap(int *_out_link_cap);
void obtainRentalDeployFeeRatio(double *_rental_deploy_fee_ratio);
private:
enum Progress {
ZOM, ///< Zero Order Minus
ZOP, ///< Zero Order Plus
FOP, ///< First Order Plus
FOM, ///< First Order Minus
EX ///< Exchange Operation
};
void _sortCspNode(double *_rental_deploy_fee_ratio);
uint32_t _selectRestNode(bool onlyAbandon);
private:
Graph &graph;
std::set<int> definiteServers; ///< set of access nodes that have to deploy a cdn server.
std::unordered_set<int> accessSet; ///< set of all access nodes.
Progress progress; ///< indicates current optimize progress.
int curIdx; ///< current possible consumption node index.
int curNBIdx; ///< current possible selected neighbor node index.
uint32_t cspCN; ///< only count those possible consumption node.
uint32_t totalCN; ///< only count those possible consumption node before ZOM progress.
uint32_t neighborCN; ///< only count those possible neighbor node selected by _selectRestNode().
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.
int *neighborRank; ///< neighbor rank used in first order plus progress.
int *outLinkCap; ///< the sum up capacity of all links of a network node, it is a point to TopologyScanner::outLinkCap.
double *cspRDFR; ///< when an access node doesn't deploy server, it will need a minimum link rental fee X, this ratio value certainly is X/singleServerFee.
bool hasExecutedZOP; ///< whether ZOP progress has been executed.
bool rightAfterExchange; ///< whether we have just executed an exchange operation.
bool inExchangeProgress; ///< whether current zero order minus operation is a sub operation of exchange operation.
int lastChangedNode; ///< store the node in previous minus operation for undo operation.
int tryExchangeTimes; ///< store the number we have tried to exchange, it is used to resume curIdx when return to exchange operation.
long lastResultFee; ///< store the total fee result by previous operation for comparsion purpose.
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 JOIN_FOP_FOM_AS_ATOM_OPERATION 0
#define REMOVE_ACCESS_NODE for (itS = servers.begin(); itS != servers.end(); ++itS) { if (*itS == cspRank[curIdx]) { servers.erase(itS); break; } }
extern int log_level;
extern uint32_t networkNodeNum;
extern uint32_t linkNum;
extern uint32_t consumptionNodeNum;
extern uint32_t serverDeploymentFee;
extern std::vector<int> accessTable;
extern std::vector<int> demandTable;
extern std::list<int> bestServers;
Greedy::Greedy(Graph& _graph, std::list<std::vector<int> >& _serverGroups) : graph(_graph), progress(Progress::ZOM), curIdx(0), curNBIdx(0), hasExecutedZOP(false), rightAfterExchange(true), inExchangeProgress(false)
{
std::vector<int> &firstGroup = _serverGroups.front(); // alias
if (firstGroup.size() != 1 || firstGroup[0] != -1)
for (size_t i = 0; i < firstGroup.size(); ++i)
definiteServers.insert(firstGroup[i]);
_serverGroups.pop_front();
for (uint32_t k = 0; k < consumptionNodeNum; ++k)
accessSet.insert(accessTable[k]);
deployed = new bool[networkNodeNum];
memset(deployed, false, networkNodeNum*sizeof(bool));
cspCN = consumptionNodeNum - static_cast<uint32_t>(definiteServers.size());
totalCN = cspCN;
cspRank = new int[cspCN];
cspRDFR = new double[cspCN];
}
Greedy::~Greedy()
{
delete []deployed;
delete []cspRank;
delete []cspRDFR;
}
/** API function of CDN server list initialization required by deploy.cpp. */
void Greedy::initialize(std::list<int>& servers)
{
printf("==================== Enter greedy category ====================\n");
info_log("==================== Progress::ZOM(1) starts ====================\n");
for (uint32_t i = 1; i < cspCN; ++i) // the least rank access node has been removed
{
servers.push_back(cspRank[i]);
deployed[cspRank[i]] = true;
}
for (std::set<int>::iterator itDef = definiteServers.begin(); itDef != definiteServers.end(); ++itDef)
{
servers.push_back(*itDef);
deployed[*itDef] = true;
}
lastChangedNode = cspRank[curIdx];
lastResultFee = consumptionNodeNum * serverDeploymentFee; // initial total fee only include server deployment fee
}
/**
* @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 127, when it is time to exit this state, then go to line 146,150;
* 2. when state switched to Progress::ZOP, starts at line 172, when it is time to exit this state, set bool variable hasExecutedZOP = true, then go to line 193,205;
* 3. when state switched back to Progress::ZOM, starts at line 97, when it is time to exit this state, then go to line 120;
* 4. when state switched to Progress::EX, starts at line 412, when an exchange action was actually done, set bool variable inExchangeProgress = true and go to line 473, next loop will switch to sub Progress::ZOM;
* 4.1. the same as step 3. but when it is time to exit loop, then go to line 115, next loop will go to line 146,154;
* 4.2. the same as step 2. but when it is time to exit loop, then go to line 193,197, next loop return back to Progress::EX and then starts at line 423;
* when tryExchangeTimes has exceed the default set or priority_queue graph.fluxFeeQueue is empty, exit Progress::EX at line 456 and switch to state Progress::FOP the next loop;
* 5. when state switch to Progress::FOP, starts at line 224, here will call function _selectRestNode() at line 266, the next loop will starts at line 306,
* when it is time to exit this state, go to line 323 and the switch state to Progress::FOM, the next loop will starts at line 335,
* note that this function will return false at line 346, thus the bool variable continueLoop will be assigned false and quit the loop in deploy.cpp.
*/
bool Greedy::optimize(std::list<int>& servers, long justRentalFee)
{
long deploymentFee = static_cast<long>(servers.size()) * serverDeploymentFee;
uint32_t i = 0;
switch (progress)
{
case Progress::ZOM:
{
if (hasExecutedZOP) // usually will enter this part
{
if (lastResultFee <= justRentalFee + deploymentFee || justRentalFee == -1) // restore the most recently removed node
{
servers.push_front(lastChangedNode);
deployed[lastChangedNode] = true;
}
else
lastResultFee = justRentalFee + deploymentFee;
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 (inExchangeProgress)
{
curIdx = -1; // prepare to start ZOP progress
hasExecutedZOP = false;
}
else
{
curIdx = 0;
graph.setExchangeOperation(true); // needed by exchange progress
progress = Progress::EX;
}
}
else if (curIdx != -1) // only the initial state ZOM will enter this part
{
if (lastResultFee <= justRentalFee + deploymentFee || justRentalFee == -1) // restore the most recently removed node
{
servers.push_front(lastChangedNode);
deployed[lastChangedNode] = true;
}
else
lastResultFee = justRentalFee + deploymentFee;
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 // curIdx == -1, actually here is a transitional state when the next loop will switch to Progress::ZOP
{
lastResultFee = justRentalFee + deploymentFee;
if (!inExchangeProgress)
{
info_log("Total fee after Progress::ZOM(1) is %ld\n\n", lastResultFee);
info_log("==================== Progress::ZOP starts ====================\n");
}
else
info_log("Total fee after sub Progress::ZOM is %ld\n", lastResultFee);
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;
}
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 <= justRentalFee + deploymentFee || justRentalFee == -1) // remove the most recently added node
{
servers.pop_front();
deployed[lastChangedNode] = false;
}
else
lastResultFee = justRentalFee + deploymentFee;
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 = justRentalFee + deploymentFee;
if (inExchangeProgress) // return to exchange progress
{
info_log("Total fee after sub Progress::ZOP is %ld\n", lastResultFee);
curIdx = 1; // assign any number that larger than 0
graph.setExchangeOperation(true); // update the whole fluxFeeQueue for next exchange preparation
progress = Progress::EX;
}
else // go to zero order progress
{
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;
info_log("Total fee after Progress::ZOP is %ld\n\n", lastResultFee);
info_log("==================== Progress::ZOM(2) starts ====================\n");
}
}
break;
}
case Progress::FOP:
{
if (curIdx == 0 && curNBIdx == 0)
{
lastResultFee = justRentalFee + deploymentFee;
// return false;
info_log("Total fee after Progress::EX is %ld\n\n", lastResultFee);
info_log("==================== Progress::FOP starts ====================\n");
// resort consumption node
uint32_t newIdx = 0, abandonIdx = 0;
int *abandonRank = new int[totalCN + definiteServers.size() - servers.size()];
double *abandonRDFR = new double[totalCN + definiteServers.size() - servers.size()];
for (i = 0; i < totalCN; ++i)
{
if (deployed[cspRank[i]])
{
cspRank[newIdx] = cspRank[i];
cspRDFR[newIdx] = cspRDFR[i];
++newIdx;
}
else
{
abandonRank[abandonIdx] = cspRank[i];
abandonRDFR[abandonIdx] = cspRDFR[i];
++abandonIdx;
}
}
if (totalCN + definiteServers.size() - servers.size() != abandonIdx)
{
error_log("assert failed.\n");
exit(EXIT_FAILURE);
}
cspCN = newIdx; // update cspCN
for (i = cspCN; i < totalCN; ++i)
{
cspRank[i] = abandonRank[i-cspCN];
cspRDFR[i] = abandonRDFR[i-cspCN];
}
delete []abandonRank;
delete []abandonRDFR;
for (i = 0; i < totalCN; ++i)
debug_log("[%u] -> cspRank: %d, cspRDFR: %f\n", i, cspRank[i], cspRDFR[i]);
neighborCN = _selectRestNode(false);
if (neighborCN == 0)
return false;
if (log_level >= INFO_LEVEL)
{
printf("INFO |");
for (i = 0; i < neighborCN; ++i)
printf(" %d", neighborRank[i]);
printf("\n");
}
servers.push_front(neighborRank[0]); // curIdx == curNBIdx == 0
deployed[neighborRank[0]] = true;
#if JOIN_FOP_FOM_AS_ATOM_OPERATION
progress = Progress::FOM; // note that curIdx still equals to 0
#else
lastChangedNode = neighborRank[curIdx++];
#endif
}
else
{
#if JOIN_FOP_FOM_AS_ATOM_OPERATION
curIdx = 0; // test starts from least access node
info_log("curNBIdx: %d\n", curNBIdx);
if (curNBIdx == static_cast<int>(neighborCN)) // all selected neighbor nodes have been tested
{
delete []neighborRank;
printf("==================== Exit greedy category ====================\n\n");
return false; // quit FOP-FOM atom operation
}
else
{
servers.push_front(neighborRank[curNBIdx]);
deployed[neighborRank[curNBIdx]] = true;
progress = Progress::FOM; // starts FOM operation
}
#else
if (lastResultFee <= justRentalFee + deploymentFee || justRentalFee == -1) // restore the most recently added neighbor node
{
servers.pop_front();
deployed[lastChangedNode] = false;
}
else
{
lastResultFee = justRentalFee + deploymentFee;
info_log("a neighbor[%d] pass the test\n", lastChangedNode);
}
servers.push_front(neighborRank[curIdx]);
deployed[neighborRank[curIdx]] = true;
lastChangedNode = neighborRank[curIdx];
if (++curIdx == static_cast<int>(neighborCN))
{
curIdx = -1; // return to -1, loop restarts again
progress = Progress::FOM;
}
#endif
}
break;
}
case Progress::FOM:
{
if (curIdx == -1)
{
#if !JOIN_FOP_FOM_AS_ATOM_OPERATION
if (lastResultFee <= justRentalFee + deploymentFee || justRentalFee == -1) // restore the most recently added neighbor node
{
servers.pop_front();
deployed[lastChangedNode] = false;
}
else
lastResultFee = justRentalFee + deploymentFee;
delete []neighborRank;
printf("==================== Exit greedy category ====================\n\n");
return false;
#endif
}
else if (curIdx == 0)
{
#if JOIN_FOP_FOM_AS_ATOM_OPERATION
if (lastResultFee < justRentalFee + deploymentFee || justRentalFee == -1) // remove the least access node
{
while (!deployed[cspRank[curIdx]]) // ensure the current access node to remove soon is deployed with a server now
++curIdx;
REMOVE_ACCESS_NODE
deployed[cspRank[curIdx]] = false;
lastChangedNode = cspRank[curIdx];
while (!deployed[cspRank[curIdx]]) // here will enter loop at least once, ensure the next access node to remove is deployed with a server now
++curIdx;
}
else
{
lastResultFee = justRentalFee + deploymentFee;
info_log("a neighbor[%d] pass the test\n", neighborRank[curNBIdx]);
++curNBIdx;
progress = Progress::FOP; // return to progress FOP, then test the next neighbor node
}
#endif
}
else
{
#if JOIN_FOP_FOM_AS_ATOM_OPERATION
if (lastResultFee < justRentalFee + deploymentFee || justRentalFee == -1) // remove the least access node
{
REMOVE_ACCESS_NODE
deployed[cspRank[curIdx]] = false;
servers.push_front(lastChangedNode);
deployed[lastChangedNode] = true;
lastChangedNode = cspRank[curIdx];
while (!deployed[cspRank[curIdx]] && curIdx < static_cast<int>(cspCN)) // here will enter loop at least once, ensure the next access node to remove is deployed with a server now
++curIdx;
if (curIdx == static_cast<int>(cspCN))
{
// remove current neighbor node added before, because this neighbor node cannot decrease the total fee and failed to pass the test
for (itS = servers.begin(); itS != servers.end(); ++itS) { if (*itS == neighborRank[curNBIdx]) { servers.erase(itS); break; } }
servers.push_front(lastChangedNode); // note lastChangedNode has been assigned at 8 lines up here, it is not neccessary to test the last access node
deployed[lastChangedNode] = true;
++curNBIdx;
progress = Progress::FOP; // return to progress FOP, then test the next neighbor node
}
}
else
{
lastResultFee = justRentalFee + deploymentFee;
info_log("a neighbor[%d] pass the test\n", neighborRank[curNBIdx]);
++curNBIdx;
progress = Progress::FOP; // return to progress FOP, then test the next neighbor node
}
#endif
}
break;
}
case Progress::EX:
{
Graph::FluxFee fluxFee;
if (curIdx == 0 || rightAfterExchange)
{
if (curIdx == 0)
{
lastResultFee = justRentalFee + deploymentFee;
info_log("Total fee after Progress::ZOM(2) is %ld\n\n", lastResultFee);
info_log("==================== Progress::EX starts ====================\n");
inExchangeProgress = true;
tryExchangeTimes = 0;
}
fluxFee = graph.fluxFeeQueue.top();
graph.fluxFeeQueue.pop();
debug_log("from: %d, to: %d, fee: %d\n", fluxFee.from, fluxFee.to, fluxFee.fee);
// exchange from and to, that is, remove 'from' node as well as add 'to' node
for (itS = servers.begin(); itS != servers.end(); ++itS) { if (*itS == fluxFee.from) { servers.erase(itS); break; } }
servers.push_front(fluxFee.to);
deployed[fluxFee.from] = false;
deployed[fluxFee.to] = true;
lastChangedNode = fluxFee.from;
graph.setExchangeOperation(false); // avoid changing fluxFeeQueue
rightAfterExchange = false;
++curIdx;
}
else
{
if (lastResultFee <= justRentalFee + deploymentFee || justRentalFee == -1) // undo previous exchange operation
{
deployed[servers.front()] = false;
servers.pop_front(); // remove the 'to' node added in previous exchange operation
servers.push_front(lastChangedNode); // restore the 'from' node removed in previous exchange operation
deployed[lastChangedNode] = true;
if (graph.fluxFeeQueue.empty() || tryExchangeTimes > 1000) // exit EX progress
{
info_log("tryExchangeTimes: %d\n", tryExchangeTimes);
curIdx = 0;
while (!graph.fluxFeeQueue.empty())
graph.fluxFeeQueue.pop();
graph.setExchangeOperation(false); // no need to change fluxFeeQueue anymore
inExchangeProgress = false; // after now, zero order operation is not a sub operation of exchange operation anymore
progress = Progress::FOP;
return true;
}
fluxFee = graph.fluxFeeQueue.top();
graph.fluxFeeQueue.pop();
debug_log("from: %d, to: %d, fee: %d\n", fluxFee.from, fluxFee.to, fluxFee.fee);
for (itS = servers.begin(); itS != servers.end(); ++itS) { if (*itS == fluxFee.from) { servers.erase(itS); break; } } // exchange from and to
servers.push_front(fluxFee.to);
deployed[fluxFee.from] = false;
deployed[fluxFee.to] = true;
lastChangedNode = fluxFee.from;
}
else
{
lastResultFee = justRentalFee + deploymentFee;
info_log("node [%d] and [%d] exchanged, now total fee is %ld\n", lastChangedNode, servers.front(), lastResultFee);
rightAfterExchange = true;
// prepare to begin sub zero order minus progress
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;
}
++tryExchangeTimes;
}
break;
}
default:
error_log("Unknown progress!\n");
}
return true;
}
void Greedy::obtainOutLinkCap(int *_out_link_cap)
{
outLinkCap = _out_link_cap;
}
void Greedy::obtainRentalDeployFeeRatio(double *_rental_deploy_fee_ratio)
{
_sortCspNode(_rental_deploy_fee_ratio);
}
void Greedy::_sortCspNode(double *_rental_deploy_fee_ratio)
{
std::vector<std::pair<double /* RDFR */, int /* cspID */> > cspSortVec;
cspSortVec.reserve(cspCN);
uint32_t i = 0;
for (i = 0; i < consumptionNodeNum; ++i)
if (definiteServers.find(accessTable[i]) == definiteServers.end())
cspSortVec.emplace_back(demandTable[i], accessTable[i]);
std::sort(cspSortVec.begin(), cspSortVec.end(), [](const std::pair<int, int> lhs, const std::pair<int, int> rhs) { return lhs.first < rhs.first; } );
for (i = 0; i < cspCN; ++i)
{
cspRank[i] = cspSortVec[i].second;
cspRDFR[i] = cspSortVec[i].first;
debug_log("[%u] -> cspRank: %d, cspRDFR: %f\n", i, cspRank[i], cspRDFR[i]);
}
}
uint32_t Greedy::_selectRestNode(bool onlyAbandon)
{
uint32_t i = 0, NB_NUM = 0;
std::vector<std::pair<int /* capacity */, int /* ID */> > neighbors;
{
std::set<int> neighborSet;
for (int j = 0; j < static_cast<int>(networkNodeNum); ++j)
if (accessSet.find(j) == accessSet.end())
neighborSet.insert(j);
NB_NUM = static_cast<uint32_t>(neighborSet.size());
neighbors.reserve(NB_NUM);
for (std::set<int>::iterator itNS = neighborSet.begin(); itNS != neighborSet.end(); ++itNS)
neighbors.emplace_back(0, *itNS);
}
info_log("NB_NUM: %u\n", NB_NUM);
uint32_t SELECTED_NB_NUM = 0;
for (i = 0; i < NB_NUM; ++i)
neighbors[i].first = outLinkCap[neighbors[i].second];
SELECTED_NB_NUM = NB_NUM; // this can be modified
std::sort(neighbors.begin(), neighbors.end(), std::greater<std::pair<int, int> >());
neighborRank = new int[SELECTED_NB_NUM];
for (i = 0; i < SELECTED_NB_NUM; ++i)
neighborRank[i] = neighbors[i].second;
return SELECTED_NB_NUM;
}
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 std::vector<int> accessTable;
extern std::vector<int> demandTable;
uint32_t networkNodeNum = 0;
uint32_t linkNum = 0;
uint32_t consumptionNodeNum = 0;
uint32_t serverDeploymentFee = 0;
std::list<int> bestServers;
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);
debug_log("NetworkNodeNum: %u, LinkNum: %u, ConsumptionNodeNum: %u\n", networkNodeNum, linkNum, consumptionNodeNum);
debug_log("ServerDeploymentFee: %u\n", serverDeploymentFee);
{
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 + consumptionNodeNum);
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.preferZKW(true);
graph.preMinimumCostMaximumFlow();
// 5. =============== critical part of finding a server deployment solution ===============
std::list<int> newServers;
std::list<std::vector<int> > initialServerCombinations;
// 5.1. ========== scan topology to obtain combinations of some carefully selected network nodes as initial scheme ==========
TopologyScanner topoScanner(graph);
topoScanner.scan();
topoScanner.recommend(initialServerCombinations);
// 5.2. ========== deploy CDN servers on one of these combinations of network nodes ==========
Greedy greedy(graph, initialServerCombinations);
greedy.obtainOutLinkCap(topoScanner.getOutLinkCap());
greedy.obtainRentalDeployFeeRatio(topoScanner.getRentalDeployFeeRatio());
greedy.initialize(newServers);
// info_log("initial servers: ");
// printList(newServers, "");
int loop = 1;
bool continueLoop = true;
double elapsedTime = 0.0;
long minRentalDeploymentFee = INF;
while (true)
{
// 5.3. ========== add a super source onto graph ==========
graph.addSuperSource(newServers);
// 5.4. ========== execute minimum cost flow algorithm ==========
long rentalFee = graph.minimumCostMaximumFlow(newServers);
long deploymentFee = serverDeploymentFee * static_cast<long>(newServers.size());
// info_log("Link fee is %ld, server fee is %ld, sum up %ld.\n", rentalFee, deploymentFee, rentalFee + deploymentFee);
// 5.5. ========== a better deployment solution ? ==========
if (minRentalDeploymentFee > rentalFee + deploymentFee && rentalFee != -1)
{
minRentalDeploymentFee = rentalFee + deploymentFee;
bestServers.assign(newServers.begin(), newServers.end());
}
continueLoop = greedy.optimize(newServers, rentalFee);
// 5.6. ========== time is not enough ==========
if (loop % 50 == 0)
elapsedTime = procedureTimer.elapsed();
if (loop % 1000 == 0)
info_log("Time elapsed: %fs\n", elapsedTime);
// how many loops do you want?
if (++loop > 10000 || !continueLoop || elapsedTime > 87.0) // we have to exit loop when only 3 seconds left
{
printf("INFO | Exit loop: %d\n", loop);
info_log("best servers: ");
printList(bestServers, "");
// 5.6.1. ===== delete current super source from graph and revert the capacity of arc to initialization =====
graph.revertStatusToInitialization();
graph.delSuperSource();
// 5.6.2. ===== add the super source of best servers' union onto graph =====
graph.addSuperSource(bestServers);
// 5.6.3. ===== calculate minimum cost flow using best servers and then record corresponding flow path =====
graph.minimumCostMaximumFlow(bestServers);
graph.recordFlowPath();
// 5.6.4. ===== in fact, it is not must to revert capacity and delete super source =====
graph.revertStatusToInitialization();
graph.delSuperSource();
break;
}
// 5.7. ========== delete the super source from graph and revert the capacity of arc to initialization ==========
graph.revertStatusToInitialization();
graph.delSuperSource();
// info_log("new servers: ");
// printList(newServers, "");
}
graph.postMinimumCostMaximumFlow();
info_log("Minimum link rental fee plus server deployment fee is %ld.\n", minRentalDeploymentFee);
for (std::list<std::vector<int> >::iterator itfp = graph.fluxPathList.begin(); itfp != graph.fluxPathList.end(); ++itfp)
{
std::vector<int>& fluxPath = *itfp;
fluxPath[fluxPath.size()-2] -= static_cast<int>(networkNodeNum);
// printVector(fluxPath, "");
}
// 6. =============== verify server deployment and flux paths scheme ===============
long totalRentalFee = 0;
bool schemeOK = verifyScheme(graph, graph.fluxPathList, totalRentalFee);
uint32_t totalDeploymentFee = serverDeploymentFee * static_cast<uint32_t>(bestServers.size());
if (schemeOK == true)
uncond_log("Congratulations! Total link rental fee is %ld, deployment fee is %u, sum up %ld.\n", totalRentalFee, totalDeploymentFee, totalRentalFee + totalDeploymentFee);
else
error_log("Shit! The scheme failed to pass verification!\n");
// 7. =============== destruct graph ===============
graph.destruct();
// 8. =============== output flux path list to result file ===============
outputToFile(argv[2], graph.fluxPathList);
/*******************************************************************
******************** Time elapsing end ********************
*******************************************************************/
}
注：本文开头处的超链接提供下载的代码包中附带有 24 个测试用例，三种级别的各 8 个，分别是初级用例、中级用例、高级用例，规模分别为 160、300、800 个网络结点，消费结点比例均为 40%。