Boost Undirected Graph Merging Vertices

Question

I am using Boost C++ Library to build a adjacency list to represent an undirected graph. Each edge on the graph is associated with respective weights and I want to check if the weight is greater than some threshold than I merge the 2 vertices together.

How I merge:

• For the vertex to merge, gather all the edges to and from this vertex and direct the edges to the new vertex
• Clear the merging vertex
• Remove the vertex

My Problem: I use a simple program to first construct the algorithm before I use it for purpose. In this program I am using simple family tree method to perform the above steps. When I remove the vertex using the function remove_vertex(vertex, Graph) I get a segmentation fault.

• I cannot figure out if once the vertex is removed, does the graph automatically updates its structure?

My C++ code is as 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 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;
}

Could I get some help and ideas on where did I got this wrong.

Answer 1

I don't know what you're actually trying to achieve with the algorithm shown in the OP.

Here's, however, one that simplifies the code considerably, so that at least it works safely:

• uses Vertex bundled property type for vertex (id, name)
• uses ranged for loops where possible (see mir, shorthand to create a boost::iterator_range from a std::pair of iterators)
• the code is written in container-selection independent way (so it works just the same when you replace vecS by listS in the Graph type declaration)
• it uses out_edges instead of adjacent_vertices to benefit more from the AdjacencyGraph concept, and avoid reverse-lookup of edge-descriptors by (source, target) vertices

• most importantly, it uses a std::set<vertex_descriptor> of vertices that have been "removed". The actual removal happens later so we don't get undefined behaviour while iterating a 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 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)))
        );
}

Prints

# 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 before:

Graph after: