gpt4 book ai didi

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

转载 作者:太空狗 更新时间:2023-10-29 21:18:06 25 4
gpt4 key购买 nike

我正在努力从我的图中删除所有没有连接边的节点(使用定义的模式 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

关于c++ - BGL 中顶点迭代器的度数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30904005/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com