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.
listS
for stable iterators – sehe