-
Notifications
You must be signed in to change notification settings - Fork 0
/
graph.h
59 lines (44 loc) · 1.55 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
#ifndef GRAPH_H_
#define GRAPH_H_
#include <string>
#include <vector>
using std::vector;
using std::string;
// In this graph, nodes are integers in 0..num_nodes-1, and arcs are also
// integers in 0..num_arcs-1.
// Thus, when you AddArc(4, 128), you implicitly declare the existence of
// at least 129 nodes (0..128).
class Graph {
public:
// Return the arc index, which will be the number of times AddArc()
// has been called before.
int AddArc(int from, int to);
// Optional: nodes are automatically added upon AddArc().
void AddNode(int node);
int NumNodes() const { return outgoing_arcs_.size(); }
int NumArcs() const { return tail_.size(); }
// Gets the tail ("from") and head ("to") of an arc.
int Tail(int arc) const { return tail_[arc]; }
int Head(int arc) const { return head_[arc]; }
bool IsNode(std::pair<double, double> arc, int index, int size);
// Returns a list of all the arc indices whose Tail is "from".
const vector<int> &OutgoingArcs(int from) const {
return outgoing_arcs_[from];
}
const vector<int> &ArcsGoingTo(int from) const {
return incoming_arcs_[from];
}
// Returns a list of all the arc indices whose Head is "to".
const vector<int> &IncomingArcs(int to) const {
return incoming_arcs_[to];
}
const vector<int> &ArcsComingFrom(int to) const {
return outgoing_arcs_[to];
}
vector<int> head_;
private:
vector <vector<int>> outgoing_arcs_;
vector <vector<int>> incoming_arcs_;
vector<int> tail_;
};
#endif // GRAPH_H_