वर्टेक्सलिस्ट के साथ डिजस्ट्रा सबसे छोटा पथ = बूस्ट ग्राफ़ में सूची एस

Question

मैं ग्राफ को बढ़ावा देने के लिए काफी नया हूं। मैं डिज्क्स्ट्रा शॉर्टस्ट पाथ एल्गोरिदम खोजने के लिए एक उदाहरण को अनुकूलित करने की कोशिश कर रहा हूं जो VertexList = vecS का उपयोग करता है। मैंने कशेरुक कंटेनर को सूची में बदल दिया। मैंने सीखा है कि अगर हम सूची का उपयोग करते हैं तो हमें एल्गोरिदम के लिए अपना खुद का vertex_index प्रदान करना होगा। 'Index.boost :: adj_list_vertex_property_map :: ऑपरेटर [] में से कोई मुकाबला नहीं' ऑपरेटर = '[के साथ:

/spvec.cpp:62:20: त्रुटि

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

मैं निम्नलिखित त्रुटि मिलती है ग्राफ़ = बूस्ट :: adjacency_list>, boost :: property>, ValueType = boost :: detail :: error_property_not_found, संदर्भ = boost :: detail :: error_property_not_found &, टैग = बूस्ट :: vertex_index_t, boost :: adj_list_vertex_property_map :: key_type = शून्य *] (i.std :: _ List_iterator < _Tp> :: ऑपरेटर * _Tp = शून्य *, _Tp & = शून्य * &) = सी '

मुझे यकीन है कि मैंने अपना खुद का वर्टेक्स इंडेक्स बनाने में गलती की है। लेकिन यह पता नहीं लगा कि वास्तव में क्या समस्या है। किसी को भी .. मैं गलत क्या कर रहा हूँ पर कुछ सुझाव हैं

Answer 1

बीजीएल वास्तव में सूचियां/सूची के साथ 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 की आवश्यकता है। समस्या को ठीक करने के लिए आप या तो Graphtypedef को vertex_index_t संपत्ति के प्रति-वर्टेक्स संग्रहण को शामिल करने के लिए या associative_property_map जैसे "बाहरी" संपत्ति मानचित्र का उपयोग करने के लिए बदल सकते हैं।

dijkstra-example-listS.cpp उदाहरण ग्राफ typedef को बदलने के दृष्टिकोण का उपयोग करता है। अपने कोड में इस दृष्टिकोण का उपयोग करने के लिए आपको निर्धारित कर सकते हैं:

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

फिर इस पारित:

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 बनाना समस्या हल हो जाती Vertex अनुक्रमणिका नक्शा dijkstra_shortest_paths() को नामित पैरामीटर के रूप में कॉल करें। पीएस: बीजीएल_FORALL_VERTICES() < बूस्ट/ग्राफ़/पुनरावृत्ति/iteration_macros.hpp>