07 апреля 2009

Графы: алгоритмы

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

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

Визитор (Visitor) в классическом виде -- это сложный и практически неприменимый шаблон проектирования. У нас будет профанация визитора, представляющая собой в общем-то тот же итератор, но с вывернутой наизнанку последовательностью управления. Если при переборе итератором команды "стой! шаг вперёд! руки за голову"  отдаются клиентом, а итератор их послушно исполняет, то в случае визитора всё наоборот: клиент инициирует итерирование и передаёт алгоритму объект-визитор. Итерирование идет само, без участия клиента, а при переходе к очередному элементу алгоритм вызывает методы визитора: "эй, ты, у меня тут следующий клиент -- хочешь с ним что-нибудь сделать?". Такой "визитор" называют иногда callback'ом, что на русский переводится корявой фразой "функция обратного вызова".

Архив с интерфейсами графа и алгоритмов на прежнем месте: http://barashev.net/src/graph.zip