c++ - Boost Undirected Graph Merging Vertices -

i using boost c++ library build adjacency list represent undirected graph. each edge on graph associated respective weights , want check if weight greater threshold merge 2 vertices together.

how merge:

• for vertex merge, gather edges , vertex , direct edges new vertex
• clear merging vertex
• remove vertex

my problem: use simple program first construct algorithm before use purpose. in program using simple family tree method perform above steps. when remove vertex using function remove_vertex(vertex, graph) segmentation fault.

• i cannot figure out if once vertex removed, graph automatically updates structure?

my c++ code follows:

#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 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 vertices in 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 graph vertex index */  typedef typename boost::property_map     <graph, boost::vertex_index_t >::type indexmap;  indexmap index_map = get(boost::vertex_index, graph);  /* container hold 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 graph  */  (tie(i, end) = vertices(graph); != 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 << " parent of ";     }     (; 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 , merge              adjacencyiterator ai, aend;              tie(ai, aend) = adjacent_vertices(*ai, graph);              (; 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; } 

could , ideas on did got wrong.

i don't know you're trying achieve algorithm shown in op.

here's, however, 1 simplifies code considerably, @ least works safely:

• uses vertex bundled property type vertex (id, name)
• uses ranged loops possible (see mir, shorthand create boost::iterator_range std::pair of iterators)
• the code written in container-selection independent way (so works same when replace vecs lists in graph type declaration)
• it uses out_edges instead of adjacent_vertices benefit more adjacencygraph concept, , avoid reverse-lookup of edge-descriptors (source, target) vertices

• most importantly, uses std::set<vertex_descriptor> of vertices have been "removed". actual removal happens later don't undefined behaviour while iterating changing container

• runs cleanly under valgrind

live on coliru

#include <boost/graph/adjacency_list.hpp> #include <iostream>  struct vertex {     int id;     const char* name;      vertex(int = -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, 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 graph  */     (auto self : mir(vertices(graph)))     {         std::cout << graph[self].name << (boost::empty(mir(out_edges(self, graph)))? " has no children " : " 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)) // elided                 break;              if (weight > 0.3f) {                 std::set<vertex_descriptor> traversed;                 (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)))         ); } 

prints

# of vertices: 7 # of edges:    6 jeanie parent of   debug: jeanie  debbie  jeanie   debug: jeanie  debbie  amanda  debbiejohnamanda  debbie has no children   rick parent of jeanie  debug: rick  margaret  rick  margaret  john parent of jeanie  debug: john  benjamin  john  benjamin  amanda parent of jeanie  margaret has no children   benjamin has no children   # of vertices: 4 # of edges:    3 

graph before:

graph after: