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

Subject: [Boost-users] [graph] Graph type needed in Graph Proptery, cyclic definition problem
From: Christoph (c_p_at_[hidden])
Date: 2011-10-26 09:03:58

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.html
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