Передача только элемент STD :: Векторная недвижимость в алгоритм BGL
-
27-09-2019 - |
Вопрос
У меня есть график с несколькими руками, хранящимися как
namespace boost {
enum edge_weightvector_t {
edge_weightvector = 1337
};
BOOST_INSTALL_PROPERTY(edge, weightvector);
}
typedef boost::adjacency_list<
boost::vecS,
boost::vecS,
boost::undirectedS,
boost::no_property,
boost::property<boost::edge_weightvector_t, std::vector<int> >
> graph_t;
Весы все нажаты на вектор.
Теперь я хочу позвонить prim_minimum_spanning_tree()
Функция на графике, с первыми элементами в векторе, используемом в качестве весов.
Как я могу выполнить правильный звонок функции?
Решение
Теперь я сделал это, сначала скопировав желаемую весы до дополнительного свойства, а затем запустить алгоритм и копировать обратно после этого. Это уродливое, но это делает трюк в моем случае.
Другие советы
Я недавно попытался сделать то же самое (использовать векторное свойство) и не удалось запустить алгоритмы только с одним из значений. Тем не менее, я обнаружил, что используя внешние свойства Является ли хорошим подходом, который не приведет к ненужным действиям копирования и явно пропустить карту недвижимости к алгоритму.
Если вы используете контейнеры произвольного доступа, которые вы можете использовать boost::iterator_property_map
это будет обернуть этот контейнер и сделать это property_map
. Отказ Вместо дескрипторов по краям требуется 0 краевых индексов для эффективного отображения между краями и значениями свойств. Вот изящная линия, дальше, которую вы найдете полный пример:
// ...
EdgeIndexMap edgeIds = get(edge_index, g);
// ...
typedef std::vector<int> Weights;
typedef std::vector<Weights> WeightsVector;
typedef iterator_property_map <Weights::iterator, EdgeIndexMap> WeightMap;
// ...
Weights weights; // = ...
WeightMap wm(weights.begin(), edgeIds);
// ...
some_bgl_algorithm(g, wm);
И вот полный пример:
using namespace boost;
void sampleExteriorProperties()
{
typedef adjacency_list<vecS, vecS, undirectedS,
no_property,
//property<edge_index_t, int, property<edge_weight_t, int> >
property<edge_index_t, std::size_t>
> Graph;
typedef graph_traits<Graph>::edge_descriptor Edge;
typedef graph_traits<Graph>::edge_iterator EdgeIterator;
typedef property_map<Graph, edge_index_t>::type EdgeIndexMap;
//typedef property_map<Graph, edge_weight_t>::type WeightMap;
const int NVERTICES = 5;
const int NEDGES = 8;
Graph g(NVERTICES);
// Add edges WITH indexes.
int edgeIndex = 0;
add_edge(0, 1, edgeIndex++, g);
add_edge(0, 2, edgeIndex++, g);
add_edge(0, 3, edgeIndex++, g);
add_edge(1, 2, edgeIndex++, g);
add_edge(1, 4, edgeIndex++, g);
add_edge(2, 3, edgeIndex++, g);
add_edge(2, 4, edgeIndex++, g);
add_edge(3, 4, edgeIndex++, g);
// Weights: there must be a weight for every edge.
// Weights will be later on accessed by edge index.
assert(num_edges(g) == NEDGES);
typedef std::vector<int> Weights;
typedef std::vector<Weights> WeightsVector;
WeightsVector weightVector({ { 2, 3, 5, 7, 9, 11, 13, 17 },
{ 8, 7, 6, 5, 4, 3, 2, 1 }
});
EdgeIndexMap edgeIds = get(edge_index, g);
for (Weights &weights : weightVector)
{
// Use the iterator_property_map to read the properties from a
// random access container. Remember: Edge ids are used to access
// the correct value from the container!
typedef iterator_property_map <Weights::iterator, EdgeIndexMap> WeightMap;
WeightMap wm(weights.begin(), edgeIds);
EdgeIterator eIt, eItEnd;
tie(eIt, eItEnd) = edges(g);
while (eIt!=eItEnd)
{
std::cout << *eIt << ": " << wm[*eIt] << " ";
++eIt;
}
std::cout << std::endl;
// Explicitly pass the exterior map to the algorithm.
std::vector<Edge> mstEdges;
kruskal_minimum_spanning_tree(g, std::back_inserter(mstEdges),
weight_map(wm));
std::for_each(mstEdges.begin(), mstEdges.end(),
[](const Edge &val){std::cout << val << " ";});
std::cout << std::endl;
}
}