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一遍又一遍地输出。似乎 (external)weightMaps[j]都相同并且等于 internal property fastestLinkWeight。但为什么？如何确保使用单独的地图？

4

1 回答 1

4

我能够修复它。必须进行的关键观察：

WeightMap只是一个接口类型。如果它在问题的代码中被初始化，则行为是未定义的。

相反，您需要将数据存储在容器中，并确保它实现了相应的接口（即属性映射文档中get()解释的put()和operator[]方法）。

就我而言，问题可以解决如下：

定义一个EdgeIndexMapwhich 将用于将边缘描述符转换为向量元素的索引：

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

并iterator_property_map使用上述EdgeIndexMap类型：

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

vector<IterWeightMap>然后可以使用 a 中提供的数据来实例化a 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 回答