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()