-
Notifications
You must be signed in to change notification settings - Fork 1
/
routing.c
195 lines (163 loc) · 9.46 KB
/
routing.c
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
#include "structs.h"
#include "dijikstra.c"
#include"graph.h"
#include"string-hash.h"
long long int calc_time(int cars,int length){
long long int factora=1;
long long int factorb= 1;
long long int time = (long long int)cars*(long long int)cars/factora + (long long int)length*factorb;
return time;
}
void update_cars(struct Graph* g,int i,int time,StrHash hash){
if(time==car[i].time_to_change && car[i].location_ptr<car[i].num_streets){ //if the car has reached the end of the edge and it still has more edge(s) to cover
//**Naval-> update_edge(car[i].names_of_streets[location_ptr]) decrease by 1
long long index = Find_StrHash(hash,car[i].names_of_streets[car[i].location_ptr]) ;//finding the index of the edge where the car currently is at using a hash function
hash->bkt_arr[index].congestion--;//decreasing the traffic at the street(edge) by 1 as the car has crossed it(in hash table)
decreaseCongestion(g,hash->bkt_arr[index].v1,hash->bkt_arr[index].v2);//decreasing the traffic at the street(edge) by 1 as the car has crossed it(in the graph)
car[i].location_ptr++;//updating the car's location to it's next path
index = Find_StrHash(hash,car[i].names_of_streets[car[i].location_ptr]) ;//finding the index of the edge where the car currently is at using a hash function
hash->bkt_arr[index].congestion++;//increasing the traffic at the street(edge) by 1 as the car has just entered it(in hash table)
increaseCongestion(g,hash->bkt_arr[index].v1,hash->bkt_arr[index].v2);//increasing the traffic at the street(edge) by 1 as the car has just entered it(in the graph)
car[i].time_to_change+= calc_time((long long)hash->bkt_arr[index].congestion,(long long)hash->bkt_arr[index].length);//updating the time it'll take for the car to cross the current street as a function of congestion and length of the street
}
}
int update_myloc(struct Graph*g ,int time,StrHash hash,int dest){
char is_free;
is_free='y';
StrHash_NODE n_node;
FILE * fp = fopen(".\\data\\curr_edge.txt","w");
if(time==me.time_to_change){ //if my car has reached the end of a street
do{
if(is_free=='n' || is_free=='N'){
//printf("modified**");
updateEdge(g,me.curr_node,n_node.v2,100);//updating the newly obtained congestion information(in graph)
long long node_ind = Find_StrHash(hash,me.curr_street);
hash->bkt_arr[node_ind].congestion = 100;//updating the newly obtained congestion information(in graph)
}
int currindex = Find_StrHash(hash,me.curr_street); //obtaing the index of the information stored about the edge using hash function via the edge name
StrHash_NODE a = hash->bkt_arr[currindex];//saving the deatils about the edge in the variable 'a'
hash->bkt_arr[currindex].congestion--;//decreasing the congestion of the road we crossed by 1 in the hash table
decreaseCongestion(g,a.v1,a.v2);//decreasing the congestion of the road we crossed by 1 in the graph
me.curr_node = a.v2;//updating the current node we are at
// printf("a.v2 = %d \n",a.v2);
Stack s = dijikstra(g,me.curr_node,dest);//applying dijkstra's algorithm between current node and the destination node to find out the best route
struct Edge* e = g->array[me.curr_node].head;//finding out the name of the edge using current node and next node to travel
while(e!=NULL)
{
if(e->dest == peek(&s))
{
break;
}
e = e->next;
}
strcpy(me.curr_street,e->name);//updating information about the current node
int next_index = Find_StrHash(hash,me.curr_street);//obtaining information about the next street to travel using the hash function and saving it to the variable 'next'
StrHash_NODE next = hash->bkt_arr[next_index];
me.time_to_change+= calc_time(next.congestion,next.length);//updating the time it'll take to reach the end of this street as a function of length and congestion
hash->bkt_arr[next_index].congestion++;//increasing congestion by 1 in new street (hash table)
increaseCongestion(g,next.v1,next.v2);//increasing congestion by 1 in new street (graph)
printf("\n\nYou are currently at intersection : %d",me.curr_node);//printing the current location
printf("\nThe next route you must take is : %s",me.curr_street);//suggesting the next path to tread
fprintf(fp,"%s\n",me.curr_street);//writing the name of the next edge on a file so that it can be used by visualise.py to highlight suggested path
fclose(fp);
if(g->V <= 100 || g->E <=100 ) //printing the graph if the number of nodes/edges isn't too large
{
system("python .\\visualize.py");
}
else
{
getch();
}
printf("\n Is the path ahead avalible to travel? (Y/N): ");
scanf(" %c",&is_free);
n_node.v2=next.v2;
} while(is_free=='N'||is_free=='n'); //loop runs again with updated congestion information obtained just now and tries to find a new path if it exists
if(n_node.v2==dest)//if the next node is our destination return 1, else return 0
return 1;
else
return 0;
}
return 0;
}
void routing(struct Graph* g,StrHash hash,int dest){
StrHash_NODE n_node;
FILE* fp = fopen(".\\data\\curr_edge.txt","w"); //opening text file to give information to visualise.py
system("cls");
// initialising conditions for simulation time 'time'=0
for (int i = 0; i < Ncars; i++)//updating the initial information about each car
{
car[i].location_ptr = 1; //updating the initial location of the car
int index = Find_StrHash(hash,car[i].names_of_streets[car[i].location_ptr]) ;//finding the details of the edge by using a hashing function
hash->bkt_arr[index].congestion++;//increasing the traffic on that street(edge) by 1 on the hash table
increaseCongestion(g,hash->bkt_arr[index].v1,hash->bkt_arr[index].v2);//increasing the traffic on that street(edge) by 1 on the graph
car[i].time_to_change = calc_time((long long)hash->bkt_arr[index].congestion,(long long)hash->bkt_arr[index].length);//calculating the time it'll take for the car to reach
}
char is_free;
is_free='y';
do{
if(is_free=='n' || is_free=='N'){
//printf("modified**");
updateEdge(g,me.curr_node,n_node.v2,100);//updating the newly obtained congestion information(in graph)
long long node_ind = Find_StrHash(hash,me.curr_street);
hash->bkt_arr[node_ind].congestion = 100;
}
Stack s3 = dijikstra(g,me.curr_node,dest) ;//applying dijkstra's algorithm to find out the best possible route from starting node to destinartion
//the following ~30 lines are the same as the update_myloc funciton, except that this is filling up the data for initial conditions when time t=0
//please refer to update_myloc(___) function to understand what each command achieves
struct Edge* e1 = g->array[me.curr_node].head;
while(e1!=NULL)
{
if(e1->dest == peek(&s3))
{
break;
}
e1 = e1->next;
}
strcpy(me.curr_street,e1->name);
//update congestion values for both nodes
int next_index = Find_StrHash(hash,me.curr_street);
StrHash_NODE next = hash->bkt_arr[next_index]; //next has information about the edge
me.time_to_change= calc_time(next.congestion,next.length);/* obtain using car[i].names_of_streets[location_ptr])*/
hash->bkt_arr[next_index].congestion++;
increaseCongestion(g,next.v1,next.v2);
printf("\n\nYou are currently at intersection : %d",me.curr_node);
printf("\nThe next route you must take is : %s",me.curr_street);
// printf("\n initalised conditions");
fprintf(fp,"%s\n",me.curr_street);
fclose(fp);
if(g->V <= 100 || g->E <=100 )
{
system("python .\\visualize.py");
}
else
{
printf("\nMap size is too large to be depicted.\n");
}
printf("\n Is the path ahead avalible to travel? (Y/N): ");
scanf(" %c",&is_free);
n_node.v2=next.v2;
} while(is_free=='N'||is_free=='n');
long long int time=0; //setting the simulation time to 0
int have_i_reached_node=0; //a flag varriable to know if we've crossed a street or not
// printf("%d %d %lld\n",me.curr_node,me.end_node,me.time_to_change);
if(n_node.v2==dest)
goto L1;
while(1){
time++;//increasing the time unit by 1
// printf("\n %lld",time);
have_i_reached_node = 0;
for(int i=0;i<Ncars;i++){ //updates the location for every car and the changes in edge weights are accounted for in this loop
update_cars(g,i,time,hash); //updates the location of each individual car and the edge weights accordingly
}
// printf("\n%d %d %lld\n",me.curr_node,me.end_node,me.time_to_change);
have_i_reached_node=update_myloc(g,time,hash,dest); //update 'me' variable, i.e. details of my car
if(have_i_reached_node==1){
L1:
printf("\n\nYou are currently at intersection : %d",me.curr_node);
printf("\nYou have reached your destination");
printf("\n(Press any key to continue)");
getch();
break;
}
}
}