Boost图:以顶点为整型，如何为Edmund的树形算法提供参数，该算法需要顶点迭代器

Question

我试图解决在有向图中找到树形图的问题。这个功能是boost图形库中的未直接提供。然而，一个基于boost图形库的实现是可用的这里。

作者可用的这里提供的接口指定了以下函数签名：

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

作者对roots_begin和roots_end的描述如下：

roots_begin和roots_end是g的顶点上的迭代器，在此范围内的任何顶点都保证是最终分支中的根。当然，这个范围可能是空的，在这种情况下，算法可以找到适当的根。

作者这里提供了一个示例，它调用该算法，因此：

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

如果我正确理解，roots_begin和roots_end都是NULL (?)因此，这个问题没有预先指定的根就能得到解决。

如果我有一个有50个顶点的图，并且我希望顶点5充当根节点，那么会发生什么变化呢？

这两个论点是否应该是：

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

但是，这将显示static_cast上的编译时错误是int的无效类型转换。

这两个论点应该是：

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

但是，这两种方法都没有使用错误进行编译：

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

我还在提交人的github页面上发布了这个问题，但提交人似乎并不经常访问它。

Answer 1

迭代器是指针的概括。指针是迭代器，但是更复杂的事情，如std::vector<T>::begin和std::vector<T>::return返回以及任何std::back_inserter构造都是迭代器。您似乎忽略了它们的关键之处在于，如果it是一个迭代器，那么与它相关的值是以*it而不是it的形式访问的。因为不能取消引用int，所以这不是有效的迭代器。

您需要按照文档所说的那样做:提供定义包含5的范围的迭代器。因为指针是迭代器，所以可以这样做。

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

该示例使用指针是迭代器来传递nullptr和nullptr作为定义空范围的事实。就类型而言，nullptr是一个指针，所以*it在edmonds_optimum_branching中的所有使用都会编译，但是当实际执行时，开始迭代器和结束迭代器将是相等的，因此不会进行访问。