顶点迭代器在BGL度 [英] Degree of Vertex Iterator in BGL

问题描述

我努力从我的图中删除所有的节点（使用定义的模式的这里），它们没有连接边。我（MWE）code迄今如下：

I am endeavouring to remove all of the nodes from my graph (using the pattern defined here) which have no connecting edges. My (MWE) code thus far is as follows:

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

不幸的是，该投诉汇编code错误的：

Unfortunately, the code errors out in compilation with the complaint:

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

我的期望是，六是 vertex_iterator 键，取消引用它应该给我一个有效的描述符。我不知道为什么，这是不会发生。

My expectation is that vi is a vertex_iterator and dereferencing it should give me a valid descriptor. I am not sure why this is not happening.

我怎样才能做到这一点？

How can I achieve this?

推荐答案

您需要通过的额外的参数先按g 到度（） 。

You need to pass the extra argument g to degree().

更进一步的LabeledGraph适配器没有建模 MutableGraph 的 remove_vertex 呼叫不能正常工作。

Further more as the LabeledGraph adaptor doesn't model a MutableGraph the remove_vertex call can't work.

幸运的是，你可以得到下面的图形和变异的。我不得不对 LabeledGraph 读取多达看是否有不良影响：

Luckily you can get the underlying graph and mutate that. I'd have to read up on LabeledGraph to see whether there are adverse effects:

<大骨节病> 住在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：

Maybe you can do without the LabeledGraph:

<大骨节病> 住在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 

这篇关于顶点迭代器在BGL度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！