Передача только элемента свойства std :: vector алгоритму BGL - PullRequest
Новая
       5

Передача только элемента свойства std :: vector алгоритму BGL

0 голосов
/ 29 октября 2010

У меня есть график с несколькими весами ребер, который хранится как 

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(), в которой в качестве весов будут использоваться первые элементы вектора.

Как я могу выполнить правильный вызов функции?

Ответы [ 2 ]

0 голосов
/ 08 января 2015

Недавно я попытался сделать то же самое (использовать векторное свойство) и не смог запустить алгоритмы только с одним из значений. Однако я обнаружил, что использование внешних свойств - это хороший подход, который не приведет к ненужным действиям копирования и явной передаче карты свойств в алгоритм.

Если вы используете контейнеры с произвольным доступом, вы можете использовать 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;
     }

  }
0 голосов
/ 29 октября 2010

Я сделал это сейчас, сначала скопировав желаемые веса в дополнительное свойство, затем запустив алгоритм и затем скопировав обратно. Это уродливо, но в моем случае это помогает.

...