Sorting the EdgeList in boost::graph

Question

I would like to to sort the edge List of boost::graph defined as followed:

struct Vertex{
int index;
};

struct Edge{
double weight;
};

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

After adding the vertices and edges, how to I sort the edge list. Getting the edge with the highest weight first?

I know one can use

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

for vectors, but it doesn't work for std::list.

Answer 1

Sorting the edges is not idiomatic boost::graph. Look at the BGL implementation of Kruskal's algorithm for spanning trees. The algorithm needs to look at each edge in increasing order of weight.

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

It uses a separate data structure to sort the edges and later iterates through the edges in that order. In your case, you want the highest weighted edges first, so you would look change the comparator operator.