-
Notifications
You must be signed in to change notification settings - Fork 1
/
Graph.h
143 lines (98 loc) · 3.4 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
#ifndef GRAPH_H
#define GRAPH_H
#include <iostream>
#include <set>
#include <map>
#include <list>
#include <vector>
#include <iterator>
#include <limits>
#include <climits>
// [[Rcpp::plugins("cpp11")]]
using namespace std;
const int MAX_NODES = 100000; //100,000 parent nodes at maxmimum
class Node;
class Edge;
double calculateDistance(Node & s, Node & e);
class Graph {
private:
vector <Node> m_nodes;
vector < set<Node> > m_adjList;
vector < list<Edge> > m_edgeList;
vector<Edge> m_edges_MST;
int current_id;
int current_cc;
int m_clock;
int m_max_nodes;
public:
/************************* ctors & scan from/save to file *************************/
Graph(const string & file);
Graph(int num_nodes);
Graph();
void scan(const string & file);
void scan_undirected(const string & file);
void scan_tmg(const string & file);
void save(const string & file) const;
void saveUndirected(const string & file) const;
void saveReverse(const string & file) const;
/************************* setters *************************/
void addEdge(const Node & a, const Node & b);
void addEdgeObj(const Node & a, const Edge & b);
void addNode(const Node & a);
void pushNode(const Node & a);
void pushEdge(const Edge & e);
void setVisited(const Node & a);
void setPre(const Node & a, int pre);
void setPost(const Node & a, int post);
void setDist(const Node & a, double dist);
void setCC(const Node & a, int cc);
void setParent(const Node & a,int parent);
void setRank(const Node & a, int rank);
void setNext(const Node & a,int next);
void setEdgeRoads(const Node & a, string roads);
void incrementClock();
void incrementCurrentCC();
/************************* getters *************************/
const string edgeRoads(const Node & a) const;
const string name(int u_id) const;
const double dist(const Node & a) const;
const int pre(const Node & a) const;
const int post(const Node & a) const;
const int cc(const Node & a) const;
const int next(const Node & a) const;
const int currentCC() const;
const int clock() const;
const int max_nodes() const;
const int rank(const Node & a) const;
const size_t num_nodes() const;
const size_t num_edges() const;
const bool visited(const Node & a) const;
const vector<Edge> & get_MST() const;
// const vector<Edge> get_MST() const;
int parent(const Node & a);
const Node & getNode (size_t i) const;
set <Node> & getAdjNodes(const Node & a);
const set <Node> & getAdjNodes(const Node & a) const;
list <Edge> & getEdges(const Node & a);
const list <Edge> & getEdges(const Node & a) const;
vector<Node>::iterator begin();
vector<Node>::iterator end();
/************************* test, print and debug *************************/
bool sameDistances(vector<int> V);
bool sameEdges(vector<Edge> E);
void printNames();
friend std::ostream& operator<<(std::ostream & out, const Graph & g);
/************************* init, update and reset *************************/
void resetClock();
void resetAllDist();
void resetAllVisited();
void reset(); //resetClock, reset pre`s, reset posts
void clearNodes();
void preAllocate();
void initEmpty(int num_nodes);
void copyNodes(Graph & g);
void copyEdges(Graph & g);
Graph reverse();
vector<Node> nodes();
};
#endif