1

ブースト プログラミングは初めてですが、頂点カラーリングでブースト グラフ ライブラリを使用したいと考えています。

私はboost/graph/smallest_last_ordering.hppにあるsmallest_last_vertex_orderingのヘルプドキュメントとソースコードを読みました。しかし、関数 minimum_last_vertex_ordering のパラメーターを作成する方法がわかりません。

ここでは、smallest_last_vertex_ordering の定義を示します。

template <class VertexListGraph, class Order, class Degree, class Marker>
  void 
  smallest_last_vertex_ordering(const VertexListGraph& G, Order order, 
                            Degree degree, Marker marker) {
    typedef typename boost::graph_traits<VertexListGraph> GraphTraits;
    typedef typename GraphTraits::vertex_descriptor Vertex;
    //typedef typename GraphTraits::size_type size_type;
    typedef std::size_t size_type;

    const size_type num = num_vertices(G);

    typedef typename boost::property_map<VertexListGraph, vertex_index_t>::type ID;
    typedef bucket_sorter<size_type, Vertex, Degree, ID> BucketSorter;

    BucketSorter degree_bucket_sorter(num, num, degree,  
                                  get(vertex_index,G));

    smallest_last_vertex_ordering(G, order, degree, marker, degree_bucket_sorter);
 }

Order、Degree、Marker の適切なクラスを作成する方法を教えてもらえますか?

どうもありがとうございました。

4

1 に答える 1

1

実装を見ると、キーとして std::size_t を持ち、value_type として vertex_descriptor を持つプロパティ マップOrderのようです。およびvertex_descriptor をキーとし、std::size_t を value_type とするプロパティ マップです。これらの最後の 2 つのマップは内部的にのみ必要であり、2 つのパラメーター (グラフと順序プロパティ マップ) のみを持つオーバーロードが存在するのはそのためです。DegreeMarker

これは、そのオーバーロードと有向バージョン (明らかにこのアルゴリズムではサポートされていないループを避けるため) を使用した例です。

#include <iostream>
#include <string>

#include <boost/graph/adjacency_list.hpp>
#include <boost/property_map/shared_array_property_map.hpp> //this should be included from smallest_last_ordering.hpp
#include <boost/graph/smallest_last_ordering.hpp>

int main()
{
    typedef boost::adjacency_list<boost::vecS,boost::vecS,boost::directedS> Graph;
    typedef boost::graph_traits<Graph>::vertex_descriptor VertexDesc;

    Graph g;
    VertexDesc A=add_vertex(g);
    VertexDesc B=add_vertex(g);
    VertexDesc C=add_vertex(g);
    VertexDesc D=add_vertex(g);
    VertexDesc E=add_vertex(g);

    add_edge(A,C,g);
    add_edge(A,E,g);
    add_edge(C,B,g);
    add_edge(E,B,g);
    add_edge(C,D,g);
    add_edge(B,D,g);
    add_edge(E,D,g);

    boost::vector_property_map<VertexDesc> order;

    smallest_last_vertex_ordering(g, order);

    std::string names[]={"A","B","C","D","E"};

    for(std::size_t index=0; index<num_vertices(g); ++index)
    {
        std::cout << names[order[index]] <<  " ";
    }
    std::cout << std::endl;
}

プロパティ マップを定義する別の方法を確認できるように、4 つのパラメーターのオーバーロードを使用するバージョンを次に示します。

#include <iostream>
#include <string>
#include <map>

#include <boost/graph/adjacency_list.hpp>
#include <boost/property_map/shared_array_property_map.hpp> //this should be included from smallest_last_ordering.hpp
#include <boost/graph/smallest_last_ordering.hpp>

int main()
{
    typedef boost::adjacency_list<boost::vecS,boost::vecS,boost::directedS> Graph;
    typedef boost::graph_traits<Graph>::vertex_descriptor VertexDesc;

    Graph g;
    VertexDesc A=add_vertex(g);
    VertexDesc B=add_vertex(g);
    VertexDesc C=add_vertex(g);
    VertexDesc D=add_vertex(g);
    VertexDesc E=add_vertex(g);

    add_edge(A,C,g);
    add_edge(A,E,g);
    add_edge(C,B,g);
    add_edge(E,B,g);
    add_edge(C,D,g);
    add_edge(B,D,g);
    add_edge(E,D,g);

    typedef std::map<std::size_t,VertexDesc> OrderMap;
    OrderMap order;
    boost::associative_property_map<OrderMap> order_prop_map(order);

    typedef std::map<VertexDesc,std::size_t> Map;
    Map degree;
    Map marker;
    boost::associative_property_map<Map> degree_prop_map(degree);
    boost::associative_property_map<Map> marker_prop_map(marker);

    smallest_last_vertex_ordering(g, order_prop_map, degree_prop_map, marker_prop_map);

    //another alternative
    // std::vector<VertexDesc> order(num_vertices(g));
    // std::vector<std::size_t> degree(num_vertices(g));
    // std::vector<std::size_t> marker(num_vertices(g));
    // smallest_last_vertex_ordering(g, make_iterator_property_map(&order[0],boost::identity_property_map()), make_iterator_property_map(&degree[0],get(boost::vertex_index,g)), make_iterator_property_map(&marker[0],get(boost::vertex_index,g)));

    std::string names[]={"A","B","C","D","E"};

    for(std::size_t index=0; index<num_vertices(g); ++index)
    {
        std::cout << names[order[index]] <<  "(" << degree[order[index]] << "," << marker[order[index]] << ") ";
    }
    std::cout << std::endl;
}
于 2013-04-28T15:12:25.470 に答える