版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

本文链接：http://blog.csdn.net/xiaxiaing00/article/details/

收起

一、ASAP和ALAP的概念

最近在看一些算法的论文，其中涉及了ASAP和ALAP算法，这两种算法由很多的应用背景，在此仅阐述对于图中节点执行顺序的选择。首先从字面上理解，ASAP是as soon as possible，是尽快执行的意思，即当图中节点没有依赖关系和资源限制的前提下就可以马上执行；相反的，ALAP是as late as possible的意思，即在图中关键路径执行结束前拖到最晚执行。从字面上理解有点笼统，下面我们可以通过一个例子来理解：

讯享网

图a是DFG图，图中节点有两种，三角形和圆形分别代表不同的操作，如加操作、乘操作、加载操作、存储操作等，图中的边表示不同操作之间的依赖关系，图b是ASAP算法下的调度方式，在第0步时，0 1 3 4这四个节点没有父节点的限制，则尽快在第一步执行，当第0步执行完毕后，在图中去掉这四个节点，所以2 5 7这三个节点又没有了父节点的依赖限制，所以在第1步就执行2 5 7，依次类推，在第2步执行6，在第3步执行8。图c是ALAP算法，可以看出，0->2->6->8是这个图的关键路径，即最长的路径，所有节点要尽量靠后执行，节点是根据关键路径反向尽快执行，图中的7节点可以在第1步或者第2步执行则选择靠后的第2步，4节点可以选择在第0步和第1步执行，则选择靠后的第1步。

二、c++代码实现

1.输入

输入图文件如下所示，其中每一行的第一个数字表示一个节点，后面的所有数字表示为第一个数字的子节点，对于后面的所有数字来说，第一个数字使他们的父节点。每一行都是如此。例如第一行表示，节点0是父节点，8 23 26 28 31 37 39 46全部是0节点的子节点。

1. 0 8 23 26 28 31 37 39 46
2. 8 28 31 37 39
3. 23 8 28 31 37 39
4. 26 8 23 28 31 37 39
5. 31 28 37 39
6. 37 28 39
7. 39 28
8. 46 8 23 26 28 31 37 39
9. 53 13

2.算法实现

讯享网 

1. #include<iostream>
2. #include<fstream>
3. #include<vector>
4. #include <regex>
5. #include<map>
6.  
7. using namespace std;
8.  
9. /*存储图节点*/
10. struct node {
11. int name;
12. vector<int> parent;
13. vector<int> child;
14. int priority = 0;
15. };
16.  
17. void input(vector<vector<int>> &Vec_Dti, string FileName);
18. void initData(map<int, node> &map, vector<vector<int>> inData);
19. void ASAP(vector<vector<int>> &output_ASAP, map<int, node> m);
20. void ALAP(vector<vector<int>> &output_ALAP, map<int, node> m);
21. void delate(map<int, node> &m, vector<int> key );
22. void print(vector<vector<int>> output);
23.  
24. void main() {
25.  
26. vector<vector<int>> inData;
27. string FileName = "E:/graph_copy.g";
28. input(inData, FileName);
29.  
30. map<int, node> m;
31. initData(m, inData);
32.  
33. vector<vector<int>> output_ASAP;
34. ASAP(output_ASAP, m);
35. cout << "-----------ASAP-------------" << endl;
36. print(output_ASAP);
37.  
38. vector<vector<int>> output_ALAP;
39. ALAP(output_ALAP, m);
40. cout << "------------ALAP------------" << endl;
41. print(output_ALAP);
42.  
43.  
44. system("PAUSE");
45. }
46.  
47.  
48. /*fuction：input
49. 将文件中标示图的节点以二维组的形式存放在vector中*/
50. void input(vector<vector<int>> &Vec_Dti,string FileName) {
51. vector<int> temp_line;
52. string line;
53. ifstream in(FileName); //读入文件
54. regex pat_regex("[[:digit:]]+"); //匹配原则，这里代表一个或多个数字
55.  
56. while (getline(in, line)) { //按行读取
57. for (sregex_iterator it(line.begin(), line.end(), pat_regex), end_it; it != end_it; ++it) { //表达式匹配，匹配一行中所有满足条件的字符
58. temp_line.push_back(stoi(it->str())); //将数据转化为int型并存入一维vector中
59. }
60. Vec_Dti.push_back(temp_line); //保存所有数据
61. temp_line.clear();
62. }
63.  
64. }
65.  
66. /*fuction:initData
67. 初始化node结构体，存储在map中，记录图的各个节点的依赖关系
68. 所给的图文件，结构像一个邻接表，每一行的第一个数字代表节点名字，后面的所有节点都是第一个节点的子节点*/
69. void initData(map<int,node> &m,vector<vector<int>> inData) {
70. for (int i = 0; i < inData.size(); i++) {
71. node tmp;
72. tmp.name = inData[i][0];//记录每一行第一节点的名字
73. for (int j=1; j < inData[i].size(); j++) {
74. tmp.child.push_back(inData[i][j]);//将每一行第一个节点后的所有节点记录到该节点的孩子节点数组中
75. }
76. m[tmp.name] = tmp;
77. }
78. //每行第一个节点都是后面所有节点的父节点，所以，将父节点的信息存储到每个节点的父节点数组中
79. for (int i = 0; i < inData.size(); i++) {
80. for (int j = 1; j < inData[i].size(); j++) {
81. m[inData[i][j]].name = inData[i][j];
82. m[inData[i][j]].parent.push_back(inData[i][0]);
83. }
84.  
85. }
86.  
87. }
88.  
89. /*fuction:print

    

90. 计算结果存储在一个二维的vector中，将结果输出在终端上*/
91. void print(vector<vector<int>> output) {
92. for (auto i : output) {
93. for (auto j : i) {
94. cout << j << " ";
95. }
96. cout << endl;
97. }
98. }
99.  
100. /*fuction:ASAP
101. 将图中所有没有父母节点先执行，并在图中删除这些已执行的节点，直到图中所有节点被删除*/
102. void ASAP(vector<vector<int>> &output_ASAP, map<int, node> m) {
103. map<int, node>::iterator it;
104.  
105. while (!m.empty()) {//当图中所有节点都被删除时结束
106. vector<int> tmp;
107. it = m.begin();
108. while (it != m.end()) {
109.  
110. if (it->second.parent.size() == 0) {//找到所有没有父节点的节点，将其存在一个tmp数组中
111. tmp.push_back(it->first);
112. }
113. it++;
114. }
115. output_ASAP.push_back(tmp);
116. delate(m, tmp);//将tmp数组中的所有节点以及有关的依赖关系删除
117. }
118. }
119.  
120. /*fuction:ALAP
121. ALAP的关键是要倒着用ASAP调度，然后反转结果即可，将图中所有没有孩子节点先执行，并在图中删除这些已执行的节点，直到图中所有节点被删除，最后反转结果顺序*/
122. void ALAP(vector<vector<int>> &output_ALAP, map<int, node> m) {
123. map<int, node>::iterator it;
124.  
125. while (!m.empty()) {
126. vector<int> tmp;
127. it = m.begin();
128. while (it != m.end()) {
129.  
130. if (it->second.child.size() == 0) {//找到所有没有子节点的节点，将其存在一个tmp数组中
131. tmp.push_back(it->first);
132. }
133. it++;
134. }
135. output_ALAP.push_back(tmp);
136. delate(m, tmp);//删除tmp
137. }
138. int n = output_ALAP.size() ;
139. for (int i = 0; i < n/2; i++) {//将所得结果反转即是ALAP的结果
140. vector<int> tm;
141. tm = output_ALAP[i];
142. output_ALAP[i] = output_ALAP[n - i - 1];
143. output_ALAP[n - i - 1] = tm;
144. }
145. }
146.  
147.  
148. /*function:delate
149. 删除图中的某些节点，即key中存储的节点，再删除节点时，要将图中所有有关这些节点的依赖关系删除，即以这些删除节点为父节点或孩子节点的依赖关系删除*/
150. void delate(map<int, node> &m, vector<int> key) {
151. map<int, node>::iterator it;
152. it = m.begin();
153. while (it != m.end()) {//删掉每个节点中有关的依赖关系，即在父节点数组和子节点数组中删掉key
154. vector<int> parent = it->second.parent;
155. vector<int> child = it->second.child;
156. vector<int>::iterator itr;
157. for (int t = 0; t < key.size(); t++) {
158. for (itr = parent.begin(); itr != parent.end(); ) {
159.  
160. if (*itr == key[t]) {
161. itr = parent.erase(itr);
162. }
163. else {
164. ++itr;
165. }
166.  
167. }
168.  
169. for (itr = child.begin(); itr != child.end();) {
170. if (*itr == key[t]) {
171. itr = child.erase(itr);
172. }
173. else {
174. ++itr;
175. }
176.  
177. }
178. }
179. it->second.parent = parent;
180. it->second.child = child;
181. it++;
182. }
183.  
184. //从map中删掉key
185. for (int t = 0; t < key.size(); t++) {
186. map<int, node>::iterator k = m.find(key[t]);
187. if (k != m.end()) {
188. m.erase(k);
189. }
190. }
191.  
192.  
193. }