提升无向图合并顶点

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

  • 下干净地运行

Live On Coliru

#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

之前的图表:

之后的图表: