CODEWITHSUNDEEP
c++boostgraph
RH6
RH6

Reputation: 89

BGL: vertices in listS and index_map

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

Thanks in advance and have a nice day!

R

Upvotes: 0

Views: 326

Answers (1)

felipegf
felipegf

Reputation: 66

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.

Upvotes: 1

Related Questions