From 722cb5c48f1b0eefb6b492f81eded5399f30c2e3 Mon Sep 17 00:00:00 2001 From: holden watson Date: Mon, 11 Nov 2019 20:55:45 -0500 Subject: Added basic connectedness scripts --- .DS_Store | Bin 0 -> 6148 bytes .gitignore | 1 + final/connectedness/dfs.py | 33 +++++++++++++++++++++++++++++++++ final/connectedness/graph.png | Bin 0 -> 132170 bytes final/connectedness/test_display.py | 8 ++++++++ 5 files changed, 42 insertions(+) create mode 100644 .DS_Store create mode 100644 final/connectedness/dfs.py create mode 100644 final/connectedness/graph.png create mode 100644 final/connectedness/test_display.py diff --git a/.DS_Store b/.DS_Store new file mode 100644 index 0000000..b85f30a Binary files /dev/null and b/.DS_Store differ 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 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