任何人都可以給我一個在boost :: graph中使用smallest_last_vertex_ordering的例子嗎？

Question

我是boost編程的新手，但我希望在頂點着色時使用boost圖形庫。

我已閱讀boost/graph/smallest_last_ordering.hpp中的smallest_last_vertex_ordering的幫助文檔和源代碼。但我不知道如何構造函數smallest_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); 
} 

你能告訴我如何創建正確的類的順序，程度和標記？

非常感謝。

Answer 1

看看執行Order似乎是一個property map它有std :: size_t作爲關鍵和vertex_descriptor作爲value_type。 Degree和Marker是屬性映射，其中vertex_descriptor爲key，std :: size_t爲value_type。這些最後兩張地圖只在內部需要，這就是爲什麼只有兩個參數（圖形和順序屬性圖）有重載的原因。

這裏是使用過載和定向的版本（以避免顯然不受此算法支持環路）的圖表here的示例：

#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; 
} 

和這裏是使用四個參數的一個版本超載，所以你可以看到另一種方式來定義屬性地圖：

#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; 
}