Merge branch 'master' of https://github.com/feynmansfedora/appcomb-proj

1 files changed, 33 insertions, 0 deletions

diff --git a/final/connectedness/dfs.py b/final/connectedness/dfs.py
new file mode 100644
index 0000000..609ddf6
--- /dev/null
+++ b/final/connectedness/dfs.py
@@ -0,0 +1,33 @@
+import networkx as nx
+import numpy as np
+import time
+
+from matplotlib import pyplot as plt
+
+def is_graph_connected(G):
+    VISITED = []
+    def dfs_connectedness(v):
+        nonlocal VISITED
+        for node in G.adj[v].keys():
+            if node not in VISITED:
+                VISITED.append(node)
+                dfs_connectedness(node)
+        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)
+
+plt.scatter(x, y)
+plt.show()