Карта внешних свойств привязана к std :: vector в библиотеке графов надстроек

Question

В настоящее время я пытаюсь определить внешние свойства графика повышения.Я использую некоторые связанные свойства в качестве внутренних:

struct VertexProperties
{
  int demand;
};

struct EdgeProperties
{ 
  uint capacity;
  int cost;
};

typedef adjacency_list <vecS, vecS, bidirectionalS, VertexProperties, EdgeProperties> Graph;

Однако во время алгоритма мне нужны некоторые внешние свойства, то есть я хочу иметь возможность отображать ребра / вершины моего графа в элементы, хранящиеся в std:: vector таким образом, что я могу получить к ним доступ через operator [] (Edge e).Я стою перед буст-документацией без понятия.Кажется, мне нужно property_map, но я не знаю, как использовать их вместе с векторами.Единственные примеры, которые я нашел до сих пор, касаются отображений из вершин в вектор, но поскольку вершины представляют собой целые числа без знака, это тривиально. много времени, чтобы самому реализовать и протестировать класс графа, я действительно не получаю этот сумасшедший материал для метапрограммирования шаблонов ...

Answer 1

Вы можете создавать внешние карты свойств независимо от того, какие внутренние и / или связанные свойства находятся на вашем графике. Создание карт свойств по краям несколько сложнее, потому что вам нужна карта edge_index, а adjacency_list по умолчанию ее не имеет; compressed_sparse_row_graph делает, но его структура в основном доступна только для чтения после создания. Вы можете либо использовать associative_property_map по краям, либо создать карту индекса края как внутреннее свойство (если вы не слишком часто меняете график), заполнить его, а затем использовать его для построения карты внешних свойств (используя shared_array_property_map, например).

Answer 2

Недавно я столкнулся с той же проблемой, и вот как я в итоге добавил свойство вершины (в этом фрагменте кода называемое градус ):

// Graph has to have _index_ property (vector-based graphs get it implicitly)
typedef typename property_map<Graph, vertex_index_t>::type IndexMap;
// Storage type for the _degree_ property
typedef std::vector<uint> DegreeVector;
// Type of the _degree_ property map
typedef iterator_property_map<typename DegreeVector::iterator, IndexMap> DegreeMap;

// Graph in question
Graph g(5);
// Actual storage
DegreeVector degree_storage(num_vertices(g));
// This is needed to construct _degree_ property map
IndexMap index_map = get(vertex_index, g);
// Create _degree_ property map
DegreeMap degree_map = make_iterator_property_map(degree_storage.begin(), index_map);

// Now degree_map is ready to be used
degree_map[some_vertex_id] = 10;