누구든지 boost :: graph에서 smallest_last_vertex_ordering을 사용하는 예제를 줄 수 있습니까?

Question

나는 부스트 프로그래밍에 익숙하지 만, 버텍스 컬러링에 부스트 그래프 라이브러리를 사용하기를 희망한다.

나는 boost/graph/smallest_last_ordering.hpp에서 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); 
} 

은 어떻게 주문, 정도와 마커의 오른쪽 클래스를 만드는 방법을 말해 줄래 : 여기

는 smallest_last_vertex_ordering의 정의는?

대단히 감사합니다.

Answer 1

구현을 보면 Order은 std :: size_t가 key이고 vertex_descriptor가 value_type 인 property map 인 것으로 보입니다. Degree 및 Marker은 vertex_descriptor가 key이고 std :: size_t가 value_type 인 속성 맵입니다. 이 마지막 두 개의 맵은 내부적으로 만 필요하며 두 개의 매개 변수 (그래프 및 주문 속성 맵)가있는 오버로드가있는 이유입니다. 네 개의 변수를 사용하는 버전 여기

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

된다 : 여기

그래프 here의 (명백하게,이 알고리즘에 의해 지원되지 않는 루프를 방지하기 위해) 그 과부하 및 감독 버전을 사용하는 예는 과부하가되면 속성지도를 정의하는 다른 방법을 볼 수 있습니다.

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