[bgl] Transitive closure
Hello, I am trying to compute the transitive closure of a graph. The definition of the graph is: typedef boost::adjacency_list<boost::vecS, boost::listS, boost::bidirectionalS, boost::property<boost::vertex_name_t, int> > graph_t; The code that calls the transitive closure function is: (g is of type graph_t) // prepare a map Vertex-int. map<Vertex,int> extmap; VertexIt vi, v_end; int i = 0; for (tie(vi,v_end) = vertices(g); vi != v_end; ++vi, i++) { extmap.insert(pair<Vertex,int>(*vi,i)); } associative_property_map<map<Vertex,int> > tempMap(extmap); map<Vertex,Vertex> vmap; adjacency_list<> c; boost::transitive_closure(g, c, vmap, tempMap); According with the documentation, tempMap must be a map from vertices to integers. When I try to compile the program, the following error occurs: /usr/local/include/boost/graph/transitive_closure.hpp:182: error: invalid initialization of reference of type 'const std::vector<long unsigned int, std::allocator<long unsigned int> >&' from expression of type 'std::vector<int, std::allocator<int> >' After taking a look at the file, the vector successors is defined as: std::vector<std::vector<cg_vertex> > successors(...); The error occurs with the following call: detail::union_successor_sets(successors[u], successors[v], successors[u]); the definition of union_successor_sets is: inline void union_successor_sets(const std::vector < std::size_t > &s1, const std::vector < std::size_t > &s2, std::vector < std::size_t > &s3) {...} Probably I am really wrong, but successors[u] is an std::vector<cg_vertex> and the function expects a std::vector < std::size_t >. So size_t and cg_vertex should be the same type, which according with the error reported by the compiler is not true. Can someone give me a hint on how to solve my problem? Thaks in advance.
typedef boost::adjacency_list<boost::vecS, boost::listS, boost::bidirectionalS, boost::property<boost::vertex_name_t, int> > graph_t;
adjacency_list<> c; boost::transitive_closure(g, c, vmap, tempMap);
Can someone give me a hint on how to solve my problem?
It may be because you're using two different graph types. graph_t makes the vertex_descriptor type a void* (because of the listS for the vertex list) and the graph c uses size_t (because it defaults to vecS). It might be that using two different types of graphs isn't a use case for this particular call. Just speculation. You might also try using the named-parameter version. That may make some of your problems a litlte more explicit (but maybe not). Andrew Sutton andrew.n.sutton@gmail.com
On 14 Aug 2009, at 13:44, Andrew Sutton wrote:
typedef boost::adjacency_list<boost::vecS, boost::listS, boost::bidirectionalS, boost::property<boost::vertex_name_t, int> > graph_t;
adjacency_list<> c; boost::transitive_closure(g, c, vmap, tempMap);
Can someone give me a hint on how to solve my problem?
It may be because you're using two different graph types. graph_t makes the vertex_descriptor type a void* (because of the listS for the vertex list) and the graph c uses size_t (because it defaults to vecS). It might be that using two different types of graphs isn't a use case for this particular call. Just speculation.
Mmm, not sure, according with the example at: http://www.boost.org/doc/libs/1_39_0/libs/graph/example/transitive_closure.c... they use typedef adjacency_list < listS, listS, directedS, Index > graph_t; for the initial graph and adjacency_list <> TC; for the result. As you can see, from this point of view we are using the same data structure to store vertices.
You might also try using the named-parameter version. That may make some of your problems a litlte more explicit (but maybe not).
Good idea, I thought abut using it, however I don't know how to pass the other map as a named-parameter. Here I am talking about the argument "orig_to_copy(G_to_TC_VertexMap g_to_tc_map)" Regards, Gustavo
participants (2)
-
Andrew Sutton -
Gustavo Gutiérrez