Graph Applications in Python - Abhishek Ahuja

"""
Implements functions:
    bfs_visited(ugraph, startnode)
    cc_visited(ugraph)
    largest_cc_size(ugraph)
    compute_resilience(ugraph, attack_order)
"""

def bfs_visited(ugraph, startnode):
    """
    lists the nodes connected to 'startnode' in the
    graph 'ugraph'

    input: undirected graph, in the form of
            adjacency matrix
    output: list of visited nodes
    """
    node_queue = []
    visited = set([startnode])
    node_queue.append(startnode)
    #adding neighbours to queue
    while node_queue != []:
        #removing nodes from queue
        connec = node_queue.pop(0)
        for ne_bour in ugraph[connec]:
            if ne_bour not in visited:
#adds node to 'visited' list if not already present
                visited.add(ne_bour)
                node_queue.append(ne_bour)
    return visited

def cc_visited(ugraph):
    """
    lists all the connected components in an
    undirected graph

    input: undirected graph in the form of
            an adjacency matrix
    output: set of connected components, each in
            the form of a list
    """
    rem_nodes = []
    for dummy_p in ugraph.keys():
        rem_nodes.append(dummy_p)
    connec_comp = []
    while rem_nodes != []:
        rand_node = rem_nodes[0]
        new_comp = bfs_visited(ugraph, rand_node)
        connec_comp.append(new_comp)
        for dummy_node in new_comp:
            rem_nodes.remove(dummy_node)
    return connec_comp

def largest_cc_size(ugraph):
    """
    returns the size of the largest connected
    component in a graph

    input: undirected graph
    output: number

    """
    compos = cc_visited(ugraph)
    compo_size = []
    for dummy_comp in compos:
        compo_size.append(len(dummy_comp))
    compo_size.sort()
    compo_size.reverse()
    #print compo_size
    #print "inside largest comp"
    #print compo_size
    #print len(compo_size)
    #print "quit largest comp"
    if compo_size == []:
        return 0
    else:
        return compo_size[0]

def attack(ugraph, node):
    """
    attacks a particular node in a graph by removing
    the node and all its edges

    input:
    undirected graph, in the form of an adjecency matrix

    output:
    undirected graph, in the form of an adjecency matrix
    with the 'node' and it's edges removed
    """
    del(ugraph[node])
    for dummy_x in ugraph:
        if node in ugraph[dummy_x]:
            ugraph[dummy_x].remove(node)
    return ugraph

def compute_resilience(ugraph, attack_order):
    """
    returns resilience of a graph to a
    sequential attack on its nodes

    input: undirected graph, list of k nodes in
             the order of attack
    output: list of size (k+1) where index 0 contains
            value of largest connected component before
            attack and index k contains size of largest
            connected component after attacking all
            k nodes
    """
    resil = []
    resil.append(largest_cc_size(ugraph))
    for node_now in attack_order:
        #print ugraph
        ugraph = attack(ugraph, node_now)
        resil.append(largest_cc_size(ugraph))
    return resil