passant seulement un élément d'une propriété std :: vecteur à un algorithme BGL

Question

je un graphique avec plusieurs coefficients de bord stockées sous forme de

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; 

Les coefficients sont tous poussés sur le vecteur.

Maintenant, je veux appeler la fonction prim_minimum_spanning_tree() sur le graphique, avec les premiers éléments du vecteur utilisés comme pondérations.

Comment puis-je effectuer un appel de fonction correct?

Answer 1

Je l'ai fait maintenant en copiant d'abord les pondérations souhaitées sur une propriété supplémentaire, puis en exécutant l'algorithme et en le copiant ensuite. C'est moche, mais ça fait l'affaire dans mon cas.

Answer 2

J'ai récemment essayé de faire la même chose (pour utiliser une propriété vectorielle) et j'ai échoué à exécuter des algorithmes uniquement avec l'une des valeurs. Cependant, j'ai trouvé que l'utilisation de exterior properties est une bonne approche qui ne conduira pas à des actions de copie inutiles et à passer la carte de propriétés explicitement à l'algorithme.

Si vous utilisez des conteneurs à accès aléatoire, vous pouvez utiliser boost::iterator_property_map pour envelopper ce conteneur et en faire un property_map. Au lieu de descripteurs de bord, il requiert des index de bord basés sur 0 pour le mappage efficace entre les arêtes et les valeurs de propriété. Voici la punchline, plus vous trouverez l'exemple fait complète:

// ... 
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); 

Et voici un exemple complet:

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; 
    } 

    }