Boost Graph: with vertices as integral type, how to provide arguments to Edmund's arborescence algorithm that requires vertex iterators

Question

I am trying to solve the problem of finding an arborescence in a directed graph. This functionality is not provided directly by the boost graph library. However, an implementation is available here that builds on boost graph library.

The interface provided by the author available here specifies the following function signature:

void
edmonds_optimum_branching(TEdgeListGraph &g,
                          TVertexIndexMap index,
                          TWeightMap weight,
                          TInputIterator roots_begin,
                          TInputIterator roots_end,
                          TOutputIterator out);

The author's description of roots_begin and roots_end is:

roots_begin and roots_end are iterators over vertices of g. Any vertices in this range are guaranteed to be roots in the final branching. This range may of course be empty, in which case appropriate roots are found by the algorithm.

An example is provided by the author here and it calls the algorithm thus:

edmonds_optimum_branching<true, false, false>(G,
                                                  vertex_indices,
                                                  weights,
                                                  static_cast<Vertex *>(0), //Is this conversion to an empty iterator  ?
                                                  static_cast<Vertex *>(0),// or is this conversion to an iterator pointing to vertex 0, the first node?
                                                  std::back_inserter(branching));

If I understand correctly, roots_begin and roots_end are both NULL (?) and hence the problem is solved with no prespecified roots.

What would change suppose I have a graph with 50 vertices, and I want vertex 5 to serve as the root node?

Should the two arguments be:

edmonds_optimum_branching<true, false, false>(G,
                                                  vertex_indices,
                                                  weights,
                                                  static_cast<Vertex *>(5),
                                                  static_cast<Vertex *>(6)
                                                  std::back_inserter(branching));

This, however, shows a compile time error over the static_cast as an invalid type conversion of an int.

Should the two argument just be:

edmonds_optimum_branching<true, false, false>(G,
                                                  vertex_indices,
                                                  weights,
                                                  5,
                                                  6,
                                                  std::back_inserter(branching));

This, however, does not compile either with the error:

../include/edmonds_optimum_branching_impl.hpp:247:41: error: invalid type argument of unary ‘*’ (have ‘int’)
  247 |                 is_specified_root[index[*roots_begin]] = true;

I posted the question on the author's github page also, but it does not seem to be frequently visited by the author.

Answer 1

Iterators are generalizations of pointers. Pointers are iterators, but more complicated things like whatever std::vector<T>::begin and std::vector<T>::return return and whatever std::back_inserter constructs are also iterators. The key thing about them that you appear to be missing is that if it is an iterator, then the value associated with it is accessed as *it, not it. Because you cannot dereference an int, that is not a valid iterator.

You need to do exactly what the documentation says: provide iterators that define a range that contains 5. Because pointers are iterators, you could do

int root = 5;
edmonds_optimum_branching<true, false, false>(
    G, vertex_indices, weights,
    &root, &root + 1, // *&root = 5, std::next(&root) = &root + 1, so this range produces 5 and then ends
    std::back_inserter(branching))

The example uses the fact that pointers are iterators to pass nullptr and nullptr as defining an empty range. Typewise, nullptr is a pointer and so all the uses of *it in edmonds_optimum_branching would compile, but when actually executing the begin and end iterators would be found equal and thus no access would be made.