Re: [Boost-users] [Graph] Problem trying to delete vertices from a graph using named vertices, please help!

Subject: Re: [Boost-users] [Graph] Problem trying to delete vertices from a graph using named vertices, please help!
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2010-04-02 11:58:12

On Thu, 1 Apr 2010, Camillo Anania wrote:

> Jeremiah wrote:
>
> 2010/3/30 Jeremiah Willcock <jewillco_at_[hidden]>
>>
>> On Mon, 29 Mar 2010, Camillo Anania wrote:
>>
>>> Hi guys,I have a graph so defined:
>>>
>>> typedef boost::adjacency_list<boost::listS, boost::listS, 
>>> boost::bidirectionalS, Osm::VertexProperties, EdgeProperties> Graph;
>>>
> Osm::Graph osmGraph;

You don't happen to specialize internal_vertex_name, do you?  What members 
are in your property structures?

>>> I'm trying to delete some vertices from osmGraph using the usual 
>>> remove_vertex(Vertex, Graph) but I get the following error from Visual 
>>> Studio 2008 when compiling:
>>
>> What is Vertex defined as here?
>>
>
> Here I call remove_vertex(v  ,osmGraph) where v is defined like:
> typedef boost::graph_traits<Osm::Graph>::vertex_descriptor Vertex;

That seems right, and the error message says that you are getting void* as 
the vertex type (which is right).

>>> boost_1_40_0\boost/graph/named_graph.hpp(349) : error C2664: 'boost::multi_index::detail::hashed_index_iterator<Node,BucketArray>boost::multi_index::detail::hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>::erase(boost::multi_index::detail::hashed_in
>>> dex_iterator<Node,BucketArray>)' : cannot convert parameter 1 from 'void *' to
>>> 'boost::multi_index::detail::hashed_index_iterator<Node,BucketArray>'
>>>
>>> the code I use is:
>>> {
>>> vector<int> component(num_vertices(osmGraph));
>>> int num = strong_components(osmGraph,
>>>             make_iterator_property_map(&component[0], get(&Osm::VertexProperties::id, osmGraph)),
>>>             vertex_index_map(get(&Osm::VertexProperties::id, osmGraph)));
>>> int main_comp = component[depotID];
>>> for (int i = 0; i != component.size(); i++){
>>> if (component[i] == main_comp)
>>> continue;
>>>
>>> if (is_incident_to_required_edge(osmGraph, i)){
>>> cerr << "Required components on input topology are not strongly connected. Check the input .osm file" << endl;
>>> return 1;
>>> }
>>> else {
>>> clear_vertex(osm_get_vertex(i, osmGraph), osmGraph);
>>> Osm::Vertex osm_v = osm_get_vertex(i, osmGraph);
>>> cout << "id=" << osmGraph[osm_v].id << endl;
>>> remove_vertex(osm_v, osmGraph);
>>> }
>>> }
>>> }
>>
>> What is Osm::Vertex, and what does osm_get_vertex do?
>
> Osm::Vertex is like above and is:
> namespace Osm { typedef
> boost::graph_traits<Osm::Graph>::vertex_descriptor Vertex;}
>
> osm_get_vertex is defined like this:
>
> Osm::Vertex osm_get_vertex(int id_vertice, Osm::Graph& g){
> 	typedef boost::graph_traits<Osm::Graph>::vertex_iterator vertex_iter;
> 	std::pair<vertex_iter, vertex_iter> vp;
> 	for (vp = vertices(g); vp.first != vp.second; ++vp.first) {
>        int uid = g[*vp.first].id;
> 		if ( uid == id_vertice) return *vp.first;
> 	}
> 	return NULL;
> }
>
> I do this because the vertex(v, g) doesnt work when the graph index
> vertices are not numbered from 0 with continuity. Do you know why that
> happens? Also the other algorithms Boost gives doesnt work if vertices
> indexes are not numbered with continuity from 0. Graphs I'm working
> with graphs having OutEdgeList = VertexList = ListS.

vertex(v, g) is probably failing because the list of vertices isn't random 
access and so it can't get a vertex with a given number out in constant 
time.  The algorithms typically need a vertex_index property map, which 
exists for vecS as the vertex container but not for listS; you can add 
(and fill in) that property manually to make the algorithms work.  There 
is another thread on the mailing list about edge index maps, and similar 
code will work for vertices.

Could you please post the whole error message, and possibly a whole 
program that fails (preferably trimmed to be as minimal as possible)?

-- Jeremiah Willcock