Boost::Graph.
Как запретить создание параллельных вершин в хранилище вершин типа listS для
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;
Как наити вершину с заданным свойством?

Здравствуйте, serge.bn, Вы писали:

SB>Как наити вершину с заданным свойством?
Собственно ответы здесь на этот вопрос я уже видел. Но, вдруг, у кого появятся новые мысли по этому поводу.
Думается мне, что это должно быть очень просто. Если контейнер вершин — список, то к нему можно применить стандартный алгоритм поиска из STL. Как бы это сделать?

Молчание — золото. Но я не за ним сюда пришел.
Или я не корректно задал вопрос?
Или здесь нет специалистов разбирающихся в библиотеке boost::graph?

Помогите, плз, написать 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, Вы писали:

SB>Молчание — золото. Но я не за ним сюда пришел.
SB>Или я не корректно задал вопрос?
SB>Или здесь нет специалистов разбирающихся в библиотеке boost::graph?

скорее второе
я вот много на бусте программирую, но с графами до сих пор дела не имел.

You will always get what you always got
  If you always do  what you always did

Здравствуйте, jazzer, Вы писали:

J>я вот много на бусте программирую, но с графами до сих пор дела не имел.
А подскажи, плз, как читать эти бесконечные сообщения об ошибках. Существует ли какой инструмент, что бы сделать их как-то более осмысленными?

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, jazzer, Вы писали:

J>>я вот много на бусте программирую, но с графами до сих пор дела не имел.
А>А подскажи, плз, как читать эти бесконечные сообщения об ошибках. Существует ли какой инструмент, что бы сделать их как-то более осмысленными?

у меня есть собственный перловый скрипт.
Он заточен под сообщения gcc (всё в одной строке, в отличие от мелкософта).
В первую очередь, он убирает все сообщения с "instantiated from" — они служат только для показа цепочки инстанцирования и обычно не нужны, потому что ошибка, скорее всего, на одном из концов цепочки.
Далее, он убирает всякие повторения типа mpl::void_, и заменяет на многоточие все, что внутри классов из detail — обычно это тоже не нужно.
Ну и обычные вещи типа изничтожения пространств имен, как своих, так и бустовских, чтоб не рябило в глазах.

Используется пакет Regexp::Common для поиска парных скобок.

You will always get what you always got
  If you always do  what you always did

Здравствуйте, serge.bn, Вы писали:

SB>Молчание — золото. Но я не за ним сюда пришел.
SB>Или я не корректно задал вопрос?
SB>Или здесь нет специалистов разбирающихся в библиотеке boost::graph?

Если проблема еще не решена, гугли дискуссию с заголовком: "Help needed with BGL & multi_index_container" в конференции буста.

Насколько я помню, последний пример кода можно найти по тут:

http://aspn.activestate.com/ASPN/Mail/Message/boost/2482206

Успехов!

Аноним 35 wrote:

> 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;

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

Попробуй заменить определение своего графа на

typedef boost::adjacency_list <
listS, //list vertex
vecS, // vector of edges
directedS,
property < vertex_name_t, int,
property < vertex_index_t, string > >,
property < edge_weight_t, float >
graph_t;

т.е. использовать вектор для хранения вершин.
Я встречался с тем, что для вершин нужны итераторы прямого доступа
зачем -то, хотя это (вроде бы) нигде не описано.

Здравствуйте, MasterZiv, Вы писали:

MZ>typedef boost::adjacency_list <
MZ> listS, //list vertex
MZ> vecS, // vector of edges
MZ> directedS,
MZ> property < vertex_name_t, int,
MZ> property < vertex_index_t, string > >,
MZ> property < edge_weight_t, float >
MZ> graph_t;

MZ>т.е. использовать вектор для хранения вершин.
MZ>Я встречался с тем, что для вершин нужны итераторы прямого доступа
MZ>зачем -то, хотя это (вроде бы) нигде не описано.
Спасибо. Я так и сделал. Все заработало. Просто обратил внимание, что в аналогичных примерах именно так. Хотя, действительно, нигде не написано, что именно так и надо. Во всяком случае я этого не нашел. А алгоритмы очень мощные и их применение избавило от многих "велосипедов".
По ходу есть еще вопрос.
Пусть задана структура

struct A {
int x;
int y;
};

и задан список

list<A*> list_A;

Требуется сортировать этот список. И вопрос — Как правильно написать функтор для алгоритма sort? для данного случая.

serge.bn wrote:

> и задан список
>
> list<A*> list_A;
>
>
> Требуется сортировать этот список. И вопрос — Как правильно написать
> функтор для алгоритма sort? для данного случая.

Можно не функтор, а функцию.
типа

bool operator < (const A* l, const A* r)
{
return *l < *r;
}