-
Notifications
You must be signed in to change notification settings - Fork 0
/
main.cpp
156 lines (138 loc) · 5.39 KB
/
main.cpp
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
#include "dijkstra.h"
#include "grap_data_struct.h"
#include "kruskal.h"
#include <ctime>
#include <sys/time.h>
using namespace std;
/*test wether generated value is unique*/
vector<unsigned int> st_pair;
bool is_uniq(unsigned int vert)
{
bool temp = true;
for(unsigned int i=0;i<st_pair.size();i++)
{
if(st_pair[i]==vert)
{
temp=false;
break;
}
}
return temp;
}
void timeval_subtract(struct timeval *result, struct timeval *t2, struct timeval *t1)
{
unsigned long int diff = (t2->tv_usec + 1000000 * t2->tv_sec) - (t1->tv_usec + 1000000 * t1->tv_sec);
result->tv_sec = diff / 1000000;
result->tv_usec = diff % 1000000;
//return (diff<0);
}
int main()
{
Graph G1;
Graph G2;
struct timeval start;
struct timeval finish;
struct timeval result;
unsigned int temp,j;
srand(time(NULL));
char filename[] = "test_graph.txt";
char out_file[] = "output.txt";
ofstream output(out_file);
#ifdef debug
G1.init_graph_file(filename);
init_data();
Make_Heap(&G1.node_list);
/*Please change your values accordingly for testing*/
cout<<"The number steps executed for Kruskal were: "<<Kruskal(&G1)<<endl;
cout<< "The steps number executed for dijkstra were: "<<normal_dijkstra(&G1,0,4)<<endl;
cout<< "The steps number executed for heap dijkstra were: "<<heap_dijkstra(&G1,0,4)<<endl;
cout<< "The steps number executed for dfs were: "<<DFS(&G1,0,4)<<endl;
#endif // debug
#ifndef debug
G1.init1_random_graph(6);
G2.init1_random_graph(1000);
//generate 5 random st_pairs
temp = rand()%VERTICES;
st_pair.push_back(temp);
for(int i=1;i<10;i++)
{ temp = rand()%VERTICES;
while(is_uniq(temp)==false)
temp = rand()%VERTICES;
st_pair.push_back(temp);
}
//test on G1
init_data();
Make_Heap(&G1.node_list);
cout<<"Running Kruskal"<<endl;
output<<"Running tests on graph G1 of degree 6"<<endl;
gettimeofday(&start,NULL);
//Running Kruskal first
output<<"The number steps executed for Kruskal were: "<<Kruskal(&G1)<<endl;
gettimeofday(&finish,NULL);
timeval_subtract(&result,&finish,&start);
cout<< "The total system runtime for Kruskal was"<<result.tv_sec<<" secs and "<<result.tv_usec<<" usecs"<<endl;
//running dijkstra
cout<<"Running dijkstra"<<endl;
gettimeofday(&start,NULL);
for(j=0;j<10;j=j+2)
output<< "The steps number executed for dijkstra were: "<<normal_dijkstra(&G1,st_pair[j],st_pair[j+1])<<endl;
gettimeofday(&finish,NULL);
timeval_subtract(&result,&finish,&start);
cout<< "The total system runtime for normal dijkstra was"<<result.tv_sec<<" secs and "<<result.tv_usec<<" usecs"<<endl;
//running heap_dijkstra
cout<<"Running heap_dijkstra"<<endl;
gettimeofday(&start,NULL);
for(j=0;j<10;j+=2)
output<< "The steps number executed for heap_dijkstra were: "<<heap_dijkstra(&G1,st_pair[j],st_pair[j+1])<<endl;
gettimeofday(&finish,NULL);
timeval_subtract(&result,&finish,&start);
cout<< "The total system runtime for heap dijkstra was"<<result.tv_sec<<" secs and "<<result.tv_usec<<" usecs"<<endl;
//running dfs
cout<<"Running DFS"<<endl;
gettimeofday(&start,NULL);
for(j=0;j<10;j+=2)
output<< "The steps number executed for dfs were: "<<DFS(&G1,st_pair[j],st_pair[j+1])<<endl;
gettimeofday(&finish,NULL);
timeval_subtract(&result,&finish,&start);
cout<< "The total system runtime for normal dfs was"<<result.tv_sec<<" secs and "<<result.tv_usec<<" usecs"<<endl;
/*
Now Testing on G2 graph
*/
init_data();
Make_Heap(&G2.node_list);
cout<<"Running Kruskal"<<endl;
output<<"Running tests on graph G2 of degree 1000"<<endl;
gettimeofday(&start,NULL);
//Running Kruskal first
output<<"The number steps executed for Kruskal were: "<<Kruskal(&G2)<<endl;
gettimeofday(&finish,NULL);
timeval_subtract(&result,&finish,&start);
cout<< "The total system runtime for Kruskal was"<<result.tv_sec<<" secs and "<<result.tv_usec<<" usecs"<<endl;
//running dijkstra
cout<<"Running dijkstra"<<endl;
gettimeofday(&start,NULL);
for(j=0;j<10;j+=2)
output<< "The steps number executed for dijkstra were: "<<normal_dijkstra(&G2,st_pair[j],st_pair[j+1])<<endl;
gettimeofday(&finish,NULL);
timeval_subtract(&result,&finish,&start);
cout<< "The total system runtime for normal dijkstra was"<<result.tv_sec<<" secs and "<<result.tv_usec<<" usecs"<<endl;
//running heap_dijkstra
cout<<"Running heap_dijkstra"<<endl;
gettimeofday(&start,NULL);
for(j=0;j<10;j+=2)
output<< "The steps number executed for heap_dijkstra were: "<<heap_dijkstra(&G2,st_pair[j],st_pair[j+1])<<endl;
gettimeofday(&finish,NULL);
timeval_subtract(&result,&finish,&start);
cout<< "The total system runtime for heap dijkstra was"<<result.tv_sec<<" secs and "<<result.tv_usec<<" usecs"<<endl;
//running dfs
cout<<"Running DFS"<<endl;
gettimeofday(&start,NULL);
for(j=0;j<10;j+=2)
output<< "The steps number executed for dfs were: "<<DFS(&G2,st_pair[j],st_pair[j+1])<<endl;
gettimeofday(&finish,NULL);
timeval_subtract(&result,&finish,&start);
cout<< "The total system runtime for normal dfs was"<<result.tv_sec<<" secs and "<<result.tv_usec<<" usecs"<<endl;
#endif // debug
output.close();
return 0;
}