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