akgorithm to order modules according to dependencies

[JUANDENT]

Hi,

i have a program that reads module interface units and stores each module's dependencies, like this pseudo code:

module A, imports B,C,D
module B, imports C,E


I need a way to create a total ordering among these modules A-E something like this:

C is required by A and B ... therefore C,A,B or C,B,A are possible orderings
D is required by A ... therefore D, C, A, B or D, C,B,A are possible orderings
E is required by B ... therefore E,B

Therefore some possible total orders are:

E,D,C,A,B or D,E,C,B,A


This is essential to get right order because compiler needs an ordering that respects the compiler dependencies...



Any ideas?

[salem c]

Yeah, you build one of these.
https://en.wikipedia.org/wiki/Directed_acyclic_graph

[mbozzi]

The relevant search term is "topological sorting"

You could do something like this:

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <stdexcept>

using adjacency_node = std::pair<std::string const, std::vector<std::string>>;
using adjacency_table = std::unordered_map<std::string, std::vector<std::string>>;

// See: https://en.wikipedia.org/wiki/Topological_sorting
std::vector<adjacency_node> topological_sort(adjacency_table t)
{
  enum class mark { none, temporary, permanent };

  struct helper
  {
    explicit helper(adjacency_table&& t)
      : table(std::move(t))
    {}

    adjacency_table table;

    std::unordered_map<std::string, mark> marks;
    std::vector<adjacency_node> result;

    void visit(adjacency_node const& n)
    {
      auto const& [name, outgoing_edges] = n;

      if (marks[name] == mark::permanent) return;
      if (marks[name] == mark::temporary) throw std::invalid_argument{ "cyclic graph" };

      marks[name] = mark::temporary;
      for (auto const& edge : outgoing_edges)
        visit({ edge, table[edge] });
      marks[name] = mark::permanent;

      result.push_back(n);
    }

    std::vector<adjacency_node> sort()
    {
      for (auto& m : table) if (marks[m.first] == mark::none) visit(m);
      return result;
    }
  } helper{ std::move(t) };

  return helper.sort();
}

int main()
{
  adjacency_table dependencies
  {
    adjacency_node{"pants",  {"shirt", "underclothes"}},
    adjacency_node{"shirt",  {"underclothes"}},
    adjacency_node{"shoes",  {"pants", "socks"}},
    adjacency_node{"tie",    {"shirt"}},
    adjacency_node{"jacket", {"shirt", "tie", "belt", "pants"}},
    adjacency_node{"belt",   {"pants", "shirt"}}
  };

  for (auto node : topological_sort(dependencies))
    std::cout << node.first << '\n';
}