
Sorting Algorithm

This is a sorting algorithm.   It may be applied to a set of data in order to sort it.    
For comparing various sorts, see compare sorts.  
For other sorting algorithms,   see sorting algorithms,   or:

O(n logn) sorts
Heap sort |
Merge sort |
Patience sort |
Quick sort
O(n log2n) sorts
Shell Sort
O(n2) sorts
Bubble sort |
Cocktail sort |
Cocktail sort with shifting bounds |
Comb sort |
Cycle sort |
Gnome sort |
Insertion sort |
Selection sort |
Strand sort
other sorts
Bead sort |
Bogo sort |
Common sorted list |
Composite structures sort |
Custom comparator sort |
Counting sort |
Disjoint sublist sort |
External sort |
Jort sort |
Lexicographical sort |
Natural sorting |
Order by pair comparisons |
Order disjoint list items |
Order two numerical lists |
Object identifier (OID) sort |
Pancake sort |
Quickselect |
Permutation sort |
Radix sort |
Ranking methods |
Remove duplicate elements |
Sleep sort |
Stooge sort |
[Sort letters of a string] |
Three variable sort |
Topological sort |
Tree sort




Given a mapping between items, and items they depend on, a topological sort orders items so that no item precedes an item it depends upon.

The compiling of a library in the VHDL language has the constraint that a library must be compiled after any library it depends on.

A tool exists that extracts library dependencies.



Task

Write a function that will return a valid compile order of VHDL libraries from their dependencies.

 Assume library names are single words. 
 Items mentioned as only dependents, (sic), have no dependents of their own, but their order of compiling must be given.
 Any self dependencies should be ignored. 
 Any un-orderable dependencies should be flagged.


Use the following data as an example:

LIBRARY          LIBRARY DEPENDENCIES
=======          ====================
des_system_lib   std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee
dw01             ieee dw01 dware gtech
dw02             ieee dw02 dware
dw03             std synopsys dware dw03 dw02 dw01 ieee gtech
dw04             dw04 ieee dw01 dware gtech
dw05             dw05 ieee dware
dw06             dw06 ieee dware
dw07             ieee dware
dware            ieee dware
gtech            ieee gtech
ramlib           std ieee
std_cell_lib     ieee std_cell_lib
synopsys


Note: the above data would be un-orderable if, for example, dw04 is added to the list of dependencies of dw01.



C.f.

   Topological sort/Extracted top item.


There are two popular algorithms for topological sorting:

   Kahn's 1962 topological sort [1] 
   depth-first search [2] [3]


#include <map>
#include <set>
 
template<typename Goal>
class topological_sorter {
protected:
    struct relations {
        std::size_t dependencies;
        std::set<Goal> dependents;
    };
    std::map<Goal, relations> map;
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>
#include <iostream>
#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) {
    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"
                "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"
                "dw06             dw06 ieee dware\n"
                "dw07             ieee dware\n"
                "dware            ieee dware\n"
                "gtech            ieee gtech\n"
                "ramlib           std ieee\n"
                "std_cell_lib     ieee std_cell_lib\n"
                "synopsys\n"
                "cycle_11     cycle_12\n"
                "cycle_12     cycle_11\n"
                "cycle_21     dw01 cycle_22 dw02 dw03\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()));
        }
}