<p>I'm looking for a simple algorithm to 'serialize' a directed graph. In particular I've got a set of files with interdependencies on their execution order, and I want to find the correct order at compile time. I know it must be a fairly common thing to do - compilers do it all the time - but my google-fu has been weak today. What's the 'go-to' algorithm for this?</p>

[{'answer_id': 4177, 'author': 'Lily Ballard', 'author_id': 582, 'author_profile': 'https://Stackoverflow.com/users/582', 'pm_score': 1, 'selected': False, 'text': "<p>I would expect tools that need this simply walk the tree in a depth-first manner and when they hit a leaf, just process it (e.g. compile) and remove it from the graph (or mark it as processed, and treat nodes with all leaves processed as leaves).</p>\n\n<p>As long as it's a DAG, this simple stack-based walk should be trivial.</p>\n"}, {'answer_id': 4185, 'author': 'Kieron', 'author_id': 588, 'author_profile': 'https://Stackoverflow.com/users/588', 'pm_score': 1, 'selected': False, 'text': "<p>I've come up with a fairly naive recursive algorithm (pseudocode):</p>\n\n<pre><code>Map&lt;Object, List&lt;Object&gt;&gt; source; // map of each object to its dependency list\nList&lt;Object&gt; dest; // destination list\n\nfunction resolve(a):\n    if (dest.contains(a)) return;\n    foreach (b in source[a]):\n        resolve(b);\n    dest.add(a);\n\nforeach (a in source):\n    resolve(a);\n</code></pre>\n\n<p>The biggest problem with this is that it has no ability to detect cyclic dependencies - it can go into infinite recursion (ie stack overflow ;-p). The only way around that that I can see would be to flip the recursive algorithm into an interative one with a manual stack, and manually check the stack for repeated elements.</p>\n\n<p>Anyone have something better?</p>\n"}, {'answer_id': 4577, 'author': 'Andrew Peters', 'author_id': 608, 'author_profile': 'https://Stackoverflow.com/users/608', 'pm_score': 7, 'selected': True, 'text': '<p><a href="http://en.wikipedia.org/wiki/Topological_sorting" rel="noreferrer">Topological Sort</a> (From Wikipedia):</p>\n\n<blockquote>\n  <p>In graph theory, a topological sort or\n  topological ordering of a directed\n  acyclic graph (DAG) is a linear\n  ordering of its nodes in which each\n  node comes before all nodes to which\n  it has outbound edges. Every DAG has\n  one or more topological sorts.</p>\n</blockquote>\n\n<p>Pseudo code:</p>\n\n<pre><code>L ← Empty list where we put the sorted elements\nQ ← Set of all nodes with no incoming edges\nwhile Q is non-empty do\n    remove a node n from Q\n    insert n into L\n    for each node m with an edge e from n to m do\n        remove edge e from the graph\n        if m has no other incoming edges then\n            insert m into Q\nif graph has edges then\n    output error message (graph has a cycle)\nelse \n    output message (proposed topologically sorted order: L)\n</code></pre>\n'}, {'answer_id': 473219, 'author': 'Community', 'author_id': -1, 'author_profile': 'https://Stackoverflow.com/users/-1', 'pm_score': 1, 'selected': False, 'text': '<p>If the graph contains cycles, how can there exist allowed execution orders for your files?\nIt seems to me that if the graph contains cycles, then you have no solution, and this\nis reported correctly by the above algorithm.</p>\n'}]
['https://Stackoverflow.com/questions/4168', 'https://Stackoverflow.com', 'https://Stackoverflow.com/users/588/']