CODEWITHSUNDEEP
c++sortingdependencies
Dess
Dess

Reputation: 2669

How to topologically sort this data struct

I'm playing around with figuring out some dependency stuff, and I got far, but now I'm stuck.

Let's say I have a data struct like this:

map<string, vector<string>> deps;

where each key in the map is a dependee node, and the value at that key is a list of nodes on which the dependee depends.

Further, lets say the map has 4 keys (A, B, C, and D) with the following dependency entries:

Dependencies

I'm looking for an algorithm (some topological sort?) which will yield a vector of strings such that the strings appear in this order: 

F, B, C, D, A
0  1  2  3  4

This list represents the order in which the dependencies should be evaluated.

Upvotes: 2

Views: 186

Answers (2)

Galik
Galik

Reputation: 48635

I recently came up with a solution for this based on this algorithm:

This is a slightly modified version for your data structure:

#include <map>
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>

/**
 * Performs dependency resolution using
 * a topological sort
 */
template<typename ValueType>
class Resolver
{
public:
    using value_type = ValueType;
    using value_vec = std::vector<value_type>;
    using value_map = std::map<value_type, value_vec>;

private:
    value_vec seen;
    value_map deps;

    void resolve(value_type const& d, value_vec& sorted)
    {
        seen.push_back(d);
        for(auto const& nd: deps[d])
        {
            if(std::find(sorted.begin(), sorted.end(), nd) != sorted.end())
                continue;
            else if(std::find(seen.begin(), seen.end(), nd) == seen.end())
                resolve(nd, sorted);
            else
            {
                std::cerr << "Circular from " << d << " to " << nd << '\n';
                continue;
            }
        }
        sorted.push_back(d);
    }

public:

    /**
     * Clear the resolver ready for new
     * set of dependencies.
     */
    void clear()
    {
        seen.clear();
        deps.clear();
    }

    /**
     * Items that don't depend on anything
     */
    void add(value_type const& a)
    {
        deps[a];
    }

    /**
     * Item a depends on item b
     */
    void add(value_type const& a, value_type const& b)
    {
        deps[a].push_back(b);
    }

    value_vec resolve()
    {
        value_vec sorted;
        for(auto const& d: deps)
            if(std::find(sorted.begin(), sorted.end(), d.first) == sorted.end())
                resolve(d.first, sorted);
        return sorted;
    }
};

int main()
{
    Resolver<std::string> resolver;

    resolver.add("A", "B");
    resolver.add("A", "C");
    resolver.add("A", "D");

    resolver.add("B", "F");

    resolver.add("C", "B");
    resolver.add("C", "F");

    resolver.add("D", "C");

    resolver.add("F");

    for(auto const& d: resolver.resolve())
        std::cout << d << '\n';
}

Output:

F
B
C
D
A

Please let me know if you find any bugs (not very well tested yet).

Added from the comments:

For efficiency, in production code, if the node type (string, in this example) can be imbued with a flag to mark the node as seen/sorted, then the calls to std::find can be replaced with setting the seen/sorted values for flag. Of course, in this example, Galik couldn't do that, which is why std::find is used, instead. - @Dess

Upvotes: 1

Abhinav
Abhinav

Reputation: 534

as you described in the question, each key in the map is a dependent node, and the value at that key is a list of nodes on which the dependent depends, or dependency.

So, the actual dependencies would something be like (say, dataset of the form 'from -> to'):

  1. B -> A
  2. C -> A
  3. D -> A
  4. F -> B
  5. B -> C
  6. F -> C
  7. C -> D

The idea is to first find the starting point. A starting point would never be on ‘to’ side of an entry. Once we find the starting point, we can simply traverse the given set to print itinerary in order. Following are the steps.

  1. Create a set of given pair of entries in the form shown above (Call this dataset). Every entry of 'dataset' is of the form "from->to".

  2. Find the starting point of itinerary.

    • Create a reverse set. Let the reverse be 'reverseMap'. Entries of 'reverseMap' are of the form "to->from". Following is 'reverseMap' for above example.

      A -> B
A -> C
A -> D
B -> F
C -> B
C -> F
D -> C

    • Traverse 'dataset'. For every key of dataset, check if it is there on the left hand side of the expression in the 'reverseMap'. If a key is not present, then we found the starting point. In the above example, "F" is starting point.

    • Start from above found starting point and traverse the 'dataset' to print itinerary considering the following rule.

      • When we encounter a node which is present at multiple 'from' positions in the dataset, then check the frequency of all of its 'to' counterparts in the reverseMap on the left hand side of the expression and choose the one with the minimum frequency.

      For example, when we start with "F" as the starting node, then we have two options in dataset to move forward with namely, "F -> B" and "F -> C". So, we check the frequencies of both "C" and "B" in the reverseMap in the left hand side of the expression, which turn out to be 2 and 1 respectively. So, we move forward with B's entry (F -> B), and discard the other entry (F -> C). This entry will never be required in future.

I hope this helps. Share with me, if you find any bugs, or have something to add to this.

Upvotes: 1

Related Questions