poa/Graph.h at master · ThomasMatlak/poa · GitHub

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
/*---Graph.h-------------------------------------------------------------------
* Thomas Matlak
*
* Graph Class
*
* Operations:
*	drawGraph()         - Output a representation of the graph for debugging
*	traverseSelfish()   - Get the minimum cost path between nodes using
*                         Dijkstra's algorithm, only considering distance
*   traverseOptimal()   - Get the optimal minimum cost path between nodes with
                          Dijkstra's algorithm
*   traversalDistance() - Get the time to travel between nodes using Dijkstra's
                          Algorithm
*   resetGraph()        - Reset the graph edges to their original weights
*----------------------------------------------------------------------------*/

#pragma once

#include <vector>
#include <deque>

struct Node {
    std::vector<int> adjacentNodes;
};

/*
* Graph
*/
class Graph
{
public:
	Graph(int setNumNodes, int setMaxEdgeLength);

	~Graph();

	/*---printGraph()----------------------------------------------------------
	* Output a representation of the graph to the console for debugging
	*
	* pre:  none
	* post: a representation of the graph is output
	*------------------------------------------------------------------------*/
	void printGraph();

	/*---traverseSelfish()-----------------------------------------------------
	* Get the minimum cost path between nodes using Dijkstra's algorithm,
	*   only considering travel distance
	*
	* start - the starting node of the graph
	* dest  - the ending node of the graph
	*
	* pre:  start, finish are indexs of nodes in the graph
	* post: the shortest path is returned
	*------------------------------------------------------------------------*/
	std::deque<int> traverseSelfish(int start, int dest);

	/*---optimalTraverse()-----------------------------------------------------
	* Get the optimal minimum cost path between nodes with Dijkstra's algorithm
	*
	* start - the starting node of the graph
	* dest  - the ending node of the graph
	*
	* pre:  start, finish are indexs of nodes in the graph
	* post: the shortest path is returned
	*------------------------------------------------------------------------*/
	std::deque<int> traverseOptimal(int start, int dest);

    /*---traversalDistance()---------------------------------------------------
    * Get the time to travel between nodes using Dijkstra's Algorithm
    *
    * start - the starting node of the graph
	* dest  - the ending node of the graph
	*
    * pre:  none
    * post: the distance from start to dest is returned
    *------------------------------------------------------------------------*/
    int traversalDistance(int start, int dest);

    /*---resetGraph()----------------------------------------------------------
    * Reset the graph edges to their original weights
    *
    * pre:  none
    * post: edges is set to initialEdges
    *------------------------------------------------------------------------*/
    void resetGraph();

    int getNumNodes();

    friend int minDistance(std::vector<int>& dist, std::vector<bool>& sptSet, Graph & graph);
private:
    std::vector<Node*> nodes; /* this could be done as a vector of a vector of
                                 adjacent nodes, but this allows for nodes to
                                 contain more information in the future */
	std::vector<std::vector<int>> edges;
	std::vector<std::vector<int>> initialEdges; // = edges
    int numNodes;
    int maxEdgeLength;
};