Tri des EdgeList en boost :: graphique

Question

Je voudrais trier la liste de bord de boost :: graphe défini comme suit:

struct Vertex{ 
int index; 
}; 

struct Edge{ 
double weight; 
}; 

boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, Vertex, Edge> Graph; 

Après avoir ajouté les sommets et les arêtes, comment trier la liste de bord . Avoir le bord avec le poids le plus élevé en premier?

Je sais qu'on peut utiliser

std::sort(edgeIt_begin,edgeIt_end,compare); 

pour les vecteurs, mais il ne fonctionne pas pour std :: liste.

Answer 1

Le tri des bords n'est pas idiomatique boost :: graph. Regardez le BGL implementation de Kruskal's algorithm pour couvrir les arbres. L'algorithme doit regarder chaque bord dans l'ordre croissant du poids.

std::priority_queue<Edge, std::vector<Edge>, weight_greater> Q(wl); 
    /*push all edge into Q*/ 
    typename graph_traits<Graph>::edge_iterator ei, eiend; 
    for (boost::tie(ei, eiend) = edges(G); ei != eiend; ++ei) 
    Q.push(*ei); 

Il utilise une structure de données distincte pour trier les arêtes et ensuite itérer sur les arêtes dans cet ordre. Dans votre cas, vous voulez d'abord les bords pondérés les plus élevés, de sorte que vous cherchiez à changer l'opérateur du comparateur.

Answer 2

Vous pouvez écrire votre propre classe EdgeList ou OutEdgeList qui trie automatiquement les éléments. Je donne un exemple parce que je ne suis pas si évident comment faire ça.

#include <iostream> 
#include <boost/graph/graph_traits.hpp> 
#include <boost/graph/adjacency_list.hpp> 

using namespace boost; 

template<class T> struct Sorted_list 
{ 
    std::list<T> v; 

public: 
    typedef T value_type; 
    typedef typename std::list<T>::size_type size_type; 
    typedef typename std::list<T>::iterator iterator; 

    iterator insert(const T& x) 
    { 
    Sorted_list<T>::iterator i = v.begin(); 

    while(i != v.end() && x > *i) 
    { 
     i++; 
    } 

    return v.insert(i, x); 
    } 

    iterator begin() { return v.begin(); } 
    iterator end() { return v.end(); } 

    size_type size() const { return v.size(); } 
}; 

struct SlistS {}; 

namespace boost { 
    template <class ValueType> struct container_gen<SlistS, ValueType> 
    { 
    typedef Sorted_list<ValueType> type; 
    }; 

    struct sorted_list_tag {}; 

    template<class T> sorted_list_tag container_category(Sorted_list<T>&) 
    { 
    return sorted_list_tag(); 
    } 

    template<class T> std::pair<typename Sorted_list<T>::iterator, bool> 
    push_dispatch(Sorted_list<T>& v, const T& x, sorted_list_tag) 
    { 
    return std::make_pair(v.insert(x), true); 
    } 

    template <> struct parallel_edge_traits<SlistS> { 
    typedef allow_parallel_edge_tag type; 
    }; 
} 

int main() 
{ 
    typedef adjacency_list<SlistS> Graph; 
    Graph g(10); 
    add_edge(1, 2, g); 
    add_edge(1, 5, g); 
    add_edge(1, 3, g); 
    add_edge(1, 7, g); 
    add_edge(1, 1, g); 

    graph_traits<Graph>::edge_iterator i, end; 

    for (tie(i, end) = edges(g); i != end; ++i) { 
    std::cout << source(*i, g) << " -> " << target(*i, g) << std::endl; 
    } 

    return 0; 
} 

Sortie:

1 -> 1 
1 -> 2 
1 -> 3 
1 -> 5 
1 -> 7 

Answer 3

Je ne sais pas toutes les interactions avec la représentation graphique Boost, mais IIRC vous pouvez utiliser std::list::sort(Cmp)

std::list<int> l = { 1, 3, -1, 9, 2 }; 
l.sort(); 

Answer 4

Réponse précédente, bien que très utile, gère les balises bgl de manière incorrecte, ce qui entraîne une définition push_dispatch redondante et peut entraîner des problèmes de construction si d'autres fonctions * _dispatch étant appelées (dans le cas d'opérations d'effacement, par exemple).

La deuxième circonstance source de confusion est que la liste des arêtes par nœud est substituée dans le modèle adj_list, mais la liste des arêtes entières non affectées est imprimée.

Il y a un code qui corrige probablement ces défauts:

// ... 

template<class T> struct Sorted_vector : public std::vector<T> 
{ 
public: 

    iterator insert(const T& x) 
    { 
    iterator where = std::upper_bound(begin(), end(), x, std::less<T>()); 
    return std::vector<T>::insert(where, x); 
    } 

}; 

struct vecSS{}; 

namespace boost{ 

    template <class ValueType> struct container_gen<vecSS, ValueType> 
    { 
     typedef Sorted_vector<ValueType> type; 
    }; 

    template <> struct parallel_edge_traits<vecSS> { 
     typedef allow_parallel_edge_tag type; 
    }; 

    template<class T> graph_detail::vector_tag container_category(const Sorted_vector<T>&) 
    { 
     return graph_detail::vector_tag(); 
    } 

    template <class T> graph_detail::unstable_tag iterator_stability(const Sorted_vector<T>&) 
    { 
     return graph_detail::unstable_tag(); 
    } 
} 

typedef adjacency_list<vecSS, ...> Graph; 

// .... 

    graph_traits<Graph>::vertex_iterator ii, ee; 
    for(boost::tie(ii,ee) = vertices(g);ii!=ee;++ii){ 
     std::cout << *ii << std::endl; 
     graph_traits<Graph>::adjacency_iterator jj, ff; 
     for(boost::tie(jj,ff)=adjacent_vertices(*ii, g);jj != ff; ++jj){ 
      std::cout << "\t -> " << *jj<<std::endl; 
     } 
    }