Added connectedness algorithms

1 files changed, 41 insertions, 6 deletions

diff --git a/final/connectedness/algorithms.py b/final/connectedness/algorithms.py
index e50cc5c..911ecfd 100644
--- a/final/connectedness/algorithms.py
+++ b/final/connectedness/algorithms.py
@@ -12,9 +12,43 @@ def bridges_1(G):
         if not is_graph_connected(graph):
             yield edge
 
+def bridges_2(G):
+    BRIDGES = []
+    TIME = 0
+    def bridges_2_recursion(v):
+        nonlocal BRIDGES, VISITED, TIME, discoveries, low, parents
+        VISITED.append(v)
+
+        discoveries[v] = TIME
+        low[v] = TIME
+        TIME += 1
+
+        for v2 in G.adj[v]:
+            if v2 not in VISITED:
+                parents[v2] = v
+                bridges_2_recursion(v2)
+
+                low[v] = min(low[v], low[v2])
+                if low[v2] > discoveries[v]:
+                    BRIDGES.append((v, v2))
+            elif parents[v] != v2:
+                low[v] = min(low[v], discoveries[v2])
+    n = len(G.nodes)
+
+    VISITED = []
+
+    discoveries = [float("Inf")] * n
+    low = [float("Inf")] * n
+    parents = [-1] * n
+
+    for v in range(n):
+        if v not in VISITED:
+            bridges_2_recursion(v)
+    return BRIDGES
+
 def test():
     G = nx.random_geometric_graph(200, 0.125)
-    br = list(bridges(G))
+    br = list(bridges_2(G))
     nx.draw(G, node_size = 20)
     plt.savefig("graph.png")
     g2 = G.copy()
@@ -23,21 +57,22 @@ def test():
     plt.savefig("graph2.png")
 
 def main():
-    x = np.zeros(50)
-    y = np.zeros(50)
-    for n in range(1, 50):
+    x = np.zeros(60)
+    y = np.zeros(60)
+    for n in range(1, 60):
         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))
+            x[n] = len(graph.edges)*(len(graph.nodes) + len(graph.edges))
             start = time.time()
-            b = list(bridges(graph))
+            b = list(bridges_1(graph))
             c += time.time() - start
         c /= 5
         y[n] = c
         print(n)
 
     plt.scatter(x, y)
+    plt.savefig("bridges_algorithm_1.png")
     plt.show()
 
 if __name__ == "__main__":