diff options
author | Marcin Chrzanowski <marcin.j.chrzanowski@gmail.com> | 2017-01-06 15:57:28 -0500 |
---|---|---|
committer | Marcin Chrzanowski <marcin.j.chrzanowski@gmail.com> | 2017-01-06 15:57:28 -0500 |
commit | ed0ac6791435c36e8374b218454ebfa7485f0845 (patch) | |
tree | 4b0b48afa48f9e09ef9ab1f9ba27f68f9f118840 /src/parse.h | |
parent | dc88e19199f056d6f2e17c481737a71fcab70398 (diff) |
Optimalize by using vectors over maps and sets
- Can iterate over vertices with for (int v = 0; v < number_vertices;
v++) loop
- This required internally remapping the vertices from their actual
names to 0, 1, ..., number_vertices - 1.
- Use Graph::get_real_vertex(vertex) to get original value
Diffstat (limited to 'src/parse.h')
-rw-r--r-- | src/parse.h | 31 |
1 files changed, 26 insertions, 5 deletions
diff --git a/src/parse.h b/src/parse.h index 31fa7c6..095232a 100644 --- a/src/parse.h +++ b/src/parse.h @@ -11,10 +11,10 @@ class Parser { public: Parser(std::string filename) : graph_(), input_file_(filename) { std::string edge; - while (std::getline(input_file_, edge)) { - parse_edge_(edge); - } - graph_.sort_vertices(); + read_file_(); + add_vertices_(); + graph_.done_with_vertices(); + add_edges_(); } const Graph& get_graph() { @@ -23,6 +23,14 @@ public: private: Graph graph_; std::ifstream input_file_; + std::vector<std::pair<int, int>> edges_; + + void read_file_() { + std::string edge; + while (std::getline(input_file_, edge)) { + parse_edge_(edge); + } + } void parse_edge_(std::string edge) { std::stringstream sstream(edge); @@ -30,7 +38,20 @@ private: int from, to; sstream >> from >> to; - graph_.add_edge(from, to); + edges_.push_back(std::pair<int, int>(from, to)); + } + + void add_vertices_() { + for (auto edge : edges_) { + graph_.add_vertex(edge.first); + graph_.add_vertex(edge.second); + } + } + + void add_edges_() { + for (auto edge : edges_) { + graph_.add_edge(edge.first, edge.second); + } } }; |