0

I am new to BGL, and I've been banging my head against the wall for several days trying to implement a graph with vertex removal, until I've found a particularly useful SO question (this one) that saved my day.

Right now my code is structured in this way (simplified code below):

struct NodeProperties
{
    int32_t data;
};

typedef property<edge_weight_t, uint32_t> EdgeProperties;

typedef adjacency_list<listS, listS, bidirectionalS,
                       property<vertex_index_t, int, NodeProperties>,
                       EdgeProperties> Graph;

/* In the graph initialization function */
Graph graph;
/* many add_vertex() and add_edge() here */

/* Assign indices */
int i = 0;
BGL_FORALL_VERTICES(v, graph, Graph) {
    get(vertex_index, graph)[v] = i++;
}

/* Make many manipulations, in particular, edge/vertex removal according 
   to certain criteria, NO add_vertex (though some edge are created) */

/* In another function */
vector<int32_t> component(num_vertices(graph));
int num = connected_components(graph, make_iterator_property_map(component.begin(), get(vertex_index, graph), component[0]));

For what I've understood so far, the use of listS for vertices prevents boost from using the position of each node as an index, and therefore I have to supply this indexing myself using a sort of "added property".

I am fine with that, but the code above does not work -- goes in segmentation fault at the connected_components line -- unless I redo the index assignment. Doing this makes everything work perfectly, but makes no sense in the mental picture I created.

Could someone

  • give me a good reference explaining all this index_map "trickery" in layman terms? Ok, there are tons of official docs, but they look way too complex to me (I am a C programmer). I am planning to learn advanced C++, but I currently have to implement this graph algorithm for my job, and I cannot spend 3 months learning C++ before starting the real code... (already getting the code above work took me something like 10 hours, I would have easily reimplemented all the above in C in that amount of time...)
  • explain me why I have to do this (or what I am doing wrong here)?

Thanks in advance and have a nice day!

R

Community
  • 1
  • 1
RH6
  • 89
  • 3
  • 12

1 Answers1

1

The connected_components function constructs a default color_map with size num_vertices(g), which in your graph is less than your maximum assigned vertex index. When the algorithm tries to write the color for one of the vertices with index greater than num_vertices(g), invalid memory is accessed.

When you reassign all the indices, they fall within num_vertices(g).

For a quick reference to properties, you should read "Adding Some Color to your Graph" in http://www.boost.org/doc/libs/1_63_0/libs/graph/doc/quick_tour.html.

felipegf
  • 56
  • 5