blob: e50cc5cee7d5512dfed73e0407a9e3314b6c7ba8 (
plain)
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
|
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()
|
