m-chrzan.xyz
aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorMarcin Chrzanowski <marcin.j.chrzanowski@gmail.com>2017-01-05 13:17:43 -0500
committerMarcin Chrzanowski <marcin.j.chrzanowski@gmail.com>2017-01-05 13:17:43 -0500
commitc88e16d8be7457fd7211c31a5d91aa521fa829a1 (patch)
tree1eecd4f6c185c6060bcb46f1db33554fec24215e /src
parent69be31ac880aa558f0cfe1313a999d85278e03f1 (diff)
parent1eae1a29340986fa5b8fca99bd797806891a511f (diff)
Merge branch 'optim'
Diffstat (limited to 'src')
-rw-r--r--src/graph.h12
-rw-r--r--src/parse.h1
2 files changed, 11 insertions, 2 deletions
diff --git a/src/graph.h b/src/graph.h
index 0f4d7ee..47dce16 100644
--- a/src/graph.h
+++ b/src/graph.h
@@ -1,6 +1,7 @@
#ifndef GRAPH_H
#define GRAPH_H
+#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <vector>
@@ -12,6 +13,7 @@ public:
void add_vertex(int vertex) {
if (vertices_.find(vertex) == vertices_.end()) {
vertices_.insert(vertex);
+ orderable_vertices_.push_back(vertex);
graph_[vertex] = std::vector<int>();
}
}
@@ -23,8 +25,12 @@ public:
has_out_edges_.insert(from);
}
- const std::unordered_set<int> & get_vertices() const {
- return vertices_;
+ void sort_vertices() {
+ std::sort(orderable_vertices_.begin(), orderable_vertices_.end());
+ }
+
+ const std::vector<int> & get_vertices() const {
+ return orderable_vertices_;
}
const std::vector<int> & get_neighbors(int vertex) const {
@@ -34,8 +40,10 @@ public:
bool has_out_edges(int vertex) const {
return has_out_edges_.count(vertex) > 0;
}
+
private:
std::unordered_set<int> vertices_;
+ std::vector<int> orderable_vertices_;
std::unordered_map<int, std::vector<int>> graph_;
std::unordered_set<int> has_out_edges_;
};
diff --git a/src/parse.h b/src/parse.h
index cb6e3c6..1d37083 100644
--- a/src/parse.h
+++ b/src/parse.h
@@ -14,6 +14,7 @@ public:
while (std::getline(input_file_, edge)) {
parse_edge_(edge);
}
+ graph_.sort_vertices();
}
const Graph & get_graph() {