external properties of boost graph behaving weird?

Question

I am doing my first steps with Boost::Graph and encountered some (to me) unexpected behavior.

What I want is to have a series of edge_weight properties (the number is only known at runtime), and use the minimum of all weights that satisfy certain constraints. First, the typedef declarations:

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;

I initialize the graph as follows:

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";
    }
}

And it outputs INT_MAX over and over. It seems like the (external) weightMaps[j] are all the same and equal to the internal property fastestLinkWeight. But why? How can I ensure that I use separate maps?

score 4 · Accepted Answer · answered Oct 24 '11 at 18:30

I was able to fix it. The key observation one has to make:

WeightMap is just an interface type. If it is initialized as in the question's code, the behavior is undefined.

Instead, you need to store the data in a container and make sure it implements the according interface (that is, the get(), put() and operator[] methods as the documentation on property maps explains).

In my case, the problem can be solved as follows:

Define an EdgeIndexMap which will be used to translate an edge descriptor into the index of a vector element:

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

And the iterator_property_map using the above-mentioned EdgeIndexMap type:

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

One can then instanciate a vector<IterWeightMap> using the data provided in 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);
}

Note that the edge_index property (naturally) is stored as an interior property.

This way, the different edge_weight properties can be used in BGL algorithm calls as usually, e.g.:

kruskal_minimum_spanning_tree(g, std::back_inserter(privateNetwork), weight_map(weightMaps[j]));

external properties of boost graph behaving weird?

1 Answers1