II Международная студенческая научная конференция Студенческий научный форум - 2010

Целями работы является создание универсального шаблона, реализующего абстрактный тип данных граф, и разработка простой семантической сети демонстрирующей его возможности. Параметрами шаблона являются метки узлов и ребер графа, на этапе создания возможен выбор типа графа (неориентированный или орграф). В основе данного типа данных лежит двусвязный список с поддержкой итераторов, что обеспечивает время выполнения основных операций абстрактного типа данных (АТД) граф (создание и удаление узлов и связей) за единичное время. Разработанный шаблон класса является универсальным и может быть использован везде, где необходима поддержка графов. Следует отметить, что поскольку граф построен на списковых структурах, возможно проигрывание в производительности решениям на основе матриц смежности. Однако для сильно разряженных графов (характерным примером которого является семантическая сеть) данное решение позволяет принципиально снизить затраты памяти при относительно небольшой потере в производительности. Данный граф рассчитан на постоянное добавление и удаление узлов, а не на скорость выполнения обхода.

В рамках поставленного технического задания основной задачей является создания типа универсального помеченного графа и реализация типичных операций над ним (добавление и удаление узлов и ребер). Причем в различных ситуациях тип метки может быть различен. В качестве языка программирования должен использоваться С++. Граф должен быть оптимизирован под активное добавление - удаление узлов и связей.

Для решения это задач был использован объектный подход в сочетании с технологией шаблонов. В качестве структуры для хранения структуры графа используются списки узлов и связей. Вначале был разработан шаблон класса универсального двусвязного списка (TList). В дополнение к нему был создан шаблон класса итератора для списков TList (TListIterator). Использование итераторов позволило снизить время последовательного обхода списка с O(n!) (для доступа к i-тому элементу списка необходимо пройти i предыдущих) до O(n) (доступ к следующему элементу выполняется за постоянное время). Также итераторы можно использовать для включения и удаления элементов из списка, причем при этих операциях другие итераторы сохраняют свою актуальность и не требую переинициализации или каких-либо других специальных действий. В этом заключается их принципиальное преимущество перед классическими указателями (которые требую проверки валидности значения при каждом изменении списка). Для обработки возможных в ходе использования списка ошибок используется стандартный механизм исключений в С++. Подробное описание возможных исключений и ситуаций при которых они проявляются дается в разделе описания модулей.

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

Все разработанные классы являются шаблонами, параметризованными двумя типами: типом метки узла и типом метки ребра. Кроме того, класс TNode содержит дополнительный член целого типа для упрощения построения различных алгоритмов (обхода, поиска путей и кратчайших путей, определения расстояния). Также в алгоритмах активно используется очереди построенные на TList (структура двусвязного списка позволяет одинаково эффективно использовать его как стек, дек или очередь).

На рис. 1 приведена структура хранения данных в объекте типа TNode.

Список ребер инцидентных данному узлу находится в списке icd, а имеющих ссылки на данный узел -  в списке pointed. Доступ к соответствующим узлам и ребрам осуществляется при помощи итераторов edgeint и position (последний используется в частности для быстрого удаления элемента). Такая схема позволяет проводить вставку и удаление элементов графа за O(1). Схема хранения данных в графе (объекте типа TGraph) достаточно проста (рис. 2). Все узлы графа хранятся в виде указателей в списке NodeTab. Для их обхода с помощью встроенного итератора nodeint используется механизм итерации (подробнее см. следующий раздел).

Ключевыми алгоритмами в реализации данной задачи являются алгоритмы итерации и работы с указателями. Они используются на всех уровнях архитектуры и обеспечивают простой механизм доступу к отдельному элементу, и перехода от одного элемента к другому. Фактически объект итератор это умный указатель. Его методы обеспечивают переход от одного элемента связанной структуры к другому, что позволяет использовать его как индекс для массива.

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

Фактически существует только один итератор данной структуры, и он является ее частью. Этот подход позволил существенно сократить накладные расходы на управления итераторами.

Интерфейсом итерации снабжены объекты TGraph и TNode. Рассмотрим его устройство на примере последнего. Интерфейс представлен функциями nextNode() - перехода на следующий узел с которым существует связть, currentNode() возвращающей указатель на узел с которым есть связь, currentEdge() - возвращающей указатель на ребро инцидентное данному узлу, numEdge() - возвращающей общее количество связей. И resetEdgeIterator() сбрасывающий итератор на начало списка ребер. О завершении обхода списка говорит false возвращаемое операцией nextNode(). Подробности использования этого механизма содержатся в html документации, а в качестве примера может служить разработанная программа для создания семантической сети.

Проект был реализован в соответствии со стандартом ISO C++ и может быть собран на любом совместимом компиляторе. Разработка и отладка велась в среде программирования Code::Blocks 8.02 (компилятор gcc 4.1.2). Тестирование проводилось на машинах: AMD Athlon XP 1500+ / 256 Mb DDR SDRAM / Ubuntu GNU/Linux 7.10 / GCC 4.1, Intel Celeron 2000 MHz / 1 Gb DDR SDRAM / Microsoft Windows XP Pro SP3 / MiniGW 4.2  и AMD Athlon XP 2000+ / 768 Mb DDR SDRAM / Microsoft Windows XP Pro SP2 / MS Visual Studio 2005

Код для цитирования: Скопировать