Boost Неправильный график, соединяющий вершины

Question

Я использую библиотеку Boost C++ для создания списка смежности для представления неориентированного графа. Каждое ребро на графике связано с соответствующими весами, и я хочу проверить, превышает ли вес какой-то порог, чем объединить две вершины вместе.

Как я сливаю:

• Для вершинных слить, собрать все ребра и из этой вершины и направить края к новой вершине
• Устраните слияния вершин
• Remove вершина

Моя проблема: Я использую простой PROGR сначала создать алгоритм, прежде чем использовать его для цели. В этой программе я использую простой метод семейного дерева для выполнения вышеуказанных шагов. Когда я удаляю вершину, используя функцию 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; 
} 

Могу ли я получить некоторую помощь и идеи о том, где я получил это неправильно.

Answer 1

Я не знаю, чего вы на самом деле пытаетесь достичь с помощью алгоритма, показанного в OP.

Вот, однако, тот, который упрощает код значительно, так что по крайней мере, это работает безопасно:

• использует Vertex в комплект типа недвижимости для вершины (идентификатор, имя)
• использует варьировался для петель, где это возможно (см mir, сокращенная создать boost::iterator_range из std::pair итераторов)
• код записывается в контейнер отбора независимым способом (так он работает точно так же, когда вы замените vecS на listS в Graph объявление типа)
• он использует out_edges вместо adjacent_vertices больше пользы от AdjacencyGraph концепции, и избежать обратного поиска краевых-дескрипторов с помощью (источник, мишень) вершины

• самое главное, он использует std::set<vertex_descriptor> вершин которые были «удалены».Фактическое удаление происходит позже, поэтому мы не получаем неопределенное поведение в то время как итерация меняющегося контейнер

• работает чисто под 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 

Graph перед:

Graph после: