""" topological sort of direct graph 
"""

from Graph import *

from SStack import SStack, StackUnderflow
from SQueue import SQueue, QueueUnderflow

# Generate the DFS sequence of rearchable vertices from v0
def DFS_seq(graph, v0):
    vnum = graph.vertex_num()
    visited = [0]*vnum
    visited[v0] = 1
    DFS_seq = [v0]
    st = SStack()
    st.push((0, graph.out_edges(v0)))
    while not st.is_empty():
        i, edges = st.pop()
        if i < len(edges):
            v, e = edges[i]
            st.push((i+1, edges))
            if visited[v] == 0: # unvisited node
                DFS_seq.append(v)
                visited[v] = 1
                st.push((0, graph.out_edges(v)))
    return DFS_seq

# Genarate span-forest of a graph, recursive definition
def DFS_span_tree(graph):
    vnum = graph.vertex_num()
    span_forest = [None]*(vnum)
    def dfs(graph, v):
        nonlocal span_forest
        for u, w in graph.out_edges(v):
            if span_forest[u] is None:
                span_forest[u] = (v, w)
                dfs(graph, u)

    for v in range(vnum):
        if span_forest[v] is None:
            span_forest[v] = (v, 0)
            dfs(graph, v)
    return span_forest

if __name__ == '__main__':
    gmat1 = [[0,1,1,0,0,0,0,0],
             [1,0,0,1,1,0,0,0],
             [1,0,0,0,0,1,1,0],
             [0,1,0,0,0,0,0,1],
             [0,1,0,0,0,0,0,1],
             [0,0,1,0,0,0,0,0],
             [0,0,1,0,0,0,0,0],
             [0,0,0,1,1,0,0,0]]

    gmat2 = [[0,1,0,1,1,1,0],
             [0,0,1,0,0,0,0],
             [0,0,0,0,0,1,0],
             [0,0,1,0,0,0,0],
             [0,0,0,0,0,0,1],
             [0,0,0,0,0,0,0],
             [0,0,1,0,0,1,0]]

    g1 = GraphA(gmat1, 0)
    dfs1 = DFS_seq(g1, 0)
    print(dfs1)

    g2 = GraphA(gmat2, 0)
    dfs2 = DFS_seq(g2, 0)
    print(dfs2, "\n")
    
    dfs_tree = DFS_span_tree(g1)
    print(dfs_tree)
    dfs_tree = DFS_span_tree(g2)
    print(dfs_tree)