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 +++++++++++++++++++++++++++++++++
final/connectedness/graph.png | Bin 0 -> 132170 bytes
final/connectedness/test_display.py | 8 ++++++++
3 files changed, 41 insertions(+)
create mode 100644 final/connectedness/dfs.py
create mode 100644 final/connectedness/graph.png
create mode 100644 final/connectedness/test_display.py
(limited to 'final/connectedness')
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
Binary files /dev/null and b/final/connectedness/graph.png differ
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
--
cgit