Added connectedness algorithms

6 files changed, 101 insertions, 6 deletions

diff --git a/final/connectedness.tex b/final/connectedness.tex
new file mode 100644
index 0000000..18a382a
--- /dev/null
+++ b/final/connectedness.tex
@@ -0,0 +1,58 @@
+A graph is connected if there exists a path between any pair of vertices.
+Beearliest is a simple algorithm that uses a depth-first search to determine whether a given graph is connected, using Python3 and the NetworkX library.
+
+{\tt \obeylines
+    import networkx as nx
+    
+    def is\_graph\_connected(G):
+    \leavevmode\hskip .25in     VISITED = []
+    \leavevmode\hskip .25in     def dfs\_connectedness(v):
+    \leavevmode\hskip .50in     nonlocal VISITED
+    \leavevmode\hskip .50in     for node in G.adj[v].keys():
+    \leavevmode\hskip .75in     if node not in VISITED:
+    \leavevmode\hskip 1.00in    VISITED.append(node)
+    \leavevmode\hskip 1.00in    dfs\_connectedness(node)
+    \leavevmode\hskip .50in     return len(VISITED) == len(G.nodes)
+    \leavevmode\hskip .25in     return dfs\_connectedness(0)
+}
+
+This algorithm compiles a list of the visited nodes of the graph G, and then determines if that list contains every node after the search is complete.
+The search can start at an arbitrary node (here, it chooses the node labelled 0). The algorithm has a time complexity of $O(V+E)$, where a given graph G has V vertices and E edges.
+
+This same algorithm can be used to create an algorithm of complexity $O(E\cdot(V+E))$ to find all bridges of a connected graph (i.e. all edges which, when removed, would result in the graph becoming unconnected).
+The algorithm simply iterates through each edge of the original graph, removing it and then determining its connectedness using the method above.
+This quadratic algorithm is, however, not the most efficient algorithm for locating bridges. An $O(V+E)$ algorithm can be developed as shown below:
+
+{\tt \obeylines
+    def bridges\_2(G):
+    \leavevmode\hskip .25in BRIDGES = []
+    \leavevmode\hskip .25in tick = 0
+    \leavevmode\hskip .25in def bridges\_2\_recursion(v):
+    \leavevmode\hskip .50in nonlocal BRIDGES, VISITED, tick, discoveries, earliest, parents
+    \leavevmode\hskip .50in VISITED.append(v)
+    \leavevmode\hskip .50in discoveries[v] = tick
+    \leavevmode\hskip .50in earliest[v] = tick
+    \leavevmode\hskip .50in tick += 1
+    \leavevmode\hskip .50in for v2 in G.adj[v]:
+    \leavevmode\hskip .75in if v2 not in VISITED:
+    \leavevmode\hskip 1.00in parents[v2] = v
+    \leavevmode\hskip 1.00in bridges\_2\_recursion(v2)
+    \leavevmode\hskip 1.00in earliest[v] = min(earliest[v], earliest[v2])
+    \leavevmode\hskip 1.00in if earliest[v2] > discoveries[v]:
+    \leavevmode\hskip 1.25in BRIDGES.append((v, v2))
+    \leavevmode\hskip .75in elif parents[v] != v2:
+    \leavevmode\hskip 1.00in earliest[v] = min(earliest[v], discoveries[v2])
+    \leavevmode\hskip .25in n = len(G.nodes)
+    \leavevmode\hskip .25in VISITED = []
+    \leavevmode\hskip .25in discoveries = [float("Inf")] * n
+    \leavevmode\hskip .25in earliest = [float("Inf")] * n
+    \leavevmode\hskip .25in parents = [-1] * n
+    \leavevmode\hskip .25in for v in range(n):
+    \leavevmode\hskip .50in if v not in VISITED:
+    \leavevmode\hskip .75in bridges\_2\_recursion(v)
+    \leavevmode\hskip .25in return BRIDGES
+}
+
+The diagram shown below plots the time taken to calculate the number of bridges on the y-axis, with the value of V+E on the x-axis.
+
+\pdfximage{connectedness/bridges_algorithm_2.png} \pdfrefximage\pdflastximage
\ No newline at end of file
diff --git a/final/connectedness/algorithms.py b/final/connectedness/algorithms.py
index e50cc5c..911ecfd 100644
--- a/final/connectedness/algorithms.py
+++ b/final/connectedness/algorithms.py
@@ -12,9 +12,43 @@ def bridges_1(G):
         if not is_graph_connected(graph):
             yield edge
 
+def bridges_2(G):
+    BRIDGES = []
+    TIME = 0
+    def bridges_2_recursion(v):
+        nonlocal BRIDGES, VISITED, TIME, discoveries, low, parents
+        VISITED.append(v)
+
+        discoveries[v] = TIME
+        low[v] = TIME
+        TIME += 1
+
+        for v2 in G.adj[v]:
+            if v2 not in VISITED:
+                parents[v2] = v
+                bridges_2_recursion(v2)
+
+                low[v] = min(low[v], low[v2])
+                if low[v2] > discoveries[v]:
+                    BRIDGES.append((v, v2))
+            elif parents[v] != v2:
+                low[v] = min(low[v], discoveries[v2])
+    n = len(G.nodes)
+
+    VISITED = []
+
+    discoveries = [float("Inf")] * n
+    low = [float("Inf")] * n
+    parents = [-1] * n
+
+    for v in range(n):
+        if v not in VISITED:
+            bridges_2_recursion(v)
+    return BRIDGES
+
 def test():
     G = nx.random_geometric_graph(200, 0.125)
-    br = list(bridges(G))
+    br = list(bridges_2(G))
     nx.draw(G, node_size = 20)
     plt.savefig("graph.png")
     g2 = G.copy()
@@ -23,21 +57,22 @@ def test():
     plt.savefig("graph2.png")
 
 def main():
-    x = np.zeros(50)
-    y = np.zeros(50)
-    for n in range(1, 50):
+    x = np.zeros(60)
+    y = np.zeros(60)
+    for n in range(1, 60):
         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))
+            x[n] = len(graph.edges)*(len(graph.nodes) + len(graph.edges))
             start = time.time()
-            b = list(bridges(graph))
+            b = list(bridges_1(graph))
             c += time.time() - start
         c /= 5
         y[n] = c
         print(n)
 
     plt.scatter(x, y)
+    plt.savefig("bridges_algorithm_1.png")
     plt.show()
 
 if __name__ == "__main__":
diff --git a/final/connectedness/bridges_algorithm_1.png b/final/connectedness/bridges_algorithm_1.png
new file mode 100644
index 0000000..1435702
--- /dev/null
+++ b/final/connectedness/bridges_algorithm_1.png
diff --git a/final/connectedness/bridges_algorithm_2.png b/final/connectedness/bridges_algorithm_2.png
new file mode 100644
index 0000000..3c8354e
--- /dev/null
+++ b/final/connectedness/bridges_algorithm_2.png
diff --git a/final/final.pdf b/final/final.pdf
index 707ee6e..2be7a9e 100644
--- a/final/final.pdf
+++ b/final/final.pdf
diff --git a/final/final.tex b/final/final.tex
index 1c706f9..7c9df8a 100644
--- a/final/final.tex
+++ b/final/final.tex
@@ -5,6 +5,8 @@
 
 \include The RSA Algorithm:rsa
 
+\include Algorithms for Graph Connectedness and Bridges:connectedness
+
 \vfil\eject\include Appendix:appendix
 
 \bye