2

I have a question related to boost graph library.

boost::adajacency_list has a constructor from a range of edge iterators and the number of vertices.

template <class EdgeIterator>
adjacency_list(EdgeIterator first, EdgeIterator last,
               vertices_size_type n, 
               edges_size_type m = 0, 
               const GraphProperty& p = GraphProperty())

I try to make use of this constructor with the following code,

#include <boost/graph/adjacency_list.hpp>

using namespace boost;
using Graph = adjacency_list<>;

int main()
{
  using edge_iterator = graph_traits<Graph>::edge_iterator;

  Graph g;
  auto const vd0 = add_vertex(g);
  auto const vd1 = add_vertex(g);
  add_edge(vd0, vd1, g);

  edge_iterator ei, ej;
  tie(ei, ej) = edges(g);

  Graph h(ei, ej, 2);
  return 0;
}

The code fails to compile with following error,

/usr/include/boost/graph/detail/adjacency_list.hpp:2121:29: error: ‘boost::detail::adj_list_edge_iterator<boost::range_detail::integer_iterator<long unsigned int>, boost::detail::out_edge_iter<__gnu_cxx::__normal_iterator<boost::detail::stored_edge_property<long unsigned int, boost::no_property>*, std::vector<boost::detail::stored_edge_property<long unsigned int, boost::no_property>, std::allocator<boost::detail::stored_edge_property<long unsigned int, boost::no_property> > > >, long unsigned int, boost::detail::edge_desc_impl<boost::directed_tag, long unsigned int>, long int>, boost::adjacency_list<> >::value_type {aka class boost::detail::edge_desc_impl<boost::directed_tag, long unsigned int>}’ has no member named ‘first’
           add_edge((*first).first, (*first).second,
                    ~~~~~~~~~^~~~~
/usr/include/boost/graph/detail/adjacency_list.hpp:2121:45: error: ‘boost::detail::adj_list_edge_iterator<boost::range_detail::integer_iterator<long unsigned int>, boost::detail::out_edge_iter<__gnu_cxx::__normal_iterator<boost::detail::stored_edge_property<long unsigned int, boost::no_property>*, std::vector<boost::detail::stored_edge_property<long unsigned int, boost::no_property>, std::allocator<boost::detail::stored_edge_property<long unsigned int, boost::no_property> > > >, long unsigned int, boost::detail::edge_desc_impl<boost::directed_tag, long unsigned int>, long int>, boost::adjacency_list<> >::value_type {aka class boost::detail::edge_desc_impl<boost::directed_tag, long unsigned int>}’ has no member named ‘second’
           add_edge((*first).first, (*first).second,

Reference: https://www.boost.org/doc/libs/1_37_0/libs/graph/doc/adjacency_list.html

sehe
  • 374,641
  • 47
  • 450
  • 633
MaxPlankton
  • 1,158
  • 14
  • 28

1 Answers1

1

If you just wanted the copy, like you have in your sample:

Graph h = g;

Or if g is of a different type: copy_graph¹

Your Approach:

std::vector<std::pair<Graph::vertex_descriptor, Graph::vertex_descriptor> > pairlist;
for (auto ed : boost::make_iterator_range(edges(g))) {
    pairlist.emplace_back(source(ed, g), target(ed, g));
}

Graph h(pairlist.begin(), pairlist.end(), 2);

¹ see also copy a graph (adjacency_list) to another one

Live Demo

Showing all the approaches mentioned:

Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/copy.hpp>

using namespace boost;
using Graph = adjacency_list<>;

int main() {
    Graph g;
    add_edge(add_vertex(g), add_vertex(g), g);

    std::vector<std::pair<Graph::vertex_descriptor, Graph::vertex_descriptor> > pairlist;
    for (auto ed : boost::make_iterator_range(edges(g))) {
        pairlist.emplace_back(source(ed, g), target(ed, g));
    }

    Graph h(pairlist.begin(), pairlist.end(), num_vertices(g));
    Graph i = h;
    Graph j;
    boost::copy_graph(h, j);
}
sehe
  • 374,641
  • 47
  • 450
  • 633
  • Thanks. The name `EdgeIterator` really confuses me. I thought it's of type `graph::edge_iterator`. It really is a `std::pair`. BGL documentation does suggest, *the value type of the EdgeIterator must be a std::pair, where the type in the pair is an integer type*. – MaxPlankton May 03 '18 at 14:48
  • No. EdgeIterator is an iterator, whose `value_type` is a pair. In fact, the docs state: [_"Creates a graph object with n vertices and with the edges specified in the edge list given by the range [first, last). The EdgeIterator must be a model of InputIterator. The value type of the EdgeIterator must be a std::pair, where the type in the pair is an integer type. The integers will correspond to vertices, and they must all fall in the range of [0, n)."_](https://www.boost.org/doc/libs/1_67_0/libs/graph/doc/adjacency_list.html) – sehe May 03 '18 at 15:33