Внешние свойства буст-графа ведут себя странно?

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;

Затем можно создать 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]));