Я пытаюсь сделать следующее:
Есть функция computeTspTour(size, start, distance)
это дает мне приближение к кратчайшему туру через size
много вершин, начиная с start
, Вот, distance
является функциональным объектом, который принимает два индекса и возвращает расстояние между ними.
Я хотел бы использовать boost::graph
«s metric_tsp_approx
, Для этого мне нужен полный график мощности 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;
}
Я также рад, если у кого-то есть альтернативное предложение, которое короче или вообще не создает какого-либо графа, полный граф на самом деле не несет никакой информации, кроме количества его вершин.
Алгоритмы DFS и TSP требуют, чтобы граф был как «список вершин», так и «граф инцидентности» (то есть граф с доступом к соседям вершин).
Ваш график должен иметь что-то вроде
struct traversal_category
: public virtual boost::vertex_list_graph_tag
, public virtual boost::adjacency_graph_tag
, public virtual boost::incidence_graph_tag
{
};
typedef typename boost::adjacency_iterator_generator<CompleteGraph<F>, vertex_descriptor, out_edge_iterator>::type adjacency_iterator;
вместо
typedef vertex_list_graph_tag traversal_category;
typedef void adjacency_iterator;
С этими изменениями плюс некоторые косметические, ваш код проходит компиляцию.
Карта индексов вершин является необязательной, Boost обернет ваш код VertexMap и ColorMap, вероятно, на основе unordered_map. Это будет менее эффективно, чем «идентичность» или аналогичные пользовательские карты, но будет работать.
Удачи!
Ваш код для пользовательского «полного» графика выглядит нормально.
Критическим компонентом, необходимым для DFS, является «карта индекса вершины»: по существу, взаимно-однозначное соответствие между vertex_descriptor и int, так что каждая вершина отображается в число в интервале [0, num_vertices (g)). Для «стандартных» графиков такое отображение известно, и DFS использует некоторое метапрограммирование для определения типа соответствующего ColorMap.
В вашем случае vertex_descriptor — это целое число в пределах правильного интервала, а отображение — «идентичная карта». Вы должны только выразить это с кодом, подобным следующему:
namespace boost{
template<class F>
struct property_map< CompleteGraph<F>, vertex_index_t >
{
typedef identity_property_map type;
//or more fancier
//typedef CompleteGraph<F> graph_t;
//typedef typed_identity_property_map<typename graph_t::vertex_descriptor> type;
typedef type const_type;
};
//then you define a "get" function:
template<class F>
identity_property_map
get(vertex_index_t, const CompleteGraph<F>& /*g -- not used */)
{
return identity_property_map();
}
} //namespace boost
Этого должно быть достаточно. Если для какого-либо алгоритма требуются другие «property_maps» для вашего типа графа, вы можете определить их аналогичным образом.
Удачи!