VPF::boost graph library и работа со связностью

neosapient

Дата 19.3.2009, 09:12 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 672
Регистрация: 16.8.2006

Репутация: нет
Всего: 4

Здравствуйте.
Надо решить задачку. Есть массив структур. В структуре определено начало и конец периода.

Код


struct period{
    int index; // уникальный номер вершины
    time_t from; // начало периода
    time_t to; // конец периода
};

Периоды пересекаются на оси времени. Надо определить есть ли разрывы во множестве.

Можно ли реализовать алгоритм решения данной задачи с использованием boost graph library? Какими шаблонами/алгоритмами удобнее воспользоваться?
(Я только начинаю изучать boost graph library, поэтому буду дополнять список вопросов новыми постами)

baldina

Дата 19.3.2009, 12:31 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 3433
Регистрация: 5.12.2007
Где: Москва

Репутация: 32
Всего: 101

можно. но не нужно. где в этой задаче собственно граф?
всё что нужно - отсортировать массив и пройтись по нему, проверяя условие max_to >= array[i]. from, где max_to - максимальное значение array[j].to, где j=(0,1...i-1)

Earnest

Дата 19.3.2009, 15:08 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Экс. модератор
Сообщений: 5962
Регистрация: 17.6.2005
Где: Рязань

Репутация: 53
Всего: 183

1) Отсортировать по from, если from одинаковы, то по to
2) Пройтись, сравнивая соседние элементы на предмет from[i+1] > to[i]

Но можно и графом (если вдруг задание такое): узлы - элементы структуры, ребра соединяют элементы с пересекающимися периодами. Нужно посчитать число связных компонент: если их > 1, то разрывы есть (в количестве N-1). Алгоритм так и называется connected_components.

--------------------

...

baldina

Дата 19.3.2009, 19:11 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 3433
Регистрация: 5.12.2007
Где: Москва

Репутация: 32
Всего: 101

Цитата

2) Пройтись, сравнивая соседние элементы на предмет from[i+1] > to[i]

после сортировки возможна ситуация:
          i-1  i    i+1
from    4  5    10
to      11  9    12

потому и предлагается вычислять максимальное и сравнивать с ним.
а граф тут совершенно излишен.

Цитата

ребра соединяют элементы с пересекающимися периодами

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

Earnest

Дата 19.3.2009, 19:24 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Экс. модератор
Сообщений: 5962
Регистрация: 17.6.2005
Где: Рязань

Репутация: 53
Всего: 183

Цитата(baldina @ 19.3.2009, 20:11

)

после сортировки возможна ситуация:

да, верно. Или просто выкидывать вложенные интервалы.

Цитата(baldina @ 19.3.2009, 20:11

)

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

если задача заключается только в том, что написал автор, то безусловно.
Однако граф может помочь решить какие-то смежные задачи, скажем, построить какие-нибудь разветвленные Work Flow... Не от балды же он про граф сказал... Хотя... smile

--------------------

...

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »