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

You could write your own EdgeList or OutEdgeList class which sorts the Elements automatically. I give an example because it's imho not that obvious how to do that.

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

Output:

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

Answer 2

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.

Answer 3

I don't know about any interactions with the Boost Graph representation, but IIRC you can use std::list::sort(Cmp)

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

Answer 4

Previous answer, though very useful, manages bgl tags in a bit incorrect manner, that results in redundant push_dispatch definition and may lead to build problems if other *_dispatch functions being called (in case of erase operations, e.g.).

Second confusing circumstance is that per-node edge list is substituted in adj_list template, but the unaffected whole-edge list is printed.

There are some code that presumably corrects these flaws:

// ...

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