Карта внешних свойств привязана к 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 е). Я стою перед буст-документацией без понятия. Кажется, мне нужно 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;