How can I Iterate over Vertices & Edges in an Order Provided by a (Bundled) Property, in the BGL?

Question

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:

1. by its id
2. in a random order
3. descending by property_2
4. ascending by property_1
5. descending/ascending by more bundled properties in a generic way.

How 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!

Answer 1

That's (obviously) not a feature of the library.

You can however use ranges or range adaptors, like you would in any other situation:

Live On Coliru

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

More, From Here

• 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

  • What is needed to use BGL algorithms on existing data structures ( edges and vertices as vector<Object *>)?

  • What is required for a custom BGL graph to work with topological sort?

UPDATE Code Generation With Boost PFR

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

Answer 2

Boost.MultiIndex can be plugged in in a rather convoluted, undocumented fashion:

Live Coliru Demo

#include <boost/graph/adjacency_list.hpp>
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/random_access_index.hpp>
#include <boost/multi_index/ordered_index.hpp>

struct mic_tag:
  /* it is assumed first index is random-access */
  virtual public boost::graph_detail::random_access_container_tag,
  virtual public boost::graph_detail::back_insertion_sequence_tag{};

namespace boost{

template<typename... Args>
mic_tag container_category(boost::multi_index_container<Args...>&){return {};}

}

template<typename GraphType,typename KeyExtractor>
struct vertex_adapted
{
  using result_type=typename KeyExtractor::result_type;
        
  decltype(auto) operator()(void* p)const
  {
    return key(
      static_cast<typename GraphType::stored_vertex*>(p)->m_property);
  }
  
  KeyExtractor key;
};

struct vertex_t
{
  double property_1;
  int    property_2;
};

struct graph_t;
struct graph_t_vertex_list;

namespace boost{
    
template<typename Value>
struct container_gen<graph_t_vertex_list,Value>
{
  using type=boost::multi_index_container<
    Value,
    boost::multi_index::indexed_by<
      boost::multi_index::random_access<>,
      boost::multi_index::ordered_non_unique<
        vertex_adapted<
          graph_t,
          boost::multi_index::member<vertex_t,double,&vertex_t::property_1>
        >
      >,
      boost::multi_index::ordered_non_unique<
        vertex_adapted<
          graph_t,
          boost::multi_index::member<vertex_t,int,&vertex_t::property_2>
        >,
        std::greater<int>
      >
    >
  >;
};

}

struct graph_t:
boost::adjacency_list<
  boost::listS,
  graph_t_vertex_list,
  boost::undirectedS,
  vertex_t
>{};

/* testing */

#include <iostream>

std::ostream& operator<<(std::ostream& os,const vertex_t& v)
{
  os<<"{"<<v.property_1<<","<<v.property_2<<"}";
  return os;
}
  
int main()
{
  graph_t g;
  add_vertex(vertex_t{0.0,0},g);
  add_vertex(vertex_t{0.1,1},g);
  add_vertex(vertex_t{0.2,2},g);
  
  for(void* p:g.m_vertices.get<1>()){
    std::cout<<static_cast<graph_t::stored_vertex*>(p)->m_property;
  }
  std::cout<<"\n";

  for(void* p:g.m_vertices.get<2>()){
    std::cout<<static_cast<graph_t::stored_vertex*>(p)->m_property;
  }
  std::cout<<"\n";
}

Output

{0,0}{0.1,1}{0.2,2}
{0.2,2}{0.1,1}{0,0}

Update Apr 14: I've refactored things a bit so that the resulting user code is much more straightforward:

struct vertex_t
{
  double property_1;
  int    property_2;
};

using graph_t= boost::adjacency_list<
  boost::listS,
  mic_listS<
    boost::multi_index::ordered_non_unique<
      boost::multi_index::member<vertex_t,double,&vertex_t::property_1>
    >,
    boost::multi_index::ordered_non_unique<
      boost::multi_index::member<vertex_t,int,&vertex_t::property_2>,
      std::greater<int>
    >
  >,
  boost::undirectedS,
  vertex_t
>;

Complete code follows:

Live Coliru Demo

#include <boost/graph/adjacency_list.hpp>
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/random_access_index.hpp>

template<typename KeyExtractor>
struct mic_list_key_extractor
{
  using result_type=typename KeyExtractor::result_type;
        
  template<typename StoredVertex>
  decltype(auto) operator()(StoredVertex& v)const{return key(v.m_property);}
  
  KeyExtractor key;
};

template<typename IndexSpecifier,typename=void>
struct mic_list_index_specifier{using type=IndexSpecifier;};

template<
  template<typename...> class IndexSpecifier,
  typename Arg1,typename Arg2,typename... Args
>
struct mic_list_index_specifier<
  IndexSpecifier<Arg1,Arg2,Args...>,
  std::void_t<typename IndexSpecifier<Arg1,Arg2,Args...>::key_from_value_type>>
{
  static constexpr bool has_tag=boost::multi_index::detail::is_tag<Arg1>::value;
  using arg1=std::conditional_t<has_tag,Arg1,mic_list_key_extractor<Arg1>>;
  using arg2=std::conditional_t<has_tag,mic_list_key_extractor<Arg2>,Arg2>;
  using type=IndexSpecifier<arg1,arg2,Args...>;
};

template<typename IndexSpecifier>
using mic_list_index_specifier_t=
  typename mic_list_index_specifier<IndexSpecifier>::type;

template<typename Value,typename... IndexSpecifiers>
struct mic_list:boost::multi_index_container<
  Value,
  boost::multi_index::indexed_by<
    boost::multi_index::random_access<>,
    mic_list_index_specifier_t<IndexSpecifiers>...
  >
>
{};

template<typename... IndexSpecifiers>
struct mic_listS;

struct mic_list_tag:
  virtual public boost::graph_detail::random_access_container_tag,
  virtual public boost::graph_detail::back_insertion_sequence_tag{};

namespace boost{

template<typename... Args>
mic_list_tag container_category(const mic_list<Args...>&){return {};}

template<typename Value,typename... IndexSpecifiers>
struct container_gen<mic_listS<IndexSpecifiers...>,Value>
{
  using type=mic_list<Value,IndexSpecifiers...>;
};

namespace detail
{

template<typename... IndexSpecifiers>
struct is_random_access<mic_listS<IndexSpecifiers...>>
{
  static constexpr bool value=true;
  using type=boost::mpl::true_;
};

}
}

/* testing */

#include <boost/multi_index/ordered_index.hpp>
#include <iostream>

struct vertex_t
{
  double property_1;
  int    property_2;
};

using graph_t= boost::adjacency_list<
  boost::listS,
  mic_listS<
    boost::multi_index::ordered_non_unique<
      boost::multi_index::member<vertex_t,double,&vertex_t::property_1>
    >,
    boost::multi_index::ordered_non_unique<
      boost::multi_index::member<vertex_t,int,&vertex_t::property_2>,
      std::greater<int>
    >
  >,
  boost::undirectedS,
  vertex_t
>;

std::ostream& operator<<(std::ostream& os,const vertex_t& v)
{
  os<<"{"<<v.property_1<<","<<v.property_2<<"}";
  return os;
}
  
int main()
{
  graph_t g;
  add_vertex(vertex_t{0.0,0},g);
  add_vertex(vertex_t{0.1,1},g);
  add_vertex(vertex_t{0.2,2},g);
  
  for(const auto& v:g.m_vertices.get<1>()){
    std::cout<<v.m_property;
  }
  std::cout<<"\n";

  for(const auto& v:g.m_vertices.get<2>()){
    std::cout<<v.m_property;
  }
  std::cout<<"\n";
}

Output

{0,0}{0.1,1}{0.2,2}
{0.2,2}{0.1,1}{0,0}