1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
|
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 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_2(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(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))
start = time.time()
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__":
main()
|
