boost图的外部属性表现得很奇怪？

Question

我正在使用 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。但为什么？如何确保我使用单独的地图？

Answer 1

我能够修复它。必须做出的关键观察：

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;

然后可以使用 a 中提供的数据实例化一个 vector 向量<向量>：

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]));