2

現在、ブースト グラフの外部プロパティを定義しようとしています。バンドルされたプロパティを内部プロパティとして使用します。

struct VertexProperties
{
  int demand;
};

struct EdgeProperties
{ 
  uint capacity;
  int cost;
};

typedef adjacency_list <vecS, vecS, bidirectionalS, VertexProperties, EdgeProperties> Graph;

ただし、アルゴリズム中にいくつかの外部プロパティが必要です。つまり、グラフのエッジ/頂点を std::vector に格納された要素にマップして、 operator[] (Edge e)。私は手がかりなしにブーストのドキュメントの前に立っています。property_map が必要なようですが、これらをベクトルと一緒に使用する方法がわかりません。これまでに見つけた唯一の例は、頂点からベクトルへのマップに関するものですが、頂点は unsigned int であるため、これは些細なことです。

これまでのところ、boost には本当に不満を感じています。自分でグラフ クラスを実装してテストする時間を大幅に節約できたと思います。このクレイジーなテンプレート メタプログラミングのものは本当にわかりません...

4

2 に答える 2

5

グラフ内の内部および/またはバンドルされたプロパティに関係なく、外部プロパティ マップを作成できます。edge_indexエッジにプロパティ マップを作成することは、マップが必要であり、adjacency_list既定では存在しないため、多少難しくなります。compressed_sparse_row_graphしますが、その構造は構築後はほとんど読み取り専用です。エッジで使用するかassociative_property_map、内部プロパティとしてエッジ インデックス マップを作成し (グラフをあまり頻繁に変更しない場合)、それを塗りつぶしてから、それを使用して外部プロパティ マップを作成します (shared_array_property_mapたとえば、 を使用)。

于 2011-11-24T23:29:18.803 に答える
1

私は最近同じ問題に遭遇しました。頂点プロパティ (このコード スニペットでは次数と呼ばれます) をアタッチする方法は次のとおりです。

// Graph has to have _index_ property (vector-based graphs get it implicitly)
typedef typename property_map<Graph, vertex_index_t>::type IndexMap;
// Storage type for the _degree_ property
typedef std::vector<uint> DegreeVector;
// Type of the _degree_ property map
typedef iterator_property_map<typename DegreeVector::iterator, IndexMap> DegreeMap;

// Graph in question
Graph g(5);
// Actual storage
DegreeVector degree_storage(num_vertices(g));
// This is needed to construct _degree_ property map
IndexMap index_map = get(vertex_index, g);
// Create _degree_ property map
DegreeMap degree_map = make_iterator_property_map(degree_storage.begin(), index_map);

// Now degree_map is ready to be used
degree_map[some_vertex_id] = 10;
于 2013-10-19T17:21:24.187 に答える