-
Notifications
You must be signed in to change notification settings - Fork 0
/
graph.h
465 lines (394 loc) · 12.2 KB
/
graph.h
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
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
/*
* graph.h
*
* Interface/specifications for Graph class
*
* @author Yusuf Pisan & Juan Arias
*
*/
#ifndef GRAPH_H
#define GRAPH_H
#include <iostream>
#include <fstream>
#include <climits>
#include <utility>
#include <string>
#include <stack>
#include <queue>
#include <set>
#include <map>
/*
* A graph is made up of vertices and edges.
* Vertex labels are unique.
* A vertex can be connected to other vertices via weighted, directed edge.
* A vertex cannot connect to itself or have multiple edges to the same vertex
*/
class Graph {
/*
* Friend function to print Graph to ostream
* @param out The ostream to print to Graph
* @param g The Graph to be printed
* @return out by reference
*/
friend std::ostream& operator<<(std::ostream& out, const Graph& g);
public:
/* Type definitions*/
using Label = std::string;
using Weight = int;
using Visit = void(const Label&);
using LabelStack = std::stack<Label>;
using LabelQ = std::queue<Label>;
using LabelWeight = std::pair<const Label, const Weight>;
using PrevLabel = std::pair<const Label, const Label>;
using WeightMap = std::map<Label, Weight>;
using PrevMap = std::map<Label, Label>;
/* Constants for reuse with meaning*/
static const Label NO_LABEL;
static const Weight NO_WEIGHT;
static const int EMPTY;
static const int COUNT;
static const char COMMA;
static const char LEFT_P;
static const char RIGHT_P;
/*
* Constructs empty graph
*/
Graph();
/*
* Copy constructor overload
* @param other The other Graph to copy
*/
Graph(const Graph& other);
/*
* Destroys Graph, all Vertices, all Edges and deallocates dynamic memory
*/
virtual ~Graph();
/*
* Assignment operator overload
* @param other The other Graph to copy
*/
Graph& operator=(const Graph& other);
/*
* Get the total number of Vertices in Graph
* @return total number of Vertices in Graph
*/
int NumberOfVertices() const;
/*
* Get the total number of Edges in Graph
* @return total number of Edges in Graph
*/
int NumberOfEdges() const;
/*
* Get the number of Edges connected to a given Vertex
* @param label The label of the Vertex
* @return number of edges from Vertex, -1 if Vertex not found
*/
int NumberOfEdges(const Label& label) const;
/*
* Add a Vertex to Graph, no duplicates allowed
* @param label The label of the Vertex
* @return true if vertex added, false if it already is in Graph
*/
bool AddVertex(const Label& label);
/*
* Check is Vertex exists in Graph
* @param label The label of the vertex to find
* @return true if Vertex in Graph, else false
*/
bool HasVertex(const Label& label) const;
/*
* String representation of Edges from a given Vertex
* @param label The label of the Vertex to get Edges from
* @return string representing Edges and weights, "" if Vertex not found
*/
std::string GetEdges(const Label& label) const;
/*
* Add a new Edge between start and end Vertex
* If the Vertices do not exist, create them
* A Vertex cant connect to itself or have multiple Edges to another Vertex
* @param label1 The starting Vertex label
* @param label2 The ending Vertex label
* @param weigt An optional weight for new Edge, defaults to 0
* @return true if successfully connected, else false
*/
bool Connect(const Label& label1, const Label& label2,
const Weight& weight = 0);
/*
* Remove Edge from Graph
* @param label1 The starting Vertex label
* @param label2 The ending Vertex label
* @return true if Edge successfully deleted, else false
*/
bool Disconnect(const Label& label1, const Label& label2);
/*
* Read Edges from file, first line of file is an integer indicating
* number of Edges, each line represents an Edge in the form of
* "string string int", Vertex labels cannot contain spaces
* Clears previous contents
* @param fileName The name of the file
* @return true if file successfully read, else false
*/
bool ReadFile(const std::string& fileName);
/*
* Depth-first traversal originating from Vertex with given label
* @param label The origin Vertex label
* @param func The function to call on each Vertex label
*/
void DFS(const Label& label, Visit func);
/*
* Breadth-first traversal originating from Vertex with given label
* @param label The origin Vertex label
* @param func The function to call on each Vertex label
*/
void BFS(const Label& label, Visit func);
/**
* Dijkstra's algorithm to find shortest distance to all other Vertices
* and the path to all other Vertices
* Path cost is recorded in the map passed in, e.g. weights["F"] = 10
* How to get to vertex is recorded in map passed in, prevs["F" = "C"
* @param label The label of the origin Vertex
* @param wMap The map to record shortest path
* @param pMap The map to record previous Vertex
*/
void Dijkstra(const Label& label, WeightMap& wMap, PrevMap& pMap);
/*
* Creates a MinSpanningTree using Prim's algorithm
* @param label The label of the origin Vertex
* @return a Graph of the MinSpanningTree
*/
Graph* MinSpanningTree(const Label& label);
/*
* Gets the sum cost of all Edges in Graph
* @return sum cost of all Edges in Graph
*/
Weight SumOfEdges() const;
private:
/*
* Private Vertex class of Graph
*/
class Vertex {
public:
/*
* Constructs Vertex with given Label
* @param label The lable of the Vertex, default to blank
* @param weight The weight of the Vertex, default to -1
* @param next The next Vertex in the list
*/
explicit Vertex(const Label& label = Graph::NO_LABEL,
const Weight& weight = Graph::NO_WEIGHT,
Vertex* next = nullptr,
const int& edges = Graph::EMPTY);
/*
* Copy constructor with pointers
* @param other The other Vertex to copy
*/
Vertex(const Vertex& other);
/*
* Assignment operator overload
* @param other The other Vertex to copy
* @return this by reference
*/
Vertex& operator=(const Vertex& other);
/*
* Destroys Vertex
*/
virtual ~Vertex();
/*
* Gets Vertex label
* @return Vertex label
*/
Label getLabel() const;
/*
* Gets Edge Weight (for adjacent Vertices)
* @return Edge Weight
*/
Weight getWeight() const;
/*
* Returns true if Vertex visited, else false
* @return true if Vertex visited, else false
*/
bool isVisited() const;
/*
* Sets the Vertex as visited or unvisited
* @param visited The boolean to indicated if visited(true) or
* unvisited(false)
*/
void setVisited(bool visited = true);
/*
* Gets the pointer to next Vertex in the adjacency list
* @retrun pointer to next Vertex in the adjacency list
*/
Vertex* getNext() const;
/*
* Sets next to new Vertex in the adjacency list
* @param pointer to next Vertex in the adjacency list to add
*/
void setNext(Vertex* next);
/*
* Counts all Edges for a Vertex
* @return number of Edges connected from Vertex
*/
int numOfEdges() const;
/*
* Gets string representation of Edges & adjacent Vertices
* @return string representation of Edges & adjacent Vertices
*/
std::string getEdges() const;
/*
* Adds new Vertex with label in adjacent list
* Must maintain sorted list, Vertex cant connect to itself
* No duplicate Edges
* @param label The label to give the adjacent Vertex
* @param weight The weight to label the Edge
* @return true if connected, else false
*/
bool connect(const Label& label, const Weight& weight);
/*
* Deletes Vertex with label in adjacent list
* @param label The label of the adjacent Vertex to delete
* @return true if disconnected, else false
*/
bool disconnect(const Label& label);
/*
* Gets the adjacent Vertex with given label
* or nullptr if it does not exist
* @param label The label of the adjacent Vertex
* @return pointer to adjacent Vertex or nullptr if it does not exist
*/
Vertex* getAdjacent(const Label& label) const;
/*
* Deallocate all adjacent Vertices
*/
void clear();
private:
/* Label to uniquely ID each Vertex */
const Label label;
/* Edge weight */
const Weight weight;
/* Visited mark for Graph traversals */
bool visited;
/* Pointer to next Vertex in adjacency list*/
Vertex* next;
/* Number of Edges from Vertex */
int edges;
/*
* Makes string representation Vertex
* @return string Vertex
*/
std::string toString() const;
};
/* Type definitions */
using VertexSet = std::set<const Vertex*>;
using LabelVert = std::pair<const Label, Vertex*>;
using AdjacencyMap = std::map<const Label, Vertex*>;
/* Adjacency Map from label to Vertex */
AdjacencyMap map;
/* Number of Edges in graph */
int edges;
/*
* Helper for copy constructor and assignment operator overload
* Copies contents of AdjacencyMap in other Graph
* @param otherMap The map in the other Graph to clone
*/
void clone(const AdjacencyMap* otherMap);
/*
* Deallocate all dynamic memory
*/
void clear();
/*
* Extracts contents from file to create Vertices & Edges
* @param file The file to extract contents from
*/
void extractFile(std::ifstream* file);
/*
* Helper for depthFirstTraversal
* @param stack The stack to search depth first with
*/
void dfs(LabelStack* stack, Visit func);
/*
* Helper for search functions
* Gets the next unvisited Vertex label adjacent to Vertex with given label
* @param label The label of the Vertex to get next from
* @return next unvisited Vertex label adjacent to Vertex, or blank if none
*/
Label nextLabel(const Label& label);
/*
* Helper for nextLabel
* Gets the next unvisited Vertex starting from curr
* @param curr The current Vertex
* @param nextLabel Pointer to store label of next unvisited Vertex
* @return next unvisited Vertexnext unvisited Vertex
*/
Vertex* nextVertex(Vertex* curr, Label* nextLabel) const;
/*
* Helper for breadthFirstTraversal
* @param q The queue to search breadth first with
* @param func The function to call on each Vertex
*/
void bfs(LabelQ* q, Visit func);
/*
* Helper for bfsHelper, adds all unvisited adjacent Vertices to q
* @param q The queue to search breadth first with
* @param curr The Vertex to get unvisited adjacent Vertices from
*/
void addUnvisited(LabelQ* q, Vertex* curr);
/*
* Helper for Dijkstra, initializes WeightMap and PrevMap for all Vertices
* adjacent to the origin Vertex
* @param curr The origin Vertex
* @param label The label of the origin Vertex
* @param wMap The WeightMap
* @param pMap The PrevMap
*/
void initMaps(const Vertex* curr, const Label& label, WeightMap* wMap,
PrevMap* pMap) const;
/*
* Helper for Dijkstra, iteratively gets the next smallest Vertex from
* WeightMap thats not in VertexSet and updates any possible shorter paths
* from the origin
* @param set The VertexSets
* @param wMap The WeightMap
* @param pMap The PrevMap
*/
void dijkstra(VertexSet* set, WeightMap* wMap, PrevMap* pMap) const;
/*
* Helper for dijkstra, gets the label for the next smallest Vertex from
* WeightMap thats not in VertexSet
* @param set The VertexSet
* @param wMap The WeightMap
* @param label The pointer to assign as the label of the next smallest Vertex
* @return pointer to the next smallest Vertex
*/
Vertex* nextSmallest(const VertexSet* set, const WeightMap* wMap,
Label* label) const;
/*
* Helper for dijkstra, updates an entry in the WeightMap if there is a shorter
* path
* @param curr The current Vertex
* @param pair The entry in the WeightMap to update
* @param label The label of the current Vertex
* @param wMap The WeightMap
* @param pMap The PrevMap
*/
void update(const Vertex* curr, const LabelWeight& pair,
const Label& label, WeightMap* wMap, PrevMap* pMap) const;
/*
* Helper for Dijkstra, removes origin Vertex entry and entries in WeightMap that
* were not visited during Dijkstra
* @param wMap The WeightMap
*/
void cleanWeights(WeightMap* wMap);
/*
* Helper for MinSpanningTree, gets the Vertices connected to the next
* minimum cost Edge
* @param curr The starting Vertex on the next minimum cost Edge
* @param next The ending Vertex on the next minimum cost Edge
* @param label The label of the starting Vertex on the next minimum cost Edge
*/
void nextMinEdge(Vertex*& curr, Vertex*& next, Label* label);
/*
* Mark all verticies as unvisited
*/
void unvisitVertices();
};
#endif // GRAPH_H