from graph import *
from dfs import dfs, dfs_all, ignore

visit = 0
def postorder(v):
    global visit
    v.disc = visit
    visit += 1

def transpose(G):
    T = Graph()
    for w in G:
        L = [(v.getDiscovery(), v.getId()) for v in w.getAdj()]
        L.sort(reverse=True)    # by postorder numbers
        for e in L:
            T.addEdge(e[1], w.getId())
    return T

def printMe(v):
    print v.id,     # note comma!

def scComp(G):
    dfs_all(G, ignore, postorder)
    L = [(v.getDiscovery(), v.getId()) for v in G]
    L.sort(reverse=True)        # by postorder numbers
    T = transpose(G)
    for n in L:
        v = T.getVertex(n[1])
        if v.getColor() == 'white':
            dfs(T, v, printMe, fresh=False)
            print

def build():
    G = Graph()
    G.addEdge('A', 'B')
    G.addEdge('B', 'C')
    G.addEdge('C', 'C')
    G.addEdge('B', 'E')
    G.addEdge('E', 'A')
    G.addEdge('D', 'B')
    G.addEdge('C', 'F')
    G.addEdge('E', 'D')
    G.addEdge('D', 'G')
    G.addEdge('G', 'E')
    G.addEdge('F', 'H')
    G.addEdge('I', 'F')
    G.addEdge('H', 'I')
    return G
