-
Notifications
You must be signed in to change notification settings - Fork 1
/
vertex.cpp
321 lines (260 loc) · 5.67 KB
/
vertex.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
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
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
/*
* This vertex.c file implements a Vertex struct for a directed graph structure.
*/
#include "vertex.h"
#include "linked_list.h"
/*
* Creates and returns a Vertex* pointer. Takes a parameter void* pointer of a value
* to be stored in the Vertex struct.
*/
/*
Vertex* create_vertex(void* element)
{
Vertex* v = (Vertex*)malloc(sizeof(*v));
if(v == NULL)
return NULL;
v->data = malloc(sizeof(element));
memcpy(v->data, element, sizeof(element));
v->arcList = linked_list_initialize(sizeof(Arc), (char*)"Arc");
v->visited = false;
v->distance = 0;
v->parent = NULL;
return v;
}
/*
* This function adds an arc struct going from the Vertex* origin parameter to the Vertex* dest parameter
* with a weight of the float price parameter.
*/
/*
bool add_vertex_arc(Vertex* origin, Vertex* dest, float price)
{
if(origin == NULL || dest == NULL)
return false;
Arc* arc = create_arc(dest, price);
int prevSize = linked_list_size(origin->arcList);
linked_list_add_last(origin->arcList, arc);
if(linked_list_size(origin->arcList) - prevSize == 1)
{
return true;
}
else
{
return false;
}
}
/*
* Removes an arc going from the origin Vertex* to the destination Vertex*.
* returns true if removes successfully.
*/
/*
bool remove_vertex_arc(Vertex* origin, Vertex* destination)
{
if(origin == NULL || destination == NULL)
return false;
LinkedList* list = origin->arcList;
int prevSize = linked_list_size(list);
for(int i = 0; i < linked_list_size(list); i++)
{
Arc* arc = (Arc*)linked_list_get(list, i);
Vertex* elem = (Vertex*) arc->vertex;
if(elem == destination)
{
linked_list_remove(list, i);
break;
}
}
if(prevSize - linked_list_size(list) == 1)
{
return true;
}
else
{
return false;
}
}
/**
* The get_data function returns the data field of the vertex* parameter.
* If the vertex pointer parameter is null, null is returned. Otherwise,
* the data stored in the vertex pointer is returned.
*/
/*
void* get_data(Vertex* v)
{
if(v == NULL)
{
return NULL;
}
else
{
return v->data;
}
}
LinkedList* get_arc_list(Vertex* v)
{
if(v == NULL)
{
return NULL;
}
else
{
return v->arcList;
}
}
bool been_visited(Vertex* v)
{
if(v == NULL)
{
return false;
}
else
{
return v->visited;
}
}
void set_visited(Vertex* v, bool value)
{
if(v == NULL)
return;
v->visited = value;
}
/*
* The get_weight function takes a Vertex* origin vertex that goes to the
* Vertex* destination vertex parameter and returns the weight of that arc
* if such an arc exists. -1 is returned if no such arc exists.
*/
/*
float get_weight(Vertex* origin, Vertex* destination)
{
if(origin == NULL || destination == NULL)
return -1;
LinkedList* list = get_arc_list(origin);
for(int i = 0; i < linked_list_size(list); i++)
{
Arc* arc = (Arc*) linked_list_get(list, i);
// If the vertex in this arc list matches the destination vertex
if(memcmp(arc->vertex, destination, sizeof(destination)) == 0)
{
return arc->weight;
}
}
return -1;
}
/*
* The change_vertex_weight function takes an origin and destination Vertex* and changes the
* weight associated with the arc from the origin vertex to the destination vertex to the
* value of the cost parameter.
*/
/*
bool change_vertex_weight(Vertex* origin, Vertex* destination, float cost)
{
if(origin == NULL || destination == NULL)
return false;
LinkedList* list = get_arc_list(origin);
for(int i = 0; i < linked_list_size(list); i++)
{
Arc* arc = (Arc*) linked_list_get(list, i);
// If this arc's vertex is equal to the destination vertex
if(memcmp(arc->vertex, destination, sizeof(destination)) == 0)
{
set_arc_weight(arc, cost);
return true;
}
}
return false;
}
void set_vertex_distance(Vertex* v, float value)
{
if(v == NULL)
return;
v->distance = value;
}
float get_vertex_distance(Vertex* v)
{
if(v == NULL)
return -1;
return v->distance;
}
void set_vertex_parent(Vertex* child, Vertex* adult)
{
if(child == NULL || adult == NULL)
return;
child->parent = adult;
}
Vertex* get_vertex_parent(Vertex* v)
{
if(v == NULL)
return NULL;
return v->parent;
}
/*
* The has_arc_to_vertex funciton takes a source and destination vertex pointers, searches
* the Arc list of the source vertex and returns true if the destination vertex is found in
* the Arc list. Otherwise false is returned.
*/
/*
bool has_arc_to_vertex(Vertex* source, Vertex* destination)
{
// If either the source or destination vertex are null, return false.
if(source == NULL || destination == NULL)
return false;
// Retrieve the list of Arcs from the source vertex.
LinkedList* list = get_arc_list(source);
// For each Arc in the Arc list.
for(int i = 0; i < linked_list_size(list); i++)
{
// Retrieve the Arc at index i in the list of Arcs.
Arc* arc = (Arc*) linked_list_get(list, i);
// If this Arc's vertex is equal to the destination vertex.
if(memcmp(arc->vertex, destination, sizeof(destination)) == 0)
{
// Immediately return true.
return true;
}
}
// Otherwise, the destination vertex is not found in the Arc list, return false.
return false;
}
Arc* create_arc(Vertex* v, float price)
{
Arc* arc = (Arc*)malloc(sizeof(*arc));
if(arc == NULL || v == NULL)
return NULL;
arc->vertex = v;
arc->weight = price;
return arc;
}
void set_arc_weight(Arc* arc, float price)
{
if(arc == NULL)
return;
arc->weight = price;
}
void set_vertex(Arc* arc, Vertex* v)
{
if(arc == NULL || v == NULL)
return;
arc->vertex = v;
}
float _get_arc_weight(Arc* arc)
{
if(arc == NULL)
{
return -1;
}
else
{
return arc->weight;
}
}
Vertex* get_arc_vertex(Arc* arc)
{
if(arc == NULL)
{
return NULL;
}
else
{
return arc->vertex;
}
}
*/