Использование Boost Graph Library

[Serge_BN]

typedef boost::adjacency_list <
  listS, //list vertex
  listS, //list edge
  directedS,
  property < vertex_name_t, int,
  property < vertex_index_t, string > >,
  property < edge_weight_t, float >
> graph_t;
graph_t g;

Помогите, плз,
Как запретить создание параллельных вершин в хранилище вершин типа listS для даного графа.
Как наити вершину с заданным свойством используя стандартные алгоритмы поиска из STL?

[Serge_BN]

А в ответ - тишина.
Попробую несколько раскрыть тему.
Цитата из книги
"Одним из первых воросов, которые необходимо рассмотреть при выборе EdgeList, является то, хоттите ли вы гарантировать отсутствие параллельных ребер в графе. Если нужна гарантия того, что граф не станет мультиграфом, можно использовать setS или hash_setS."
Но мне в качестве хранилища ребер и вершин необходимо использовать listS. Отсюда и вопрос. Как реализовать для listS такую функциональность графа, что бы он гарантированно не становился мультиграфом?

[maxal]

Serge_BN в сообщении #200904 писал(а):

Но мне в качестве хранилища ребер и вершин необходимо использовать listS. Отсюда и вопрос. Как реализовать для listS такую функциональность графа, что бы он гарантированно не становился мультиграфом?

Нужно хранить и поддерживать этот список в отсортированном виде и не допускать повторений в нем одинаковых ребер.

[Serge_BN]

maxal писал(а):

Нужно хранить и поддерживать этот список в отсортированном виде и не допускать повторений в нем одинаковых ребер.

Загрузка графа осуществляется за один проход последовательно по мере поступления узлов (узлы поступают упорядоченно по возрастанию номера узла) и для каждого узла - списка смежных узлов. В списке смежности могут присутствовать узлы, которые еще не добавлены в список вершин.
Т.е. алгоритм приблизительно следующий.

< Загрузка графа | =
  < Загрузка очередной вершины |=
    Получить очередной узел N_k.
    Проверить существует ли уже вершина графа N_k,
    если нет, то 
    Занести узел в список вершин графа - add_vertex( N_k );
    Получить список смежных узлов для текущего узла
      < Загрузка списка смежности для текущей вершины |=
      проверить (существует ли вершина с номером N_l ? add_edge(N_k, N_l): add_vertex( N_k), add_edge( N_k, N_l );
      Обработать все N_l для k>
    Обработать все N_k >
>

=> каждый раз необходимо осуществлять сортировку и поиск, что при большом количестве вершин весьма накладно.
Можно было бы изменить алгоритм так, что обработать сначала все узлы в порядке их поступления. Затем для каждой вершины получить список смежности. Но тогда загрузка всего графа будет осуществляться за два прохода.
С библиотекой boost я работаю первый раз. Поэтому и вопросы, возможно, для кого-то покажутся не интересными либо давно решенными. Уж, извините.

[Serge_BN]

Если у кого есть опыт работы с указанной библиотекой, ответьте, плз, на вопрос.
Как по имеющемуся итератору вершин (vertex_iterator) получить описатель вершины (vertex_descriptor)?

Добавлено спустя 10 минут 25 секунд:

Спасибо, уже сообразил.

[maxal]

Serge_BN
Замечание за дублирование тем. Темы слиты.

[Serge_BN]

Помогите, плз, написать class distance_heuristic для алгоритма boost/graph/astar_search если граф в котором надо найти путь выглядит так:

typedef boost::adjacency_list <
  listS, //list vertex
  listS, //list edge
  directedS,
  property < vertex_name_t, int,
  property < vertex_index_t, string > >,
  property < edge_weight_t, float >
> graph_t;
graph_t g;

Свойство грани property < edge_weight_t, float > содержит длину грани или расстояние между вершинами, кому как удобнее. Следовательно надо передать в distance_heuristic соответствующее ребро и достать из него расстояние.
Я пишу следующее:

template <class graph_t, class CostType>
  class distance_heuristic : public astar_heuristic <graph_t, CostType> {
 public:
    typedef typename graph_traits <graph_t>::vertex_descriptor Vertex;
    typedef typename graph_traits <graph_t>::edge_descriptor Edge;
    typedef property_map<graph_t, edge_weight_t>::type weight_map_tt;

 distance_heuristic( Vertex goal, Edge e, weight_map_tt w, rg_t rg ) : 
    m_goal( goal ), m_edge( edge ), m_weight_map( w ), m_g( rg ){}
    CostType operator()( Vertex u ){
      return get( edge_weight, m_g, m_edge );
    }
 private:
    weight_map_tt m_weight_map;
    Vertex m_goal;
    Edge m_edge;
    rg_t m_g;
};

Но это не правильно. компилятор ругается страшными словами. Что делать?

[Serge_BN]

Подскажите, плз, существует ли какой тулз или утилита для того, что бы укоротить сообщения об ошибках при компиляции с использованием Boost Library?
Просто так читать эти метры сообщений просто не возможно.

[Serge_BN]

Помогите, плз, разобраться.
Имеется граф:

typedef boost::adjacency_list < 
  listS, //list vertex
  listS, //list edge
  directedS, 
  property < vertex_name_t, int, // num_nod
  property < vertex_index_t, string > >, //POINT( X Y )
  property < edge_weight_t, float > //distance edge
> r_graph_t;

Где-то в коде

...
r_graph_t * rg = new r_graph_t(N)
...
//заполняем граф
...
//создаем строку, содержащую значение свойства vertex_index вершины
...
   std::string * tmp_str = new string( "tra_ta_ta" );
/*строка 293*/   tmp_str->append( boost::get( vertex_index, *rg, vri1->vd ));

где
vertex\_index - имя свойства,
*rg - граф,
vri1->vd - дескриптор вершины.
Компилируется и работает.
Теперь я меняю тип хранилища для граней графа на vecS ( вместо listS //list edge )
После этого компилятор ругается следующим образом:

a_0.cc:293: error: invalid conversion from `size_t' to `const char*'
a_0.cc:293: error:   initializing argument 1 of `std::basic_string<_CharT, _Traits, _Alloc>& std::basic_string<_CharT, _Traits, _Alloc>::append(const _CharT*) [with _CharT = char, _Traits = std::char_traits<char>, _Alloc = std::allocator<char>]'

Что это значит?
Я поменял тип хранилища для граней. Только и всего. Значение свойства извлекаю из вершины.
Из руководства по boost graph

template <typename PropertyTag, typename X>
typename property_traits<
  typename property_map<adjacency_list, 
  PropertyTag>::const_type>::value_type
get( PropertyTag, const adjacency_list& g, X x)

Цитата:

Возвращает значение свойства для x, где x дескриптор вершины или ребра.

На этом моя мысль останавливается.