From 722cb5c48f1b0eefb6b492f81eded5399f30c2e3 Mon Sep 17 00:00:00 2001
From: holden watson <holdenew@gmail.com>
Date: Mon, 11 Nov 2019 20:55:45 -0500
Subject: Added basic connectedness scripts

---
 final/connectedness/dfs.py | 33 +++++++++++++++++++++++++++++++++
 1 file changed, 33 insertions(+)
 create mode 100644 final/connectedness/dfs.py

(limited to 'final/connectedness/dfs.py')

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()
-- 
cgit