CS8Final/graph.cpp at master · joerenzullo/CS8Final · 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
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
#include "graph.h"


Graph::Graph(const int& size) //
{
    sizeOfAirports = size;
    initialize();
}

Graph::~Graph() //
{
    nukem();
}

Graph::Graph(const Graph &other) //
{
    copy(other);
}

Graph& Graph::operator=(const Graph &other) //
{
    if(this != &other)
    {
        nukem();
        copy(other);
    }
    return *this;
}

void Graph::addEdge(Edge*& e) //
{
    adj[e->SourceAirportID].push_back(e);
    ++sizeOfEdges;
//    cout << e->source << endl;
//    cout << adj[0][0]->source << endl;
}

int Graph::getSizeOfEdges() //
{
    return sizeOfEdges;
}

int Graph::getSizeOfAirports() //
{
    return sizeOfAirports;
}

double Graph::getDistTo(const int& dest)  //
{
    return distTo[dest];
}

void Graph::getPathTo(int dest, list<int>*& path)  //
{
    path->clear();
    for ( ; dest != -1; dest = pathTo[dest])
        path->push_front(dest);
}

void Graph::shortestPath(const int& source)
{

    dijkstra(source);
}

void Graph::dijkstra(const int& source)  //
{
    int n = adj.size();
    distTo.clear();
    distTo.resize(n, infinite);
    distTo[source] = 0;
    pathTo.clear();
    pathTo.resize(n, -1);

    pq.push(make_pair(distTo[source], source));

    while (!pq.empty())
    {
        double dist = pq.top().first;
        int s = pq.top().second;
        pq.pop();

        // Because we leave old copies of the vertex in the priority queue
        // (with outdated higher distances), we need to ignore it when we come
        // across it again, by checking its distance against the minimum distance
        if (dist > distTo[s])
            continue;

        // Visit each edge exiting s
        for (std::vector<Edge*>::const_iterator iter = adj[s].begin(); iter != adj[s].end(); iter++)
        {
            int d = (*iter)->DestinationAirportID;
            double weight = (*iter)->weight;
            double dist_through_s = dist + weight;
            if (dist_through_s < distTo[d])
            {
                distTo[d] = dist_through_s;
                pathTo[d] = s;
                pq.push(make_pair(distTo[d], d));
            }
        }
    }
}

void Graph::clear() //
{
    adj.clear();
    distTo.clear();
    pathTo.clear();
    sizeOfEdges = int();
    sizeOfAirports = int();
}

void Graph::copy(const Graph &other) //
{
    //operator =
    //Assigns new contents to the container, replacing its current content.
    adj = other.adj;
    distTo = other.distTo;
    pathTo = other.pathTo;
    sizeOfEdges = other.sizeOfEdges;
    sizeOfAirports = other.sizeOfAirports;
}

void Graph::nukem() //
{
    clear();
}

void Graph::initialize() //
{
    sizeOfEdges = 0;
    adj.reserve(sizeOfAirports);
    for(int i = 0; i < sizeOfAirports; ++i) {
        adj.push_back(vector<Edge*>());
        adj[i].reserve(200);
    }
    distTo.reserve(sizeOfAirports);
    pathTo.reserve(sizeOfAirports);
}