Apr 27, 2023 at 11:39am Apr 27, 2023 at 11:39am UTC
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?
Last edited on Apr 27, 2023 at 11:48am Apr 27, 2023 at 11:48am UTC
Apr 27, 2023 at 9:01pm Apr 27, 2023 at 9:01pm UTC
The relevant search term is "topological sorting"
You could do something like this:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65
#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' ;
}
Last edited on Apr 27, 2023 at 9:04pm Apr 27, 2023 at 9:04pm UTC