Форумы GIS-Lab.info

а если реализовать жадный алгоритм раскраски графа используя инструменты Oracle для графов?

А вот не нашёл там ничего. Да и жадный алгоритм на таблицах делается на раз два.

Попробовал придумать алгоритм на mapbasice для Mapinfo (чертовски любопытно стало).
На картинка видно, как получается. Рассмотрел два случая: когда запрещены любые пересечения и когда пересечение в одной точке разрешено. Внёс элемент случайности, так что результат каждый раз разный.
Работает только со структурой приложенной таблицы.
Перед запуском нужно выбрать полигоны.

Когда: "Пересечение в точке разрешено" - "Да"
Не работает. Где-то ошибка - цвета могут пересекаться

Когда: "Пересечение в точке разрешено" - "Нет"
Очевидно использован приблизительный алгоритм По теореме о четырех красках можно раскрасить более оптимальным способом: 4 цвета вместо 5

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

Попробовал.
В первом случае, действительно, топология не совершенна, поэтому Мапинфо считает, что красные полигоны пересекаются в одной точке.
Во втором случае со второго запуска получил 4 цвета (топология также поправлена).
В любом случае для большого количества полигонов нужно оптимизировать (например, сохранить после первого перебора для каждого полигона "отношения" с соседями, чтобы исключить повторные ресурсоёмкие геозапросы)

Действительно, топология...

Классическая жадная раскраска на MapBasic )))))
Через объединение таблиц.
Раскрашиваются все полигоны в таблице.

1) Строится таблица с rowID пересекающихся объектов.
2) Сортируем в зависимости от количества пересечений
3) Раскрашиваем объект

спасибо ginpetr, за команду для нахождения пересечений Относительно точного алгоритма
В программе, полигоны сортируются в зависимости от количества связанных полигонов в обратном порядке.
Всегда существует такой порядок, который приводит жадный алгоритм к оптимальному числу.
Однако количество перестановок равно n!
т.е. для 10 полигонов - количество перестановок = 3628800 )))

деревья!