Boost logo

Boost Users :

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,

struct vertex_properties;
struct edge_properties;
struct graph_properties;

struct vertex_properties {
         std::map <int, link_adjacency_list_traits::edge_descriptor >
         // this one works fine, i can use a traits::edge_descriptor

struct degree_compare;

struct graph_properties {
         int delta;
             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,

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,
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 list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at