#include <stack>

std::stack <int> sorted;

enum EdgeClass {TREE, BACK, FORWARD, CROSS, NOCLASS};

void load_graphD(graph *g, bool directed)

{

    initialize_graph(g, directed);

    g->nvertices = 7;

    insert_edge(g, 1, 2, directed);

    insert_edge(g, 1, 3, directed);

    insert_edge(g, 2, 6, directed);

    insert_edge(g, 3, 4, directed);

    insert_edge(g, 3, 5, directed);

    insert_edge(g, 4, 2, directed);

    insert_edge(g, 4, 6, directed);

    insert_edge(g, 5, 4, directed);

    insert_edge(g, 5, 7, directed);

    insert_edge(g, 6, 7, directed);

}

void process_vertex_late(int v)

{

    sorted.push(v);

}

void process_edge(int x, int y)

{

    printf("processed edge (%d %d)\n", x, y);

    EdgeClass edgeClass;

    edgeClass = edge_classification(x, y);

    if (edgeClass == BACK)

    {

        printf("Warning: directed cycle found, not a DAG\n");

    }

}

EdgeClass edge_classification(int x, int y)

{

    if (parent[y] == x) return TREE;

    if (discovered[y] && !processed[y]) return BACK;

    if (processed[y] && (entry_time[y] > entry_time[x])) return FORWARD;

    if (processed[y] && (entry_time[y] < entry_time[x])) return CROSS;

    printf("Warning: unclassified edge (%d, %d)\n", x, y);

    return NOCLASS;

}

void dfs(graph *g, int v)

{

    edgenode *p;

    int y;

    if (finished) return;

    discovered[v] = true;

    dfstime = dfstime + 1;

    entry_time[v] = dfstime;

    process_vertex_early(v);

    p = g->edges[v];

    while(p != NULL) {

        y = p->y;

        if (discovered[y] == false) {

            parent[y] = v;

            process_edge(v, y);

            dfs(g, y);

        }

        else if (!processed[y] || (g->directed))

            process_edge(v, y);

        if (finished) return;

        p = p->next;

    }

    process_vertex_late(v);

    dfstime = dfstime + 1;

    exit_time[v] = dfstime;

    processed[v] = true;

}

void print_stack(std::stack <int> stk)

{

    while (!stk.empty())

    {

        printf("%d ", stk.top());

        stk.pop();

    }

}

void topsort(graph *g)

{

    int i;

    for ( i = 1; i <= g->nvertices; i++)

        if (discovered[i] == false)

            dfs(g, i);

}

 int main(int argc, const char * argv[]) {

    graph *myGraph = (graph *)malloc(sizeof(graph));

    load_graphD(myGraph, true);

    initialize_search(myGraph);

    topsort(myGraph);

    print_stack(sorted);

    return 0;

}