Topological sort: Difference between revisions

Content added Content deleted
m (→‎{{header|C++17}}: typo fixed)
Line 798: Line 798:


=={{header|C++}}==
=={{header|C++}}==
===C++11===
<lang c>
#include <map>
<lang c>#include <map>
#include <set>
#include <set>

template <typename Goal>
template<typename Goal>
class topological_sorter
class topological_sorter {
{
protected:
protected:
struct relations
struct relations {
std::size_t dependencies;
{
std::set<Goal> dependents;
std::size_t
};
dependencies;
std::set<Goal>
std::map<Goal, relations> map;
public:
dependents;
void add_goal(Goal const &goal) {
};
map[goal];
std::map<Goal, relations>
}
map;
void add_dependency(Goal const &goal, Goal const &dependency) {
public:
if (dependency == goal)
void
return;
add_goal(Goal const& goal)
auto &dependents = map[dependency].dependents;
{
if (dependents.find(goal) == dependents.end()) {
map[goal];
dependents.insert(goal);
}
++map[goal].dependencies;
void
}
add_dependency(Goal const& goal, Goal const& dependency)
}
{
template<typename Container>
if(dependency == goal)
void add_dependencies(Goal const &goal, Container const &dependencies) {
return;
for (auto const &dependency : dependencies)
auto&
add_dependency(goal, dependency);
dependents = map[dependency].dependents;
}
if(dependents.find(goal) == dependents.end())
template<typename ResultContainer, typename CyclicContainer>
{
void destructive_sort(ResultContainer &sorted, CyclicContainer &unsortable) {
dependents.insert(goal);
sorted.clear();
++map[goal].dependencies;
unsortable.clear();
}
for (auto const &lookup : map) {
}
auto const &goal = lookup.first;
template <typename Container>
auto const &relations = lookup.second;
void
if (relations.dependencies == 0)
add_dependencies(Goal const& goal, Container const& dependencies)
sorted.push_back(goal);
{
}
for(auto const& dependency : dependencies)
for (std::size_t index = 0; index < sorted.size(); ++index)
add_dependency(goal, dependency);
for (auto const &goal : map[sorted[index]].dependents)
}
if (--map[goal].dependencies == 0)
template <typename ResultContainer, typename CyclicContainer>
sorted.push_back(goal);
void
for (auto const &lookup : map) {
destructive_sort(ResultContainer& sorted, CyclicContainer& unsortable)
auto const &goal = lookup.first;
{
auto const &relations = lookup.second;
sorted.clear();
if (relations.dependencies != 0)
unsortable.clear();
unsortable.push_back(goal);
for(auto const& lookup : map)
}
{
}
auto const&
template<typename ResultContainer, typename CyclicContainer>
goal = lookup.first;
void sort(ResultContainer &sorted, CyclicContainer &unsortable) {
auto const&
topological_sorter<Goal> temporary = *this;
relations = lookup.second;
temporary.destructive_sort(sorted, unsortable);
if(relations.dependencies == 0)
}
sorted.push_back(goal);
void clear() {
}
map.clear();
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
Example usage with text strings
*/
*/

#include <fstream>
#include <fstream>
#include <sstream>
#include <sstream>
Line 894: Line 868:
#include <string>
#include <string>
#include <vector>
#include <vector>

using namespace
using namespace std;

std;
void display_heading(string const &message) {
cout << endl << "~ " << message << " ~" << endl;
void
display_heading(string const& message)
{
cout << endl << "~ " << message << " ~" << endl;
}
}
void display_results(string const &input) {
void
topological_sorter<string> sorter;
display_results(string const& input)
vector<string> sorted, unsortable;
{
stringstream lines(input);
topological_sorter<string>
string line;
sorter;
while (getline(lines, line)) {
vector<string>
stringstream buffer(line);
sorted,
string goal, dependency;
unsortable;
buffer >> goal;
stringstream
sorter.add_goal(goal);
lines(input);
while (buffer >> dependency)
string
sorter.add_dependency(goal, dependency);
line;
}
while(getline(lines, line))
sorter.destructive_sort(sorted, unsortable);
{
if (sorted.size() == 0)
stringstream
display_heading("Error: no independent variables found!");
buffer(line);
else {
string
display_heading("Result");
goal,
for (auto const &goal : sorted)
dependency;
cout << goal << endl;
buffer >> goal;
}
sorter.add_goal(goal);
if (unsortable.size() != 0) {
while(buffer >> dependency)
display_heading("Error: cyclic dependencies detected!");
sorter.add_dependency(goal, dependency);
for (auto const &goal : unsortable)
}
cout << goal << endl;
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) {
int
main(int argc, char** argv)
if (argc == 1) {
string example = "des_system_lib std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee\n"
{
"dw01 ieee dw01 dware gtech\n"
if(argc == 1)
"dw02 ieee dw02 dware\n"
{
"dw03 std synopsys dware dw03 dw02 dw01 ieee gtech\n"
string
"dw04 dw04 ieee dw01 dware gtech\n"
example =
"dw05 dw05 ieee dware\n"
"des_system_lib std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee\n"
"dw01 ieee dw01 dware gtech\n"
"dw06 dw06 ieee dware\n"
"dw02 ieee dw02 dware\n"
"dw07 ieee dware\n"
"dw03 std synopsys dware dw03 dw02 dw01 ieee gtech\n"
"dware ieee dware\n"
"dw04 dw04 ieee dw01 dware gtech\n"
"gtech ieee gtech\n"
"dw05 dw05 ieee dware\n"
"ramlib std ieee\n"
"dw06 dw06 ieee dware\n"
"std_cell_lib ieee std_cell_lib\n"
"dw07 ieee dware\n"
"synopsys\n"
"dware ieee dware\n"
"cycle_11 cycle_12\n"
"gtech ieee gtech\n"
"cycle_12 cycle_11\n"
"ramlib std ieee\n"
"cycle_21 dw01 cycle_22 dw02 dw03\n"
"cycle_22 cycle_21 dw01 dw04";
"std_cell_lib ieee std_cell_lib\n"
display_heading("Example: each line starts with a goal followed by it's dependencies");
"synopsys\n"
cout << example << endl;
"cycle_11 cycle_12\n"
display_results(example);
"cycle_12 cycle_11\n"
display_heading("Enter lines of data (press enter when finished)");
"cycle_21 dw01 cycle_22 dw02 dw03\n"
string line, data;
"cycle_22 cycle_21 dw01 dw04";
while (getline(cin, line) && !line.empty())
display_heading("Example: each line starts with a goal followed by it's dependencies");
data += line + '\n';
cout << example << endl;
if (!data.empty())
display_results(example);
display_results(data);
display_heading("Enter lines of data (press enter when finished)");
} else
string
while (*(++argv)) {
line,
ifstream file(*argv);
data;
typedef istreambuf_iterator<char> iterator;
while(getline(cin, line) && !line.empty())
display_results(string(iterator(file), iterator()));
data += line + '\n';
}
if(!data.empty())
}</lang>
display_results(data);
}
else while(*(++argv))
{
ifstream
file(*argv);
typedef istreambuf_iterator<char>
iterator;
display_results(string(iterator(file), iterator()));
}
}

</lang>


=={{header|C++17}}==
===C++17===
<lang c>#include <unordered_map>
<lang c>#include <unordered_map>
#include <unordered_set>
#include <unordered_set>
Retrieved from "https://rosettacode.org/wiki/Topological_sort"