начал работу над приложение тесно связанным с теорией графов. решил использовать BGL сейчас нужно реализовать серию функций которые на запросы пользователей отдавали маршруты из точки в точку, кратчайший из них и т.д.

Конкретно сейчас реализую функцию которая по входным данным (граф, вершина 1, вершина 2) возвращала бы набор маршрутов которые есть между этими вершинами.

Кто-то может уже писал такую? В BGL реализации подобной задачи не нашел.

Спасибо, за внимание.   

Если что, я пионер в этом деле - больно не бейте.

Поиск всех маршрутов - это простой перебор, что тут еще придумаешь.
Только нужно исключить циклы, иначе маршрутов будет бесконечное число.
Начинаем с вершины 1, идем по какому-нибудь ребру, если доходим до вершины 2, запоминаем маршрут, если упираемся во что-нибудь другое - выбрасываем. Затем возвращаемся к ближайшей развилке, копируем часть маршрута до нее, пытаемся пройти другим путем. И т.д., пока все развилки не кончатся. Естественно, ребра текущего маршрута нужно помечать, чтобы не ходить по ним многократно.

А тебе точно нужно все маршруты? Ибо задача о кратчайшем пути решается более элегантно, и такие алгоритмы в BGL есть.

Если в графе есть циклы, то количество маршрутов - бесконечно. Нужно наложить ограничения на маршрут. Например, маршруты диной не более К ребер. Или Эйлеровы маршруты, или Гамильтоновы маршруты.  
Если на ребра (или вершины навешены веса, то обычно ищут минимальные в некотором смысле пути.

Если граф ацикличный, то количество маршрутов конечно.

Пока пишу функцию на основе BGL и путем перебора буду искать маршруты, нужны именно все маршруты. Специфика задачи такая, что нужны все возможные маршруты. В BGL есть реализация некоторых алгоритмов поиска кратчайшего пути, но вот чтобы все возможные - нет.
Задача у меня такая - составление графика движения поездов в метро. А там бывает лучше поезд пустить по более длинному маршруту, но пропустить другие поезда в это время или подобные этому ситуации, как следствие нужно знать множество маршрутов.

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

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

И еще...
Посмотри тему "Потоки в сетях", ключевые фамилии Форд-Фалкерсон... Это о пропускной способности ребер - то есть путей... 



Это сообщение отредактировал(а) SerpentVV - 10.4.2007, 15:00

SerpentVV, 
Пасиб. Гляну. Я пока еще разбираюсь с идеологией BGL.

Библиотека достаточно сложная для понимания... Была книжка переводная - в издательстве Питер... Серия - библиотека программиста...

SerpentVV, 
Да, я ее распечатал.

ИМХО Если ненадо решать никаких замудренных задач. Например максимальны потом за O(m*n*log(n)), каскраска в 4 цвета, максимальное покрытие, гамильтонов цикл.
То разбирать библиотеку смысла нету. Проще написать то что нужно на лету.

А все возможные маршруты думаю можно искать, ДФСом убирая метку при выходе из вершины. 

Для более быстрого поиска можно попробовать следать динамику, сохраняя уже найденые маршруты к вершине в ней самой. В этом случае для хранения маршрутов лучше всего использовать битмаски, так как легко и быстро можно будет проверить уже найденые маршруты.
Эту динамику я придумал прямо сейчас, поэтому за 100% правильность алгоритма не ручаюсь.

AFAIR Строго говоря быстрый поиск всех маршрутов мало вероятен, потому как задача по определению самого длинного пути между двумя заданными вершинами в графе принадлежит классу NP полных задач. 

Это сообщение отредактировал(а) Mayk - 12.4.2007, 02:22

При таком подходе проще написать все самому. На лету - не получится. Т.е. получится, но ерунда наколенная.
BGL хороша не только своей реализацией, но и продуманностью подхода. Который, кстати, позволяет адаптировать свою библиотеку к BGL-интерфейсу, и использовать готовые алгоритмы.
И не так уж она сложна, просто на вид страшновато. Примерно как с STL, внутрь лучше (сразу) не заглядывать, а снаружи - все очень удобно и логично.

Да, лучше, елси есть время, мозги и желания. Хоть бы разбираться потом будеш во всем до конца. Но некоторые вещи не так просто пишуться, поэтому время на них уйдет очень много, что тоже не есть хорошо.
Поэтому если надо что-то замудренное, то стоит изучить библиотеку + сам принцип алгоритма.
Но если надо БФС, ДФС, найти длину самого короткого пути, или минимальное остовное дерево - все функции в пределах 30-50 строк кода, то смысла изучать библиотеку думаю особо не имеет.