C++ Boost 

subgraph<Graph>

副グラス・クラスはグラフとその副グラフの進路を保持する機構を提供する。 もし G' の頂点集合がグラフ G の頂点集合の部分集合であり かつもし G' の辺集合が G の辺集合の部分集合であるなら、 グラフ G' はグラフ G の副グラフである。すなわち、 もし G'=(V',E') かつ G=(V,E) ならば、もし V' が V の部分集合で E' が E の部分集合ならば G' は G の副グラフである。誘導副グラフ は頂点集合 V' で指定することにより、それから V' 中の二つの頂点を結ぶ 元のグラフからの全ての辺を選択することにより作られた副グラフである。 それでこの場合E' = {(u,v) in E: u,v in V'} である。Figure 1 は グラフ G0 と二つの副グラフ G1 と G2 を示す。G1 のための辺集合はE1 = { (E,F), (C,F) } であり、 G2 のための辺集合は E2 = { (A,B) } である。副グラフの外に交差した (E,B) と (F,D) のような辺は 副グラフの辺集合中にはない。

[訳注: (F,D) は (B,C) ではないだろうか？]

Figure 1:木構造中で保持された、 入れ子にされた副グラフを伴うグラフ。

subgraph クラスは誘導副グラフを実装する。メインのグラフとその副 グラフは木データ構造中に保持される。メインのグラフは根で、副グラフは 根の子または他の副グラフの子のどちからである。この木中の全てのノードは 根のグラフも含めて、subgraph クラスのインスタンスである。 subgraph の実装は木中の各ノードがその親の誘導副グラフであることを 確実にする。subgraph クラスは BGL グラフのインターフェースを 実装し、それで各副グラフ・オブジェクトはグラフとして扱うことができる。

Example

この例のための完全なソース・コードは example/subgraph.cpp 中に ある。グラフと副グラフを作成するために、最初に根グラフ・オブジェクトを作成 する。ここで基礎にあるグラフの実装として adjacency_list を使う。 基礎にあるグラフは vertex_index と edge_index の内部的 プロパティを持つ必要があるので、隣接リストに辺の添え字プロパティを付け加え る。頂点の添え字プロパティは adjacency_list に組み込まれているので、 付け加える必要はない。Figure 1 中でグラフと副グラフを作っているつもりであり、 合計六つの頂点を必要とするだろう。 
typedef adjacency_list_traits Traits;
typedef subgraph< adjacency_list > > Graph;

const int N = 6;
Graph G0(N);

enum { A, B, C, D, E, F};  // G0 中の頂点を便利よく引用するため
次に二つの空の副グラフ・オブジェクトを作成し、GO をその親と指定 する。 
Graph& G1 = G0.create_subgraph(), G2 = G0.create_subgraph();
enum { A1, B1, C2 }; // G1 中の頂点を便利よく引用するため
enum { A2, B2 };     // G2 中の頂点を便利よく引用するため
add_vertex 関数を使って、根グラフから副グラフへ頂点を付け加える ことができる。グラフの実装は VertexList=vecS である adjacency_list であるから、範囲 [0,6) 内の整数 (または この場合列挙体) を頂点記述子として使うことができる。 
add_vertex(C, G1); // 大域頂点 C は G1 にとって局所的な A1 になる
add_vertex(E, G1); // 大域頂点 E は G1 にとって局所的な B1 になる
add_vertex(F, G1); // 大域頂点 F は G1 にとって局所的な C1 になる

add_vertex(A, G2); // 大域頂点 A は G2 にとって局所的な A2 になる
add_vertex(B, G2); // 大域頂点 B は G2 にとって局所的な B2 になる
次に add_edge 関数を用いてメインのグラフに辺を付け加えることが できる。 
add_edge(A, B, G0);
add_edge(B, C, G0);
add_edge(B, D, G0);
add_edge(E, B, G0);
add_edge(E, F, G0);
add_edge(F, D, G0);
同様に add_edge 関数を使って G1 のような副グラフに辺を 付け加えることができる。各副グラフは独自の頂点記述子と辺記述子を持ち、 それを局所記述子と呼ぶ。根グラフの頂点記述子と辺記述子を大域 記述子と呼ぶ。上で、大域頂点記述子をグラフに頂点を付け加えるために使った。 しかしながら、大部分の subgraph 関数は局所記述子と共に動作する。 それで、以下の add_edge の呼び出しの中で、大域辺 (C,F) (また は数値的には(2,5)) の (副グラフ G1 のための) 局所バージョンである辺 (A1,C1) (または数値的には (0,2)) を付け加える。 副グラフへに辺を追加すると、辺はさらに副グラフ・プロパティが維持されることを 保証する副グラフ木中の全ての祖先への追加をもたらす。 
add_edge(A1, C1, G1); // (A1,C1) は大域辺 (C,F) のための
                      // 副グラフ G1 の局所添え字。

Where Defined

boost/graph/subgraph.hpp

Template Parameters

パラメータ説明
Graph VertexMutableGraph と EdgeMutableGraph をモデルとするグラフ型。 さらにグラフは内部の vertex_index と edge_index プロパティ を持っていなければならない。頂点の添え字はグラフによって自動的に維持される はずであるのに対して、辺の添え字は subgraph クラス実装によって 割り当てられるだろう。

Model Of

subgraph は VertexMutableGraph のモデルである。さらに、もし Graph の型が VertexListGraph、 EdgeListGraph かつ/または BidirectionalGraph をモデルとしているなら、 subgraph<Graph> もまたこれらのコンセプトをモデルとするだろう。

Associates Types

もしグラフが副グラフ木の根ならば、頂点記述子と辺記述子は根グラフにとって 局所記述子でもあり、大域記述子でもある。もしグラフが根グラフでないならば、 記述子は副グラフにとって局所記述子である。副グラフのイテレータは基礎にある Graph の型のイテレータと同じイテレータ型である。 
graph_traits<subgraph>::vertex_descriptor
頂点記述子のための型。(Graph によって必要とされる。) 
graph_traits<subgraph>::edge_descriptor
辺記述子のための型。(Graph によって必要とされる。) 
graph_traits<subgraph>::vertex_iterator
vertices によって返されるイテレータのための型。 (VertexListGraph によって必要とされる。) 
graph_traits<subgraph>::edge_iterator
edges によって返されるイテレータのための型。 (EdgeListGraph によって必要とされる。) 
graph_traits<subgraph>::out_edge_iterator
out_edges によって返されるイテレータのための型。 (IncidenceGraph によって必要とされる。) 
graph_traits<subgraph>::in_edge_iterator
in_edge_iterator は in_edges 関数によって返されるイテレータ 型。(BidirectionalGraph によって必要と される。) 
graph_traits<subgraph>::adjacency_iterator
adjacent_vertices によって返されるイテレータのための型。 (AdjacencyGraph によって必要とされる。) 
graph_traits<subgraph>::directed_category
グラフが有向 (directed_tag) であるか、無向 (undirected_tag) であるかについての情報を提供する。(Graph によって 必要とされる。) 
graph_traits<subgraph>::edge_parallel_category
これはグラフ・クラスが多重辺 (同じ始点と終点を持つ辺) の挿入を許可するか どうか述べる。そしてそれは基礎にある Graph クラスに依存する。 二つのタグは allow_parallel_edge_tag と disallow_parallel_edge_tag である。 (Graph によって必要とされる。) 
graph_traits<subgraph>::vertices_size_type
グラフ中の頂点数を扱うために使われる型。 (VertexListGraph によって必要とされる。) 
graph_traits<subgraph>::edges_size_type
グラフ中の辺数を扱うために使われる型。 (EdgeListGraph によって必要とされる。) 
graph_traits<subgraph>::degree_size_type
頂点の出辺数を扱うために使われる型。 (IncidenceGraph によって必要とされる。) 
property_map<subgraph, PropertyTag>::type
property_map<subgraph, PropertyTag>::const_type
グラフ中の頂点プロパティと辺プロパティのためのマップ型。具体的なプロパティは PropertyTag テンプレート引数によって指定され、グラフのための VertexProperty または EdgeProperty 中で指定されるプロパティ の一つに一致しなければならない。 (PropertyGraph によって必要とされる。) 
subgraph::children_iterator
グラフの子副グラフをアクセスするためのイテレータ型。

Member Functions

subgraph(vertices_size_type n, const GraphProperty& p = GraphProperty())
n 個の頂点と 0 個の辺からなる根グラフ・オブジェクトを作成する。 
subgraph<Graph>& create_subgraph();
親が this のグラフである空の副グラフ・オブジェクトを作成する。 
template <typename VertexIterator>
subgraph<Graph>&
create_subgraph(VertexIterator first, VertexIterator last)
指定された頂点集合からなる副グラフ・オブジェクトを作成する。副グラフの 辺は頂点集合から誘導される。すなわち、副グラフ中の二つの頂点を結ぶ 親グラフ (this グラフ) 中の全ての辺が副グラフに付け加えられるだろう。 
vertex_descriptor local_to_global(vertex_descriptor u_local) const
局所頂点記述子を相当する大域頂点記述子に変形する。 
vertex_descriptor global_to_local(vertex_descriptor u_global) const
大域頂点記述子を相当する局所頂点記述子に変形する。 
edge_descriptor local_to_global(edge_descriptor e_local) const
局所辺記述子を相当する大域辺記述子に変形する。 
edge_descriptor global_to_local(edge_descriptor u_global) const
大域辺記述子を相当する局所辺記述子に変形する。 
std::pair<vertex_descriptor, bool> find_vertex(vertex_descriptor u_global) const
もし頂点 u がこの副グラフ中にあるなら、関数は大域頂点記述子に相当する 局所頂点記述子をペアの第一の部分として、true をペアの第二の部分と して返す。もし頂点 u が副グラフ中にないなら、この関数は false を ペアの第二の部分中に返す。 
subgraph& root()
副グラフ木の根グラフを返す。 
bool is_root() const
もしグラフが副グラフ木の根ならば true を返し、そうでなければ false を返す。 
subgraph& parent()
親グラフを返す。 
std::pair<children_iterator, children_iterator> children() const
子副グラフをアクセスするためのイテレータのペアを返す。

Nonmember Functions

subgraph の機能性は Graph の型に依存する。例えば、 もしGraph が BidirectionalGraph で、in_edges をサポートしているなら、subgraph もそうなる。ここで VertexListGraph、 EdgeListGraph そして BidirectionalGraph をモデルとする Graph の型によって与えられる、subgraph が サポートできるであろう全ての関数の一覧表を作る。 もし subgraph と共に使う Graph の型がこれらのコンセプトを モデルとせず、より少ない関数しかサポートしないなら、subgraph もまた 小数の関数しかサポートせず、以下に載せてある関数のいくつかは実装されない だろう。 
std::pair<vertex_iterator, vertex_iterator>
vertices(const subgraph& g)
副グラフ g の頂点集合へのアクセスを提供するイテレータ範囲を返す。 (VertexListGraph によって必要とされる。) 
std::pair<edge_iterator, edge_iterator>
edges(const subgraph& g)
副グラフ g の辺集合へのアクセスを提供するイテレータ範囲を返す。 (EdgeListGraph によって必要とされる。) 
std::pair<adjacency_iterator, adjacency_iterator>
adjacent_vertices(vertex_descriptor u_local, const subgraph& g)
副グラフ g 中の頂点 u に隣接する頂点へのアクセスを提供する イテレータ範囲を返す。 (AdjacencyGraph によって必要とされる。) 
std::pair<out_edge_iterator, out_edge_iterator>
out_edges(vertex_descriptor u_local, const subgraph& g)
副グラフ g 中の頂点 u の出辺へのアクセスを提供する イテレータ範囲を返す。もしグラフが無向グラフならば、このイテレータ範囲は 頂点 u に接続する全ての辺へのアクセスを提供する。 (IncidenceGraph によって必要とされる。) 
std::pair<in_edge_iterator, in_edge_iterator>
in_edges(vertex_descriptor v_local, const subgraph& g)
副グラフ g 中の頂点 v の入辺へのアクセスを提供するイテレータ範囲 を返す。 (BidirectionalGraph によって必要と される。) 
vertex_descriptor
source(edge_descriptor e_local, const subgraph& g)
副グラフ g 中の辺 e の始点を返す。 (IncidenceGraph によって必要とされる。) 
vertex_descriptor
target(edge_descriptor e_local, const subgraph& g)
副グラフ g 中の辺 e の終点を返す。 (IncidenceGraph によって必要とされる。) 
degree_size_type
out_degree(vertex_descriptor u_local, const subgraph& g)
副グラフ g 中の頂点 u の出辺数 (出次数) を返す。 (IncidenceGraph によって必要とされる。) 
degree_size_type in_degree(vertex_descriptor u_local, const subgraph& g)
副グラフ g 中の頂点 u の入辺数 (入次数) を返す。 (BidirectionalGraph によって必要と される。) 
vertices_size_type num_vertices(const subgraph& g)
副グラフ g 中の頂点数を返す。 (VertexListGraph によって必要とされる。) 
edges_size_type num_edges(const subgraph& g)
副グラフ g 中の辺数を返す。 (EdgeListGraph によって必要とされる。) 
vertex_descriptor vertex(vertices_size_type n, const subgraph& g)
副グラフの頂点リスト中の n 番目の頂点を返す。 
std::pair<edge_descriptor, bool>
edge(vertex_descriptor u_local, vertex_descriptor v_local, const subgraph& g)
副グラフ g 中の頂点 u と頂点 v を結ぶ辺を返す。 (AdjacencyMatrix によって必要とされる。) 
std::pair<edge_descriptor, bool>
add_edge(vertex_descriptor u_local, vertex_descriptor v_local, subgraph& g)
副グラフ g と副グラフ木中の副グラフの全ての祖先に辺 (u,v) を 付け加える。この関数は新しい辺を指す辺記述子を返す。もし辺が既にグラフ中に あるなら、重複は付け加えられず、ブール・フラグは false になるだろう。 (EdgeMutableGraph によって必要とされる。) 
std::pair<edge_descriptor, bool>
add_edge(vertex_descriptor u_local, vertex_descriptor v_local,
         const EdgeProperty& p, subgraph& g)
辺 (u,v) をグラフに付け加え、p を辺の内部的プロパティ記憶 の値として結びつける。さらに詳細のために先の add_edge メンバ関数を 見なさい。 
void remove_edge(vertex_descriptor u_local, vertex_descriptor v_local,
                 subgraph& g)
辺 (u,v) を副グラフと副グラフ木中の g の全ての祖先から 削除する。 (EdgeMutableGraph によって必要とされる。) 
void remove_edge(edge_descriptor e_local, subgraph& g)
辺 e を副グラフと副グラフ木中の g の全ての祖先から 削除する。 (EdgeMutableGraph によって必要とされる。) 
vertex_descriptor
add_vertex(subgraph& g)
頂点を副グラフに付け加え、新しい頂点を指す頂点記述子を返す。頂点はさらに 副グラフ・プロパティを維持するために副グラフ木中の g の全ての祖先 にも付け加えられる。 (VertexMutableGraph によって必要と される。) 
vertex_descriptor
add_vertex(vertex_descriptor u_global, subgraph& g)
頂点 u を根グラフから副グラフ g に付け加える。 (VertexMutableGraph によって必要と される。) 
template <class PropertyTag>
property_map<subgraph, PropertyTag>::type
get(PropertyTag, subgraph& g)

template <class PropertyTag>
property_map<subgraph, PropertyTag>::const_type
get(PropertyTag, const subgraph& g)
PropertyTag によって指定される頂点記述子または辺記述子のための プロパティ・マップ・オブジェクトを返す。PropertyTag はグラフの PropertyTag テンプレート引数中で指定されたプロパティの一つに 一致しなければならない。頂点プロパティと辺プロパティは全ての副グラフによって 共有されるので、一つの副グラフのための局所頂点記述子を通したプロパティの変更 は大域頂点記述子のためのプロパティを、それゆえ他の全ての副グラフを 変更するだろう。しかしながら、副グラフのプロパティ・マップのためのキー型は 副グラフで局所的な頂点記述子または辺記述子である。 (PropertyGraph によって必要とされる。) 
template <class PropertyTag, class Key>
typename property_traits<
  typename property_map<subgraph, PropertyTag>::const_type
>::value_type
get(PropertyTag, const subgraph& g, Key k_local)
これはキー k_local のためのプロパティ値を返す。そしてそれは 局所頂点記述子または局所辺記述子である。プロパティ・マップについての さらなる情報のために上の get 関数を見なさい。 (PropertyGraph によって必要とされる。) 
template <class PropertyTag, class Key, class Value>
void
put(PropertyTag, const subgraph& g, Key k_local, const Value& value)
これはキー k_local のためのプロパティ値を value にする。 k_local は局所頂点記述子または局所辺記述子のどちらかである。 Value は typename property_traits<property_map<adjacency_matrix, PropertyTag>::type>::value_type に変換可能でなければならない。 (PropertyGraph によって必要とされる。) 
template <class GraphProperties, class GraphPropertyTag>
typename property_value<GraphProperties, GraphPropertyTag>::type&
get_property(subgraph& g, GraphPropertyTag);
グラフ・オブジェクト g に結びつけられた GraphPropertyTag によって指定されるプロパティを返す。property_value 特性クラスは boost/pending/property.hpp 中で定義される。 
template <class GraphProperties, class GraphPropertyTag>
const typename property_value<GraphProperties, GraphPropertyTag>::type&
get_property(const subgraph& g, GraphPropertyTag);
グラフ・オブジェクト g に結びつけられた GraphPropertyTag によって指定されるプロパティを返す。property_value 特性クラスは boost/pending/property.hpp 中で定義される。

Japanese Translation Copyright © 2003 Takashi Itou
オリジナルの、及びこの著作権表示が全ての複製の中に現れる限り、この文書の複製、利用、変更、販売そして配布を認める。このドキュメントは「あるがまま」に提供されており、いかなる明示的、暗黙的保証も行わない。また、いかなる目的に対しても、その利用が適していることを関知しない。

このドキュメントの対象: Boost Version 1.30.0
最新版ドキュメント (英語)