Added more algorithms

5 files changed, 64 insertions, 16 deletions

diff --git a/.gitignore b/.gitignore
index aff0aa4..3ca5ed9 100644
--- a/.gitignore
+++ b/.gitignore
@@ -1,4 +1,5 @@
 *.log
 *.pgf # TeX temp files
 *.swp # Vim temp files
-.DS_Store # Mac storage files
\ No newline at end of file
+.DS_Store # Mac storage files
+*.pyc
diff --git a/final/connectedness/algorithms.py b/final/connectedness/algorithms.py
new file mode 100644
index 0000000..e50cc5c
--- /dev/null
+++ b/final/connectedness/algorithms.py
@@ -0,0 +1,44 @@
+from dfs import is_graph_connected
+from matplotlib import pyplot as plt
+import networkx as nx
+import numpy as np
+import time
+
+# An O(E*(V+E)) algorithm for finding bridges in a connected graph
+def bridges_1(G):
+    for edge in G.edges:
+        graph = G.copy()
+        graph.remove_edge(*edge)
+        if not is_graph_connected(graph):
+            yield edge
+
+def test():
+    G = nx.random_geometric_graph(200, 0.125)
+    br = list(bridges(G))
+    nx.draw(G, node_size = 20)
+    plt.savefig("graph.png")
+    g2 = G.copy()
+    g2.remove_edge(*br[0])
+    nx.draw(g2, node_size = 20)
+    plt.savefig("graph2.png")
+
+def main():
+    x = np.zeros(50)
+    y = np.zeros(50)
+    for n in range(1, 50):
+        c = 0
+        for _ in range(5):
+            graph = nx.random_geometric_graph(n, 0.25)
+            x[n] = len(graph.edges) * (len(graph.nodes) + len(graph.edges))
+            start = time.time()
+            b = list(bridges(graph))
+            c += time.time() - start
+        c /= 5
+        y[n] = c
+        print(n)
+
+    plt.scatter(x, y)
+    plt.show()
+
+if __name__ == "__main__":
+    main()
diff --git a/final/connectedness/dfs.py b/final/connectedness/dfs.py
index 609ddf6..00e14ee 100644
--- a/final/connectedness/dfs.py
+++ b/final/connectedness/dfs.py
@@ -15,19 +15,22 @@ def is_graph_connected(G):
         return len(VISITED) == len(G.nodes)
     return dfs_connectedness(0)
 
-x = np.zeros(400)
-y = np.zeros(400)
-for n in range(1, 400):
-    c = 0
-    for _ in range(5):
-        graph = nx.random_geometric_graph(n, 0.125)
-        x[n] = len(graph.nodes) + len(graph.edges)
-        start = time.time()
-        is_graph_connected(graph)
-        c += time.time() - start
-    c /= 5
-    y[n] = c
-    print(n)
+def main():
+    x = np.zeros(400)
+    y = np.zeros(400)
+    for n in range(1, 400):
+        c = 0
+        for _ in range(5):
+            graph = nx.random_geometric_graph(n, 0.125)
+            x[n] = len(graph.nodes) + len(graph.edges)
+            start = time.time()
+            is_graph_connected(graph)
+            c += time.time() - start
+        c /= 5
+        y[n] = c
 
-plt.scatter(x, y)
-plt.show()
+    plt.scatter(x, y)
+    plt.show()
+
+if __name__ == "__main__":
+    main()
diff --git a/final/connectedness/graph.png b/final/connectedness/graph.png
index 8f77862..d251531 100644
--- a/final/connectedness/graph.png
+++ b/final/connectedness/graph.png
diff --git a/final/connectedness/graph2.png b/final/connectedness/graph2.png
new file mode 100644
index 0000000..6db5dfc
--- /dev/null
+++ b/final/connectedness/graph2.png