ColorMap в неявном графике boost::graph для metric_tsp_ приблизительно

Я пытаюсь выполнить следующее: есть функция computeTspTour(size, start, distance), которая дает мне приближение к кратчайшему маршруту через size множество вершин, начиная с start. Здесь distance — это объект функции, который принимает два индекса и возвращает расстояние между ними.

Я хотел бы использовать metric_tsp_approx boost::graph. Для этого мне нужен полный граф мощности size, поэтому я хотел бы использовать для этого неявно определенный граф, чтобы избежать создания бесполезной тривиальной структуры огромного графа.

Кажется, все работает нормально, но моя проблема в том, что metric_tsp_approx в какой-то момент использует dijkstra_shortest_paths, который определяет ColorMap. Это приводит к следующим двум проблемам:

/usr/include/boost/graph/dijkstra_shortest_paths.hpp:373:60: error: no type named 'value_type' in 'struct boost::property_traits<boost::bgl_named_params<boost::detail::_project2nd<double, double>, boost::distance_combine_t, boost::bgl_named_params<std::less<double>, boost::distance_compare_t, boost::bgl_named_params<boost::iterator_property_map<__gnu_cxx::__normal_iterator<long unsigned int*, std::vector<long unsigned int> >, boost::typed_identity_property_map<long unsigned int>, long unsigned int, long unsigned int&>, boost::vertex_predecessor_t, boost::bgl_named_params<EdgeWeightMap<double>, boost::edge_weight_t, boost::bgl_named_params<boost::typed_identity_property_map<long unsigned int>, boost::vertex_index_t, boost::bgl_named_params<long unsigned int, boost::root_vertex_t, boost::no_property> > > > > > >'
typedef typename property_traits<ColorMap>::value_type ColorValue;
                                                       ^

/usr/include/boost/graph/dijkstra_shortest_paths.hpp:374:38: error: no type named 'value_type' in 'struct boost::property_traits<boost::bgl_named_params<boost::detail::_project2nd<double, double>, boost::distance_combine_t, boost::bgl_named_params<std::less<double>, boost::distance_compare_t, boost::bgl_named_params<boost::iterator_property_map<__gnu_cxx::__normal_iterator<long unsigned int*, std::vector<long unsigned int> >, boost::typed_identity_property_map<long unsigned int>, long unsigned int, long unsigned int&>, boost::vertex_predecessor_t, boost::bgl_named_params<EdgeWeightMap<double>, boost::edge_weight_t, boost::bgl_named_params<boost::typed_identity_property_map<long unsigned int>, boost::vertex_index_t, boost::bgl_named_params<long unsigned int, boost::root_vertex_t, boost::no_property> > > > > > >'
typedef color_traits<ColorValue> Color;
                                 ^

Тем не менее, я не вижу, как я мог бы исправить черты ColorMap, где я нахожусь, создание карты свойств цвета самостоятельно не приносит никакой пользы.

Код, который я использую для создания неявного графа и запуска на нем tsp_metric_approx, выглядит следующим образом. Прошу прощения за длину, надеюсь понятно. Что он делает, так это устанавливает класс CompleteGraph, имеющий один параметр шаблона F, который указывает тип возвращаемого значения функции distance. Этот класс имеет необходимые итераторы, чтобы быть VertexListGraph и IncidenceGraph, так что tsp_metric_approx может работать на нем.

#include <algorithm>
#include <functional>
#include <iostream>
#include <iterator>
#include <vector>

#include <boost/iterator/iterator_facade.hpp>
#include <boost/graph/metric_tsp_approx.hpp>

using namespace boost;

typedef std::size_t VertexDescriptor;
typedef std::pair<VertexDescriptor, VertexDescriptor> EdgeDescriptor;

class VertexIterator : public boost::iterator_facade<VertexIterator, VertexDescriptor const, boost::bidirectional_traversal_tag>
{
    public:
        //! Default constructor
        VertexIterator() : pos_(0) {}

        //! Constructor setting the position
        explicit VertexIterator(VertexDescriptor pos) : pos_(pos) {}

        //! Dereference the iterator
        VertexDescriptor const& dereference() const { return pos_; }

        //! Check for equality
        bool equal(VertexIterator const& other) const { return pos_ == other.pos_; }

        //! Increment
        void increment() { ++pos_; }

        //! Decrement
        void decrement() { --pos_; }

    private:
        //! Grant access to boost::iterator_facade
        friend class boost::iterator_core_access;

        //! The current position
        VertexDescriptor pos_ = 0;
};

class OutEdgeIterator : public boost::iterator_facade<OutEdgeIterator, EdgeDescriptor const, boost::bidirectional_traversal_tag>
{
    public:
        //! Constructor setting the source vertex
        explicit OutEdgeIterator(VertexDescriptor source) { const std::size_t target = source == 0 ? 1 : 0; pos_ = EdgeDescriptor(source, target); }

        //! Constructor setting the source vertex and the target
        explicit OutEdgeIterator(VertexDescriptor source, VertexDescriptor target) : pos_(source, target) {}

        //! Dereference the iterator
        EdgeDescriptor const& dereference() const { return pos_; }

        //! Check for equality
        bool equal(OutEdgeIterator const& other) const { return pos_ == other.pos_; }

        //! Increment
        void increment() { ++pos_.second; if(pos_.first == pos_.second) { ++pos_.second; } }

        //! Decrement
        void decrement() { --pos_.second; if(pos_.first == pos_.second) { --pos_.second; } }

    private:
        //! Grant access to boost::iterator_facade
        friend class boost::iterator_core_access;

        //! The current edge
        EdgeDescriptor pos_ = EdgeDescriptor(0, 1);
};

//! Class representing a complete graph
/*!
 * This class works as a complete graph.
 * It defines a distance property map between any two points by calling the passed distance function.
 * \tparam F The return type of the distance function
 */
template<typename F>
class CompleteGraph
{
    public:
        typedef VertexDescriptor vertex_descriptor;
        typedef EdgeDescriptor edge_descriptor;
        typedef void adjacency_iterator;
        typedef OutEdgeIterator out_edge_iterator;
        typedef void in_edge_iterator;
        typedef void edge_iterator;
        typedef VertexIterator vertex_iterator;
        typedef std::size_t degree_size_type;
        typedef std::size_t vertices_size_type;
        typedef std::size_t edges_size_type;
        typedef undirected_tag directed_category;
        typedef disallow_parallel_edge_tag edge_parallel_category;
        typedef vertex_list_graph_tag traversal_category;

        //! Delete default constructor
        CompleteGraph() = delete;

        //! Constructor from a given size
        /*!
         * If no distance is specified, we default to a constant function returning F(1)
         */
        explicit CompleteGraph(std::size_t size) : size_(size), distance_(returnOne) {}

        //! Constructor from a given size and a distance function of type F
        /*!
         * The constructed graph will have size many vertices.
         * Its distance map will be of the following form: The distance between points i and j is distance(i, j).
         * \param[in] size The size the graph should have
         * \param[in] distance Binary function taking std::size_t arguments and returning the distance between two points
         */
        explicit CompleteGraph(std::size_t size, std::function<F(std::size_t, std::size_t)> const& distance) : size_(size), distance_(distance) {}

        //! Access to size_
        std::size_t size() const { return size_; }

        //! Access to distance_
        std::function<F(std::size_t, std::size_t)> const& distance() const { return distance_; }

    private:
        //! The size of the graph
        std::size_t size_;

        //! The distance function used to find the distance between point i and point j
        std::function<F(std::size_t, std::size_t)> const& distance_;

        //! Distance function that just returns F(1)
        std::function<F(std::size_t, std::size_t)> returnOne = [] (std::size_t, std::size_t) { return F(1); };
};

//! Weigth map for all edges
template<typename F>
class EdgeWeightMap
{
    public:
        typedef F value_type;
        typedef F reference_type;
        typedef reference_type reference;
        typedef EdgeDescriptor key_type;
        typedef readable_property_map_tag category;

        //! Constructor from a distance function
        explicit EdgeWeightMap(std::function<F(std::size_t, std::size_t)> const& distance) : distance_(distance) {}

        //! Operator to dereference the property map
        value_type operator[](key_type key) const { return distance_(key.first, key.second); }

        //! Get function
        friend inline value_type get(EdgeWeightMap<F> const& edgeWeightMap, EdgeWeightMap<F>::key_type const& key) { return edgeWeightMap[key]; }

    private:
        //! The distance function
        std::function<F(std::size_t, std::size_t)> const& distance_;
};

//! Return the number of vertices of a CompleteGraph
template<typename F>
std::size_t num_vertices(CompleteGraph<F> const& g) { return g.size(); }

//! Return a pair allowing iteration over all vertices
template<typename F>
std::pair<VertexIterator, VertexIterator> vertices(CompleteGraph<F> const& g) { return std::make_pair(VertexIterator(0), VertexIterator(g.size())); }

//! Return a pair allowing iteration over all outgoing edges of a vertex
template<typename F>
std::pair<OutEdgeIterator, OutEdgeIterator> out_edges(VertexDescriptor s, CompleteGraph<F> const& g) { return std::make_pair(OutEdgeIterator(s), OutEdgeIterator(s, g.size())); }

//! Return the out-degree which is constant size - 1 for all vertices
template<typename F>
std::size_t out_degree(VertexDescriptor, CompleteGraph<F> const& g) { return g.size() - 1; }

//! Return the source of an edge
template<typename F>
VertexDescriptor source(EdgeDescriptor e, CompleteGraph<F> const&) { return e.first; }

//! Return the target of an edge
template<typename F>
VertexDescriptor target(EdgeDescriptor e, CompleteGraph<F> const&) { return e.second; }

//! Return the index map
template<typename F>
identity_property_map get(vertex_index_t, CompleteGraph<F> const&) { return identity_property_map(); }

//! Return the distance map
template<typename F>
EdgeWeightMap<F> get(edge_weight_t, CompleteGraph<F> const& g) { return EdgeWeightMap<F>(g.distance()); }

//! Wrapper function for automatic template parameter
template<typename F>
CompleteGraph<F> makeCompleteGraph(std::size_t size, std::function<F(std::size_t, std::size_t)> const& distance) { return CompleteGraph<F>(size, distance); }

//! Compute a metric TSP solution through the points supplied
/*!
 * This function finds a solution through n many points whose pairwise distance is given by a function argument.
 * The supplied distance function needs to satisfy the triangle inequality and must be symmetric.
 * \tparam F The type of the return value of distance
 * \param[in] size The number of points through which the TSP tour should be found
 * \param[in] start The index of the point at which to start
 * \param[in] distance A function taking two std::size_t's and returning the distance between point i and point j
 * \return A vector representing the TSP tour
 */
template<typename F>
std::vector<std::size_t> computeTspTour(std::size_t size, std::size_t start, std::function<F(std::size_t, std::size_t)> const& distance)
{
    std::vector<std::size_t> tour;
    const auto completeGraph = makeCompleteGraph(size, distance);
    metric_tsp_approx_tour_from_vertex(completeGraph, start, std::back_inserter(tour));
    return tour;
}

int main()
{
    typedef std::complex<double> Point;

    const std::vector<Point> points{{.0, .0}, {1.0, 2.0}, {1.0, 5.0}, {2.5, 9.2}, {-100.2, 24.1}, {.1, 10.0}};
    const std::function<double(std::size_t, std::size_t)> distance = [&points] (std::size_t i, std::size_t j) { return std::abs(points[i] - points[j]); };

    const auto tour = computeTspTour(points.size(), 0, distance);

    std::cout << "Found TSP tour:\n";
    std::copy(tour.cbegin(), tour.cend(), std::ostream_iterator<char>(std::cout, " "));

    return EXIT_SUCCESS;
}

Я также рад, если у кого-то есть альтернативное предложение, которое короче или вообще не создает никакого графа, полный граф на самом деле не несет никакой информации, кроме количества его вершин.