提升无向图合并顶点
Boost Undirected Graph Merging Vertices
我正在使用 Boost C++ 库构建邻接表来表示无向图。图上的每条边都与各自的权重相关联，我想检查权重是否大于某个阈值，而不是将 2 个顶点合并在一起。
我如何合并：
- 对于要合并的顶点，收集进出该顶点的所有边，并将边指向新顶点
- 清除合并顶点
- 移除顶点
我的问题：
在将其用于特定目的之前，我使用一个简单的程序首先构建算法。在这个程序中，我使用简单的家谱法来执行上述步骤。当我使用函数 remove_vertex(vertex, Graph) 删除顶点时，出现分段错误。
- 我不知道一旦移除顶点，图形是否会自动更新其结构？
我的C++代码如下：
#include <boost/graph/adjacency_list.hpp>
#include <boost/tuple/tuple.hpp>
#include <boost/config.hpp>
#include <iostream>
#include <vector>
#include <string>
using namespace std;
typedef boost::property<boost::vertex_index_t, int> vertex_property;
typedef boost::property<boost::edge_weight_t, float> edge_property;
typedef typename boost::adjacency_list <boost::vecS,
boost::vecS,
boost::undirectedS,
vertex_property,
edge_property> Graph;
void boostSampleGraph() {
enum family {
Jeanie, Debbie, Rick, John, Amanda, Margaret, Benjamin, N };
const char *name[] = { "Jeanie", "Debbie", "Rick", "John", "Amanda",
"Margaret", "Benjamin", "N"
};
/* actual graph structure */
Graph graph;
/* add vertices to the graph */
add_vertex(Jeanie, graph);
add_vertex(Debbie, graph);
add_vertex(Rick, graph);
add_vertex(John, graph);
add_vertex(Amanda, graph);
add_vertex(Margaret, graph);
add_vertex(Benjamin, graph);
// add_vertex(N, graph);
/* add edges to the vertices in the graph*/
add_edge(Jeanie, Debbie, edge_property(0.5f), graph);
add_edge(Jeanie, Rick, edge_property(0.2f), graph);
add_edge(Jeanie, John, edge_property(0.1f), graph);
add_edge(Debbie, Amanda, edge_property(0.3f), graph);
add_edge(Rick, Margaret, edge_property(0.4f), graph);
add_edge(John, Benjamin, edge_property(0.6f), graph);
// add_edge(Benjamin, Benjamin, edge_property(0.7f), graph);
/* vertex iterator */
boost::graph_traits<Graph>::vertex_iterator i, end;
typedef typename boost::graph_traits<
Graph>::adjacency_iterator AdjacencyIterator;
/* gets the graph vertex index */
typedef typename boost::property_map
<Graph, boost::vertex_index_t >::type IndexMap;
IndexMap index_map = get(boost::vertex_index, graph);
/* container to hold the edge descriptor info */
typedef typename boost::graph_traits<
Graph>::edge_descriptor EdgeDescriptor;
EdgeDescriptor e_descriptor;
typedef typename boost::property_map<Graph, boost::edge_weight_t
>::type EdgePropertyAccess;
EdgePropertyAccess edge_weights = get(boost::edge_weight, graph);
typedef typename boost::property_traits<boost::property_map<
Graph, boost::edge_weight_t>::const_type>::value_type EdgeValue;
float edge_size = num_vertices(graph);
std::cout << "# of Edges: " << edge_size << std::endl;
/* iterator throught the graph */
for (tie(i, end) = vertices(graph); i != end; ++i) {
std::cout << name[get(index_map, *i)];
AdjacencyIterator ai, a_end;
tie(ai, a_end) = adjacent_vertices(*i, graph);
if (ai == a_end) {
std::cout << " has no children";
} else {
std::cout << " is the parent of ";
}
for (; ai != a_end; ++ai) {
AdjacencyIterator tmp;
bool found;
tie(e_descriptor, found) = edge(*i, *ai, graph);
float weights_ = 0.0f;
if (found) {
EdgeValue edge_val = boost::get(
boost::edge_weight, graph, e_descriptor);
weights_ = edge_val;
if (weights_ > 0.3f) {
// - remove and merge
AdjacencyIterator aI, aEnd;
tie(aI, aEnd) = adjacent_vertices(*ai, graph);
for (; aI != aEnd; aI++) {
EdgeDescriptor ed;
bool located;
tie(ed, located) = edge(*aI, *ai, graph);
if (located && *aI != *i) {
add_edge(
get(index_map, *i), get(index_map, *aI), graph);
}
std::cout << "\n DEBUG: " << *i << " "
<< *ai << " "
<< *aI << " ";
}
std::cout << std::endl;
clear_vertex(*ai, graph);
remove_vertex(*ai, graph);
// std::cout << "\nGraph Size: " <<
// num_vertices(graph) << std::endl;
}
}
// ai = tmp;
std::cout << name[get(index_map, *ai)];
if (boost::next(ai) != a_end) {
std::cout << ", ";
}
}
std::cout << std::endl << std::endl;
}
std::cout << "\nGraph Size: " << num_vertices(graph) << std::endl;
}
int main(int argc, const char *argv[]) {
boostSampleGraph();
return 0;
}
我能得到一些帮助和想法吗，我在哪里做错了。
我不知道你实际上想用 OP 中显示的算法实现什么。
然而，这里有一个大大简化了代码，因此至少它可以安全地工作：
- 使用
Vertex 捆绑的 属性 顶点类型 (id, name)
- 尽可能使用范围循环（参见
mir、shorthand 从 std::pair 迭代器创建 boost::iterator_range）
- 代码是以独立于容器选择的方式编写的（因此当您在
Graph 类型声明中将 vecS 替换为 listS 时，它的工作原理是一样的）
- 它使用
out_edges 而不是 adjacent_vertices 以从 AdjacencyGraph 概念中获益更多，并避免通过（源，目标）顶点反向查找边描述符
最重要的是，它使用 std::set<vertex_descriptor> 个已经 "removed" 的顶点。实际删除发生在稍后，因此我们在迭代不断变化的容器时不会出现未定义的行为
在 valgrind
#include <boost/graph/adjacency_list.hpp>
#include <iostream>
struct Vertex {
int id;
const char* name;
Vertex(int i = -1, const char* name = "default") : id(i), name(name) {}
};
template <typename It> boost::iterator_range<It> mir(std::pair<It, It> const& p) {
return boost::make_iterator_range(p.first, p.second);
}
template <typename It> boost::iterator_range<It> mir(It b, It e) {
return boost::make_iterator_range(b, e);
}
typedef typename boost::adjacency_list<
boost::vecS, boost::vecS,
boost::undirectedS,
Vertex, // bundled properties (id, name)
boost::property<boost::edge_weight_t, float> // interior property
> Graph;
Graph make() {
Graph graph;
auto Jeanie = add_vertex(Vertex { 0, "Jeanie" }, graph);
auto Debbie = add_vertex(Vertex { 1, "Debbie" }, graph);
auto Rick = add_vertex(Vertex { 2, "Rick" }, graph);
auto John = add_vertex(Vertex { 3, "John" }, graph);
auto Amanda = add_vertex(Vertex { 4, "Amanda" }, graph);
auto Margaret = add_vertex(Vertex { 5, "Margaret" }, graph);
auto Benjamin = add_vertex(Vertex { 6, "Benjamin" }, graph);
add_edge(Jeanie, Debbie, 0.5f, graph);
add_edge(Jeanie, Rick, 0.2f, graph);
add_edge(Jeanie, John, 0.1f, graph);
add_edge(Debbie, Amanda, 0.3f, graph);
add_edge(Rick, Margaret, 0.4f, graph);
add_edge(John, Benjamin, 0.6f, graph);
return graph;
}
Graph reduce(Graph graph) {
/* vertex iterator */
using vertex_descriptor = boost::graph_traits<Graph>::vertex_descriptor;
std::cout << "# of vertices: " << num_vertices(graph) << "\n";
std::cout << "# of edges: " << num_edges(graph) << "\n";
std::set<vertex_descriptor> to_remove;
/* iterator throught the graph */
for (auto self : mir(vertices(graph)))
{
std::cout << graph[self].name << (boost::empty(mir(out_edges(self, graph)))? " has no children " : " is the parent of ");
for(auto edge : mir(out_edges(self, graph))) {
auto weight = boost::get(boost::edge_weight, graph, edge);
auto mid_point = target(edge, graph);
if (to_remove.count(mid_point)) // already elided
break;
if (weight > 0.3f) {
std::set<vertex_descriptor> traversed;
for (auto hop : mir(out_edges(mid_point, graph))) {
auto hop_target = target(hop, graph);
if (hop_target != self)
add_edge(self, hop_target, graph);
std::cout << "\n DEBUG: " << graph[self].name << " " << graph[mid_point].name << " " << graph[hop_target].name << " ";
}
std::cout << "\n";
clear_vertex(mid_point, graph);
to_remove.insert(mid_point);
}
std::cout << graph[mid_point].name;
}
std::cout << "\n\n";
}
for(auto vd : to_remove)
{
clear_vertex(vd, graph);
remove_vertex(vd, graph);
}
std::cout << "# of vertices: " << num_vertices(graph) << "\n";
std::cout << "# of edges: " << num_edges(graph) << "\n";
return graph;
}
void save(Graph const& g, const char* fname);
int main() {
auto const g = make();
auto const h = reduce(g);
save(g, "before.dot");
save(h, "after.dot");
}
#include <boost/graph/graphviz.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/property_map/function_property_map.hpp>
#include <boost/property_map/transform_value_property_map.hpp>
#include <boost/format.hpp>
#include <fstream>
void save(Graph const& g, const char* fname) {
std::ofstream ofs(fname);
using namespace boost;
write_graphviz(
ofs,
g,
make_label_writer(make_function_property_map<Graph::vertex_descriptor, std::string>([&] (Graph::vertex_descriptor v){ return g[v].name; })),
make_label_writer(make_transform_value_property_map([](float v){return boost::format("%1.1f") % v;}, boost::get(edge_weight, g)))
);
}
版画
# of vertices: 7
# of edges: 6
Jeanie is the parent of
DEBUG: Jeanie Debbie Jeanie
DEBUG: Jeanie Debbie Amanda
DebbieJohnAmanda
Debbie has no children
Rick is the parent of Jeanie
DEBUG: Rick Margaret Rick
Margaret
John is the parent of Jeanie
DEBUG: John Benjamin John
Benjamin
Amanda is the parent of Jeanie
Margaret has no children
Benjamin has no children
# of vertices: 4
# of edges: 3
之前的图表：
之后的图表：
我正在使用 Boost C++ 库构建邻接表来表示无向图。图上的每条边都与各自的权重相关联，我想检查权重是否大于某个阈值，而不是将 2 个顶点合并在一起。
我如何合并：
- 对于要合并的顶点，收集进出该顶点的所有边，并将边指向新顶点
- 清除合并顶点
- 移除顶点
我的问题： 在将其用于特定目的之前，我使用一个简单的程序首先构建算法。在这个程序中，我使用简单的家谱法来执行上述步骤。当我使用函数 remove_vertex(vertex, Graph) 删除顶点时，出现分段错误。
- 我不知道一旦移除顶点，图形是否会自动更新其结构？
我的C++代码如下：
#include <boost/graph/adjacency_list.hpp>
#include <boost/tuple/tuple.hpp>
#include <boost/config.hpp>
#include <iostream>
#include <vector>
#include <string>
using namespace std;
typedef boost::property<boost::vertex_index_t, int> vertex_property;
typedef boost::property<boost::edge_weight_t, float> edge_property;
typedef typename boost::adjacency_list <boost::vecS,
boost::vecS,
boost::undirectedS,
vertex_property,
edge_property> Graph;
void boostSampleGraph() {
enum family {
Jeanie, Debbie, Rick, John, Amanda, Margaret, Benjamin, N };
const char *name[] = { "Jeanie", "Debbie", "Rick", "John", "Amanda",
"Margaret", "Benjamin", "N"
};
/* actual graph structure */
Graph graph;
/* add vertices to the graph */
add_vertex(Jeanie, graph);
add_vertex(Debbie, graph);
add_vertex(Rick, graph);
add_vertex(John, graph);
add_vertex(Amanda, graph);
add_vertex(Margaret, graph);
add_vertex(Benjamin, graph);
// add_vertex(N, graph);
/* add edges to the vertices in the graph*/
add_edge(Jeanie, Debbie, edge_property(0.5f), graph);
add_edge(Jeanie, Rick, edge_property(0.2f), graph);
add_edge(Jeanie, John, edge_property(0.1f), graph);
add_edge(Debbie, Amanda, edge_property(0.3f), graph);
add_edge(Rick, Margaret, edge_property(0.4f), graph);
add_edge(John, Benjamin, edge_property(0.6f), graph);
// add_edge(Benjamin, Benjamin, edge_property(0.7f), graph);
/* vertex iterator */
boost::graph_traits<Graph>::vertex_iterator i, end;
typedef typename boost::graph_traits<
Graph>::adjacency_iterator AdjacencyIterator;
/* gets the graph vertex index */
typedef typename boost::property_map
<Graph, boost::vertex_index_t >::type IndexMap;
IndexMap index_map = get(boost::vertex_index, graph);
/* container to hold the edge descriptor info */
typedef typename boost::graph_traits<
Graph>::edge_descriptor EdgeDescriptor;
EdgeDescriptor e_descriptor;
typedef typename boost::property_map<Graph, boost::edge_weight_t
>::type EdgePropertyAccess;
EdgePropertyAccess edge_weights = get(boost::edge_weight, graph);
typedef typename boost::property_traits<boost::property_map<
Graph, boost::edge_weight_t>::const_type>::value_type EdgeValue;
float edge_size = num_vertices(graph);
std::cout << "# of Edges: " << edge_size << std::endl;
/* iterator throught the graph */
for (tie(i, end) = vertices(graph); i != end; ++i) {
std::cout << name[get(index_map, *i)];
AdjacencyIterator ai, a_end;
tie(ai, a_end) = adjacent_vertices(*i, graph);
if (ai == a_end) {
std::cout << " has no children";
} else {
std::cout << " is the parent of ";
}
for (; ai != a_end; ++ai) {
AdjacencyIterator tmp;
bool found;
tie(e_descriptor, found) = edge(*i, *ai, graph);
float weights_ = 0.0f;
if (found) {
EdgeValue edge_val = boost::get(
boost::edge_weight, graph, e_descriptor);
weights_ = edge_val;
if (weights_ > 0.3f) {
// - remove and merge
AdjacencyIterator aI, aEnd;
tie(aI, aEnd) = adjacent_vertices(*ai, graph);
for (; aI != aEnd; aI++) {
EdgeDescriptor ed;
bool located;
tie(ed, located) = edge(*aI, *ai, graph);
if (located && *aI != *i) {
add_edge(
get(index_map, *i), get(index_map, *aI), graph);
}
std::cout << "\n DEBUG: " << *i << " "
<< *ai << " "
<< *aI << " ";
}
std::cout << std::endl;
clear_vertex(*ai, graph);
remove_vertex(*ai, graph);
// std::cout << "\nGraph Size: " <<
// num_vertices(graph) << std::endl;
}
}
// ai = tmp;
std::cout << name[get(index_map, *ai)];
if (boost::next(ai) != a_end) {
std::cout << ", ";
}
}
std::cout << std::endl << std::endl;
}
std::cout << "\nGraph Size: " << num_vertices(graph) << std::endl;
}
int main(int argc, const char *argv[]) {
boostSampleGraph();
return 0;
}
我能得到一些帮助和想法吗，我在哪里做错了。
我不知道你实际上想用 OP 中显示的算法实现什么。
然而，这里有一个大大简化了代码，因此至少它可以安全地工作：
- 使用
Vertex捆绑的 属性 顶点类型 (id, name) - 尽可能使用范围循环（参见
mir、shorthand 从std::pair迭代器创建boost::iterator_range） - 代码是以独立于容器选择的方式编写的（因此当您在
Graph类型声明中将vecS替换为listS时，它的工作原理是一样的） - 它使用
out_edges而不是adjacent_vertices以从AdjacencyGraph概念中获益更多，并避免通过（源，目标）顶点反向查找边描述符 最重要的是，它使用
std::set<vertex_descriptor>个已经 "removed" 的顶点。实际删除发生在稍后，因此我们在迭代不断变化的容器时不会出现未定义的行为在 valgrind
下干净地运行
#include <boost/graph/adjacency_list.hpp>
#include <iostream>
struct Vertex {
int id;
const char* name;
Vertex(int i = -1, const char* name = "default") : id(i), name(name) {}
};
template <typename It> boost::iterator_range<It> mir(std::pair<It, It> const& p) {
return boost::make_iterator_range(p.first, p.second);
}
template <typename It> boost::iterator_range<It> mir(It b, It e) {
return boost::make_iterator_range(b, e);
}
typedef typename boost::adjacency_list<
boost::vecS, boost::vecS,
boost::undirectedS,
Vertex, // bundled properties (id, name)
boost::property<boost::edge_weight_t, float> // interior property
> Graph;
Graph make() {
Graph graph;
auto Jeanie = add_vertex(Vertex { 0, "Jeanie" }, graph);
auto Debbie = add_vertex(Vertex { 1, "Debbie" }, graph);
auto Rick = add_vertex(Vertex { 2, "Rick" }, graph);
auto John = add_vertex(Vertex { 3, "John" }, graph);
auto Amanda = add_vertex(Vertex { 4, "Amanda" }, graph);
auto Margaret = add_vertex(Vertex { 5, "Margaret" }, graph);
auto Benjamin = add_vertex(Vertex { 6, "Benjamin" }, graph);
add_edge(Jeanie, Debbie, 0.5f, graph);
add_edge(Jeanie, Rick, 0.2f, graph);
add_edge(Jeanie, John, 0.1f, graph);
add_edge(Debbie, Amanda, 0.3f, graph);
add_edge(Rick, Margaret, 0.4f, graph);
add_edge(John, Benjamin, 0.6f, graph);
return graph;
}
Graph reduce(Graph graph) {
/* vertex iterator */
using vertex_descriptor = boost::graph_traits<Graph>::vertex_descriptor;
std::cout << "# of vertices: " << num_vertices(graph) << "\n";
std::cout << "# of edges: " << num_edges(graph) << "\n";
std::set<vertex_descriptor> to_remove;
/* iterator throught the graph */
for (auto self : mir(vertices(graph)))
{
std::cout << graph[self].name << (boost::empty(mir(out_edges(self, graph)))? " has no children " : " is the parent of ");
for(auto edge : mir(out_edges(self, graph))) {
auto weight = boost::get(boost::edge_weight, graph, edge);
auto mid_point = target(edge, graph);
if (to_remove.count(mid_point)) // already elided
break;
if (weight > 0.3f) {
std::set<vertex_descriptor> traversed;
for (auto hop : mir(out_edges(mid_point, graph))) {
auto hop_target = target(hop, graph);
if (hop_target != self)
add_edge(self, hop_target, graph);
std::cout << "\n DEBUG: " << graph[self].name << " " << graph[mid_point].name << " " << graph[hop_target].name << " ";
}
std::cout << "\n";
clear_vertex(mid_point, graph);
to_remove.insert(mid_point);
}
std::cout << graph[mid_point].name;
}
std::cout << "\n\n";
}
for(auto vd : to_remove)
{
clear_vertex(vd, graph);
remove_vertex(vd, graph);
}
std::cout << "# of vertices: " << num_vertices(graph) << "\n";
std::cout << "# of edges: " << num_edges(graph) << "\n";
return graph;
}
void save(Graph const& g, const char* fname);
int main() {
auto const g = make();
auto const h = reduce(g);
save(g, "before.dot");
save(h, "after.dot");
}
#include <boost/graph/graphviz.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/property_map/function_property_map.hpp>
#include <boost/property_map/transform_value_property_map.hpp>
#include <boost/format.hpp>
#include <fstream>
void save(Graph const& g, const char* fname) {
std::ofstream ofs(fname);
using namespace boost;
write_graphviz(
ofs,
g,
make_label_writer(make_function_property_map<Graph::vertex_descriptor, std::string>([&] (Graph::vertex_descriptor v){ return g[v].name; })),
make_label_writer(make_transform_value_property_map([](float v){return boost::format("%1.1f") % v;}, boost::get(edge_weight, g)))
);
}
版画
# of vertices: 7
# of edges: 6
Jeanie is the parent of
DEBUG: Jeanie Debbie Jeanie
DEBUG: Jeanie Debbie Amanda
DebbieJohnAmanda
Debbie has no children
Rick is the parent of Jeanie
DEBUG: Rick Margaret Rick
Margaret
John is the parent of Jeanie
DEBUG: John Benjamin John
Benjamin
Amanda is the parent of Jeanie
Margaret has no children
Benjamin has no children
# of vertices: 4
# of edges: 3
之前的图表：
之后的图表：