प्रतिलिपि बनाई जा रही बढ़ावा साथ adjacency_list को :: copy_graph

Question

मैं बढ़ावा ग्राफ लाइब्रेरी का उपयोग कर रहा हूँ और initalise करने के लिए एक MutableGraph एक ग्रिड के रूप में जीवन शुरू करने के लिए कोशिश कर रहा। किनारों को बाद में जीवन में जोड़ा और हटा दिया जाएगा, इसलिए मुझे लगता है कि adjacency_list<vecS,listS,undirectedS> सही विकल्प है।

बीजीएल के बारे में मेरे पढ़ने संकेत दिया है कि समझदार तरीका इन किनारों के साथ यह initalise को boost::copy_graph का उपयोग कर एक boost::grid_graph कि मुक्त करने के लिए मेरे लिए सब प्रारंभिक किनारों कर सकते हैं से कॉपी करने के लिए द्वारा boost::grid_graph का लाभ लेने के लिए होगा। मुझे लगता है कि बनाया भावना सोचा - एक MutableGraph का एक मॉडल है, जो वास्तव में मैं क्या है के लिए VertexListGraph का एक मॉडल से copy_graph प्रतियां।

मैंने शुरुआत में copy_graph के 2-तर्क संस्करण का उपयोग करने की कोशिश की, अस्पष्ट आशा है कि शेष के लिए डिफ़ॉल्ट के साथ कुछ समझदार होगा। यह मामला नहीं है, grid_graph (जिन कारणों से मैं काफी समझ नहीं पाया) में PropertyMap एस का उपयोग किनारों या शिखर के साथ करने की सुविधा नहीं है, इसलिए डिफ़ॉल्ट vertex_copy और edge_copy विफल रहा (एक कंपाइलर के साथ त्रुटि) गुणों की प्रतिलिपि बनाएँ।

2-तर्क संस्करण के बाद से स्पष्ट रूप से उचित मैं आगे बढ़ने और कोने और किनारों कॉपी करने के लिए अपने ही द्विआधारी ऑपरेटर को लागू करने की कोशिश की नहीं मालूम था। यहां तक ​​कि 'नो-ऑप' प्रतिलिपि के साथ यह काम नहीं करता है और साथ ही मुझे आशा है कि (यानी यह संकलित नहीं होता)।

मैं एक साथ रख दिया एक न्यूनतम काम कर उदाहरण है कि समस्या दिखाता है:

#include <boost/graph/adjacency_list.hpp> 
#include <boost/graph/grid_graph.hpp> 
#include <boost/graph/copy.hpp> 

struct Position { 
    int x, y; 
}; 

struct VertexProperties { 
    Position pos; 
}; 

typedef boost::adjacency_list<boost::vecS, boost::listS, boost::undirectedS, 
         VertexProperties> Graph; 

struct MyCopy { 
    template <typename S, typename D> 
    void operator()(const S& /*src*/, D& /*dest*/) { 
    // Nothing for now, deduced types to try and just make it compile 
    // TODO: set values for pos to reflect position on grid. 
    } 
}; 

int main() { 
    boost::array<std::size_t, 2> lengths = { { 3, 3 } }; 
    boost::grid_graph<2> grid(lengths); 

    Graph graph; 
    MyCopy copier; 
    // Using 3-Arg version of copy_graph so we can specify a custom way of copying to create the properties 
    boost::copy_graph(grid,graph,boost::bgl_named_params<MyCopy,boost::vertex_copy_t, 
           boost::bgl_named_params<MyCopy,boost::edge_copy_t> >(copier)); 
} 

यह उदाहरण संकलन नहीं करता है:

g++ -Wextra -Wall -O2 -g -o copytest.o -c copytest.cc 
In file included from /usr/include/boost/graph/grid_graph.hpp:24:0, 
       from copytest.cc:2: 
/usr/include/boost/iterator/transform_iterator.hpp: In constructor ‘boost::transform_iterator<UnaryFunction, Iterator, Reference, Value>::transform_iterator() [with UnaryFunc = boost::detail::grid_graph_vertex_at<boost::grid_graph<2u> >, Iterator = boost::counting_iterator<unsigned int, boost::use_default, boost::use_default>, Reference = boost::use_default, Value = boost::use_default]’: 
/usr/include/boost/graph/copy.hpp:115:55: instantiated from ‘static void boost::detail::copy_graph_impl<0>::apply(const Graph&, MutableGraph&, CopyVertex, CopyEdge, Orig2CopyVertexIndexMap, IndexMap) [with Graph = boost::grid_graph<2u>, MutableGraph = boost::adjacency_list<boost::vecS, boost::listS, boost::undirectedS, VertexProperties>, CopyVertex = MyCopy, CopyEdge = MyCopy, IndexMap = boost::grid_graph_index_map<boost::grid_graph<2u>, boost::array<unsigned int, 2u>, unsigned int>, Orig2CopyVertexIndexMap = boost::iterator_property_map<__gnu_cxx::__normal_iterator<void**, std::vector<void*, std::allocator<void*> > >, boost::grid_graph_index_map<boost::grid_graph<2u>, boost::array<unsigned int, 2u>, unsigned int>, void*, void*&>]’ 
/usr/include/boost/graph/copy.hpp:327:5: instantiated from ‘void boost::copy_graph(const VertexListGraph&, MutableGraph&, const boost::bgl_named_params<P, T, R>&) [with VertexListGraph = boost::grid_graph<2u>, MutableGraph = boost::adjacency_list<boost::vecS, boost::listS, boost::undirectedS, VertexProperties>, P = MyCopy, T = boost::vertex_copy_t, R = boost::bgl_named_params<MyCopy, boost::edge_copy_t>]’ 
/mnt/home/ajw/code/hpcwales/copytest.cc:31:66: instantiated from here 
/usr/include/boost/iterator/transform_iterator.hpp:100:26: error: no matching function for call to ‘boost::detail::grid_graph_vertex_at<boost::grid_graph<2u> >::grid_graph_vertex_at()’ 
/usr/include/boost/graph/grid_graph.hpp:104:7: note: candidates are: boost::detail::grid_graph_vertex_at<Graph>::grid_graph_vertex_at(const Graph*) [with Graph = boost::grid_graph<2u>] 
/usr/include/boost/graph/grid_graph.hpp:100:33: note:     boost::detail::grid_graph_vertex_at<boost::grid_graph<2u> >::grid_graph_vertex_at(const boost::detail::grid_graph_vertex_at<boost::grid_graph<2u> >&) 

कि त्रुटि के मेरे विश्लेषण है कि यह हो रहा है है grid_graph के आंतरिक भाग का डिफ़ॉल्ट रूप से निर्माण करने का प्रयास कर रहा है, जिसे डिफ़ॉल्ट रूप से निर्मित नहीं किया जा सकता है, किसी कारण से जो मुझे बहुत स्पष्ट नहीं है। (क्लैंग वास्तव में मुझे कुछ भी नहीं बताता है मैं यहां g ++ से नहीं देख सकता)।

सवाल:

1. इस सही तरीके से एक परिवर्तनशील ग्राफ initalising एक नियमित ग्रिड के रूप में शुरू करने के लिए के बारे में जाने के लिए है? मैंने शुरू में सोचा था कि ऐसा करने के लिए एक समारोह लिखना बहुत आसान था, लेकिन अब मुझे इतना यकीन नहीं है!
2. orig_to_copy और/या vertex_index नहीं उचित यहाँ का डिफ़ॉल्ट मान क्यों है? मुझे लगता है कि वे दोनों त्रुटि का कारण हैं। (जो, यदि कोई है, तो वास्तव में समस्या का कारण बन रहा है? मैं समझ नहीं सकता कि वर्तमान त्रुटि का मूल कारण क्या है)।
3. इसे ठीक करने का "सही" तरीका क्या है?

Answer 1

आप सही रास्ते पर हैं, लेकिन आपके कोड में दो चीजें बदलने की आवश्यकता है। पहला यह है कि कस्टम वर्टेक्स गुणों को परिभाषित करने का एक विशेष तरीका है। दूसरी बात यह है कि बीजीएल नामित पैरामीटर के लिए एक अलग वाक्यविन्यास (अधिक पसंदीदा और शायद एकमात्र सही है) है।

पहला आइटम पर, the section of the documentation titled Custom Vertex Properties को देखें।

struct vertex_position_t { 
    typedef boost::vertex_property_tag kind; 
}; 

तो फिर तुम boost::property टेम्पलेट में कहीं टैग प्रकार में शामिल हैं: अनिवार्य रूप से, आदेश में एक कस्टम शीर्ष संपत्ति को परिभाषित करने के लिए, आपको पहले एक "टैग प्रकार" (एक struct एक नाम _t में समाप्त होने के साथ) परिभाषित करने की जरूरत कि परिभाषित करता है आंतरिक रूप से संग्रहीत शिखर गुण:

typedef boost::property<boost::vertex_index_t, std::size_t, 
     boost::property<vertex_position_t, Position> > VertexProperties; 

ऊपर typedef को परिभाषित करता है दो आंतरिक रूप से संग्रहीत गुण: सूचकांक और कस्टम "स्थिति"।

दूसरे आइटम पर, नामित पैरामीटर का उपयोग करने के लिए the preferred way एक "विधि श्रृंखला-जैसी" वाक्यविन्यास है। उदाहरण के लिए, यदि कोई फ़ंक्शन दो नामित पैरामीटर, named_param1 और named_param2 स्वीकार करता है, तो boost नामस्थान नाम named_param1 और named_param2 नाम से दो कार्य हैं। boost::named_param1 समारोह named_param1 पैरामीटर के लिए मूल्य स्वीकार करता है और एक वस्तु एक named_param2विधि (इसी तरह, boost::named_param2 समारोह named_param2 पैरामीटर के लिए मूल्य स्वीकार करता है और एक वस्तु एक named_param1विधि होने देता है) होने देता है। आप उस नामित पैरामीटर के मान को सेट करने के लिए विधि को कॉल करते हैं (जो बदले में अन्य समर्थित नाम पैरामीटर के लिए अन्य ऑब्जेक्ट वाले विधियों को देता है)। या तो उपयोग

आदेश मूल्यों val1 उत्तीर्ण करने के लिए और, नाम वाले पैरामीटर named_param1 और named_param2 के लिए val2 आप कर सकते हैं:

boost::named_parameter1(val1).named_param2(val2) 

या:

boost::named_parameter2(val2).named_param1(val1) 

 

संदर्भ के लिए, यहाँ है एक पूर्ण कार्यक्रम जो Graph की किसी ऑब्जेक्ट पर ग्रिड की प्रतिलिपि बनाता है प्रकार:

#include <cassert> 
#include <cstddef> 
#include <cstdlib> 
#include <iostream> 
#include <boost/graph/adjacency_list.hpp> 
#include <boost/graph/copy.hpp> 
#include <boost/graph/graphviz.hpp> 
#include <boost/graph/grid_graph.hpp> 
#include <boost/property_map/property_map.hpp> 

struct vertex_position_t { 
    typedef boost::vertex_property_tag kind; 
}; 

struct Position { 
    std::size_t x, y; 

    Position() 
     : x(0), y(0) 
    { 
    } 
}; 

typedef boost::property<boost::vertex_index_t, std::size_t, boost::property<vertex_position_t, Position> > VertexProperties; 
typedef boost::adjacency_list<boost::vecS, boost::listS, boost::undirectedS, VertexProperties> Graph; 
typedef boost::graph_traits<Graph> GraphTraits; 

namespace detail { 
typedef boost::grid_graph<2> Grid; 
typedef boost::graph_traits<Grid> GridTraits; 

struct grid_to_graph_vertex_copier { 
    typedef boost::property_map< Grid, boost::vertex_index_t>::type grid_vertex_index_map; 
    typedef boost::property_map< ::Graph, boost::vertex_index_t>::type graph_vertex_index_map; 
    typedef boost::property_map< ::Graph, ::vertex_position_t>::type graph_vertex_position_map; 

    const Grid& grid; 
    grid_vertex_index_map grid_vertex_index; 
    graph_vertex_index_map graph_vertex_index; 
    graph_vertex_position_map graph_vertex_position; 

    grid_to_graph_vertex_copier(const Grid& grid_, Graph& graph) 
     : grid(grid_), grid_vertex_index(get(boost::vertex_index_t(), grid_)), 
     graph_vertex_index(get(boost::vertex_index_t(), graph)), 
     graph_vertex_position(get(::vertex_position_t(), graph)) 
    { 
    } 

private: 
    Position grid_vertex_index_to_position(std::size_t idx) const { 
     unsigned num_dims = grid.dimensions(); 
     assert(grid.dimensions() == 2); 

     idx %= grid.length(0) * grid.length(1); 

     Position ret; 
     ret.x = idx % grid.length(0); 
     ret.y = idx/grid.length(0); 

     return ret; 
    } 

public: 
    void operator()(GridTraits::vertex_descriptor grid_vertex, ::GraphTraits::vertex_descriptor graph_vertex) const { 
     std::size_t idx = get(grid_vertex_index, grid_vertex); 
     put(graph_vertex_index, graph_vertex, idx); 
     Position pos = grid_vertex_index_to_position(idx); 
     std::cout << "grid_vertex = " << idx << ", pos.x = " << pos.x << ", pos.y = " << pos.y << std::endl; 
     put(graph_vertex_position, graph_vertex, pos); 
    } 
}; 

struct grid_to_graph_edge_copier { 
    void operator()(GridTraits::edge_descriptor grid_edge, ::GraphTraits::edge_descriptor graph_edge) const { 
    } 
}; 
} 

int main() 
{ 
    boost::array<std::size_t, 2> lengths = { { 3, 5 } }; 
    detail::Grid grid(lengths); 

    Graph graph; 

    boost::copy_graph(grid, graph, boost::vertex_copy(detail::grid_to_graph_vertex_copier(grid, graph)) 
      .edge_copy(detail::grid_to_graph_edge_copier())); 

    std::cout << std::endl; 
    boost::write_graphviz(std::cout, graph); 

    return EXIT_SUCCESS; 
} 

जब मैं इस भाग गया, मैं निम्नलिखित उत्पादन प्राप्त किया:

 
grid_vertex = 0, pos.x = 0, pos.y = 0 
grid_vertex = 1, pos.x = 1, pos.y = 0 
grid_vertex = 2, pos.x = 2, pos.y = 0 
grid_vertex = 3, pos.x = 0, pos.y = 1 
grid_vertex = 4, pos.x = 1, pos.y = 1 
grid_vertex = 5, pos.x = 2, pos.y = 1 
grid_vertex = 6, pos.x = 0, pos.y = 2 
grid_vertex = 7, pos.x = 1, pos.y = 2 
grid_vertex = 8, pos.x = 2, pos.y = 2 
grid_vertex = 9, pos.x = 0, pos.y = 3 
grid_vertex = 10, pos.x = 1, pos.y = 3 
grid_vertex = 11, pos.x = 2, pos.y = 3 
grid_vertex = 12, pos.x = 0, pos.y = 4 
grid_vertex = 13, pos.x = 1, pos.y = 4 
grid_vertex = 14, pos.x = 2, pos.y = 4 

graph G { 
0; 
1; 
2; 
3; 
4; 
5; 
6; 
7; 
8; 
9; 
10; 
11; 
12; 
13; 
14; 
0--1 ; 
1--2 ; 
3--4 ; 
4--5 ; 
6--7 ; 
7--8 ; 
9--10 ; 
10--11 ; 
12--13 ; 
13--14 ; 
1--0 ; 
2--1 ; 
4--3 ; 
5--4 ; 
7--6 ; 
8--7 ; 
10--9 ; 
11--10 ; 
13--12 ; 
14--13 ; 
0--3 ; 
1--4 ; 
2--5 ; 
3--6 ; 
4--7 ; 
5--8 ; 
6--9 ; 
7--10 ; 
8--11 ; 
9--12 ; 
10--13 ; 
11--14 ; 
3--0 ; 
4--1 ; 
5--2 ; 
6--3 ; 
7--4 ; 
8--5 ; 
9--6 ; 
10--7 ; 
11--8 ; 
12--9 ; 
13--10 ; 
14--11 ; 
}