Verify that given list of nodes of a graph is a correct topological order

Question

I've been given a task to write some code that takes in a list of nodes from a graph, and determines whether they are in correct topological order.

The graph is represented in memory as follows:

typedef struct graph_t* Graph;
typedef struct node_t* Node;

struct node_t {
    int id;
    /*incoming edges*/
    Linked_list incoming;
    /*outgoing edges*/
    Linked_list outgoing;
};

struct graph_t {
    int order;
    int size;
    Node nodes;
};

I omitted the implementation of the linked list for brevity but it is just a standard implementation of a linked list.

I have also been given the following algorithm (pseudocode):

L <- topologically sorted list of nodes
V <- empty list of visited nodes
for each node n in L do
    add n to V
    for each node m reachable from n do
        if m in V then L is not sorted

I do understand the definition of a topological order, but I don't understand how or why this would verify the topological sort.

How is this algorithm correct? Also, given the above representation of the graph, how would the line for each node m reachable from n do be implemented?

Also, is there a better algorithm than the one above to perform this task?

Answer 1

Quoting CLRS:

A topological sort of a dag G = (V,E) is a linear ordering of all its vertices such that if G contains an edge (u,v), then u appears before v in the ordering.

This is what you are actually checking in the innermost for loop. If m is reachable from n, but it is already in V, then it means that you have already visited m before visiting n. Hence L is not topologically sorted.

Answering your next question, you can implement the line

for each node m reachable from n do

using a DFS or BFS. So, on node n, you need to check if there is a directed edge which goes from n to m.