BGL(boost graph Library)(0-7)

BGL公式サイト入口Boostライブラリ説明
BGLの用途は、一部の図の構造にインタフェースを提供し、内部の詳細を隠すためにbuiltを必要としないが、コンパイラは必ずoptimizedの3つの方法でSTLを得ることである.

アルゴリズム/データ構造各アルゴリズムは、データ構造に関係なく書かれ、異なるクラスのコンテナで使用できるようにします.符号量はO(m+n),mはアルゴリズム数,nは容器数である.

関数オブジェクト拡張ユーザは、関数オブジェクトによってSTLを自分で修正することができる.

要素タイプパラメトリックstd::list,BGLはSTLのような方式

を採用している.

アルゴリズム/データ構造相互接続まず、BGLのグラフィックアルゴリズムを特定のグラフィックデータ構造の詳細を抽出できるインタフェースに書き込む.STLのように、BGLは反復器を使用してデータ構造の遍歴インタフェースを定義する.3つの異なるグラフィック遍歴モードがあります.グラフィック内のすべての頂点を遍歴し、すべてのエッジを遍歴し、グラフィックの隣接構造(頂点から各隣接構造)に沿っています.各遍歴モードには独立した反復器があり、この汎用インタフェースはbreadth_first_search()のようなテンプレート関数は,ポインタリンクノードを用いたグラフィックから配列で符号化されたグラフィックまで,様々なグラフィックデータ構造を処理することができる.この柔軟性はグラフィック分野で特に重要である.グラフィックデータ構造は、通常、特定のアプリケーションに対してカスタマイズされます.従来、プログラマがアルゴリズム実装を再利用する場合は、それらのグラフィックデータをグラフィックライブラリの所定のグラフィック構造に変換/コピーする必要があります.図書館はLEDA、GTL、Stanford GraphBaseのようです.Fortranで記述されたグラフィックアルゴリズムは特にそうである.これはグラフィックアルゴリズムの再利用を深刻に制限している.対照的に、外部適応BGL汎用グラフィックアルゴリズムを使用すると、カスタマイズされた(または残された)グラフィック構造をそのまま使用できます(「既存のグラフィックをBGLに変換する方法」を参照).外部アダプティブは、アダプタオブジェクト内にデータを配置することなく、データ構造の周りに新しいインタフェースをパッケージします.BGL界面は丹念に設計され,適応性が容易になった.これを実証するために,BGLパターンアルゴリズムにおいて,種々のパターン構造(LEDAパターン,Stanford GraphBaseパターン,さらにはFortranパターンアレイ)を用いたインタフェースコードを確立した.

は、訪問者によって拡張BGLを実現するグラフアルゴリズムが拡張可能である.BGLは,複数の方法を有する関数オブジェクトにすぎないアクセス者の概念を導入した.グラフィックアルゴリズムでは、通常、ユーザー定義の操作を挿入するためにいくつかの重要なイベントポイントが使用されます.アクセス・オブジェクトには、各イベント・ポイントで呼び出される異なる方法があります.特定のイベントポイントと対応するアクセス者メソッドは、特定のアルゴリズムに依存します.通常start_が含まれますvertex(),discover_vertex(),inspect_edge(),tree_edge()とfinish_vertex()などの方法.

頂点とエッジ属性の多パラメータ化BGLに共通する第3の方法はSTLコンテナ内の要素タイプのパラメータ化に似ているが、図形にとって物語はもっと複雑である.アトリビュート(Attributes)と呼ばれる値を、シェイプの頂点とエッジに関連付ける必要があります.また、通常、複数のアトリビュートを各頂点とエッジに関連付ける必要があります.これは私たちが多パラメータ化することを意味します.STL std::listクラスの要素タイプにはパラメータTがあります.同様に、BGLクラスには、頂点とエッジの「プロパティ」のテンプレートパラメータがあります.属性は、属性のパラメータ化タイプを指定し、属性に識別ラベルを割り当てます.このラベルは、エッジまたは頂点が持つ可能性のある複数のプロパティを区別するために使用します.特定の頂点またはエッジにアタッチされたアトリビュート値は、アトリビュートマッピングで取得できます.各プロパティには、個別のプロパティマッピングがあります.従来のグラフィックライブラリとグラフィック構造は、グラフィックプロパティのパラメータ化において低下しています.これは、グラフデータ構造がアプリケーションにカスタマイズされなければならない主な理由の1つです.BGLクラスの属性のパラメータ化は、繰り返し使用に非常に適しています.

アルゴリズム#アルゴリズム#
コアアルゴリズムモードと一連の図アルゴリズム:コアアルゴリズムモード:

Breadth First Search

Depth First Search

Uniform Cost Search BGLは、コアアルゴリズムモードで図上に数値を計算することはなく、図アルゴリズムのためにブロックを構築するだけである.図アルゴリズムは、

を含む.

Dijkstra's Shortest Paths

Bellman-Ford Shortest Paths

Johnson's All-Pairs Shortest Paths

Kruskal's Minimum Spanning Tree

Prim's Minimum Spanning Tree

Connected Components

Strongly Connected Components

Dynamic Connected Components (using Disjoint Sets)

Topological Sort

Transpose

Reverse Cuthill Mckee Ordering

Smallest Last Vertex Ordering

Sequential Vertex Coloring

データ構造
2つの図タイプを提供し、エッジリストアダプタの隣接テーブルを提供します.隣接マトリクス;エッジリスト;その中で最も一般的なのは隣接表です.高度にパラメータ化され、状況に応じて最適化されます.

int main(int,char*[])
  {
    // create a typedef for the Graph type
    typedef adjacency_list Graph;//  vector             ，  

    // Make convenient labels for the vertices
    enum { A, B, C, D, E, N };
    const int num_vertices = N;
    const char* name = "ABCDE";

    // writing out the edges in the graph
    typedef std::pair Edge;
    Edge edge_array[] = 
    { Edge(A,B), Edge(A,D), Edge(C,A), Edge(D,C),
      Edge(C,E), Edge(B,D), Edge(D,E) };
    const int num_edges = sizeof(edge_array)/sizeof(edge_array[0]);

    // declare a graph object
    Graph g(num_vertices);

    // add the edges to the graph object
    for (int i = 0; i < num_edges; ++i)
      add_edge(edge_array[i].first, edge_array[i].second, g);
    ...
    return 0;
  }

add_を使用する以外はedge()インタフェース、反復器も使用できます.

Graph g(edge_array, edge_array + sizeof(edge_array) / sizeof(Edge), num_vertices);`

また、点数も一定ではなくadd_を使用できますvertex() & remove_vertex()エッジセットアクセス:edges()が返す反復器、source()とtarget()がエッジに接続されたポイント

  int main(int,char*[])
  {
    // ...
    std::cout << "edges(g) = ";
    graph_traits::edge_iterator ei, ei_end;
    for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
//tie      pair       。     ei ei_end;
        std::cout << "(" << index[source(*ei, g)] 
                  << "," << index[target(*ei, g)] << ") ";
    std::cout << std::endl;
    // ...
    return 0;
  }

隣接構造:std::for_each(vertices(g).first, vertices(g).second, exercise_vertex(g)); exercise_の使用vertexは、実行中に画像への参照を保持するためです.異なる図タイプで再利用するためにテンプレート化
頂点記述子は、以下のセクションで説明するout_に使用できる各グラフィックタイプによって提供されます.edges(),in_edges(),adjacent_vertices()と属性マッピング関数は、グラフィックに関する情報にアクセスします.vertex_descriptorタイプgraph_traitsクラスが取得します.scope::operator(graph_traitsタイプ)の左側のタイプはテンプレートパラメータ(Graphタイプ)に依存するため、以下で使用するtypenameキーワードが必要です.これは、通信の適用方法を定義する方法です.

  template  struct exercise_vertex {
    //...
    typedef typename graph_traits
      ::vertex_descriptor Vertex;
    void operator()(const Vertex& v) const
    {
      //...
    }
    //...
  };

エッジの説明えっじのきじゅつ:out_edges()関数、2つのパラメータ:定点と図オブジェクト.頂点のすべてのエッジのインタフェースを提供するpair反復器を返し、エッジ記述子オブジェクトを与えるエッジ反復器dereferenceのいずれかを返します.(頂点記述子に類似)

  template  struct exercise_vertex {
    //...
    void operator()(const Vertex& v) const
    {
      typedef graph_traits GraphTraits;
      typename property_map::type index = get(vertex_index, g);

      std::cout << "out-edges: ";
      typename GraphTraits::out_edge_iterator out_i, out_end;
      typename GraphTraits::edge_descriptor e;
      for (boost::tie(out_i, out_end) = out_edges(v, g); 
           out_i != out_end; ++out_i) {
        e = *out_i;
        Vertex src = source(e, g), targ = target(e, g);
        std::cout << "(" << index[src] << "," 
                  << index[targ] << ") ";
      }
      std::cout << std::endl;
      //...
    }
    //...
  };

in_edges()と同様に、(双方向図を前提とし、隣接テーブル構造のみに使用される)アルゴリズムは、グラフィックのエッジを表示する必要がなく、頂点のみに関心を持つ場合があります.したがって、グラフィックインタフェースには、AdjacencyGraphインタフェースのadjacent_も含まれます.vertices()関数は、隣接する頂点への直接アクセスを提供します.この関数は、隣接する反復器のペアを返します.dereference隣接反復器は、隣接する頂点の頂点記述子を与える.塗り:重み付け.一般的に1つのアルゴリズムは1つの属性しか使用するので、属性と図オブジェクトはそれぞれ記憶すべきである.属性には、内部記憶属性/外部記憶属性の2種類がある.内部属性は通常テンプレートプラグインを用いる、外部属性の方法が多い.直接格納方法:点またはエッジマッピングのマッピング.vecS(すなわちvector、ある章を参照)では、このマッピング型コンテナは自分でインデックスを割り当て、vertex_を使用します.index_tは検索するが、辺は(くだらないことが多すぎるとインデックスを付けるのではないか)訪問者拡張アルゴリズムでは一般的にlib中のアルゴリズムは十分に使用できるが、完全に同じではない可能性が高い.例えばDijアルゴリズムは通常最短距離を記録するが、最短経路ツリーを使用する必要がある可能性がある.1つの方法は、最短パスツリーに各ノードの先頭を記録することである.STLでは、この計算はfunctorによって実現する.これは各アルゴリズムのオプションパラメータである.BGLではこれは観光客によって実現される.観光客はfunctorで、さまざまな方法で呼び出されます(vistorの章で詳しく説明します.)各方法はアルゴリズムのある点で呼び出すことができる.BGLはいくつかの一般的なタスクの訪問者を提供した.BGLからvisitorを自分で作成することができ、ここではまず接頭辞記録の実現と使用について説明する.Dijkstraを例として、Dijkstra visitorプレフィックスを作成するアクセス者を記録する機能は2つの部分に分けられる.アクセス可能なプレフィックス属性を格納するために、属性マッピングを用いる.その後、接頭辞訪問者は、記録する親にのみ責任を負う.レコードが作成されましたpredessorプロパティクラスとテンプレートは接頭辞プロパティマッピングにあります.このアクセス者には1つの方法しかないので、dijkstra_を継承します.visitorは、残りに空白の方法を提供する.コンストラクション関数は、属性を使用するオブジェクトをマッピングし、データメンバーに保存します.レビュー:m_冒頭の説明はクラスメンバー変数であり,構造関数の意図はpをm_に格納することである.このprotectedに行きます.そしてまたテンプレート関数

  template 
  class record_predecessors : public dijkstra_visitor<>
  {
  public:
    record_predecessors(PredecessorMap p)
      : m_predecessor(p) { }

    template 
    void edge_relaxed(Edge e, Graph& g) {
      // set the parent of the target(e) to source(e)
      put(m_predecessor, target(e, g), source(e, g));
    }
  protected:
    PredecessorMap m_predecessor;
  };

ソースをターゲット頂点の前身として記録する、relaxのたびに前の値を上書きし、putを用いて接頭辞を記録する.訪問者のedge_filter通知アルゴリズムはexplore()をいつ有効にするか、この場合、最短パスツリーでエッジのみを通知するのでtree_を作成します.edge_tag. 接頭辞アクセスの作成を容易にするには、helperを次のように有効にします.

//      ？     make_,   record_   
  template 
  record_predecessors
  make_predecessor_recorder(PredecessorMap p) {
    return record_predecessors(p);
  }

次のように使用できます.

vector p(num_vertices(G), graph_traits::null_vertex());
 //  (  ,   )
  dijkstra_shortest_paths(G, s, distance_map(&d[0]). 
                          visitor(make_predecessor_recorder(&p[0])));
//      ,  visitor            
  cout << "parents in the tree of shortest paths:" << endl;
  for(vi = vertices(G).first; vi != vertices(G).second; ++vi) {
    cout << "parent(" << *vi;
    if (p[*vi] == graph_traits::null_vertex())
      cout << ") = no parent" << endl; 
    else 
      cout << ") = " << p[*vi] << endl;
  }

隣接マトリクス:一般的に密グラフのエッジリストで使用されます.任意のエッジ反復と実装を使用できます.