1

Order list by dependencies

 2 years ago
source link: https://www.codesd.com/item/order-list-by-dependencies.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

Order list by dependencies

advertisements

This question already has an answer here:

  • How to sort depended objects by dependency 8 answers

Given the following list:

var modules = new List<Module>() {
    new Module() { Name = "Audits", Dependencies = new[] { "Logs" } },
    new Module() { Name = "Blog", Dependencies = new[] { "Content", "Tags" } },
    new Module() { Name = "Content", Dependencies = new[] { "Audits" } },
    new Module() { Name = "Logs" },
    new Module() { Name = "Tags" }
};

I need to create a way to order this list programmatically so that the modules that are most-dependable are at the top. Therefore the desired order using the above example would be:

  1. Audits
  2. Content

Since "Content" has a dependency on "Audits" then "Audits" appears first. But since "Audits" has a dependency on "Logs" then "Logs" comes above "Audits" and so. "Blog" appears last since it has dependencies on both "Content" and "Tags" and therefore they come above.

I hope I've described my problem clear enough. I'm sure there's some clever algorithm to handle this and make it as efficient as possible but it's alluded me so far. I'd appreciate if someone could point me in the right direction.

Thanks


The problem you are describing is called topological sort: given a partial ordering, try to find a linear description that respects that ordering.

The typical algorithm to solve this problem takes O(|V| + |E|) time, where |V| is the number of vertices (modules in your example) and |E| is the number of edges (dependencies in your example).

The linked Wikipedia article also provides pseudo code. It will take some book keeping to convert the algorithm to your example, but it is relatively straightforward.


About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK