title: Edge direction in a dependency graph for topological sort?
body: <p>Wikipedia explains a <a href="https://en.wikipedia.org/wiki/Dependency_graph" rel="nofollow noreferrer">dependency graph</a> in a very intuitive way (IMO), citing that an edge goes from <code>a =&gt; b</code> when <code>a</code> depends on <code>b</code>. 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.</p>
  
  <p>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.</p>
  
  <p>The Wikipedia page for <a href="https://en.wikipedia.org/wiki/Topological_sorting" rel="nofollow noreferrer">topological sorting</a> explains the definition as:</p>
  
  <blockquote>
    <p>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.</p>
  </blockquote>
  
  <p>This is the opposite of what I'd expect given a "dependency graph". We just explained that if <code>a</code> depends on <code>b</code>, there is a directed edge <code>a =&gt; b</code>, and we must visit/execute <code>b</code> <em>before</em> <code>a</code>. However, with the graph explained above, since we execute/visit task <code>u</code> before <code>v</code>, it stands to reason that <code>v</code> depends on <code>u</code>. 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 <code>n</code>, recurse to the nodes that depend on <code>n</code> (not <code>n</code>'s dependencies), after which <em>prepending</em> <code>n</code> 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.</p>
  
  <p>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.</p>
  
  <h2>Question</h2>
  
  <p>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 <code>n</code> to <code>n</code>'s dependents, and effectively reverse the output by recording to something like a stack.</p>
  
  <p>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 <code>n</code>'s dependencies, we'd have to iterate through the entire graph asking "Does this node point to n?", which seems odd.</p>