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

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

2 голосов
/ 21 октября 2011

Я делаю свои первые шаги с 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. Но почему? Как я могу гарантировать, что я использую отдельные карты?

1 Ответ

4 голосов
/ 24 октября 2011

Я смог это исправить. Ключевое замечание, которое нужно сделать:

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 как обычно, например ::101033 

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