I am trying to create a boost::subgraph of a boost::adjacency_list, and I'm getting an error on creation that I do not understand. Similar code exclusively using the boost::adjacency_list builds and works just fine.
The line creating base_graph is sufficient for the error, but the rest demonstrates how I've been using the adjacency_list on its own, and thereby how I expect to use the subgraph.
Sample code:
struct Component { int vert_id; };
struct Connection { int edge_id; };
struct NetworkData { int graph_id; };
boost::subgraph<boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, Component, Connection, NetworkData>> base_graph;
auto& sub_graph = base_graph.create_subgraph();
base_graph[boost::graph_bundle].graph_id;
sub_graph[boost::graph_bundle].graph_id;
const auto base_vert = boost::add_vertex(base_graph);
const auto sub_vert = boost::add_vertex(sub_graph);
base_graph[base_vert].vert_id;
base_graph[sub_vert].vert_id;
sub_graph[base_vert].vert_id;
sub_graph[sub_vert].vert_id;
const auto [base_edge, a1] = boost::add_edge(base_vert, sub_vert, base_graph);
const auto [sub_edge, a2] = boost::add_edge(base_vert, sub_vert, sub_graph);
base_graph[base_edge].edge_id;
base_graph[sub_edge].edge_id;
sub_graph[base_edge].edge_id;
sub_graph[sub_edge].edge_id;
Error log:
In file included from /.../include/boost/graph/adjacency_list.hpp:255,
from /.../main.cpp:1:
/.../include/boost/graph/detail/adjacency_list.hpp: In instantiation of ‘struct boost::detail::adj_list_any_edge_pmap::bind_<boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, Component, Connection, NetworkData>, Connection, boost::edge_index_t>’:
/.../include/boost/graph/detail/adjacency_list.hpp:2801:12: required from ‘struct boost::detail::adj_list_choose_edge_pmap<boost::edge_index_t, boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, Component, Connection, NetworkData>, Connection>’
/.../include/boost/graph/detail/adjacency_list.hpp:2809:16: required from ‘struct boost::detail::adj_list_edge_property_selector::bind_<boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, Component, Connection, NetworkData>, Connection, boost::edge_index_t>’
/.../include/boost/graph/properties.hpp:218:12: required from ‘struct boost::detail::edge_property_map<boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, Component, Connection, NetworkData>, boost::edge_index_t>’
/.../include/boost/graph/properties.hpp:234:8: required from ‘struct boost::property_map<boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, Component, Connection, NetworkData>, boost::edge_index_t, void>’
/.../include/boost/graph/subgraph.hpp:351:64: required from ‘class boost::subgraph<boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, Component, Connection, NetworkData> >’
/.../main.cpp:46:122: required from here
/.../include/boost/graph/detail/adjacency_list.hpp:2764:33: error: forming reference to void
2764 | typedef value_type& reference;
| ^~~~~~~~~
/.../include/boost/graph/detail/adjacency_list.hpp:2765:39: error: forming reference to void
2765 | typedef const value_type& const_reference;
| ^~~~~~~~~~~~~~~
/.../include/boost/graph/detail/adjacency_list.hpp:2770:17: error: forming reference to void
2770 | type;
| ^~~~
/.../include/boost/graph/detail/adjacency_list.hpp:2774:17: error: forming reference to void
2774 | const_type;
| ^~~~~~~~~~
vert_id, edge_id and graph_id are all notional to demonstrate how I anticipate accessing node/edge data.
I have figured out that if I change Connection to boost::property<boost::edge_index_t, std::size_t> it will build. But this prevents access to the graph_bundle, as well as makes access to edge properties less convenient, and I don't know how to use boost::property.
I've also reviewed this SO question and this SO question but they do not use subgraph, and my issue appears to be related to subgraph particularly.
I get similar errors using GCC13 and MSVC.
Subgraph requires vertex_index as well as edge_index: doc
A graph type modeling
VertexMutableGraphandEdgeMutableGraph. Also the graph must have internalvertex_indexandedge_indexproperties. The vertex indices must be maintained automatically by the graph, whereas the edge indices will be assigned by the subgraph class implementation.
The simplest way to automatically advertise this property is to use the internal property tag instead of your bundle type:
// struct Connection { int edge_id; };
using Connection = boost::property<boost::edge_index_t, int>;
Indeed, with some modifications, here's the thing working:
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/subgraph.hpp>
struct Component {
int vert_id;
};
#ifndef CUSTOM_PROPERTY_MAPS
using Connection = boost::property<boost::edge_index_t, int>;
#else
struct Connection {
int edge_id;
};
#endif
struct NetworkData {
int graph_id;
};
using G = boost::adjacency_list< //
boost::vecS, boost::vecS, boost::directedS, //
Component, //
Connection, //
NetworkData //
>;
using Sub = boost::subgraph<G>;
int main() {
Sub base_graph;
auto& sub_graph = base_graph.create_subgraph();
get_property(base_graph).graph_id;
get_property(sub_graph).graph_id;
auto const base_vert = add_vertex(base_graph);
auto const sub_vert = add_vertex(sub_graph);
base_graph[base_vert].vert_id;
base_graph[sub_vert].vert_id;
sub_graph[base_vert].vert_id;
sub_graph[sub_vert].vert_id;
auto const [base_edge, a1] = add_edge(base_vert, sub_vert, base_graph);
auto const [sub_edge, a2] = add_edge(base_vert, sub_vert, sub_graph);
#ifndef CUSTOM_PROPERTY_MAPS
auto bmi = get(boost::edge_index, base_graph);
auto smi = get(boost::edge_index, sub_graph);
bmi[base_edge];
smi[sub_edge];
#else
base_graph[base_edge].edge_id;
// base_graph[sub_edge].edge_id; // UB!?
// sub_graph[base_edge].edge_id; // UB!?
sub_graph[sub_edge].edge_id;
#endif
}
You might insist on bundled properties. In that case you have to tweak the required traits to tell subgraph about the edge index:
namespace Lib {
struct Component { int vert_id; };
struct Connection { int edge_id = 0; };
struct NetworkData { int graph_id; };
using G = boost::adjacency_list< //
boost::vecS, boost::vecS, boost::directedS, //
Component, //
Connection, //
NetworkData //
>;
} // namespace Lib
template <>
struct boost::property_map<Lib::G, boost::edge_index_t>
: boost::property_map<Lib::G, decltype(&Lib::Connection::edge_id)> {};
namespace Lib {
// ADL accessible
static inline auto get(boost::edge_index_t, G const& g) { return boost::get(&Connection::edge_id, g); }
static inline auto get(boost::edge_index_t, G& g) { return boost::get(&Connection::edge_id, g); }
using Sub = boost::subgraph<G>;
} // namespace Lib
See it Live On Coliru as well