andrewcchen · August 29, 2015 14:15 · Feb 12, 2015 · Feb 12, 2015 · Feb 12, 2015 · Feb 12, 2015
diff --git a/graph_triangles.cpp b/graph_triangles.cpp
@@ -14,7 +14,7 @@
 
 using std::unique_ptr;
 
-auto read_graph(char* filename) {
+auto read_graph(std::string filename) {
     auto graph = std::make_unique<
             std::unordered_map<int, unique_ptr<std::unordered_set<int>>>>();
 

diff --git a/graph_triangles.cpp b/graph_triangles.cpp
@@ -15,9 +15,8 @@
 using std::unique_ptr;
 
 auto read_graph(char* filename) {
-    unique_ptr<std::unordered_map<int, unique_ptr<std::unordered_set<int>>>>
-            graph(new std::unordered_map<
-                    int, unique_ptr<std::unordered_set<int>>>());
+    auto graph = std::make_unique<
+            std::unordered_map<int, unique_ptr<std::unordered_set<int>>>>();
 
     std::ifstream infile(filename);
     std::string line;
@@ -44,7 +43,8 @@ auto read_graph(char* filename) {
     return graph;
 }
 
-int count_triangles(unique_ptr<std::unordered_map<int, unique_ptr<std::unordered_set<int>>>> graph) {
+int count_triangles(unique_ptr<
+        std::unordered_map<int, unique_ptr<std::unordered_set<int>>>> graph) {
     int count = 0;
     for (auto iter = graph->begin(); iter != graph->end(); iter++) {
         std::vector<int> neighbours(iter->second->begin(), iter->second->end());

diff --git a/graph_triangles.cpp b/graph_triangles.cpp
@@ -14,8 +14,7 @@
 
 using std::unique_ptr;
 
-unique_ptr<std::unordered_map<int, unique_ptr<std::unordered_set<int>>>>
-        read_graph(char* filename) {
+auto read_graph(char* filename) {
     unique_ptr<std::unordered_map<int, unique_ptr<std::unordered_set<int>>>>
             graph(new std::unordered_map<
                     int, unique_ptr<std::unordered_set<int>>>());

diff --git a/graph_triangles.cpp b/graph_triangles.cpp
@@ -1,9 +1,10 @@
 #include <ctime>
 #include <cassert>
 
+#include <string>
+
 #include <fstream>
 #include <sstream>
-#include <string>
 
 #include <memory>
 

diff --git a/graph_triangles.cpp b/graph_triangles.cpp
@@ -0,0 +1,82 @@
+#include <ctime>
+#include <cassert>
+
+#include <fstream>
+#include <sstream>
+#include <string>
+
+#include <memory>
+
+#include <vector>
+#include <unordered_map>
+#include <unordered_set>
+
+using std::unique_ptr;
+
+unique_ptr<std::unordered_map<int, unique_ptr<std::unordered_set<int>>>>
+        read_graph(char* filename) {
+    unique_ptr<std::unordered_map<int, unique_ptr<std::unordered_set<int>>>>
+            graph(new std::unordered_map<
+                    int, unique_ptr<std::unordered_set<int>>>());
+
+    std::ifstream infile(filename);
+    std::string line;
+    while (std::getline(infile, line)) {
+        if (line[0] != '#') {
+            std::istringstream iss(line);
+            int a, b;
+            iss >> a >> b;
+            if (graph->count(a) == 0) {
+                graph->insert(std::make_pair(a, 
+                        unique_ptr<std::unordered_set<int>>(
+                        new std::unordered_set<int>())));
+            }
+            graph->at(a)->insert(b);
+            if (graph->count(b) == 0) {
+                graph->insert(std::make_pair(b, 
+                        unique_ptr<std::unordered_set<int>>(
+                        new std::unordered_set<int>())));
+            }
+            graph->at(b)->insert(a);
+        }
+    }
+
+    return graph;
+}
+
+int count_triangles(unique_ptr<std::unordered_map<int, unique_ptr<std::unordered_set<int>>>> graph) {
+    int count = 0;
+    for (auto iter = graph->begin(); iter != graph->end(); iter++) {
+        std::vector<int> neighbours(iter->second->begin(), iter->second->end());
+        for (auto i = neighbours.begin(); i != neighbours.end(); i++) {
+            for (auto j = i + 1; j != neighbours.end(); j++) {
+                if(graph->at(*i)->count(*j) != 0) { // contains edge (i, j)
+                    count++;
+                }
+            }
+        }
+    }
+    return count / 3;
+}
+
+int main(int args, char* argv[]) {
+    assert(args == 2);
+
+    auto graph = read_graph(argv[1]);
+
+    printf("Number of vetices: %d\n", graph->size());
+    int edge_count = 0;
+    for (auto iter = graph->begin(); iter != graph->end(); iter++) {
+        edge_count += iter->second->size();
+    }
+    edge_count /= 2;
+    printf("Number of edges: %d\n", edge_count);
+
+    int start_time = clock();
+    int count = count_triangles(std::move(graph));
+    int end_time = clock();
+
+    printf("Number of triangles: %d\n", count);
+    printf("Time elapsed: %f\n",
+           (end_time - start_time) / (double) CLOCKS_PER_SEC);
+}