Как переставить узлы в boost :: adjacency_list? - PullRequest
Новая
       13

Как переставить узлы в boost :: adjacency_list?

1 голос
/ 22 января 2012

Притворимся в следующих определениях и определениях типов: 

#include <boost/graph/adjacency_list.hpp>
using namespace boost;

int main()
{
    typedef adjacency_list<vecS, vecS, directedS, property<vertex_index_t, int> > GraphTC;
    GraphTC g;

    typedef typename property_map<GraphTC, vertex_index_t>::const_type VertexIndexMap;
    VertexIndexMap index_map = get(vertex_index, g);

    typedef typename graph_traits<GraphTC>::vertex_descriptor tc_vertex;
    std::vector<tc_vertex> to_tc_vec(num_vertices(g));

    iterator_property_map < tc_vertex *, VertexIndexMap, tc_vertex, tc_vertex&>
    g_to_tc_map(&to_tc_vec[0], index_map);
}

У меня есть алгоритм, который выводит мне g и g_to_tc_map (как указано выше).Теперь мне нужно переставить узлы с помощью g_to_tc_map (я думаю, что-то вроде целочисленного массива или std :: map).

Примечание: я обнаружил, что есть повышение / график / детализация/permutation.hpp, но я понятия не имею, как его использовать (получение даже ошибок, включая этот файл, конфликт с другими заголовками).

Спасибо за любую идею / код, как сделать эту перестановку.

1 Ответ

0 голосов
/ 09 февраля 2012

Если вы можете жить с созданием перестановочной копии графа, вы можете создать новый граф, используя диапазон итераторов: 

struct permute_edge {
  iterator_property_map < tc_vertex *, VertexIndexMap, tc_vertex, tc_vertex&> g_to_tc_map;
  const GraphTC& g;
  permute_edge(iterator_property_map < tc_vertex *, VertexIndexMap, tc_vertex, tc_vertex&> g_to_tc_map, const GraphTC& g): g_to_tc_map(g_to_tc_map), g(g) {}
  std::pair<tc_vertex, tc_vertex> operator()(graph_traits<Graph>::edge_descriptor e) const {
    return std::make_pair(get(g_to_tc_map, source(e, g)), get(g_to_tc_map, target(e, g));
  }
};

permute_edge perm(g_to_tc_map, g);
typedef graph_traits<GraphTC>::edge_iterator edge_iterator;
std::pair<edge_iterator, edge_iterator> g_edges = edges(g);
GraphTC g_permuted(
          make_transform_iterator(g_edges.first, perm),
          make_transform_iterator(g_edges.second, perm),
          num_vertices(g), num_edges(g));

PS: вам не нужно свойство vertex_index_t в графе с vecS контейнером вершин; оно создается (и заполняется) автоматически.

...