Sorting algorithm for Provides/DependsOn objects

Question

I have a set of type rewriters, each modifies a given C# type in a different way. Examples are:

1. Add the XYZ attribute to each property of the class
2. Add an ID property
3. Add two properties and some corresponding method

As you can see there are implicit dependencies: 1 should definitely run after 2 and 3, otherwise not all properties would have the XYZ attribute in the end.

We made this implicit dependencies explicit using attributes on the type rewriters:

[Performs(typeof(IAttributeOnPropertiesCreation))]
[DependsOn(typeof(IPropertyCreation))]
public class SomeRewriter
{
 // this one resembles example 1
}
[Performs(typeof(IPropertyCreation))]
// no DependsOn
public class SomeOtherRewriter
{
 // resembles example 2
}

I need an algorithm to sort a set of such type rewriters by dependency (if possible, i.e., if there are no circular dependencies).

Is there a well-known reference-algorithm for this task? Maybe even a well-known name I can use for looking up various algorithms?

Side note: I know the full set of possible Performs/DependsOn types. Still, there may be DependsOn() statements for which none, a single or even multiple rewriters have a corresponding Performs() statement. In turn there are also Performs() declarations which nobody depends upon.

Answer 1

the best thing you could use for this is probably a toposort algorithm (topolocial sort). Basically you can write similar code as seen in this so post

Note that this algorithm will also easily detect cyclic dependencies.

More info: If you know something about directed graphs, it's basically a depth-first search on such a directed graph. Such an algorithm can also be used to detect independent parts of a graph, which can be useful for automatic Task / Program parallelization and such.

I recommend reading more about graphs, as they can be really helpful for programming and optimizing data structures. See: Wikipedia