What is required for a custom BGL graph to work with topological sort?

Question

As you correctly surmised, the error novel is telling you that there is no index map. That is required for the default color map:

UTIL/OUT: color_map(ColorMap color) This is used by the algorithm to
keep track of its progress through the graph. The type ColorMap must
be a model of Read/Write Property Map and its key type must be the
graph’s vertex descriptor type and the value type of the color map
must model ColorValue.

Default: an iterator_property_map created from
a std::vector of default_color_type of size num_vertices(g) and using
the i_map for the index map.

Indeed, the index map isn’t even required if you fulfill the color map requirement yourself: Live On Coliru

std::map<V, boost::default_color_type> vertex_colors;
boost::topological_sort(
        g,
        back_inserter(rev_topo),
        boost::color_map(boost::make_assoc_property_map(vertex_colors))
    );

More Musings: Teaching BGL Vertex Indices

Now, many algorithms require an index-map, and many get much more convenient, just like above, when your graph model does have a vertex index map.

A vertex index should map the vertex descriptors to integral numbers [0, n) (where n is the total number of vertices). In the case of the example graph model, a trivial index would be the element index into the vector of vertices.

So, you could also express the index map as:

auto idmap = boost::make_function_property_map<V>([&](V v) {
    auto match = std::find(begin(vv), end(vv), v);
    assert(match != end(vv));
    return std::distance(begin(vv), match);
});

Now you can call the algorithm relying on their default color map: Coliru

boost::topological_sort(
        g,
        back_inserter(rev_topo),
        boost::vertex_index_map(idmap)
    );

That’s not a big win, since now we still need optional named params, and even need the idmap contraption which seems more complicated than the vertex_colors map before?

Simplifying / Integrating Into The Model

We can make it better by teaching the BGL how to get our property maps from the Glue::MyGraph model.

Property Maps will be found by BGL using

the type trait boost::property_map<Graph, Tag> which tells BGL about the type of the propertymap.

Here, Tag would be e.g. boost::vertex_index_t for the vertex index map.
the accessor functions
- get(tag, graph)
  
  Returning a copy of the property-map of that type
- get(tag_type, graph, descriptor)
For writable property maps there’s also the corresponding put accessor, but I’ll leave it for brevity. See the documentation for Boost PropertyMap Library for more information on the features of that library.

Let’s do that. We start by moving the idmap generator to our MyGraph model, so we don’t need to know about the implementation details anymore:

    auto idmap() const {
        using V = YourLibrary::myVertex const*;
        return boost::make_function_property_map<V>([this](V v) {
            auto match = std::find(begin(_vertices), end(_vertices), v);
            assert(match != end(_vertices));
            return std::distance(begin(_vertices), match);
        });
    }

That means you could simply call g.idmap() to get the same propery map. However, we wanted the library to “magically” know. So, first we specialize the trait:

namespace boost {
    template <> struct property_map<Glue::MyGraph, boost::vertex_index_t> {
        using const_type = decltype(std::declval<Glue::MyGraph>().idmap());
    };
}

It’s a delight of c++14 that we can deduce all these types. Only remaining step: the accessor functions, which are again ADL-enabled customization points, so we put them into our Glue namespace:

    auto get(boost::vertex_index_t, MyGraph const& g) {
        return g.idmap();
    }
    auto get(boost::vertex_index_t, MyGraph const& g, YourLibrary::myVertex const* v) {
        return g.idmap()[v];
    }
}  // namespace Glue

Proof Of The Pudding

Now, since the library “just understands” vertex indices for our model, we can enjoy the algorithms that need one without any additional help:

std::list<V> order;
boost::topological_sort(g, back_inserter(order));

And we can exercise the other accessor for fun:

std::cout << "Topo order:\n";
order.reverse(); // output is reversed
for (auto v : order)
    std::cout << "Vertex index:" << get(boost::vertex_index, g, v)
              << " name:" << v->name << "\n";

In your own (non-generic, library) code you would probably write

auto idmap = g.idmap(); // or
auto idmap = get(boost::vertex_index, g, v);

And use idmap[v] to get values instead.

Live Demo

Live On Coliru

#include <algorithm>
#include <boost/container/flat_map.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/depth_first_search.hpp>
#include <boost/graph/topological_sort.hpp>
#include <boost/property_map/function_property_map.hpp>
#include <iostream>
#include <utility>

namespace YourLibrary {
    struct myVertex {
        myVertex(std::string n) : name(std::move(n)) {}
        std::string name;
    };

    struct myEdge {
        myVertex* _s = nullptr;
        myVertex* _t = nullptr;

        [[nodiscard]] myVertex* source() const { return _s; }
        [[nodiscard]] myVertex* target() const { return _t; }
    };

    using Vertices = std::vector<myVertex *>;
    using Edges = std::vector<myEdge *>;
}  // namespace YourLibrary

namespace Glue {

    struct MyGraph {
        struct EdgeOrder {
            template <typename A, typename B>
                bool operator()(A const* a, B const* b) const { return source(a) < source(b); }
            private:
            static auto source(YourLibrary::myVertex const* v) { return v; }
            static auto source(YourLibrary::myEdge const* e) { return e->source(); }
        };

        using Vertices = YourLibrary::Vertices;
        using Edges = YourLibrary::Edges;

        Vertices& _vertices;
        Edges& _edges;

        auto idmap() const {
            using V = YourLibrary::myVertex const*;
            return boost::make_function_property_map<V>([this](V v) {
                auto match = std::find(begin(_vertices), end(_vertices), v);
                assert(match != end(_vertices));
                return std::distance(begin(_vertices), match);
            });
        }

        MyGraph(Vertices& vv, Edges& ee) : _vertices(vv), _edges(ee)  { 
            assert(std::is_sorted(_edges.begin(), _edges.end(), EdgeOrder{}));
        }
    };
}  // namespace Glue

namespace boost {

    template <> struct graph_traits<Glue::MyGraph> {
        // Due to Graph concept
        using vertex_descriptor      = YourLibrary::myVertex*;
        using edge_descriptor        = YourLibrary::myEdge*;
        using directed_category      = directed_tag;
        using edge_parallel_category = allow_parallel_edge_tag;
        static vertex_descriptor null_vertex() { return nullptr; }

        // Due to Vertex List concept
        struct traversal_category : vertex_list_graph_tag, incidence_graph_tag { };
        using vertex_iterator        = Glue::MyGraph::Vertices::const_iterator;
        using vertices_size_type     = std::size_t;

        // Due to Incidence Graph concept
        using out_edge_iterator = Glue::MyGraph::Edges::const_iterator;
        using degree_size_type = std::size_t;
    };

}  // namespace boost

namespace Glue {
    // Due to Vertex List concept
    auto vertices(MyGraph const& g) {
        return std::make_pair(g._vertices.begin(), g._vertices.end());
    }

    std::size_t num_vertices(MyGraph const& g) {
        return g._vertices.size();
    }

    // Due to Incidence Graph concept
    auto source(YourLibrary::myEdge const* e, MyGraph const& /*g*/) {
        return e->source();
    }
    auto target(YourLibrary::myEdge const* e, MyGraph const& /*g*/) {
        return e->target();
    }

    auto out_edges(YourLibrary::myVertex const* v, MyGraph const& g) {
        return std::equal_range(g._edges.begin(), g._edges.end(), v, MyGraph::EdgeOrder{});;
    }
    std::size_t out_degree(YourLibrary::myVertex const* v, MyGraph const& g) {
        auto oee = std::equal_range(g._edges.begin(), g._edges.end(), v, MyGraph::EdgeOrder{});
        return std::distance(oee.first, oee.second);
    }

    auto get(boost::vertex_index_t, MyGraph const& g) {
        return g.idmap();
    }
    auto get(boost::vertex_index_t, MyGraph const& g, YourLibrary::myVertex const* v) {
        return g.idmap()[v];
    }
}  // namespace Glue

namespace boost {
    template <> struct property_map<Glue::MyGraph, boost::vertex_index_t> {
        using const_type = decltype(std::declval<Glue::MyGraph>().idmap());
    };
}

int main() {
    // I hate manual memory management, so let's own some objects
    auto a = std::make_unique<YourLibrary::myVertex>("a");
    auto b = std::make_unique<YourLibrary::myVertex>("b");
    auto c = std::make_unique<YourLibrary::myVertex>("c");
    auto ab = std::make_unique<YourLibrary::myEdge>(YourLibrary::myEdge{a.get(), b.get()});
    auto cb = std::make_unique<YourLibrary::myEdge>(YourLibrary::myEdge{c.get(), b.get()});

    // These were given in your question:
    YourLibrary::Vertices vv { a.get(), b.get(), c.get() };
    YourLibrary::Edges ee { ab.get(), cb.get() };

    // this is the glue required to fulfill the BGL concepts:
    using boost::make_iterator_range;

    Glue::MyGraph g(vv, ee);
    for (auto v : make_iterator_range(vertices(g)))
        for (auto e : make_iterator_range(out_edges(v, g)))
            std::cout << "out edge ("
                      << source(e, g)->name << " -> "
                      << target(e, g)->name << ")\n";

    // this is showing that you can now BFS on it
    using V = boost::graph_traits<Glue::MyGraph>::vertex_descriptor;
    V start_vertex = a.get();
    std::map<V, boost::default_color_type> color_data;

    boost::breadth_first_search(g, start_vertex,
        boost::visitor(boost::default_bfs_visitor {})
            .color_map(boost::make_assoc_property_map(color_data)));

    boost::depth_first_search(g, boost::default_dfs_visitor {},
        boost::make_assoc_property_map(color_data), start_vertex);

    // named params
    boost::depth_first_search(g,
        boost::visitor(boost::default_dfs_visitor {})
            .color_map(boost::make_assoc_property_map(color_data))
            .root_vertex(start_vertex));

    std::list<V> order;
    boost::topological_sort(g, back_inserter(order));

    std::cout << "Topo order:\n";
    order.reverse(); // output is reversed

    auto idmap = g.idmap();
    for (auto v : order)
        std::cout << "Vertex index:" << idmap[v] << " name:" << v->name << "\n";
}

Printing

out edge (a -> b)
out edge (c -> b)
Topo order:
Vertex index:2 name:c
Vertex index:0 name:a
Vertex index:1 name:b

More Musings: Teaching BGL Vertex Indices

Simplifying / Integrating Into The Model

Proof Of The Pudding

Live Demo

More Related Contents:

Leave a Comment Cancel reply