Anonymous user
Topological sort: Difference between revisions
m
→{{header|C++}}: plan
m (→{{header|C++17}}: typo fixed) |
m (→{{header|C++}}: plan) |
||
Line 798:
=={{header|C++}}==
===C++11===
<lang c>#include <map>
#include <set>
template
class topological_sorter {
protected:
std::size_t dependencies;
std::set<Goal> dependents;
};
public:
void add_goal(Goal const &goal) {
map[goal];
}
void add_dependency(Goal const &goal, Goal const &dependency) {
if (dependency == goal)
return;
auto &dependents = map[dependency].dependents;
if (dependents.find(goal) == dependents.end()) {
dependents.insert(goal);
++map[goal].dependencies;
}
}
template<typename Container>
void add_dependencies(Goal const &goal, Container const &dependencies) {
for (auto const &dependency : dependencies)
add_dependency(goal, dependency);
}
template<typename ResultContainer, typename CyclicContainer>
void destructive_sort(ResultContainer &sorted, CyclicContainer &unsortable) {
sorted.clear();
unsortable.clear();
for (auto const &lookup : map) {
auto const &goal = lookup.first;
auto const &relations = lookup.second;
if (relations.dependencies == 0)
sorted.push_back(goal);
}
for (std::size_t index = 0; index < sorted.size(); ++index)
for (auto const &goal : map[sorted[index]].dependents)
if (--map[goal].dependencies == 0)
sorted.push_back(goal);
for (auto const &lookup : map) {
auto const &goal = lookup.first;
auto const &relations = lookup.second;
if (relations.dependencies != 0)
unsortable.push_back(goal);
}
}
template<typename ResultContainer, typename CyclicContainer>
void sort(ResultContainer &sorted, CyclicContainer &unsortable) {
topological_sorter<Goal> temporary = *this;
temporary.destructive_sort(sorted, unsortable);
}
void clear() {
map.clear();
}
};
/*
Example usage with text strings
*/
#include <fstream>
#include <sstream>
Line 894 ⟶ 868:
#include <string>
#include <vector>
using namespace std;
void display_heading(string const &message) {
cout << endl << "~ " << message << " ~" << endl;
}
void display_results(string const &input) {
topological_sorter<string> sorter;
vector<string> sorted, unsortable;
stringstream lines(input);
string line;
while (getline(lines, line)) {
stringstream buffer(line);
string goal, dependency;
buffer >> goal;
sorter.add_goal(goal);
while (buffer >> dependency)
sorter.add_dependency(goal, dependency);
}
sorter.destructive_sort(sorted, unsortable);
if (sorted.size() == 0)
display_heading("Error: no independent variables found!");
else {
display_heading("Result");
for (auto const &goal : sorted)
cout << goal << endl;
}
if (unsortable.size() != 0) {
display_heading("Error: cyclic dependencies detected!");
for (auto const &goal : unsortable)
cout << goal << endl;
}
}
int main(int argc, char **argv) {
string example = "des_system_lib std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee\n"
"dw01 ieee dw01 dware gtech\n"
"dw02 ieee dw02 dware\n"
"dw03 std synopsys dware dw03 dw02 dw01 ieee gtech\n"
"dw04 dw04 ieee dw01 dware gtech\n"
"dw05 dw05 ieee dware\n"
"cycle_22 cycle_21 dw01 dw04";
display_heading("Example: each line starts with a goal followed by it's dependencies");
cout << example << endl;
display_results(example);
display_heading("Enter lines of data (press enter when finished)");
string line, data;
while (getline(cin, line) && !line.empty())
data += line + '\n';
if (!data.empty())
display_results(data);
} else
while (*(++argv)) {
ifstream file(*argv);
typedef istreambuf_iterator<char> iterator;
display_results(string(iterator(file), iterator()));
}
}</lang>
==
<lang c>#include <unordered_map>
#include <unordered_set>
| |||