Dijkstra最短パス（VertexList =ブーストグラフのリスト）

Question

私はブーストグラフが新しくなりました。私は、VertexList = vecSを使ったDijkstra Shortest Pathアルゴリズムを見つけるための例を適応しようとしています。頂点コンテナをListSに変更しました。私は、listSを使用する場合、アルゴリズムが動作するために独自のvertex_indexを用意しなければならないことを知りました。

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

私は次のエラーを取得する：

/spvec.cpp:62:20：エラー：index.boost」内の '演算子=' の一致なし:: adj_list_vertex_property_map ::演算子[] [とタグ= boost :: vertex_index_t、boost :: adj_list_vertex_property_map :: key_type = boost :: adjacency_list>、boost :: adjacency_list>、boost :: adjacency_list>、boost :: adjacency_list> void *]（i.std :: _List_iterator）< _Tp :: ::演算子* _Tp = void *、_Tp & = void * &）= c '

私は自分の頂点インデックスを作成するのに間違いを犯したと確信しています。しかし、何が問題かを正確に突き止めることはできませんでした。誰もが...私が間違っているのかについていくつかの提案を持っています

Answer 1

BGLは、実際のリスト/リストをdijkstra_shortest_pathsを使用する例がありますが、それは、HTML文書からリンクされていない：http://www.boost.org/doc/libs/release/libs/graph/example/dijkstra-example-listS.cpp

エラーメッセージは何ですか（error: no match for ‘operator=’ in ‘index.boost::adj_list_vertex_property_map...ValueType = boost::detail::error_property_not_found...）は、vertex_index_tプロパティのための頂点ごとのストレージがないということです。これはadj_list_vertex_property_mapに必要なものです。問題を修正するには、vertex_index_tプロパティの頂点ごとのストレージを含めるか、associative_property_mapなどの「外部」プロパティマップを使用するようにGraphtypedefを変更します。

dijkstra-example-listS.cppの例では、グラフtypedefを変更する方法が使用されています。あなたのコードでは、このアプローチを使用するには、定義することができます。

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

誰かが解決策に関心がある場合、前の回答で提案されているようassociative_property_mapを作成する問題を解決：

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++); 
    } 

は、次にこれを渡します頂点インデックスは、指定されたパラメータとしてdijkstra_shortest_paths（）コールにマップされます。 PS：BGL_FORALL_VERTICES（）が<で定義されています。boost/graph/iteration/iteration_macros.hpp>