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