aboutsummaryrefslogtreecommitdiff
path: root/final/connectedness/algorithms.py
diff options
context:
space:
mode:
authorholden watson <holdenew@gmail.com>2019-11-11 21:49:44 -0500
committerholden watson <holdenew@gmail.com>2019-11-11 21:49:44 -0500
commit399fbca52880871a9a927677275ba754d2874c04 (patch)
treef522a29bb464619af1773d600e29ecdbf1b07ad8 /final/connectedness/algorithms.py
parent8c5df53fa24f117311a7a3da4553e0b245ec1b56 (diff)
Added more algorithms
Diffstat (limited to 'final/connectedness/algorithms.py')
-rw-r--r--final/connectedness/algorithms.py44
1 files changed, 44 insertions, 0 deletions
diff --git a/final/connectedness/algorithms.py b/final/connectedness/algorithms.py
new file mode 100644
index 0000000..e50cc5c
--- /dev/null
+++ b/final/connectedness/algorithms.py
@@ -0,0 +1,44 @@
+from dfs import is_graph_connected
+from matplotlib import pyplot as plt
+import networkx as nx
+import numpy as np
+import time
+
+# An O(E*(V+E)) algorithm for finding bridges in a connected graph
+def bridges_1(G):
+ for edge in G.edges:
+ graph = G.copy()
+ graph.remove_edge(*edge)
+ if not is_graph_connected(graph):
+ yield edge
+
+def test():
+ G = nx.random_geometric_graph(200, 0.125)
+ br = list(bridges(G))
+ nx.draw(G, node_size = 20)
+ plt.savefig("graph.png")
+ g2 = G.copy()
+ g2.remove_edge(*br[0])
+ nx.draw(g2, node_size = 20)
+ plt.savefig("graph2.png")
+
+def main():
+ x = np.zeros(50)
+ y = np.zeros(50)
+ for n in range(1, 50):
+ c = 0
+ for _ in range(5):
+ graph = nx.random_geometric_graph(n, 0.25)
+ x[n] = len(graph.edges) * (len(graph.nodes) + len(graph.edges))
+ start = time.time()
+ b = list(bridges(graph))
+ c += time.time() - start
+ c /= 5
+ y[n] = c
+ print(n)
+
+ plt.scatter(x, y)
+ plt.show()
+
+if __name__ == "__main__":
+ main()