Re: [Boost-users] [graph] Graph type needed in graph proptery, cyclic definition problem, minimal example

Subject: Re: [Boost-users] [graph] Graph type needed in graph proptery, cyclic definition problem, minimal example
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2011-10-26 15:52:40

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