Say I have some boost graph
#include <boost/graph/adjacency_list.hpp>
struct Vertex {
double property_1;
int property_2;
};
using Graph_t = boost::adjacency_list<boost::listS,
boost::listS,
boost::undirectedS,
Vertex,
boost::no_property>;
Graph_t g(5);
and now want to iterate over the vertices in different orders, say:
property_2property_1How do I do this in the most efficient way?
As of now, I created std::vectors with the properties, and vectors containing indices, and sorted them by the properties. But if you have many properties that creates a ton of structure that could be avoided.
I also looked at boost::multi_index maps, as in this cplusplus.com question, but that doesn't seem slim to me either.
How can I do this? Happy about any hint!
That's (obviously) not a feature of the library.
You can however use ranges or range adaptors, like you would in any other situation:
#include <boost/graph/adjacency_list.hpp>
#include <boost/range/adaptors.hpp>
#include <boost/range/algorithm.hpp>
#include <boost/range/algorithm_ext.hpp>
#include <fmt/ranges.h>
#include <fmt/ostream.h>
#include <random>
struct Vertex {
double property_1;
int property_2;
};
static inline std::ostream& operator<<(std::ostream& os, Vertex const& v) {
return os << "V(" << v.property_1 << ", " << v.property_2 << ")";
}
using Graph_t =
boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS,
Vertex, boost::no_property>;
int main() {
using boost::make_iterator_range;
using namespace boost::adaptors;
Graph_t g(5);
int i = 0;
for (auto& v : make_iterator_range(vertices(g))) {
++i;
g[v] = {i / -.3, i * 11};
}
auto get_bundle = [&g](auto v) -> auto& { return g[v]; };
fmt::print("Natural order: {}\n",
make_iterator_range(vertices(g)));
fmt::print("Natural order: {}\n",
make_iterator_range(vertices(g) | transformed(get_bundle)));
fmt::print(
"Reverse natural order: {}\n",
make_iterator_range(vertices(g) | transformed(get_bundle) | reversed));
auto make_view = [=](auto range) {
return std::vector<std::reference_wrapper<Vertex>>(
begin(range), end(range));
};
auto view =
make_view(make_iterator_range(vertices(g) | transformed(get_bundle)));
boost::reverse(view);
fmt::print("view: {}\n", view);
boost::reverse(view);
fmt::print("reversed: {}\n", view);
auto less_by = [](auto member) {
return [=, prj = std::mem_fn(member)](auto const& a, auto const& b) {
return prj(a) < prj(b);
};
};
boost::sort(view, less_by(&Vertex::property_1));
fmt::print("less_by property_1: {}\n", view);
boost::sort(view, less_by(&Vertex::property_2));
fmt::print("less_by property_2: {}\n", view);
{
static std::random_device rd;
static std::mt19937 randgen{rd()};
std::shuffle(view.begin(), view.end(), randgen);
fmt::print("random order: {}\n", view);
}
// just a loop is also fine, of course
i = 0;
for (Vertex& bundle : view) {
bundle.property_2 = i++;
}
fmt::print("modified: {}\n", view);
}
Prints
Natural order: {0x1467eb0, 0x1467f10, 0x1467f70, 0x1467fd0, 0x1468030}
Natural order: {V(-3.33333, 11), V(-6.66667, 22), V(-10, 33), V(-13.3333, 44), V(-16.6667, 55)}
Reverse natural order: {V(-16.6667, 55), V(-13.3333, 44), V(-10, 33), V(-6.66667, 22), V(-3.33333, 11)}
view: {V(-16.6667, 55), V(-13.3333, 44), V(-10, 33), V(-6.66667, 22), V(-3.33333, 11)}
reversed: {V(-3.33333, 11), V(-6.66667, 22), V(-10, 33), V(-13.3333, 44), V(-16.6667, 55)}
less_by property_1: {V(-16.6667, 55), V(-13.3333, 44), V(-10, 33), V(-6.66667, 22), V(-3.33333, 11)}
less_by property_2: {V(-3.33333, 11), V(-6.66667, 22), V(-10, 33), V(-13.3333, 44), V(-16.6667, 55)}
random order: {V(-13.3333, 44), V(-3.33333, 11), V(-10, 33), V(-6.66667, 22), V(-16.6667, 55)}
modified: {V(-13.3333, 0), V(-3.33333, 1), V(-10, 2), V(-6.66667, 3), V(-16.6667, 4)}
std::ranges could give you most of these but in my experience has a few more limitations. However, it will be generally safer (because Boost Range V2 is quite old).
to have "living indexes" (like a database) make your vertex container selector select a Multi Index Container. See e.g. the advice here https://marc.info/?l=boost&m=118835654637830
to model your own graph datastructure, see e.g. here for inspiration
In response to the comments, you could use Boost PFR to generate a array with comparators simple types statically:
template <typename T, typename Op = std::less<> >
constexpr static inline auto make_field_comparers(Op op = {}) {
namespace pfr = boost::pfr;
auto constexpr N = pfr::tuple_size<T>::value;
using A = std::array<std::function<bool(T const&, T const&)>, N>;
auto lift = [op](auto prj) {
return [=](T const& a, T const& b) { return op(prj(a), prj(b)); };
};
return [lift]<size_t... I>(std::index_sequence<I...>){
return A{lift([](T const& v) { return pfr::get<I>(v); })...};
}
(std::make_index_sequence<N>{});
}
Which you could use like Live On Compiler Explorer
std::vector orderings {
std::pair { "asc", make_field_comparers<Vertex>() },
std::pair { "desc", make_field_comparers<Vertex>(std::greater<>{}) },
};
for (auto const& [dir, fields] : orderings) {
for (size_t field = 0; field < fields.size(); ++field) {
boost::sort(view, fields[field]);
fmt::print("by field #{} {}: {}\n", field, dir, view);
}
}
Printing
by field #0 asc: {V(-16.6667, 55), V(-13.3333, 44), V(-10, 33), V(-6.66667, 22), V(-3.33333, 11)}
by field #1 asc: {V(-3.33333, 11), V(-6.66667, 22), V(-10, 33), V(-13.3333, 44), V(-16.6667, 55)}
by field #0 desc: {V(-3.33333, 11), V(-6.66667, 22), V(-10, 33), V(-13.3333, 44), V(-16.6667, 55)}
by field #1 desc: {V(-16.6667, 55), V(-13.3333, 44), V(-10, 33), V(-6.66667, 22), V(-3.33333, 11)}