Added basic connectedness scripts

5 files changed, 42 insertions, 0 deletions

diff --git a/.DS_Store b/.DS_Store
new file mode 100644
index 0000000..b85f30a
--- /dev/null
+++ b/.DS_Store
diff --git a/.gitignore b/.gitignore
index 92c4cf1..aff0aa4 100644
--- a/.gitignore
+++ b/.gitignore
@@ -1,3 +1,4 @@
 *.log
 *.pgf # TeX temp files
 *.swp # Vim temp files
+.DS_Store # Mac storage files
\ No newline at end of file
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()
diff --git a/final/connectedness/graph.png b/final/connectedness/graph.png
new file mode 100644
index 0000000..8f77862
--- /dev/null
+++ b/final/connectedness/graph.png
diff --git a/final/connectedness/test_display.py b/final/connectedness/test_display.py
new file mode 100644
index 0000000..3b45d59
--- /dev/null
+++ b/final/connectedness/test_display.py
@@ -0,0 +1,8 @@
+from matplotlib import pyplot as plt
+import networkx as nx
+
+G = nx.random_geometric_graph(200, 0.125)
+
+nx.draw(G, node_size = 20)
+plt.savefig("graph.png")
+plt.show()
\ No newline at end of file