我正在努力从我的图中删除所有没有连接边的节点(使用定义的模式 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
以查看是否存在不利影响:
// 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:
// 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
关于c++ - BGL 中顶点迭代器的度数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30904005/