Algorithms‎ > ‎Graph‎ > ‎

### Topological Sorting

 #include std::stack 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 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; }