Boost Graph：以顶点为整数类型，如何为需要顶点迭代器的 Edmund 树状算法提供参数

Question

我正在尝试解决在有向图中找到树状结构的问题。此功能 by the boost graph library. However, an implementation is available here 建立在 boost 图形库的基础上。

作者提供的接口可用here指定如下函数签名：

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

作者对roots_begin和roots_end的描述是：

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.

作者提供了一个例子here，算法调用如下：

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 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 是一个指针，因此 edmonds_optimum_branching 中 *it 的所有使用都可以编译，但是当实际执行开始和结束迭代器时，会发现它们相等，因此不会进行访问.

Boost Graph：以顶点为整数类型，如何为需要顶点迭代器的 Edmund 树状算法提供参数

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

c++

algorithm

boost

graph

boost-graph