/* DepthTopSort: generate depth-first topological ordering

 
Pre:  G is a directed graph with no cycles implemented with a contiguous list
     of vertices and linked adjacency lists.
Post: The function makes a depth-first traversal of G and generates the
      resulting topological order in the array T.
Uses: RecDepthSort performs the recursive depth-first traversal.
 */
void DepthTopSort(Graph *G, Toporder T)
{
    Vertex v;       /* next vertex whose successors are to be ordered       */
    int place;      /* next position in the topological order to be filled  */

    for (v = 0; v < G->n; v++)
        visited[v] = FALSE;
    place = G->n - 1;
    for (v = 0; v < G->n; v++)
        if (!visited[v])
            RecDepthSort(G, v, &place, T);
}
 /* RecDepthSort: perform recursion for DepthTopSort.

 
Pre:  v is a vertex of the graph G and place is the next location in the
     topological order T to be determined (starting from the end of the final
     ordered list).
Post: The procedure puts all the successors of/ v and finally/ v itself
     into the topological order T in depth-first order.
Uses: Global array visited and RecDepthSort recursively.
 */
void RecDepthSort(Graph *G, int v, int *place, Toporder T)
{
    Vertex curvertex;   /* vertex adjacent to v       */
    Edge *curedge;      /* traverses list of vertices adjacent to v   */

    visited[v] = TRUE;
    curedge = G->firstedge[v];  /* Find the first vertex succeeding v.    */

    while (curedge) {
        curvertex = curedge->endpoint;  /* curvertex is adjacent to v.  */
        if (!visited[curvertex])
            RecDepthSort(G, curvertex, place, T);   /* Order the successors of curvertex. */
        curedge = curedge->nextedge;    /* Go on to the next immediate successor of/ v.  */
    }

    T[*place] = v;      /* Put v itself into the topological order.   */
    (*place)--;
}
 /* BreadthTopSort: generate breadth-first topological ordering

 
Pre:  G is a directed graph with no cycles implemented with a contiguous
     list of vertices and linked adjacency lists.
Post: The function makes a breadth-first traversal of G and generates the
      resulting topological order in T.
Uses: Functions for processing queues.
 */
void BreadthTopSort(Graph *G, Toporder T)
{
    int predecessorcount[MAXVERTEX]; /* number of immediate predecessors of each vertex */
    Queue Q;        /* vertices ready to be placed into the order   */
    Vertex v;       /* vertex currently being visited       */
    Vertex succ;    /* one of the immediate successors of v   */
    Edge *curedge;  /* traverses the adjacency list of v  */
    int place;      /* next position in topological order   */

    /* Initialize all the predecessor counts to 0.  */
    for (v = 0; v < G->n; v++)
        predecessorcount[v] = 0;

    /* Increase the predecessor count for each vertex that is a successor.  */
    for (v = 0; v < G->n; v++)
        for (curedge = G->firstedge[v]; curedge; curedge = curedge->nextedge)
            predecessorcount[curedge->endpoint]++;

    CreateQueue(&Q);
    /* Place all vertices with no predecessors into the queue.  */
    for (v = 0; v < G->n; v++)
        if (predecessorcount[v] == 0)
            Append(v, &Q);

    /* Start the breadth-first traversal.   */
    place = -1;
    while (!QueueEmpty(Q)) {
        /* Visit v by placing it into the topological order.  */
        Serve(&v, &Q);
        place++;
        T[place] = v;

        /* Traverse the list of immediate successors of v.    */
        for (curedge = G->firstedge[v]; curedge; curedge = curedge->nextedge) {
        /* Reduce the predecessor count for each immediate successor.   */
            succ = curedge->endpoint;
            predecessorcount[succ]--;
            if (predecessorcount[succ] == 0)
            /* succ has no further predecessors, so it is ready to process.   */
                Append(succ, &Q);
        }
    }
}