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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
| /***** FORD-FULKERSON ALGORITHM IMPLEMENTATION *****/
/** Module Name : ff.cpp **/
/** Date : 10 / 26 / 2005 **/
/** Description : Finding maximum flow on directed graph
using FORD-FULKERSON algorithm **/
/** Author : Chinh Trung VU **/
/** Purpose : Completing algorithm class assignment **/
#include <fstream>
#include <ostream.h>
#include <ctime>
/*/USEFUL FUNCTION/*/
#define min(x,y) (x)<(y)? (x):(y) ; // returns minimum
#define clrscr() system("cls");
/*/ BASIC DEFINITIONS /*/
typedef int dat_type; // data type for capacity, flow, ...
//for bfs
#define WHITE 0 // node is not visited
#define GRAY 1 // node is not visited but wait in line (on queue)
#define BLACK 2 // node visited
//for graph input
int No_of_Node; // number of nodes
int No_of_Edge; // number of edges
#ifndef INFINITY
#define INFINITY 0x7fff
#endif
//for estimating running time
// #define NO_LOOP 50 //1000
/*/ ADJACENCY LIST DATA STRUCTURE/*/
struct link // Structure for adjacency links (edges)
{
dat_type capacity; // link capacity
dat_type flow; // flow after each time augmenting
int node_name; // name of the end node of the edge
struct link *adj; // the next edge
};
struct node_detail // Structure for nodes
{
int node_name; // name of the node
int bfs_status,prev;// for bfs use
struct link *adj; // next edge
};
typedef struct node_detail Vertex;
// ~ End of ADJACENCY LIST DATA STRUCTURE\\
/*/ adjacency list for origin graph G + residual graph of G /*/
Vertex *vertices;
/*/ ADD NECESSARY LIBRARY/*/
#include "Queue.cpp" // queue class
#include "graph_lib.cpp"// graph randomizing
/*/FUNCTION PROTOTYPE/*/
struct link * find_edge(int from, int to);
int bfs(int start, int target);
double Ford_Fulkerson (int source, int sink);
bool read_input_file(char *filename);
void declare_adj_list();
void remove_adj_list();
/*/FUNCTION IMPLEMENTATION/*/
/* Find edge [from,to] on adjacency list.
- input: from, to node
- output: edge in the form pointer of link structure
*/
struct link * find_edge(int from, int to){
struct link *e_temp;
e_temp = vertices[from].adj;
//begin to find in the link list the edge [from,to]
while ((e_temp->node_name !=to) && (e_temp!=NULL))
e_temp = e_temp->adj;
return e_temp;
}
/* Breapth First Search (BFS) Traversal on RESIDUAL graph.
- input: residual graph. source, sink node
- output: + sortest (in term of "no of edge") path
saved on the adjacency list
+ return true if reach target, and vice versa
*/
int bfs(int start, int target){
int i=1,j=0;
int vnode,v;
struct link *e_temp;
Queue qu; //creat queue class
// Reset all node to not visited status
for(i=0;i<No_of_Node;i++)
vertices[i].bfs_status=WHITE;
//Start to traverse
qu.Add_Queue(start);
vertices[start].bfs_status=GRAY;
while(!qu.Queue_Empty()) // If queue empty, we stop!
{ vnode = qu.Del_Queue();
vertices[vnode].bfs_status=BLACK; //node vnode is visited
// Search all adjacent WHITE nodes v of vnode
e_temp = vertices[vnode].adj;
while(e_temp!=NULL) {
v=e_temp->node_name;
// We only care edges in the RESIDUAL graph having POSITIVE RESIDUAL CAPACITY
if ( (vertices[v].bfs_status==WHITE) && (e_temp->capacity > e_temp->flow) ){
qu.Add_Queue(v);
vertices[v].bfs_status=GRAY; //show that node v is waiting in queue
vertices[v].prev = vnode;
//Small trick: If we reach to target, paint it BLACK and stop
if (v==target){
vertices[target].bfs_status=BLACK;
qu.ClearAll(); //remove Queue from memory
break;
}
}
e_temp = e_temp->adj;
}
}
// The color of the target node is black means it was reached.
return (vertices[target].bfs_status==BLACK);
}
/* Main FORD-FULKERSON methods, EDMONDS-KARP algorithm [Cormen]
- input: residual graph. source, sink node
- output: return Maximum flow
*/
double Ford_Fulkerson (int source, int sink) {
int u;
struct link *e_temp;
double max_flow = 0;
// idea: While there exists an augmenting path, increment the flow along this path.
while (bfs(source,sink)) { //1. Find shortest path
// 2. Determine the amount by which we can increment the flow.
int increment = INFINITY;
u=sink;
while (u!=source){ //go along shortest path from sink to source
e_temp = find_edge(vertices[u].prev,u);
increment = min(increment, e_temp->capacity - e_temp->flow);
u = vertices[u].prev;
}
// 3. Increment the flow along the found shortest path.
u=sink;
while (u!=source){ //go along shortest path from sink to source
//3.1: increment flow edge [prev_u,u] if [prev_u,u] on shortest path
e_temp = find_edge(vertices[u].prev,u);
e_temp->flow+= increment;
//3.2: decrement flow edge [u,prev_u] if [prev_u,u] on shortest path
e_temp = find_edge(u,vertices[u].prev);
e_temp->flow-= increment;
u = vertices[u].prev; //continue crawling to source
}
max_flow += double(increment);
}
return max_flow;
}
/* Delete adjacency list vertices after each running time estimation
- input: vertices matrix
- output: return true if successful and vice versa
*/
void remove_adj_list(){
struct link *e_temp;
struct link *next_e;
// go through all list elements
for(int i=0;i<No_of_Node;i++){
//delete all adjacent nodes of each element
e_temp = vertices[i].adj;
while (e_temp!=NULL){
next_e=e_temp->adj;
if (next_e!=NULL)
delete e_temp;
e_temp = next_e;
}
}
delete e_temp;
delete next_e;
delete vertices;
}
int main (int argc, char *argv[]) {
char *filename;
int NO_LOOP;
int maximum_flow;
clock_t start, elapsed; //for estimating running time
struct link *e_temp; //for restarting flow each test
//A. Preparation
//A.1 print welcome screen
clrscr();
cout<<"**********************************************************\n";
cout<<"* *\n";
cout<<"* Student name: Chinh Trung VU *\n";
cout<<"* *\n";
cout<<"* FORD-FULKERSON ALGORITHMS IMPLEMENTATION *\n";
cout<<"* *\n";
cout<<"**********************************************************\n\n";
//A.2: randomize cost (weight) link values for indirect graph
//A.2.1. processing command parameter to get No_of_Node & No_of_Edge value
if (argc<4) {
cout << "PROGRAM SYNTAX:\n\n";
cout << "\t ff [N/D/T] Number_Of_Iteration \n\t\t[Number_Of_Node/File_name] [Number_Of_Edge/Graph Density]\n";
cout << " ----------------\n First parameter:\n ----------------\n";
cout << "\tN: Input number of edges\n";
cout << "\tD: Input graph density\n";
cout << "\tT: Input from text file\n";
cout << " --------\n Example:\n --------\n";
cout << "\t ff N 1000 100 5000\n";
cout << "\t ff D 1000 100 90\n";
cout << "\t ff T 1000 sample.txt\n\n";
return 0;
}
//A.2.2. Randomizing input or Reading text file
switch (toupper(*argv[1])){
case 'N': //input no of edges
if (argc!=5) {cout << "\nNot enough parameter"; return 0;}
NO_LOOP=atoi(argv[2]);
No_of_Node=atoi(argv[3]);
No_of_Edge=atoi(argv[4]);
randomize_input(No_of_Node,No_of_Edge);
break;
case 'D': //input density
if (argc!=5) {cout << "\nNot enough parameter"; return 0;}
NO_LOOP=atoi(argv[2]);
No_of_Node=atoi(argv[3]);
No_of_Edge=(No_of_Node*(No_of_Node-1)*atoi(argv[4]))/100;
randomize_input(No_of_Node,No_of_Edge);
break;
case 'T': //input text sample file
NO_LOOP=atoi(argv[2]);
filename = argv[3];
read_input_file(filename);
break;
default:
cout << "Wrong input";
break;
}
//B. Running algorithm and measuring run-time
start = clock();
// Running algorithm
for (int m=0;m<NO_LOOP;m++){
//restarting all flow to 0 before implementing algorithm
for (int i=0; i<No_of_Node;i++){
e_temp = vertices[i].adj;
while(e_temp!=NULL) {
e_temp->flow=0;
e_temp=e_temp->adj;
}
}
maximum_flow = Ford_Fulkerson(0,No_of_Node-1);
}
//Showing running time on screen
elapsed = clock() - start;
cout << "\n\nAlgo name\tNo_of_Node\tNo_of_Edge\tRunning time\n";
cout << "---------\t----------\t----------\t------------\n";
cout << "Ford-Fulkerson\t" << No_of_Node << "\t\t" << No_of_Edge << "\t\t" << float(elapsed)/float(NO_LOOP) <<"\n";
cout << "\n\nMaxomum flow \t\t:"<<maximum_flow<<"\n";
delete e_temp;
remove_adj_list(); //clean memory
//system("PAUSE");
return 0;
} |
