import random
from collections import deque
from bridges import analyze


def _components(nodes, edges):
    adj = {n: [] for n in nodes}
    for e in edges:
        els = tuple(e)
        if len(els) < 2:
            continue
        a, b = els
        adj[a].append(b); adj[b].append(a)
    seen = set(); comp = 0
    for n in nodes:
        if n in seen: continue
        comp += 1
        dq = deque([n]); seen.add(n)
        while dq:
            u = dq.popleft()
            for w in adj[u]:
                if w not in seen:
                    seen.add(w); dq.append(w)
    return comp


def brute_bridges(graph):
    from bridges import _normalize
    nodes, adj_ids, edge_list = _normalize(graph)
    adj = {n: [] for n in nodes}
    for e in edge_list:
        els = tuple(e)
        if len(els) < 2: continue
        a, b = els
        adj[a].append(b); adj[b].append(a)
    res = set()
    for e in edge_list:
        els = tuple(e)
        if len(els) < 2: continue
        a, b = els
        if edge_list.count(e) > 1:
            continue
        remaining = [x for x in edge_list if x != e]
        if _components(nodes, remaining) > _components(nodes, edge_list):
            res.add(e)
    return res


def brute_art(graph):
    from bridges import _normalize
    nodes, adj_ids, edge_list = _normalize(graph)
    adj = {n: [] for n in nodes}
    for e in edge_list:
        els = tuple(e)
        if len(els) < 2: continue
        a, b = els
        adj[a].append(b); adj[b].append(a)
    res = set()
    for node in nodes:
        rest = [x for x in nodes if x != node]
        if not rest: continue
        def connected_original(x, y):
            seen = set([x]); dq = deque([x])
            while dq:
                u = dq.popleft()
                if u == y: return True
                for w in adj[u]:
                    if w not in seen:
                        seen.add(w); dq.append(w)
            return False
        is_art = False
        for x in rest:
            for y in rest:
                if x >= y: continue
                if not connected_original(x, y): continue
                seen2 = set([node, x]); dq = deque([x]); ok = False
                while dq:
                    u = dq.popleft()
                    if u == y: ok = True; break
                    for w in adj[u]:
                        if w not in seen2:
                            seen2.add(w); dq.append(w)
                if not ok:
                    is_art = True; break
            if is_art: break
        if is_art:
            res.add(node)
    return res


def test_random_small():
    rng = random.Random(42)
    for _ in range(3000):
        n = rng.randint(1, 7)
        nodes = list(range(n))
        adj = {i: [] for i in nodes}
        m = rng.randint(0, n + 3)
        for _ in range(m):
            u = rng.randrange(n); v = rng.randrange(n)
            adj[u].append(v); adj[v].append(u)
        b, a = analyze(adj)
        assert b == brute_bridges(adj), (adj, b, brute_bridges(adj))
        assert a == brute_art(adj), (adj, a, brute_art(adj))


def test_path():
    g = {i: [i-1, i+1] for i in range(5)}
    for i in g: g[i] = [x for x in g[i] if 0 <= x < 5]
    b, a = analyze(g)
    assert len(b) == 4 and a == {1,2,3}


def test_cycle():
    g = {0:[1,2],1:[0,2],2:[0,1]}
    b,a = analyze(g)
    assert b == set() and a == set()


def test_empty():
    assert analyze({}) == (set(), set())


def test_single():
    assert analyze({0: []}) == (set(), set())


def test_parallel_edges():
    g = {0: [1, 1], 1: [0, 0]}
    b, a = analyze(g)
    assert b == set() and a == set()


if __name__ == '__main__':
    for name in ['test_random_small','test_path','test_cycle','test_empty','test_single','test_parallel_edges']:
        globals()[name]()
        print('PASS', name)
    print('ALL OK')