SA403_final_fall_2017.sagews

def DFS_Visit(g, i, color):
    # print for strongly connected components
    print " " + str(i)
    # color vertex red
    color[i] = 1;
    for j in g.neighbors_out(i):
        if color[j] == 0:
            color = DFS_Visit(g, j, color)
    # we are finished visiting this vertex
    #print "vertex " + str(i) + " is colored blue."
    color[i] = 2
    return color
# end def DFS_Visit


def DFS_finish(g, i, cur_time, fin, color):
    #print "vertex " + str(i) + " start time = " + str(cur_time)
    # color vertex red
    #print "vertex " + str(i) + " is colored red."
    color[i] = 1;
    for j in g.neighbors_out(i):
        if color[j] == 0:
            # increment the cur_time to the next time step
            (cur_time, fin, color) = DFS_finish(g, j, cur_time + 1, fin, color)
    
    # we are finished visiting this vertex
    #print "vertex " + str(i) + " is colored blue."
    color[i] = 2
    #print "vertex " + str(i) + " finish time = " + str(cur_time)
    fin[i] = cur_time;
    # return the data structures
    return (cur_time + 1, fin, color)
#end def DFS_finish

# generate a random directed graph
n = 20; p = .1
g = digraphs.RandomDirectedGNP(n, p, false);
g.show()

# show the strongly connected components using built-in functions
for scc in g.strongly_connected_components_subgraphs():
    scc.show()

# initialize all variables having to do with implementation
# of StronglyConnectedComponents
# initialize all beginning variables
color = [0]*n
fin = [0]*n
cur_time = 0

# main loop of the depth first search to calculate finishing times
for i in range(0, n):
    if color[i] == 0:
        (cur_time, fin, color) = DFS_finish(g, i, cur_time, fin, color)

# get the indices of the sorted list
s_fin = [i[0] for i in sorted(enumerate(fin), key=lambda x:x[1])]

# reverse the graph
g_rev = g.reverse();
# reinitialize the color array to restart your DFS
color = [0]*n
# iterate over the list in reverse
for i in range(n-1,-1,-1):
    if color[s_fin[i]] == 0:
        print "strongly connected component:"
        color = DFS_Visit(g_rev, s_fin[i], color)

# helper code to help sort lists
# myList = [1, 2, 3, 100, 5]
# L = [i[0] for i in sorted(enumerate(myList), key=lambda x:x[1])]
# L
#for i in range(4,-1,-1):  iterate the list in reverse
#     myList[L[i]]

strongly connected component: 16 strongly connected component: 18 strongly connected component: 14 strongly connected component: 13 strongly connected component: 19 strongly connected component: 7 strongly connected component: 0 8 9 15 10 2 1 4 17 5 11 3 6 strongly connected component: 12