Using std::sort to sort dependency tree

Question

I want to sort a bunch of plugins by their dependencies to each other in a way so that I can load them linearly without any conflicts. Dependency cycles are excluded by contract (result in undefined behavior).

Imagine a binary tree of depth two whose edges are directed to the leaves. Let this be an artificial dependency tree. The set of edges denote the relation R. Compare returns true if the tuple (lhs, rhs) is in R.

Can I use std::sort with a compare which represents the relation rhs depends on lhs to achieve this?

Answer 1

No - I don't think so.

Imagine the following:

  A
 / \
B   C
     \
      D

B and C depend on A, D depends on C. Now:

1. B does not depend on C, therefore B is not less than C.
2. C does not depend on B, therefore C is not less than B.
3. Therefore B "is equal to" C as far as the sort algorithm is concerned.
4. Similarly, D "is equal to" B

First problem: B=C, B=D, but C<D is likely to confuse many sorting algorithms.

Secondly, the algorithm used by std::sort is not specified, but we know many implementations use some form of quicksort. Quicksort implementations are allowed to partition values into three buckets - those that are less than the pivot, those that are greater than the pivot, and those that are all equal to the pivot, and therefore do not need any additional sorting. (See the "Repeated elements" section on Wikipedia.)

If such a quicksort selected B as the pivot, then C and D would both find themselves in this "fat partition" in some unspecified order, and std::sort wouldn't even test C against D with your comparison function.

Answer 2

I had the same requirement recently. I was modelling database entities in code and needed a way to map dependencies so that the entities could be created and destroyed in the correct order.

I found a solution with the boost::graph library. I have included a snippet (of real code) in the hope that it can get you started in the right direction.

In the code below, the function create_order yields a vector of entities in the order they must be created, and drop_order does the opposite (the most dependant entity comes first):

    using edge = std::pair<std::size_t, std::size_t>;
    using edge_vector = std::vector<edge>;

    using graph_properties = boost::property<
    boost::vertex_color_t,
    boost::default_color_type
    >;

    typedef boost::adjacency_list<boost::vecS, boost::vecS,
    boost::bidirectionalS,
    graph_properties
    > Graph;
    typedef boost::graph_traits<Graph>::vertex_descriptor Vertex;

    struct cycle_detector : public boost::dfs_visitor<>
    {
        cycle_detector( edge_vector& back_edges)
        : _back_edges(back_edges)
        { }

        void back_edge(const boost::graph_traits<Graph>::edge_descriptor& e, const Graph&) const {
            _back_edges.emplace_back(e.m_source, e.m_target);
        }
    protected:
        edge_vector& _back_edges;
    };


    auto generate_graph() const {
        Graph g(std::begin(_edges), std::end(_edges), _entities.size());
        return g;
    }

    void check_cycles(const Graph& g) const
    {
        edge_vector back_edges;
        cycle_detector vis(back_edges);
        boost::depth_first_search(g, visitor(vis));

        if (back_edges.size())
        {
            std::ostringstream ss;
            ss << "cyclic dependency detected. Back edges are:\n";
            for (auto& p : back_edges)
            {
                ss << value::debug::demangle(typeid(_entities[p.first].get()))
                << " <<==>> "
                << value::debug::demangle(typeid(_entities[p.second].get()))
                << std::endl;
            }
            throw std::logic_error(ss.str());
        }
    }

    auto create_order() const {
        using namespace boost;

        auto g = generate_graph();
        check_cycles(g);

        std::vector<std::size_t> result_order;
        vector_type result;

        boost::topological_sort(g, std::back_inserter(result_order));
        std::transform(std::begin(result_order), std::end(result_order),
                       std::back_inserter(result), [this](auto i) {
                           return _entities[i];
                       });

        return result;
    }

    auto drop_order() const {
        auto result = create_order();
        std::reverse(std::begin(result), std::end(result));
        return result;
    }