[graph] Graph type needed in Graph Proptery, cyclic definition problem
Hi List, id like to use a std::priority_queue as a property of my graph. In the priority queue i store some vertices by the vertex degree. I have to Problems i think: First i have to define the priority_queue in a struct graph_properties. Within this priority_queue definition i use a comparison object as the 3rd template parameter. Now the problem is, that the class vertex_degree_compare needs to know the graph type, because of the use of out_degree(u, g) but the graph type depends on the graph_struct and this depends on the priority_queue definition. For the edge descriptors and vertex descriptors i used the traits_class http://www.boost.org/doc/libs/1_47_0/libs/graph/doc/adjacency_list_traits.ht... but for the graph itself i don't know how to proceed. Any help is highly appreciated. // begin code #include <iostream> #include <queue> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/graph_utility.hpp> typedef boost::adjacency_list_traits<boost::listS, boost::vecS, boost::bidirectionalS> link_adjacency_list_traits; struct vertex_properties { vertex_properties () : color (-1) {} unsigned int vertex_index; unsigned int vertex_index_t; int color; std::list <int> free_colors; std::map <int, link_adjacency_list_traits::edge_descriptor > used_colors; }; struct edge_properties { edge_properties () : color (-1) {} int color; }; struct graph_properties { int delta; std::priority_queue < link_adjacency_list_traits::vertex_descriptor, vertex_degree_compare> A; std::priority_queue < link_adjacency_list_traits::vertex_descriptor, vertex_degree_compare> B; }; typedef boost::adjacency_list < boost::listS, boost::listS, boost::bidirectionalS, vertex_properties, edge_properties, graph_properties> link_graph; typedef boost::graph_traits <link_graph> lgt; class vertex_degree_compare { private: link_graph g; public: vertex_degree_compare (const link_graph &g) : g(g) {} bool operator() (link_adjacency_list_traits::vertex_descriptor& u, link_adjacency_list_traits::vertex_descriptor& v) const { return out_degree (u, g) < out_degree (v, g); } }; int main(int argc, char** argv) { return 0; } // end code best regards Christoph
Hi, here is a minimal version. The code compiles however in the graph_properties struct i would like to define a traits graph type as it is possible for vertex_descriptors. // begin code #include <iostream> #include <map> #include <boost/graph/adjacency_list.hpp> typedef boost::adjacency_list_traits<boost::listS, boost::vecS, boost::bidirectionalS> link_adjacency_list_traits; struct vertex_properties { std::map <int, link_adjacency_list_traits::edge_descriptor > used_colors; // this one works fine, i can use a traits::edge_descriptor }; struct graph_properties { int delta; // link_adjacency_list_traits::??? g; // i need a 'traits_graph', too // link_graph g; is not possible because its definition needs // the definition of graph_properties // how to declare it? // but out_degree (u, g) does not need to know any properties }; struct edge_properties { int color; }; typedef boost::adjacency_list < boost::listS, boost::listS, boost::bidirectionalS, vertex_properties, edge_properties, graph_properties> link_graph; int main () { link_graph g; } // end code best regards christoph
On Wed, 26 Oct 2011, Christoph wrote:
Hi,
here is a minimal version. The code compiles however in the graph_properties struct i would like to define a traits graph type as it is possible for vertex_descriptors.
See http://stackoverflow.com/questions/4232409/how-to-solve-boostbgl-template-cl... or http://comments.gmane.org/gmane.comp.lib.boost.user/70832 for the solution to that problem. -- Jeremiah Willcock
Hi,
See
http://stackoverflow.com/questions/4232409/how-to-solve-boostbgl-template-cl... [...] funny this is my own mail and your answer. Thank you again for that one.
or http://comments.gmane.org/gmane.comp.lib.boost.user/70832 for the solution to that problem.
-- Jeremiah Willcock _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
[...] i am sorry but i can't find the solution to my problem. I know how to use boost::adjacency_list_traits<boost::listS, boost::vecS, boost::bidirectionalS>::vertex_descriptor and boost::adjacency_list_traits<boost::listS, boost::vecS, boost::bidirectionalS>::edge_descriptor inside of bundled graph properties but i need the graph type itself to use 'vertex_degree (u, g)' in the comparison object given to a priority_queue inside of the graph_property struct (see first example). best regards Christoph
On Wed, 26 Oct 2011, Christoph wrote:
i am sorry but i can't find the solution to my problem. I know how to use
boost::adjacency_list_traits<boost::listS, boost::vecS, boost::bidirectionalS>::vertex_descriptor
and
boost::adjacency_list_traits<boost::listS, boost::vecS, boost::bidirectionalS>::edge_descriptor
inside of bundled graph properties but i need the graph type itself to use 'vertex_degree (u, g)' in the comparison object given to a priority_queue inside of the graph_property struct (see first example).
Is having a shared_ptr (or scoped_ptr) to the priority_queue acceptable to have in your graph property? If so, I have it working: // begin code #include <iostream> #include <map> #include <queue> #include <boost/graph/adjacency_list.hpp> #include <boost/smart_ptr.hpp> typedef boost::adjacency_list_traits<boost::listS, boost::vecS, boost::bidirectionalS> link_adjacency_list_traits; struct vertex_properties; struct edge_properties; struct graph_properties; struct vertex_properties { std::map <int, link_adjacency_list_traits::edge_descriptor > used_colors; // this one works fine, i can use a traits::edge_descriptor }; struct degree_compare; struct graph_properties { int delta; boost::shared_ptr< std::priority_queue< link_adjacency_list_traits::vertex_descriptor, std::vector<link_adjacency_list_traits::vertex_descriptor>, degree_compare> > pq; // link_adjacency_list_traits::??? g; // i need a 'traits_graph', too // link_graph g; is not possible because its definition needs // the definition of graph_properties // how to declare it? // but out_degree (u, g) does not need to know any properties }; struct edge_properties { int color; }; typedef boost::adjacency_list < boost::listS, boost::listS, boost::bidirectionalS, vertex_properties, edge_properties, graph_properties> link_graph; struct degree_compare { const link_graph& g; degree_compare(const link_graph& g): g(g) {} bool operator()(const boost::graph_traits<link_graph>::vertex_descriptor& a, const boost::graph_traits<link_graph>::vertex_descriptor& b) const { return out_degree(a, g) < out_degree(b, g); } }; int main () { link_graph g; } // end code -- Jeremiah Willcock
Hi, [snip]
Is having a shared_ptr (or scoped_ptr) to the priority_queue acceptable to have in your graph property? If so, I have it working: [snap]
Great, your code compiles without any errors. I do not have any experience with shared_ptr (or scoped_ptr) and do not know how and why they are needed but i will have a look into the boost documentation first :) best regards Christoph
ahh now i see, because of the (shared) pointer to the priority_queue the forward declaration 'struct degree_compare;' works. This is really good to know. So this was my missing part. Thank you for your patience! On Wed, 2011-10-26 at 15:52 -0400, Jeremiah Willcock wrote:
On Wed, 26 Oct 2011, Christoph wrote:
i am sorry but i can't find the solution to my problem. I know how to use
boost::adjacency_list_traits<boost::listS, boost::vecS, boost::bidirectionalS>::vertex_descriptor
and
boost::adjacency_list_traits<boost::listS, boost::vecS, boost::bidirectionalS>::edge_descriptor
inside of bundled graph properties but i need the graph type itself to use 'vertex_degree (u, g)' in the comparison object given to a priority_queue inside of the graph_property struct (see first example).
Is having a shared_ptr (or scoped_ptr) to the priority_queue acceptable to have in your graph property? If so, I have it working:
// begin code
#include <iostream> #include <map> #include <queue> #include <boost/graph/adjacency_list.hpp> #include <boost/smart_ptr.hpp>
typedef boost::adjacency_list_traits<boost::listS, boost::vecS, boost::bidirectionalS> link_adjacency_list_traits;
struct vertex_properties; struct edge_properties; struct graph_properties;
struct vertex_properties { std::map <int, link_adjacency_list_traits::edge_descriptor > used_colors; // this one works fine, i can use a traits::edge_descriptor };
struct degree_compare;
struct graph_properties { int delta; boost::shared_ptr< std::priority_queue< link_adjacency_list_traits::vertex_descriptor, std::vector<link_adjacency_list_traits::vertex_descriptor>, degree_compare> > pq; // link_adjacency_list_traits::??? g; // i need a 'traits_graph', too // link_graph g; is not possible because its definition needs // the definition of graph_properties // how to declare it? // but out_degree (u, g) does not need to know any properties };
struct edge_properties { int color; };
typedef boost::adjacency_list < boost::listS, boost::listS, boost::bidirectionalS, vertex_properties, edge_properties, graph_properties> link_graph;
struct degree_compare { const link_graph& g; degree_compare(const link_graph& g): g(g) {} bool operator()(const boost::graph_traits<link_graph>::vertex_descriptor& a, const boost::graph_traits<link_graph>::vertex_descriptor& b) const { return out_degree(a, g) < out_degree(b, g); } };
int main () { link_graph g; }
// end code
-- Jeremiah Willcock _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
-- Christoph <c_p@gmx-topmail.de>
participants (2)
-
Christoph -
Jeremiah Willcock