bridges.py

from pprint import pprint as pp
from collections import deque

def find_bridge_bf(nodes, edges, a, b):
    """
    Simple brute-force bridge finding
    For each edge, explore nodes from *a* and try to reach b without using the edge
    If it can't reach the *b*, it was a bridge
    """
    for edge in edges:
        #explore nodes without using edge
        q = deque([a])
        seen = {a}
        while len(q) > 0:
            node = q.pop()
            for connected in nodes[node]:
                if connected not in seen and edge != {node,connected}:
                    seen.add(connected)
                    if connected == b:
                        break
                    q.append(connected)
        if b not in seen:
            return edge

def print_tree(node,lvl=0):
    print('  '*lvl,node)
    for child in node.children:
        print_tree(child,lvl+1)

def find_bridge_tarjan(nodes,edges,a,b):
    """
    Tarjan algoritm from http://en.wikipedia.org/wiki/Bridge_%28graph_theory%29 and https://www.udacity.com/course/viewer#!/c-cs215/l-48723544/m-48729232
    """
    class BFSNode:
        def __init__(self, node, children=None, parent=None, others=None):
            self.node = node
            self.children = children if children else []
            self.parent = parent
            self.others = others if others else [] #other connections

            #scoring
            self.scores = {}

        def __str__(self):
            return "{name} (scores={n},ND=,L=,H=)       parent[{parent}] others[{others}]".format(
                name=self.node,
                n=self.scores,
                parent=self.parent.node if self.parent else None,
                others=','.join(str(n.node) for n in self.others))

        def postorder_traversal(self):
            for child in self.children:
                for x in child.postorder_traversal(): #snif...my yield from is not pypy compatible yet
                    yield x
            yield self

    #build spanning tree
    root = BFSNode(a)

    bfs_nodes = {a:root} #dict of node<->BFSNode
    #bfs_nodes_ordered = [None]*len(nodes) #order nodes by n
    #bfs_nodes_ordered[n] = root

    q = deque((root,))
    seen = {root.node}
    while len(q) > 0:
        node = q.pop()
        for connected in nodes[node.node]:
            if connected not in seen:
                child_node = BFSNode(connected, parent=node)

                #bfs_nodes_ordered[n] = child_node
                bfs_nodes[connected] = child_node
                
                node.children.append(child_node)
                seen.add(connected)
                q.append(child_node)
            elif bfs_nodes[connected] is not node.parent:
                node.others.append(bfs_nodes[connected])

    #postorder numbering and other scoring
    n = 1
    for node in root.postorder_traversal():
        node.scores['n'] = n
        node.scores['ND'] = 1 + sum(node.scores['ND'] for node in node.children) #number of chilren recursively
        n += 1
    for node in root.postorder_traversal():
        L, H = None, None
        n = node.scores['n']
        if node.children+node.others:
            L = min(node.scores.get('L',node.scores['n']) for node in node.children+node.others) 
            H = max(node.scores.get('H',node.scores['n']) for node in node.children+node.others) 
        node.scores['L'] = min(n, L) if L else n
        node.scores['H'] = max(n, H) if H else n

        if node.scores['H'] <= node.scores['n'] and node.scores['L'] > node.scores['n']-node.scores['ND'] and node is not root:
            return root, {node.node, node.parent.node}

import random

def gen_sub_graph(N,start=0, E=3):
    nums = range(start, N+start)
    nodes = {x:[] for x in nums}
    edges = []
    for node in nums:
        to_sample = set(nums) - {node} - set(nodes[node])
        n = E-len(nodes[node])
        if n > 0:
            connected = random.sample(to_sample,n)
            for other_node in connected:
                edges.append({node,other_node})
                nodes[node].append(other_node)
                nodes[other_node].append(node)

    return nodes,edges

def gen_graph(N=10):
    #gen two subgraph
    nodes1, edges1 = gen_sub_graph(N)
    nodes2, edges2 = gen_sub_graph(N,N)
 
    #random nodes for each subgraph
    a,b = random.choice(list(nodes1.keys())), random.choice(list(nodes2.keys()))

    #add bridge
    x,y = random.choice(list(nodes1.keys())), random.choice(list(nodes2.keys()))
    edges = edges1+edges2+[{x,y}]

    nodes = nodes1
    nodes1.update(nodes2)
    nodes[x].append(y)
    nodes[y].append(x)

    return nodes, edges, a, b, {x,y}

def test_bf(n,i):
    for _ in range(n):
        *graph, bridge = gen_graph(N=i)
        sol = find_bridge_bf(*graph)
        assert sol == bridge 

def test_troj(n,i):
    for _ in range(n):
        *graph, bridge = gen_graph(N=i)
        tree, sol = find_bridge_tarjan(*graph)
        assert sol == bridge 

if __name__ == '__main__':
    import timeit
    out = open('perf.csv','w')
    for i in range(10,300,10):
        n = 10
        print('N=',i)
        t1 = timeit.timeit("test_bf({n},{i})".format(n=n, i=i), number=n, setup="from __main__ import test_bf")
        print('bf',t1)
        t2 = timeit.timeit("test_troj({n},{i})".format(n=n, i=i), number=n, setup="from __main__ import test_troj")
        print('troj',t2)
        out.write('{},{},{}\n'.format(i,t1,t2))