C++ - BGL: sort edges

Question

I was wondering if there was a way to get a sorted vector of a boost graph's edges without the use of lambda functions.

I.e. I am currently sorting like this:

std::vector<Edge> edgs = ...;
std::sort(edgs.begin(),edgs.end(),
        [&](const Edge& e1, const Edge& e2){
            return g[e1].source < g[e2].source || (g[e1].source == g[e2].source && g[e1].target < g[e2].target);
    });

Where g is the graph we have taken the edges from and

struct EdgeProperties{
    int weight;
    int source;
    int target;
};
typedef boost::adjacency_list<vecS,vecS,undirectedS,no_property,EdgeProperties> Graph;
typedef boost::graph_traits<Graph> Traits;
typedef Traits::vertex_descriptor Vertex;
typedef Traits::edge_descriptor Edge;

Works, but I'd prefer not having to use lambda functions. Is there a way to avoid them (still using the std::sort) or am I stuck with them?

The [`std::sort`](http://en.cppreference.com/w/cpp/algorithm/sort) documentation gives examples which do not involve lambda. — James Adkison, Oct 14 '15 at 16:53

score 1 · Accepted Answer · edited May 23 '17 at 10:27

1

You can use operators and functors:

 // sort using a custom function object
    class customLess{
        Graph &_g;
    public:
        customLess(Graph g)
        {
            _g = g;
        }

        bool operator()(const Edge& e1, const Edge& e2)
        {   
           return _g[e1].source < _g[e2].source || (_g[e1].source ==  _g[e2].source && _g[e1].target < _g[e2].target);
        }   
     } ;

    std::sort(edgs.begin(), edgs.end(), customLess(g));

So that you dont have to write down same operator content in every sort operation in your code.

with reference: http://en.cppreference.com/w/cpp/algorithm/sort and C++ Functors - and their uses

edited May 23 '17 at 10:27

Community

1
1

answered Oct 14 '15 at 16:58

fatihk

7,789
1
26
48

Thank you, but where does your function object get its ``g`` from? Because that's the reason I'm using lambda functions in the first place. Can I just store a reference to the graph in the struct, or..? – User1291 Oct 14 '15 at 17:49
1

@User1291 yes. That's the idea of a stateful functor – sehe Oct 14 '15 at 18:18

score 1 · Answer 2 · answered Oct 14 '15 at 18:27

Alternatively, use the default sorting comparison: std::less<Edge>

E.g.:

#include <boost/tuple/tuple_comparison.hpp>

using namespace boost;

struct EdgeProperties{
    int weight;
    int source;
    int target;

private:
    auto key() const { return tie(weight, source, target); }
public:

    bool operator<(EdgeProperties const& other) const {
        return key() < other.key();
    }
};

Now

std::edge<EdgeProperties> selfsorting;

is already sorted

C++ - BGL: sort edges

2 Answers2