Chart serialization

Question

I am looking for a simple algorithm to “serialize” a directed graph. In particular, I have a set of files with interdependencies in the order of their execution, and I want to find the correct order at compile time. I know this should be quite common - compilers do this all the time, but my google-fu is weak today. What is the "go" algorithm for this?

Answer 1

Topological sorting (from Wikipedia):

In graph theory, topological sorting or topological ordering of a directed acyclic graph (DAG) is a linear ordering of its nodes, in which each node occurs in front of all nodes to which it has outgoing edges. Each group has one or more topological varieties.

Pseudocode:

L ← Empty list where we put the sorted elements Q ← Set of all nodes with no incoming edges while Q is non-empty do remove a node n from Q insert n into L for each node m with an edge e from n to m do remove edge e from the graph if m has no other incoming edges then insert m into Q if graph has edges then output error message (graph has a cycle) else output message (proposed topologically sorted order: L) 

Answer 2

I would expect the tools that need it to just go through the tree with depth for the first time, and when they hit the sheet, just process it (for example, compile) and remove it from the graph (or mark it as processed and process the nodes with all leaves treated like leaves).

While this is a DAG, this simple stack-based step should be trivial.

Answer 3

If the graph contains cycles, how can there be valid execution orders for your files? It seems to me that if the graph contains cycles, then you have no solution, and this is correctly reported by the above algorithm.

Answer 4

I came up with a rather naive recursive algorithm (pseudocode):

 Map<Object, List<Object>> source; // map of each object to its dependency list List<Object> dest; // destination list function resolve(a): if (dest.contains(a)) return; foreach (b in source[a]): resolve(b); dest.add(a); foreach (a in source): resolve(a); 

The biggest problem is that it does not have the ability to detect circular dependencies - it can go into infinite recursion (i.e. stack overflow; -p). The only way I can see is to turn the recursive algorithm into an interactive one with a manual stack and manually check the stack for repeated elements.

Does anyone have something better?