Find bridges of graph，bridgesgraph,[Python]代码#

Find bridges of graph，bridgesgraph,[Python]代码#

[Python]代码

# In order to represent a spanning tree# we need to create two classes of edges# we'll refer to them as "green" and "red"# for the green and red edges as specified in lecture## So, for example, the graph given in lecture# G = {'a': {'c': 1, 'b': 1}, #      'b': {'a': 1, 'd': 1}, #      'c': {'a': 1, 'd': 1}, #      'd': {'c': 1, 'b': 1, 'e': 1}, #      'e': {'d': 1, 'g': 1, 'f': 1}, #      'f': {'e': 1, 'g': 1},#      'g': {'e': 1, 'f': 1} #      }# would be written as a spanning tree# S = {'a': {'c': 'green', 'b': 'green'}, #      'b': {'a': 'green', 'd': 'red'}, #      'c': {'a': 'green', 'd': 'green'}, #      'd': {'c': 'green', 'b': 'red', 'e': 'green'}, #      'e': {'d': 'green', 'g': 'green', 'f': 'green'}, #      'f': {'e': 'green', 'g': 'red'},#      'g': {'e': 'green', 'f': 'red'} #      }#       def create_rooted_spanning_tree(G, root):    S = {}    # your code here    traversed = {}    open_list = [root]    while (len(open_list)>0):        current = open_list[0]        del open_list[0]        for neighbor in G[current].keys():            if neighbor not in traversed:                traversed[neighbor] = True                (G[current])[neighbor] = 0                (G[neighbor])[current] = 0                make_link(S, current, neighbor, 'green')                open_list.append(neighbor)            else:                if (G[current])[neighbor] == 1:                    make_link(S, current, neighbor, 'red')                (G[current])[neighbor] = 0                (G[neighbor])[current] = 0    return Sdef make_link(G, node1, node2, color):    if node1 not in G:        G[node1] = {}    (G[node1])[node2] = color    if node2 not in G:        G[node2] = {}    (G[node2])[node1] = color    return G# This is just one possible solution# There are other ways to create a # spanning tree, and the grader will# accept any valid result# feel free to edit the test to# match the solution your program producesdef test_create_rooted_spanning_tree():    G = {'a': {'c': 1, 'b': 1},          'b': {'a': 1, 'd': 1},          'c': {'a': 1, 'd': 1},          'd': {'c': 1, 'b': 1, 'e': 1},          'e': {'d': 1, 'g': 1, 'f': 1},          'f': {'e': 1, 'g': 1},         'g': {'e': 1, 'f': 1}          }    S = create_rooted_spanning_tree(G, "a")    assert S == {'a': {'c': 'green', 'b': 'green'},                  'b': {'a': 'green', 'd': 'red'},                  'c': {'a': 'green', 'd': 'green'},                  'd': {'c': 'green', 'b': 'red', 'e': 'green'},                  'e': {'d': 'green', 'g': 'green', 'f': 'green'},                  'f': {'e': 'green', 'g': 'red'},                 'g': {'e': 'green', 'f': 'red'}                  }test_create_rooted_spanning_tree()###########def post_order(S, root):    # return mapping between nodes of S and the post-order value    # of that node    marked = {}    po = {}    dfs_post_order(S, root, marked, po)    return podef dfs_post_order(S, root, marked, po):    marked[root] = 1    for neighbor in S[root].keys():        if neighbor not in marked:            dfs_post_order(S, neighbor, marked, po)    if len(po) == 0:        po[root] = 1    else:        po[root] = max(po.values()) + 1# This is just one possible solution# There are other ways to create a # spanning tree, and the grader will# accept any valid result.# feel free to edit the test to# match the solution your program producesdef test_post_order():    S = {'a': {'c': 'green', 'b': 'green'},          'b': {'a': 'green', 'd': 'red'},          'c': {'a': 'green', 'd': 'green'},          'd': {'c': 'green', 'b': 'red', 'e': 'green'},          'e': {'d': 'green', 'g': 'green', 'f': 'green'},          'f': {'e': 'green', 'g': 'red'},         'g': {'e': 'green', 'f': 'red'}          }    po = post_order(S, 'a')    assert po == {'a':7, 'b':1, 'c':6, 'd':5, 'e':4, 'f':2, 'g':3}test_post_order()##############def number_of_descendants(S, root):    # return mapping between nodes of S and the number of descendants    # of that node    po = post_order(S, root)    num_list = {}    for node in S.keys():        marked = {}        if node not in num_list.keys():            num_list[node] = get_num_of_descendants(S, node, marked, po)    return num_listdef get_num_of_descendants(S, root, marked, po):    marked[root] = 1    number = 1    for neighbor in S[root].keys():        if neighbor not in marked and po[neighbor] < po[root] and (S[neighbor])[root] != 'red':            marked[neighbor] = 1            number = number + get_num_of_descendants(S, neighbor, marked, po)    return numberdef test_number_of_descendants():    S =  {'a': {'c': 'green', 'b': 'green'},           'b': {'a': 'green', 'd': 'red'},           'c': {'a': 'green', 'd': 'green'},           'd': {'c': 'green', 'b': 'red', 'e': 'green'},           'e': {'d': 'green', 'g': 'green', 'f': 'green'},           'f': {'e': 'green', 'g': 'red'},          'g': {'e': 'green', 'f': 'red'}           }    nd = number_of_descendants(S, 'a')    assert nd == {'a':7, 'b':1, 'c':5, 'd':4, 'e':3, 'f':1, 'g':1}test_number_of_descendants()###############def get_all_reachables(S, node, po):    reachables = {}    reachables[node] = po[node]    for neighbor in S[node].keys():        if (S[neighbor])[node] == 'red':            reachables[neighbor] = po[neighbor]        if po[neighbor] < po[node]:            l = get_all_reachables(S, neighbor, po)            for key in l.keys():               if key not in reachables:                   reachables[key] = po[key]    return reachablesdef lowest_post_order(S, root, po):    # return a mapping of the nodes in S    # to the lowest post order value    # below that node    # (and you're allowed to follow 1 red edge)    lowest_po = {}    for node in S.keys():        reachables = get_all_reachables(S, node, po)        lowest_po[node] = min(reachables.values())    return lowest_po    def test_lowest_post_order():    S = {'a': {'c': 'green', 'b': 'green'},          'b': {'a': 'green', 'd': 'red'},          'c': {'a': 'green', 'd': 'green'},          'd': {'c': 'green', 'b': 'red', 'e': 'green'},          'e': {'d': 'green', 'g': 'green', 'f': 'green'},          'f': {'e': 'green', 'g': 'red'},         'g': {'e': 'green', 'f': 'red'}          }    po = post_order(S, 'a')    l = lowest_post_order(S, 'a', po)    assert l == {'a':1, 'b':1, 'c':1, 'd':1, 'e':2, 'f':2, 'g':2}test_lowest_post_order()################def highest_post_order(S, root, po):    # return a mapping of the nodes in S    # to the highest post order value    # below that node    # (and you're allowed to follow 1 red edge)    highest_po = {}    for node in S.keys():        reachables = get_all_reachables(S, node, po)        highest_po[node] = max(reachables.values())    return highest_podef test_highest_post_order():    S = {'a': {'c': 'green', 'b': 'green'},          'b': {'a': 'green', 'd': 'red'},          'c': {'a': 'green', 'd': 'green'},          'd': {'c': 'green', 'b': 'red', 'e': 'green'},          'e': {'d': 'green', 'g': 'green', 'f': 'green'},          'f': {'e': 'green', 'g': 'red'},         'g': {'e': 'green', 'f': 'red'}          }    po = post_order(S, 'a')    h = highest_post_order(S, 'a', po)    assert h == {'a':7, 'b':5, 'c':6, 'd':5, 'e':4, 'f':3, 'g':3}test_highest_post_order()#################def bridge_edges(G, root):    # use the four functions above    # and then determine which edges in G are bridge edges    # return them as a list of tuples ie: [(n1, n2), (n4, n5)]    S = {}    S = create_rooted_spanning_tree(G, root)    po = post_order(S, root)    nd = number_of_descendants(S, root)    lo = lowest_post_order(S, root, po)    hi = highest_post_order(S, root, po)    bridges = []    open_list = [root]    marked = {}    marked[root] = 1    while (len(open_list)>0):        current = open_list[0]        del open_list[0]        for neighbor in S[current].keys():            if neighbor not in marked:                marked[neighbor] = 1                open_list.append(neighbor)                if check_bridge_condition(neighbor, po, nd, lo, hi) == True and (S[current])[neighbor] == 'green':                    bridges.append((current, neighbor))    return bridgesdef check_bridge_condition(node, po, nd, lo, hi):    if hi[node] <= po[node] and lo[node] > po[node] - nd[node]:        return True    else:        return Falsedef test_bridge_edges():    G = {'a': {'c': 1, 'b': 1},          'b': {'a': 1, 'd': 1},          'c': {'a': 1, 'd': 1},          'd': {'c': 1, 'b': 1, 'e': 1},          'e': {'d': 1, 'g': 1, 'f': 1},          'f': {'e': 1, 'g': 1},         'g': {'e': 1, 'f': 1}          }    bridges = bridge_edges(G, 'a')    assert bridges == [('d', 'e')]test_bridge_edges()