Đường dẫn ngắn nhất Dijkstra với VertexList = Danh sách trong đồ thị tăng cường

Question

Tôi khá mới để Tăng đồ thị. Tôi đang cố gắng để thích ứng với một ví dụ cho việc tìm kiếm thuật toán Dijkstra Shortest Path sử dụng VertexList = vecS. Tôi đã thay đổi vùng chứa đỉnh thành ListS. Tôi đã học được rằng chúng ta phải cung cấp vertex_index của riêng mình cho thuật toán để làm việc nếu chúng ta sử dụng listS.

int main(int, char *[]) 
{ 
    typedef float Weight; 
    typedef boost::property<boost::edge_weight_t, Weight> WeightProperty; 
    typedef boost::property<boost::vertex_name_t, std::string> NameProperty; 
    typedef boost::property<boost::vertex_index_t, int> IndexProperty; 

    typedef boost::adjacency_list < boost::listS, boost::listS, boost::directedS, 
    NameProperty, WeightProperty > Graph; 

    typedef boost::graph_traits <Graph>::vertex_descriptor Vertex; 
    typedef boost::graph_traits <Graph>::vertex_iterator Viter; 

    typedef boost::property_map < Graph, boost::vertex_index_t >::type IndexMap; 
    typedef boost::property_map < Graph, boost::vertex_name_t >::type NameMap; 

    typedef boost::iterator_property_map < Vertex*, IndexMap, Vertex, Vertex& > PredecessorMap; 
    typedef boost::iterator_property_map < Weight*, IndexMap, Weight, Weight& > DistanceMap; 

    Graph g; 


    Vertex v0 = boost::add_vertex(std::string("v0"), g); 
    Vertex v1 = boost::add_vertex(std::string("v1"), g); 
    Vertex v2 = boost::add_vertex(std::string("v2"), g); 
    Vertex v3 = boost::add_vertex(std::string("v3"), g); 

    Weight weight0 = 5; 
    Weight weight1 = 3; 
    Weight weight2 = 2; 
    Weight weight3 = 4; 

    boost::add_edge(v0, v1, weight0, g); 
    boost::add_edge(v1, v3, weight1, g); 
    boost::add_edge(v0, v2, weight2, g); 
    boost::add_edge(v2, v3, weight3, g); 


    std::vector<Vertex> predecessors(boost::num_vertices(g)); // To store parents 
    std::vector<Weight> distances(boost::num_vertices(g)); // To store distances 

    IndexMap indexMap; // = boost::get(boost::vertex_index, g); 
    NameMap name; 
    Viter i, iend; 
//Create our own vertex index. This is what I changed in the original code 
    int c = 0; 
    for (boost::tie(i, iend) = vertices(g); i != iend; ++i, ++c) { 
     indexMap[*i] = c; // **Error points to this line** 
     name[*i] = 'A' + c; 
    } 
PredecessorMap predecessorMap(&predecessors[0], indexMap); 
DistanceMap distanceMap(&distances[0], indexMap); 
boost::dijkstra_shortest_paths(g, v0, boost::distance_map(distanceMap).predecessor_map(predecessorMap)); 


    // Extract a shortest path 
    std::cout << std::endl; 
    typedef std::vector<Graph::edge_descriptor> PathType; 
    PathType path; 
    Vertex v = v3; 
    for(Vertex u = predecessorMap[v]; 
    u != v; // Keep tracking the path until we get to the source 
    v = u, u = predecessorMap[v]) // Set the current vertex to the current predecessor,  and the predecessor to one level up 
    { 
    std::pair<Graph::edge_descriptor, bool> edgePair = boost::edge(u, v, g); 
    Graph::edge_descriptor edge = edgePair.first; 
    path.push_back(edge); 
    } 

    // Write shortest path 
    std::cout << "Shortest path from v0 to v3:" << std::endl; 
    float totalDistance = 0; 
    for(PathType::reverse_iterator pathIterator = path.rbegin(); pathIterator !=  path.rend(); ++pathIterator) 
    { 
    std::cout << name[boost::source(*pathIterator, g)] << " -> " <<  name[boost::target(*pathIterator, g)] 
       << " = " << boost::get(boost::edge_weight, g, *pathIterator) <<  std::endl; 

    } 

    std::cout << std::endl; 

    std::cout << "Distance: " << distanceMap[v3] << std::endl; 

    return EXIT_SUCCESS; 
} 

tôi nhận được lỗi sau:

/spvec.cpp:62:20: lỗi: không phù hợp cho 'operator =' trong 'index.boost :: adj_list_vertex_property_map :: operator [] [với Graph = boost :: adjacency_list>, boost :: property>, ValueType = boost :: detail :: error_property_not_found, Reference = boost :: detail :: error_property_not_found &, Tag = boost :: vertex_index_t, boost :: adj_list_vertex_property_map :: key_type = void *] (i.std :: _ List_iterator < _Tp> :: toán tử * với _Tp = void *, _Tp & = void * &) = c '

Tôi chắc chắn tôi đã mắc lỗi khi tạo chỉ mục đỉnh của riêng mình. Nhưng không thể tìm ra chính xác vấn đề là gì. Có ai có một số gợi ý về những gì tôi đang làm sai ..

Answer 1

BGL thực sự có một ví dụ của việc sử dụng dijkstra_shortest_paths với danh sách/danh sách, nhưng nó không được liên kết đến từ các tài liệu HTML: http://www.boost.org/doc/libs/release/libs/graph/example/dijkstra-example-listS.cpp

gì được thông báo lỗi là cố gắng nói với bạn (error: no match for ‘operator=’ in ‘index.boost::adj_list_vertex_property_map...ValueType = boost::detail::error_property_not_found...) là không có lưu trữ trên mỗi đỉnh cho thuộc tính vertex_index_t, đó là nhu cầu của adj_list_vertex_property_map. Để khắc phục sự cố, bạn có thể thay đổi Graphtypedef để bao gồm dung lượng lưu trữ theo từng đỉnh cho thuộc tính vertex_index_t hoặc sử dụng bản đồ thuộc tính "bên ngoài" chẳng hạn như associative_property_map.

Ví dụ dijkstra-example-listS.cpp sử dụng phương pháp thay đổi biểu đồ typedef. Để sử dụng phương pháp này trong mã của bạn, bạn có thể định nghĩa:

typedef boost::adjacency_list <boost::listS, boost::listS, boost::directedS, 
    boost::property<boost::vertex_name_t, std::string, boost::property<boost::vertex_index_t, int> >, 
    boost::property<boost::edge_weight_t, Weight> > Graph; 

Answer 2

Nếu ai đó là quan tâm đến các giải pháp, Tạo một associative_property_map như đề xuất trong câu trả lời trước đó giải quyết vấn đề này:

typedef std::map<vertex_desc, size_t>IndexMap; 
    IndexMap mapIndex; 
    boost::associative_property_map<IndexMap> propmapIndex(mapIndex); 
    //indexing the vertices 
    int i=0; 
    BGL_FORALL_VERTICES(v, g, pGraph) 
    { 
     boost::put(propmapIndex, v, i++); 
    } 

Sau đó chuyển thông tin này Vertex index map tới hàm dijkstra_shortest_paths() gọi là tham số được đặt tên. PS: BGL_FORALL_VERTICES() được xác định trong < boost/graph/iteration/iteration_macros.hpp>