c++ - BGL中的顶点迭代器度

我正在努力从图形中删除没有连接边的所有节点(使用定义的模式here)。到目前为止，我的(MWE)代码如下:

//g++ -O3 question.cpp -o question.exe
#include <iostream>

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/labeled_graph.hpp>
#include <boost/graph/iteration_macros.hpp>

typedef long long node_id_t;

typedef boost::adjacency_list<
  boost::listS,           // Store out-edges of each vertex in a std::list
  boost::listS,           // Store vertex set in a std::list
  boost::bidirectionalS,  // The file dependency graph is directed
  boost::no_property,     // vertex properties
  boost::no_property      // edge properties
> AdjGraph;

typedef boost::labeled_graph<
  AdjGraph,
  node_id_t          // Node ID
> LabeledGraph;

int main(){
  LabeledGraph g;

  add_vertex( 10, g );
  add_vertex( 20, g );
  add_vertex( 30, g );
  add_vertex( 40, g );
  add_vertex( 50, g );

  boost::graph_traits<LabeledGraph>::vertex_iterator vi, vi_end, next;
  boost::tie(vi, vi_end) = boost::vertices(g);
  for (next = vi; vi != vi_end; vi = next) {
    ++next;
    if(boost::degree(*vi)==0)
      boost::remove_vertex(*vi, g);
  }
}

不幸的是，代码错误在编译时出现了以下抱怨:

question.cpp:36:25: error: no matching function for call to ‘degree(void*&)’
 if(boost::degree(*vi)==0)

我的期望是vi是vertex_iterator，取消引用它应该给我一个有效的描述符。我不确定为什么这种情况不会发生。

我该如何实现？

最佳答案

您需要传递extra argument g to degree() 。

此外，由于LabeledGraph适配器无法为MutableGraph建模，因此remove_vertex调用无法正常工作。

幸运的是，您可以获取基础图形并将其变异。我必须阅读LabeledGraph才能查看是否有不良影响:

Live On Coliru

// g++ -O3 question.cpp -o question.exe
#include <iostream>

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/labeled_graph.hpp>
#include <boost/graph/iteration_macros.hpp>

typedef long long node_id_t;

typedef boost::adjacency_list<boost::listS,          // Store out-edges of each vertex in a std::list
                              boost::listS,          // Store vertex set in a std::list
                              boost::bidirectionalS, // The file dependency graph is directed
                              boost::no_property,    // vertex properties
                              boost::no_property     // edge properties
                              > AdjGraph;

typedef boost::labeled_graph<AdjGraph,
                             node_id_t // Node ID
                             > LabeledGraph;

int main() {
    LabeledGraph g;

    add_vertex(10, g);
    add_vertex(20, g);
    add_vertex(30, g);
    add_vertex(40, g);
    add_vertex(50, g);

    boost::graph_traits<LabeledGraph>::vertex_iterator vi, vi_end, next;

    AdjGraph& underlying = g.graph();

    boost::tie(vi, vi_end) = boost::vertices(underlying);
    for (next = vi; vi != vi_end; vi = next) {
        ++next;
        if (boost::degree(*vi, underlying) == 0)
            boost::remove_vertex(*vi, underlying);
    }
}

也许您可以不用LabeledGraph:

Live On Coliru

// g++ -O3 question.cpp -o question.exe
#include <iostream>

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

typedef long long node_id_t;

typedef boost::adjacency_list<boost::listS,          // Store out-edges of each vertex in a std::list
                              boost::listS,          // Store vertex set in a std::list
                              boost::bidirectionalS, // The file dependency graph is directed
                              node_id_t,             // vertex properties
                              boost::no_property     // edge properties
                              > AdjGraph;

int main() {
    AdjGraph g;

               add_vertex(10, g);
    auto v20 = add_vertex(20, g);
               add_vertex(30, g);
    auto v40 = add_vertex(40, g);
               add_vertex(50, g);

    add_edge(v40, v20, g);

    std::cout << "BEFORE:\n";
    print_graph(g, boost::get(boost::vertex_bundle, g));

    boost::graph_traits<AdjGraph>::vertex_iterator vi, vi_end, next;

    boost::tie(vi, vi_end) = boost::vertices(g);
    for (next = vi; vi != vi_end; vi = next) {
        ++next;
        if (boost::degree(*vi, g) == 0)
            boost::remove_vertex(*vi, g);
    }

    std::cout << "\n---\nAFTER:\n";
    print_graph(g, boost::get(boost::vertex_bundle, g));
}

打印品:

BEFORE:
10 -->
20 -->
30 -->
40 --> 20
50 -->

---
AFTER:
20 -->
40 --> 20