| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > C/C++: Общие вопросы > BGL: изменение стандартного алгоритма BFS |
| Автор: Jawello 26.5.2013, 14:50 |
| Доброе время суток. есть задача для решения, которой необходимо использовать графы. чтобы не изобретать велосипед решил воспользоваться Boost Graph Library. но столкнулся с проблемой. Есть двудольный ориентированный граф. Вершины деляться на два типа - A и B. соотвсетвенно, Из вершин типа А ребра могут идти только в вершины типа B, а из вершин типа B в вершины типа А. Необходимо реализовать алгоритм поиска в ширину, для нахождения кратчайшего маршрута (не обязательно для 100% случаев, чтобы маршрут действительно был самым коротким из возможных) между вершиной типа А(начальной) и достижением набора конечных вершин типа А. Но есть условие, что переход (во время поиска) от вершины типа B к вершине типа А возможен только, если все вершины типа А входящие в вершину типа B уже посещены. Изначально несколько вершин типа А помечаются как посещенные. Наверное достаточно запутанное объяснение. При необходимости отвечу на любые вопросы. Спасибо. |
| Автор: Earnest 27.5.2013, 07:46 |
| Ну есть же алгоритм Дийкстры для поиска кратчайшего пути. Реализуй соответствующий визитер, который будет определенным образом считать веса или релакс делать или еще что-то. Я в твою задачу не вникала, но BGL-алгоритмы весьма гибкие. |
| Автор: Jawello 29.5.2013, 14:38 |
| Спасибо за ответ. То что реализовывать визитер необходимо, я и сам понимаю. Но я уже столкнулся с одной проблемой - мой граф ориентированный, соответственно из вершины я не могу получить доступ к входящим ребрам (соотвественно и к вершинам), только к исходящим. А мне необходим доступ к входящим ребрам, чтобы понимать были ли посещены все входящие вершины. Да, граф можно описать как двунаправленный или же все ребра дублировать в разные стороны, но при обходе алгоритм все равно будет заходить в те вершины, в которые по идее еще нет доступа (даже если ребру указать очень большой вес), а это лишние шаги и неверное поведение алгоритма. Я пока не нашел способа корректо реализовать задуманный мной алгоритм при помощи BGL, поэтому сейчас пишу свою реализацию алгоритма. |
| Автор: Earnest 29.5.2013, 15:08 |
| У BGL-графа есть не только out_edges, но и in_edges. Если использовать подходящий концепт - BidirectionalGraph |
| Автор: Jawello 29.5.2013, 20:01 |
| да, я понимаю, что BidirectionalGraph предоставляет доступ к in_edges. но этот концепт мне подходит по другим причинам. в частности, что есть возможность попасть из вершины типа В во все входящие ребра. это нарушит алгоритм поиска. |
| Автор: Earnest 30.5.2013, 06:22 |
| С чего бы? Стандартные алгоритмы поиска требуют Vertex List Graph и Incidence Graph. Т.е. свойства Bidirectional Graph не используются. |