blob: 00e14ee11709dcc2adf15bf0ca2512f8dc4cab2a (
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
|
import networkx as nx
import numpy as np
import time
from matplotlib import pyplot as plt
def is_graph_connected(G):
VISITED = []
def dfs_connectedness(v):
nonlocal VISITED
for node in G.adj[v].keys():
if node not in VISITED:
VISITED.append(node)
dfs_connectedness(node)
return len(VISITED) == len(G.nodes)
return dfs_connectedness(0)
def main():
x = np.zeros(400)
y = np.zeros(400)
for n in range(1, 400):
c = 0
for _ in range(5):
graph = nx.random_geometric_graph(n, 0.125)
x[n] = len(graph.nodes) + len(graph.edges)
start = time.time()
is_graph_connected(graph)
c += time.time() - start
c /= 5
y[n] = c
plt.scatter(x, y)
plt.show()
if __name__ == "__main__":
main()
|
