हम कक्षा को ग्राफ बूस्ट के तहत मुखौटा करते हैं। भाग 2: अवधारणा समर्थन के कार्यान्वयन को पूरा करना

प्रस्तावना: बूस्ट कॉन्सेप्ट्स
भाग 1: स्रोत वर्ग इंटरफ़ेस के साथ जुड़े बिना संबद्ध प्रकार को जोड़ना

संक्षेप में कार्य याद करते हैं। कोशिकाओं का एक द्वि-आयामी खेल क्षेत्र है, जिनमें से कुछ स्वतंत्र हैं, और कुछ व्यस्त हैं। एक क्षेत्र की स्थिति से दूसरे में मुक्त कोशिकाओं के माध्यम से एक रास्ता खोजने के लिए आवश्यक है। बूस्ट में एल्गोरिथ्म को खोजने का मार्ग लागू किया गया है। लेकिन इसके लिए जरूरी है कि हमारा क्षेत्र एक ग्राफ की परिभाषा के अनुकूल हो। अधिक सटीक रूप से, वर्ग को दो अवधारणाओं को संतुष्ट करना चाहिए - बढ़ावा :: वर्टेक्लिस्टग्राफ और बढ़ावा :: इंसीडेंसग्राफ । उसी समय, मैं खेल के मैदान के इंटरफ़ेस को बदलना नहीं चाहता - बाकी परियोजना के लिए, यह एक ग्राफ़ नहीं है और कभी भी ग्राफ़ नहीं बनेगा।

पिछले भाग में, एक वर्ग को व्याख्या करने के लिए आवश्यक बाहरी संबद्ध प्रकार के कनेक्शन को एक बढ़ावा ग्राफ माना जाता था। बेशक, कुछ प्रकार पर्याप्त नहीं हैं। किसी दिए गए हस्ताक्षर और पुनरावृत्तियों के साथ कई कार्यों को लागू करना भी आवश्यक है, जिसके साथ पुस्तकालय एक ग्राफ़ के रूप में खेल के मैदान में हेरफेर करने में सक्षम होगा।

चलो num_vertices फ़ंक्शन के साथ शुरू करते हैं, जो, जैसा कि आप नाम से अनुमान लगा सकते हैं, ग्राफ वर्टिस की संख्या वापस करना चाहिए। हमारे मामले के लिए, यह खेल मैदान की लंबाई चौड़ाई से गुणा है। प्रकार VerticesSizeType आलेख के पहले भाग में परिभाषित किया गया है (यह वास्तव में int है)।

VerticesSizeType num_vertices(const GameField& graph) { return graph.getWidth() * graph.getHeight(); } 

अब हम पहले पुनरावृत्ति के कार्यान्वयन के लिए आगे बढ़ सकते हैं। वह ग्राफ के सभी शीर्षों की गणना के लिए जिम्मेदार होगा। हम पहले इस बात पर सहमत थे कि पूर्णांक शून्य से num_vertices तक दर्शाए जाएंगे । खरोंच से एक पुनरावृत्ति लिखने से बचने के लिए, हम सहायक वर्ग को बढ़ावा देते हैं :: forward_iterator_helper । यह आपको केवल कुछ मूल ऑपरेटरों: वेतन वृद्धि (++), तुलना (==), और dereference (*) को परिभाषित करके एक पूर्ण पुनरावृत्ति प्राप्त करने की अनुमति देता है। इसके अलावा, खोज एल्गोरिथ्म के लिए आवश्यक है कि एक डिफ़ॉल्ट निर्माता इट्टर के लिए मौजूद हो। स्वाभाविक रूप से, इस रूप में ऑब्जेक्ट का उपयोग असंभव है - उपयोग करने से पहले, पुस्तकालय पुनरावृत्त को सही मान देगा।

सबसे पहले, क्लास इंटरफ़ेस को देखें

 class VertexIteratorImpl : public boost::forward_iterator_helper<VertexIteratorImpl, Vertex, std::ptrdiff_t, Vertex*, Vertex> { public: VertexIteratorImpl(); VertexIteratorImpl(const GameField& field, int index); void operator++ (); bool operator== (const VertexIteratorImpl& anotherIterator) const; Vertex operator*() const; private: bool isValid(); int mIndex; const GameField* mField; }; 

पुनरावृत्तिकर्ता वर्तमान वर्टेक्स की संख्या और प्‍लेंटर को प्‍लेइंग फ़ील्ड में संग्रहीत करता है। बस एक स्पष्ट डिफ़ॉल्ट निर्माता होना चाहिए - यह "कार्य" ऑब्जेक्ट नहीं बनाता है:

 VertexIteratorImpl::VertexIteratorImpl() : mField(NULL) , mIndex(0) { } 

दूसरा निर्माणकर्ता आपको पूरी तरह कार्यात्मक वस्तु बनाने की अनुमति देता है

 VertexIteratorImpl::VertexIteratorImpl(const GameField& field, int index) : mField(&field) , mIndex(index) { } 

isValid - एक सहायक फ़ंक्शन जो यह जाँचता है कि क्या इट्रेटर सही स्थिति में है (गेम फ़ील्ड सेट है, इंडेक्स में एक वैध फ़ंक्शन है)

 bool VertexIteratorImpl::isValid() { return (mField != NULL) && (mIndex < num_vertices(*mField)) && (mIndex >=0); } 

यह देखते हुए कि शीर्ष एक संख्या है, ऑपरेटरों का कार्यान्वयन अत्यंत सरल है, और mIndex क्षेत्र के साथ काम करने के लिए नीचे आता है। यहाँ एक समानता परीक्षण है

 bool VertexIteratorImpl::operator== (const VertexIteratorImpl& anotherIterator) const { return mIndex == anotherIterator.mIndex; } 

यह है कि इटरेटर की वृद्धि कैसे की जाती है - आपको केवल यह जांचने की आवश्यकता है कि क्या सूचकांक अनुलंब संख्या से अधिक है

 void VertexIteratorImpl::operator++ () { if (isValid()) { ++mIndex; } } 

शीर्ष क्रम संख्या वापस करने के लिए Dereferencing आता है

 Vertex VertexIteratorImpl::operator*() const { return mIndex; } 

उसके बाद, ग्राफ़ अवधारणाओं द्वारा आवश्यक एक और फ़ंक्शन बनाना संभव हो जाता है - कोने । यह दो पुनरावृत्तियों के कोने को वापस करना चाहिए - प्रारंभिक और अगले (मानक संग्रह में अंत के एनालॉग) के बाद।

 std::pair<VertexIterator, VertexIterator> vertices(const GameField& graph) { return std::make_pair(VertexIterator(graph, 0), VertexIterator(graph, num_vertices(graph))); } 

वेरटेक्सटाइटर का प्रकार लेख के पहले भाग में परिभाषित किया गया है (यह उर्फ ​​वर्टेकार्टरइंटरप्ल है)। अब किनारों को सेट करें। पहले आपको उन कार्यों की एक जोड़ी को परिभाषित करने की आवश्यकता है जो एक बढ़त प्राप्त कर रहे हैं, अपने प्रारंभिक और अंतिम शीर्ष को वापस कर देंगे।

 Vertex source(Edge edge, const GameField &graph) { return edge.first; } Vertex target(Edge edge, const GameField &graph) { return edge.second; } 

दूसरे पैरामीटर को उनके पास ग्राफ़ को पास करना चाहिए, भले ही ऑपरेशन के लिए इसकी आवश्यकता न हो (हमारे मामले में, एक किनारा एक जोड़ी कोने है)। यह दिए गए शीर्ष से आने वाले किनारों का पुनरावृत्त बनाने के लिए बना हुआ है। इसे लागू करना थोड़ा मुश्किल है, लेकिन अभी भी काफी आदिम है। कार्य की एल्गोरिथ्म: किसी दिए गए के चारों ओर 8 छोरों की जांच करने के लिए, यदि वे स्वतंत्र हैं, तो किनारों हैं, यदि व्यस्त हैं, तो इस दिशा में कोई रास्ता नहीं है। इंटरफेस के साथ शुरू करते हैं

 class OutEdgeIteratorImpl : public boost::forward_iterator_helper<OutEdgeIterator, Edge, std::ptrdiff_t, Edge*, Edge> { public: OutEdgeIteratorImpl(const GameField& field, Vertex cellPosition, int index = 0); OutEdgeIteratorImpl(); Edge operator*() const; void operator++ (); bool operator== (const OutEdgeIterator& other) const; private: Vertex getCurrentPosition() const; Vertex getTargetPosition() const; void updateShift(); bool isValid(); int mShift; Vertex mCellPosition; const GameField* mField; static const int sShiftsX[8]; static const int sShiftsY[8]; }; 

sShiftsX और sShiftsY एरे के साथ x और y कुल्हाड़ियों के साथ निकटवर्ती कोने पर पुनरावृति करने के लिए एरेज़ हैं।

 const int OutEdgeIteratorImpl::sShiftsX[8] = { -1, 0, 1, -1, 1, -1, 0, 1 }; const int OutEdgeIteratorImpl::sShiftsY[8] = { 1, 1, 1, 0, 0, -1, -1, -1}; 

कंस्ट्रक्टर्स के साथ भी यही स्थिति वर्टिकल इटरेटर के लिए थी - डिफॉल्ट डिजाइनर एक डमी ऑब्जेक्ट बनाता है (काम करने के लिए लाइब्रेरी की जरूरत होती है), हम खुद दूसरे डिजाइनर का इस्तेमाल करेंगे।

 OutEdgeIteratorImpl::OutEdgeIteratorImpl() : mField(NULL) , mCellPosition(0) , mShift(0) { } OutEdgeIteratorImpl::OutEdgeIteratorImpl(const GameField& field, Vertex cellPosition, int index/* = 0*/) : mField(&field) , mCellPosition(cellPosition) , mShift(index) { updateShift(); } 

वर्टेक्स ट्रैवर्सल के विपरीत, यह सभी किनारों को एक पंक्ति में वापस करने के लिए यहां काम नहीं करेगा - उनमें से कुछ मौजूद नहीं हो सकते हैं। इसलिए, वेतन वृद्धि ऑपरेटर में अपडेटशिफ्ट विधि शामिल होगी, जिसका कार्य इटरेटर की वर्तमान स्थिति की वैधता की जांच करना है और यदि आवश्यक हो, तो इसे "स्क्रॉल" करें।

 void OutEdgeIteratorImpl::operator++ () { ++mShift; updateShift(); } 

गेम फ़ील्ड GameField :: canPass (int x, int y) की विधि का उपयोग करके जांच की जाती है, यदि यह गलत है (दिए गए सेल का कोई रास्ता नहीं है), तो अगले पड़ोसी सेल को चेक किया जाएगा। बाहर जाने वाले किनारे शून्य से आठ तक हो सकते हैं।

 void OutEdgeIteratorImpl::updateShift() { if (isValid()) { int x, y; std::tie(x, y) = getCoordinates(mCellPosition, *mField); int dx = sShiftsX[mShift]; int dy = sShiftsY[mShift]; if (!mField->canPass(x + dx, y + dy)) { ++mShift; updateShift(); } } } bool OutEdgeIteratorImpl::isValid() { return (mField != NULL) && (mShift < 8) && (mShift >=0); } 

इटरेटर में दो सहायक विधियाँ भी होती हैं जो प्रारंभिक वर्टेक्स (जो कि कंस्ट्रक्टर को पास की गई थी) और आउटगोइंग वन ( mShift ऑफ़सेट के आधार पर गणना की गई ) को वापस करती हैं।

 Vertex OutEdgeIteratorImpl::getCurrentPosition() const { return mCellPosition; } Vertex OutEdgeIteratorImpl::getTargetPosition() const { return getCurrentPosition() + sShiftsX[mShift] + mField->getWidth() * sShiftsY[mShift]; } 

अनुमंडल ऑपरेटर इस जोड़ी को वापस लौटाता है:

 Edge OutEdgeIteratorImpl::operator*() const { return std::make_pair(getCurrentPosition(), getTargetPosition()); } 

बढ़त पुनरावृत्तियों की तुलना में, लंबवत के मामले में, संख्यात्मक सूचकांकों की तुलना करने के लिए कम करता है

 bool OutEdgeIteratorImpl::operator== (const OutEdgeIteratorImpl& other) const { return mShift == other.mShift; } 

और अंतिम चरण बना हुआ है - किनारे पर चलने वाले कार्यों को परिभाषित करने के लिए जो बनाए गए पुनरावृत्तियों के आधार पर काम करते हैं। यह किसी दिए गए शीर्ष के लिए आउटबाउंड एज खोज फ़ंक्शन की तरह दिखेगा

 std::pair<OutEdgeIterator, OutEdgeIterator> out_edges(Vertex v, const GameField& graph) { return std::make_pair(OutEdgeIterator(graph, v, 0), OutEdgeIterator(graph, v, 8)); } 

इंडेक्स 8 के साथ एक ऑब्जेक्ट को अंतिम पुनरावृत्त के रूप में पारित किया जाता है, क्योंकि इस संख्या के साथ किनारों को नहीं किया जा सकता है (वैध मान 0 से 7 तक हैं)। आउटगोइंग किनारों की संख्या का निर्धारण करने के लिए फ़ंक्शन भी OutEdgeIterator पुनरावृत्ति का उपयोग करता है - यह गणना द्वारा किनारों की गणना करता है

 DegreeSizeType out_degree(Vertex v, const GameField& graph) { DegreeSizeType result = 0; std::pair<OutEdgeIterator, OutEdgeIterator> edges = out_edges(v, graph); for (OutEdgeIterator i = edges.first; i != edges.second; ++i) { ++result; } return result; } 

वह सब है। अब आप अवधारणाओं की जाँच के लिए कार्य लिख सकते हैं और परिणाम का आनंद ले सकते हैं - हमारा खेल मैदान एक साथ दो प्रकार के रेखांकन के लिए आवश्यकताओं को संतुष्ट करता है:

  boost::function_requires<boost::VertexListGraphConcept<GameField> >(); boost::function_requires<boost::IncidenceGraphConcept<GameField> >(); 

यह अवधारणाओं के कार्यान्वयन को पूरा करता है। काम करने के लिए पथ खोज एल्गोरिदम के लिए, कुछ और सुधारों की आवश्यकता है - मैं चक्र के अंतिम लेख में उनके बारे में बात करूंगा।