1 files changed, 44 insertions, 0 deletions
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()