@@ -0,0 +1,2818 @@
+%22%22%22%0AAlgorithmic Thinking: Project 2%0AConnected Components and Graph Resilience%0A%0AThis code implements an efficient breadth-%0Afirst search algorithm for determining%0Aconnected components in a graph as well%0Aas the graph's resilience to removing nodes.%0A%0AAuthor: Weikang Sun%0ADate: 6/23/15%0A%0ACodeSkulptor source:%0Ahttp://www.codeskulptor.org/#user40_7TXMr52VHl_3.py%0A%22%22%22%0A%0A# sample graphs for module 2%0Aimport alg_module2_graphs as alg_graphs%0A# Queue class from PoC%0Aimport poc_queue%0A%0A%0Adef bfs_visited(ugraph, start_node):%0A    %22%22%22%0A    Input: undirected graph dictionary and %0A    source node start_node%0A    %0A    Output: Set of all nodes visited by algorithm%0A    %22%22%22%0A    %0A    # error check for start_node in ugraph%0A    if not ugraph.has_key(start_node):%0A        return set(%5B%5D)%0A    %0A    node_queue = poc_queue.Queue()%0A    visited = set(%5Bstart_node%5D)%0A    %0A    node_queue.enqueue(start_node)%0A    %0A    while len(node_queue) %3E 0:%0A        active_node = node_queue.dequeue()%0A        %0A        if ugraph.has_key(active_node):        %0A            for neighbor in ugraph%5Bactive_node%5D:%0A                if neighbor not in visited and ugraph.has_key(neighbor):%0A                    visited.add(neighbor)%0A                    node_queue.enqueue(neighbor)%0A    %0A    return visited%0A%0A%0Adef cc_visited(ugraph):%0A    %22%22%22%0A    Input: undirected graph dictionary%0A    %0A    Output: list of sets of connected components%0A    %22%22%22%0A    %0A    remaining_nodes = ugraph.keys()%0A    connected_comp = %5B%5D%0A    %0A    while remaining_nodes != %5B%5D:%0A        active_node = remaining_nodes.pop()%0A        set_visited = bfs_visited(ugraph, active_node)%0A        connected_comp.append(set_visited)%0A        %0A        for node in set_visited:%0A            if node in remaining_nodes:%0A                remaining_nodes.remove(node)%0A    %0A    return connected_comp%0A    %0A%0Adef largest_cc_size(ugraph):%0A    %22%22%22%0A    Input: undirected graph dictionary%0A    %0A    Output: integer value of the largest%0A    connected component in this graph%0A    %22%22%22%0A    %0A    connected_comp = cc_visited(ugraph)%0A    max_length = 0%0A    %0A    # debug purposes%0A    # print connected_comp%0A    %0A    for set_cc in connected_comp:%0A        max_length = max(max_length, len(set_cc))%0A    %0A    return max_length%0A%0A%0Adef compute_resilience(ugraph, attack_order):%0A    %22%22%22%0A    Input: undirected graph dictionary and%0A    list of order of nodes to be removed%0A    %0A    Output: list of the largest connected%0A    component in graph after removing k'th%0A    node given in attack_order%0A    %22%22%22%0A    %0A    resilience = %5Blargest_cc_size(ugraph)%5D%0A    %0A    for attack_node in attack_order:%0A        if ugraph.has_key(attack_node):%0A            ugraph.pop(attack_node)%0A        %0A        resilience.append(largest_cc_size(ugraph))%0A    %0A    return resilience%0A%0A    %0A    %0A# debug tests    %0A#ugraph = alg_graphs.GRAPH9%0A#print compute_resilience(ugraph, ugraph.keys())%0A

Create 2p-connected-components.py