diff options
| -rw-r--r-- | final/connectedness.tex | 58 | ||||
| -rw-r--r-- | final/connectedness/algorithms.py | 47 | ||||
| -rw-r--r-- | final/connectedness/bridges_algorithm_1.png | bin | 0 -> 13694 bytes | |||
| -rw-r--r-- | final/connectedness/bridges_algorithm_2.png | bin | 0 -> 21081 bytes | |||
| -rw-r--r-- | final/final.pdf | bin | 78363 -> 132097 bytes | |||
| -rw-r--r-- | final/final.tex | 2 |
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 Binary files differnew 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 Binary files differnew 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 Binary files differindex 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 |
