[Boost-users] [graph] Graph type needed in Graph Proptery, cyclic definition problem

26 Oct 2011

      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