Здравствуйте!

Не подскажите в BGL есть алгоритм поиска глобального минимального разреза графа. Нашел поиск максимального потока, который можно использовать для поиска минимального разреза, но в этом случае нужен исток и сток. Нужны реализации алгоритмов двух типов: типа Stoer-Wagner algorithm и типа Shi-Malik normalized Cuts algorithm. Или если нет в BGL, то может есть в других либах?

AM>Не подскажите в BGL есть алгоритм поиска глобального минимального разреза графа. Нашел поиск максимального потока, который можно использовать для поиска минимального разреза, но в этом случае нужен исток и сток. Нужны реализации алгоритмов двух типов: типа Stoer-Wagner algorithm и типа Shi-Malik normalized Cuts algorithm. Или если нет в BGL, то может есть в других либах?

А в чем проблема нзначить сток и исток?
Все равно ведь если требуется разрез графа, существуют вершины которые обязательно должны принадлежать разным частям?

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

K13>А в чем проблема нзначить сток и исток?
K13>Все равно ведь если требуется разрез графа, существуют вершины которые обязательно должны принадлежать разным частям?

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

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

Тогда режем граф на два множества одно из которых пустое
Какова исходная задача? для чего режем граф?
пропускная способность не имеет смысла без указания источника и стока.

У меня было подобное при генерации бесшовных текстур и разбиения на "фон/объект" но в этих случаях произвольное разбиение было недопустимо.
Вот и хочется понять, откуда может возникнуть необходимость разрезать граф "как попало, лишь бы разрезать".

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

K13>Тогда режем граф на два множества одно из которых пустое
K13>Какова исходная задача? для чего режем граф?
K13>пропускная способность не имеет смысла без указания источника и стока.

K13>У меня было подобное при генерации бесшовных текстур и разбиения на "фон/объект" но в этих случаях произвольное разбиение было недопустимо.
K13>Вот и хочется понять, откуда может возникнуть необходимость разрезать граф "как попало, лишь бы разрезать".

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

Я бы попробовал поискать по ключевым словам

video segmentation, graph cut

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

M>Я бы попробовал поискать по ключевым словам

M>video segmentation, graph cut

Алгоритм найден(писал выше), нужна его реализация(или реализацию другого алгоритма для данной задачи). Пока никак не могу найти.

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

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

M>>Я бы попробовал поискать по ключевым словам

M>>video segmentation, graph cut

AM>Алгоритм найден(писал выше), нужна его реализация(или реализацию другого алгоритма для данной задачи). Пока никак не могу найти.

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

AndreyM16 wrote:

> Не подскажите в BGL есть алгоритм поиска глобального минимального
> разреза графа.

Глобально минимального -- это как ?


Нашел поиск максимального потока, который можно
> использовать для поиска минимального разреза, но в этом случае нужен
> исток и сток.

Так этот алгоритм и используется. Кажется он есть и в явном виде.
За исток берут вершину с минимальной смежностью (мин. кол-вом рёбер).
За сток -- любую вершину, несмежную с ней.

AndreyM16 wrote:

в примерах есть пример разреза графа
(boost_1_38_0\libs\graph\example\edge-connectivity.cpp)

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

MZ>Глобально минимального -- это как ?

Когда граф G разбивается на два подграфа S,T != 0 c минимальным разрезом(в обычном смысле) из всех возможных разбиений этого графа, т. е. как описано
здесь Или с минимальным нормальным разрезом как тут. Второй алгоритм используется, к примеру, в сегментации изображений.
В BGL такого нет.