グラフBoostの下のクラスをマスクします。 パート2：コンセプトサポートの実装の完了

プロローグ：ブーストコンセプト

パート1：ソースクラスインターフェイスに干渉することなく関連する型を接続する



タスクを簡単に思い出してください。 セルには2次元の遊び場があり、その一部は無料で、一部は忙しいものです。 1つのフィールド位置から別の位置へのフリーセルを通るパスを見つける必要があります。 パス検索アルゴリズムはBoostに実装されています。 ただし、フィールドがグラフの定義に適合することが必要です。 より正確には、クラスは、 boost :: VertexListGraphおよびboost :: IncidenceGraphの 2つの概念を満たす必要があります。 同時に、私は競技場のインターフェースを変更したくありません-プロジェクトの残りの部分では、これはグラフではなく、グラフになりません。



最後の部分では、クラスをブーストグラフとして解釈するために必要な外部関連型の接続について検討しました。 もちろん、一部のタイプでは十分ではありません。 また、ライブラリがプレイフィールドをグラフとして操作できるように、特定のシグネチャとイテレータでいくつかの関数を実装する必要があります。



名前から推測できるように、 num_vertices関数から始めましょう。これはグラフの頂点の数を返すはずです。 私たちの場合、これは競技場の長さに幅を掛けたものです。 タイプVerticesSizeTypeは 、記事の最初の部分で定義されています （実際にはintです）。

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

これで、最初のイテレーターの実装に進むことができます。 彼はグラフのすべての頂点を列挙する責任があります。 以前、頂点はゼロからnum_verticesまでの整数で示されることに同意しました 。 イテレータを最初から記述するのを避けるために、補助クラスboost :: forward_iterator_helperを使用します。 増分（++）、比較（==）、および間接参照（*）といった基本的な演算子をいくつか定義するだけで、本格的なイテレーターを取得できます。 さらに、検索アルゴリズムでは、イテレーターのデフォルトコンストラクターが存在する必要があります。 当然、この形式ではオブジェクトの使用は不可能です-使用する前に、ライブラリはイテレータに正しい値を割り当てます。



まず、クラスインターフェイスを見てみましょう

 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) { }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

2番目のコンストラクターを使用すると、完全に機能するオブジェクトを作成できます

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

逆参照は、頂点番号を返すことになります

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

その後、グラフの概念に必要な別の関数- 頂点を作成することが可能になります。 頂点の2つのイテレータを返す必要があります-最初と最後の次（標準コレクションのend（）のアナログ）。

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

タイプVertexIteratorは、記事の最初の部分で定義されています （これはエイリアスVertexIteratorImplです）。 次に、エッジを設定します。 最初に、エッジを受け取って、最初と最後の頂点を返す関数のペアを定義する必要があります。

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

2番目のパラメーターは、操作に必要ない場合でもグラフを渡す必要があります（この場合、エッジは頂点のペアです）。 指定された頂点から来るエッジの反復子を作成するために残ります。 実装はもう少し難しいですが、それでもかなり原始的です。 作業のアルゴリズム：指定された頂点の周りの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};
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

コンストラクターの場合と同じ状況が頂点イテレーターの場合でした-デフォルトのデザイナーはダミーのオブジェクトを作成し（ライブラリが機能するために必要です）、自分で2番目のデザイナーを使用します。

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

頂点トラバーサルとは異なり、ここではすべてのエッジを連続して返すことはできません。一部のエッジは存在しない場合があります。 したがって、増分演算子にはupdateShiftメソッドが含まれます。 このメソッドのタスクは、イテレーターの現在の位置の有効性をチェックし、必要に応じてさらに「スクロール」することです。

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

チェックは、ゲームフィールドGameField :: canPass（int x、int y）のメソッドを使用して実行され、falseが返された場合（指定されたセルへの道がない）、次の隣接セルがチェックされます。 発信エッジは、0〜8です。

 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オフセットに基づいて計算された）を返す2つの補助メソッドも含まれています。

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

それだけです これで、概念をチェックするための関数を作成し、結果を楽しむことができます-私たちの競技場は、同時に2種類のグラフの要件を満たします。

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

これで概念の実装が完了しました。 パス検索アルゴリズムを機能させるには、さらにいくつかの改善が必要です。それらについては、サイクルの最終記事で説明します。