Edge direction in a dependency graph for topological sort?

Question

Wikipedia explains a dependency graph in a very intuitive way (IMO), citing that an edge goes from a => b when a depends on b. In other words, we can find any given node's direct dependencies (if any) immediately by looking at its neighbors, available in its adjacency list.

This seems to be a sensible way to realize dependencies; it allows us to perform topological sort basically as easily as doing a Depth-First-Traversal (DFS from every node in the graph). If the nodes represent "tasks", then we can execute/visit a task only when all of its transitive dependencies have been executed/visited. Leaf nodes are the first to be visited, and so on.

The Wikipedia page for topological sorting explains the definition as:

In computer science, a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering.

This is the opposite of what I'd expect given a "dependency graph". We just explained that if a depends on b, there is a directed edge a => b, and we must visit/execute b before a. However, with the graph explained above, since we execute/visit task u before v, it stands to reason that v depends on u. So if I'm not mistaken, it seems that the input graph that Wiki's topo sorting page expects is a "dependency graph" with its edges reversed. The algorithms on the page corroborate this; for example, their DFS approach would start at a node n, recurse to the nodes that depend on n (not n's dependencies), after which prepending n to the head of some list so it appears earlier than its dependents. The result is the same as the DFT I explained, and to be clear, I'm not saying anything on either page is wrong, it just demonstrates several ways of doing something.

It does feel weird though that Wiki has this definition of a dependency graph, yet seems to use its inverse on the topological sort page, by recursing through reverse dependencies, and essentially reversing the output list.

Question

My only question is: is there some glaringly obvious reason that I'm missing, that the expected graph on the topological sorting page is basically the opposite of the "dependency graph" dfn? It feels unintuitive that we traverse from n to n's dependents, and effectively reverse the output by recording to something like a stack.

More generally, the graph that the topological sorting page seems to expect doesn't seem to be a good dependency graph anyways. If we considered this graph to be the canonical "dependency graph", then in order to find n's dependencies, we'd have to iterate through the entire graph asking "Does this node point to n?", which seems odd.

Answer 1

A topological sort produces a total ordering that is consistent with a partial ordering.

A partial ordering is the same thing as a DAG.

Very often we topologically sort items according to a dependency graph...

But the partial ordering we usually use is the "must come before" graph, not the "depends on" graph. This is the same graph, but with the edges reversed.

The two things I think you're missing are:

1) The graph is an interpretation of the data structure. The data structure is not the graph. In most real-life situations graph algorithms are applied over data structures that do not literally or explicitly represent the graph itself. In this case where there's a pointer from a to b, the DAG we're sorting has an edge from b to a.

2) Reversing the edges in the DAG just means reversing the final topological ordering, or starting from the other end. It hardly matters, so in colloquial speech, it's natural to talk about topologically sorting the dependency graph instead of topologically sorting the edge-reversed dependency graph. Sorting in descending order is still sorting, and reverse topological sorting is still topological sorting.