-
Notifications
You must be signed in to change notification settings - Fork 0
/
route.h
91 lines (62 loc) · 3.67 KB
/
route.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#ifndef __ROUTE_H__
#define __ROUTE_H__
//test
void search_route(char *graph[5000], int edge_num, char *condition);
const int MAX_VERTEX_NUM = 600; // max vertex number in the graph
const int MAX_INCLUDING_SET = 50; // max vertex number in the including set
#define ROUTEDEBUG
#define PRINTDEBUG
#define DFSDEBUG
//#define actualNodes MAX_VERTEX_NUM
#define GREEDYALGORITHM
typedef struct EdgeNode
{
int linkID;
int nodeID;
int weight;
EdgeNode *next;
} EdgeNode;
#define MAX_SEARCH_DEPTH 5
typedef struct SetNode
{
int startNode;
int endNode;
int length;
bool mark;
int nodeList[MAX_SEARCH_DEPTH] = {0};
SetNode *next;
} SetNode;
//未注释的为通用公共函数
void getTopoArray(int edge_num, char *topo[5000], int topoArray[][4]);
void getDemand(char *demand, int includingSet[MAX_INCLUDING_SET], int& sourceID, int& destinationID, int& cntPass);
void change2List(EdgeNode *node[MAX_VERTEX_NUM], int topoArray[][4], int edge_num);
bool checkInDemand(int nodeDemand[MAX_INCLUDING_SET], int ID);
int getCost(EdgeNode *node[MAX_VERTEX_NUM], int sequence[MAX_VERTEX_NUM], int route[MAX_VERTEX_NUM], int length);
void copyRoute(int recordRoute[MAX_VERTEX_NUM][MAX_VERTEX_NUM], int recordDepth[MAX_VERTEX_NUM], int currentID, int nodeID);
int getMinNode(int dijkstraDistance[MAX_VERTEX_NUM], bool inStack[MAX_VERTEX_NUM]);
void updateBaseOnCurrentNode(EdgeNode *pNode, int dijkstraDistance[MAX_VERTEX_NUM], int recordRoute[MAX_VERTEX_NUM][MAX_VERTEX_NUM], int recordDepth[MAX_VERTEX_NUM], bool inStack[MAX_VERTEX_NUM], int currentID);
bool getRoute2DestinationID(EdgeNode *node[MAX_VERTEX_NUM], bool inStack[MAX_VERTEX_NUM], int route[MAX_VERTEX_NUM], int &length, int &dijkstraDistance, int currentID, int destinationID);
void popStack(int nodeStack[MAX_VERTEX_NUM], bool inStack[MAX_VERTEX_NUM], int &stackDepth, bool hasVisited[MAX_VERTEX_NUM][MAX_VERTEX_NUM], int nodeDemand[MAX_INCLUDING_SET], int sourceID);
void pushStack(int nodeStack[MAX_VERTEX_NUM], bool inStack[MAX_VERTEX_NUM], int &stackDepth, bool hasVisited[MAX_VERTEX_NUM][MAX_VERTEX_NUM], int route[MAX_VERTEX_NUM], int length);
bool getPoints1Dijkstra(EdgeNode *node[MAX_VERTEX_NUM], bool inStack[MAX_VERTEX_NUM], bool hasVisited[MAX_VERTEX_NUM][MAX_VERTEX_NUM], int route[MAX_VERTEX_NUM], int &routeLength, int sourceID, int nodeDemand[MAX_INCLUDING_SET]);
int checkNumbersInStack(int nodeStack[MAX_VERTEX_NUM], int stackDepth, int nodeDamand[MAX_INCLUDING_SET]);
#if (defined(PRINTDEBUG) && defined(ROUTEDEBUG))
void testChange2List(EdgeNode *node[MAX_VERTEX_NUM]);
#endif
#ifdef DFSDEBUG
void getDFS(EdgeNode *node[MAX_VERTEX_NUM], int nodeDemand[MAX_INCLUDING_SET], int cntPass, int sourceID, int destinationID);
void getDFS1(EdgeNode *node[MAX_VERTEX_NUM], int nodeDemand[MAX_INCLUDING_SET], int cntPass, int sourceID, int destinationID);
int getDFS2(EdgeNode *node[MAX_VERTEX_NUM], int includingSet[MAX_INCLUDING_SET], int cntPass, int destinationID, int *path);
bool CheckConf(SetNode *path, bool hasVisited[MAX_VERTEX_NUM]);
void CopyToHead(SetNode *head, SetNode *path, bool hasVisited[MAX_VERTEX_NUM]);
void CleanState(SetNode *node, bool hasVisited[MAX_VERTEX_NUM]);
int GetPath(EdgeNode *node[MAX_VERTEX_NUM], int nodeStack[MAX_INCLUDING_SET], int stackDepth, int *path, int *weight);
int ConToPath(EdgeNode *node[MAX_VERTEX_NUM], int startId, int nodeId, int *weight);
#endif // DFSDEBUG
#ifdef PRINTDEBUG
void printRoute(int route[MAX_VERTEX_NUM], int length, int value);
#endif // PRINTDEBUG
#ifdef GREEDYALGORITHM
void mainGreedyAlgorithm(EdgeNode *node[MAX_VERTEX_NUM], int nodeDemand[MAX_INCLUDING_SET], int cntPass, int sourceID, int destinationID);
#endif // GREEDYALGORITHM
#endif // __ROUTE_H__