2

Boost :: Graphを使用して最初のステップを実行していますが、(私にとっては)予期しない動作が発生しました。

私が欲しいのは、一連のedge_weightプロパティ(数は実行時にのみ知られている)を持ち、特定の制約を満たすすべての重みの最小値を使用することです。まず、typedef宣言:

typedef adjacency_list<vecS, vecS, undirectedS, property<vertex_distance_t, int>, property<edge_weight_t, int> > Graph;
typedef graph_traits<Graph>::edge_descriptor Edge;
typedef property_map<Graph, edge_weight_t>::type WeightMap;
typedef property_map<Graph, vertex_distance_t>::type DistanceMap;

次のようにグラフを初期化します。

void testcase() {
    int t, e, s, a, b;
    cin >> t >> e >> s >> a >> b;
    Graph g(t);
    WeightMap fastestLinkWeight = get(edge_weight, g);
    vector<WeightMap> weightMaps(s);
    for (int i=0;i<e;i++) {
        int u, v;
        cin >> u >> v;

        Edge edge; bool worked;
        tie(edge, worked) = add_edge(u, v, g);
        for (int j=0;j<s;j++) {
            cin >> weightMaps[j][edge];
        }
        fastestLinkWeight[edge] = INT_MAX;

        cout << weightMaps[0][edge] << "\n";
    }
}

そして何度も出力INT_MAXします。(外部)weightMaps[j]はすべて同じで、内部プロパティと等しいようfastestLinkWeightです。しかし、なぜ?個別のマップを使用するようにするにはどうすればよいですか?

4

1 に答える 1

4

私はそれを修正することができました。重要な観察事項は次のとおりです。

WeightMap単なるインターフェースタイプです。質問のコードのように初期化されている場合、動作は未定義です。

代わりに、コンテナにデータを格納し、それに応じたインターフェイス (つまり、プロパティ マップのドキュメントでget()説明されている、 、put()およびoperator[]メソッド) が実装されていることを確認する必要があります。

私の場合、問題は次のように解決できます。

EdgeIndexMapエッジ記述子をベクトル要素のインデックスに変換するために使用される を定義します。

typedef property_map<Graph, edge_index_t>::type EdgeIndexMap;

そして、iterator_property_map上記のEdgeIndexMapタイプを使用する:

typedef iterator_property_map<int*, EdgeIndexMap, int, int&> IterWeightMap;

次に、vector<IterWeightMap>で提供されるデータを使用して をインスタンス化できvector<vector<int> >ます。

EdgeIndexMap eim = get(edge_index, g);
vector<vector<int> > weights(s, vector<int>(e));
vector<IterWeightMap> weightMaps(s);
for (int j=0;j<s;j++) {
    weightMaps[j] = make_iterator_property_map(&(weights[j][0]), eim);
}

edge_indexプロパティは (当然のことながら) 内部プロパティとして格納されることに注意してください。

このようにして、さまざまedge_weightなプロパティを通常どおり BGL アルゴリズム呼び出しで使用できます。たとえば、次のようになります。

kruskal_minimum_spanning_tree(g, std::back_inserter(privateNetwork), weight_map(weightMaps[j]));
于 2011-10-24T18:30:08.987 に答える