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;
} |
Partager