1

私は次のことを達成しようとしてcomputeTspTour(size, start, distance)いsizeますstart。は、2 つのインデックスを取り、distanceそれらの間の距離を返す関数オブジェクトです。

を活用したいと思いboost::graphますmetric_tsp_approx。このためには、カーディナリティの完全なグラフが必要なsizeので、これには暗黙的に定義されたグラフを使用して、役に立たない単純な巨大なグラフ構造を作成しないようにします。

すべて正常に動作しているように見えますが、私の問題は、metric_tsp_approxある時点dijkstra_shortest_pathsで を定義する を使用することColorMapです。これにより、次の 2 つの問題が発生します。

/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は次のとおりです。長くなって申し訳ありませんが、簡単であることを願っています。それが行うことは、関数の戻り値の型を指定するCompleteGraph1 つのテンプレート パラメーターを持つclass をセットアップすることです。このクラスには、および であるために必要な反復子があるため、を実行できます。FdistanceVertexListGraphIncidenceGraphtsp_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;
}

また、誰かがより短い、またはグラフの作成をまったく回避する代替提案を持っている場合も嬉しく思います。完全なグラフには、頂点の数以外の情報は実際には含まれていません。

4

2 に答える 2

1

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 はおそらく unordered_map に基づいて VertexMap と ColorMap でコードをラップします。「アイデンティティ」または同様のカスタム マップよりも効率は低くなりますが、機能します。

幸運を！

于 2013-10-31T07:02:22.280 に答える
0

カスタムの「完全な」グラフのコードは問題ないようです。

DFS に必要な重要なコンポーネントは「頂点インデックス マップ」です。基本的に、各頂点が間隔 [0, num_vertices(g)) 内の数値にマップされるように、vertex_descriptor と int が 1 対 1 で対応します。「標準」グラフの場合、そのようなマッピングは既知であり、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」が必要なアルゴリズムがある場合は、同様の方法でそれらを定義できます。

幸運を！

于 2013-10-30T09:13:59.453 に答える